Computational cryptography › Public-key encryption and key exchange › Classical number theory › Pairing groups: BLS12-381, BN254
Hardness assumptionKE: gives key exchangeTD: gives trapdoor functions

q-type assumptions

In plain words

A stronger puzzle: the attacker gets many related hints about a secret number and still mustn't find it. More hints means more risk.

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: If it failed, the tiny proofs and data seals built on it (KZG commitments, many zero-knowledge proofs) could be faked.

The details

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

Assumptions where the attacker sees many related values, g^τ, g^(τ²), ..., g^(τ^q) for a secret τ, and must still be unable to compute something like g^(1/(τ+c)) (q-SDH)[1] or τ itself (q-DLOG).

They are stronger, so riskier, than plain Diffie-Hellman: more given information means more attack surface, and Cheon's attack shaves off security when q is large[2]. KZG commitments and pairing SNARKs rely on them[3, 4]. A Diffie-Hellman solver would break them, so they imply key exchange (KE).

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

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.
TD
This assumption gives trapdoor functions on its own (computable by anyone, invertible only with a secret), so it falls if trapdoor functions don't exist. Schemes built on it need not use a trapdoor: ElGamal doesn't.

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. Jung Hee Cheon. Security Analysis of the Strong Diffie-Hellman Problem. Advances in Cryptology - EUROCRYPT 2006. doi:10.1007/11761679_1
  3. 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
  4. Jens Groth. On the Size of Pairing-Based Non-interactive Arguments. Advances in Cryptology – EUROCRYPT 2016. doi:10.1007/978-3-662-49896-5_11