Computational cryptography › Live on mainnet today › Pairing curves
Hardness assumptionKE: gives key exchange

q-SDH on BLS12-381

In plain words

A puzzle where the attacker sees many hints about a secret number and still mustn't find it.

The idea: KZG and SNARK setups publish a secret number τ hidden inside curve points, in many powers: τ, τ², τ³ and so on, all hidden. That lets anyone evaluate a polynomial "at τ" without knowing τ, which is how a whole polynomial gets squeezed into one point. The bet is that even with all these hints, nobody can compute certain other hidden values that would let them cheat. More hints means more risk, which makes it a stronger bet than plain Diffie-Hellman.

Why it matters: Makes the KZG commitments used for blobs binding.

The details

On the map: given q powers gτ, gτ², gτ³, …

Given many powers of a secret τ hidden in the group (g^τ, g^τ², ...), nobody can compute certain related values. This is the q-strong Diffie-Hellman assumption[1], and it is what makes KZG commitments binding: a prover can't open a commitment to two different values[2].

It is a stronger, riskier assumption than plain Diffie-Hellman, because the attacker sees many related values (KE)[3].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Everything that falls with it (2 boxes)

About the tags

KE
This assumption gives key exchange on its own, so it needs more than one-way functions and falls if public-key encryption is impossible.

References

  1. Dan Boneh and Xavier Boyen. Short Signatures Without Random Oracles. Advances in Cryptology - EUROCRYPT 2004. doi:10.1007/978-3-540-24676-3_4
  2. Aniket Kate, Gregory M. Zaverucha and Ian Goldberg. Constant-Size Commitments to Polynomials and Their Applications. Advances in Cryptology - ASIACRYPT 2010. doi:10.1007/978-3-642-17373-8_11
  3. Jung Hee Cheon. Security Analysis of the Strong Diffie-Hellman Problem. Advances in Cryptology - EUROCRYPT 2006. doi:10.1007/11761679_1