Computational cryptography › Live on mainnet today › Pairing curves
Hardness assumption

Discrete log on pairing curves

In plain words

The special curves behind validator signatures and zero-knowledge proofs. Their security needs the discrete-log puzzle to be hard on them.

The idea: A pairing takes two curve points and combines them so that secret multipliers pass straight through: pairing a·P with b·Q gives the same result as pairing P with Q and raising it to the power a·b. That lets anyone check relationships between hidden numbers without learning them, the engine behind BLS signatures and SNARKs. The price: the result lands in a third group where discrete log is easier to attack, so the curves must be sized for the weakest of the three.

Why it matters: If it breaks, BLS signatures, KZG and most ZK verifiers fall.

The details

On the map: in G1, G2 and GT ⊂ Fq*, q = p¹², so field DL attacks apply: BLS12-381 ~126-bit, BN254 fell to ~100-bit (exTNFS, 2016)

BLS12-381 and BN254 are pairing-friendly curves[1, 2]: a bilinear map combines points from two curve groups into a third group that sits inside a finite field. Security needs discrete log to be hard in all three.

The finite-field side is attacked with faster number-field-sieve methods. Improved variants (exTNFS, 2016)[3, 4] cut BN254, the curve behind Ethereum's original ZK precompiles, from about 128 to about 100 bits of security. BLS12-381 was designed for 128 bits and is estimated at about 126 (IETF CFRG pairing-curves draft)[5]. Shor's algorithm breaks both.

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 (15 boxes)

References

  1. Sean Bowe. BLS12-381: New zk-SNARK Elliptic Curve Construction. Electric Coin Company blog, 2017. electriccoin.co/blog/new-snark-curve
  2. Christian Reitwiessner. EIP-196: Precompiled contracts for addition and scalar multiplication on the elliptic curve alt_bn128. Ethereum Improvement Proposals (Final), 2017. eips.ethereum.org/EIPS/eip-196
  3. Taechan Kim and Razvan Barbulescu. Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case. Advances in Cryptology – CRYPTO 2016. doi:10.1007/978-3-662-53018-4_20
  4. Razvan Barbulescu and Sylvain Duquesne. Updating Key Size Estimations for Pairings. Journal of Cryptology, 2019. doi:10.1007/s00145-018-9280-5
  5. Yumi Sakemi, Tetsutaro Kobayashi, Tsunekazu Saito and Riad S. Wahby. Pairing-Friendly Curves (Internet-Draft draft-irtf-cfrg-pairing-friendly-curves). IRTF CFRG, 2022. datatracker.ietf.org/doc/draft-irtf-cfrg-pairing-friendly-curves