Computational cryptography › Public-key encryption and key exchange › Classical number theory › Pairing groups: BLS12-381, BN254
Hardness assumption

Discrete log on pairing curves

In plain words

Special elliptic curves that come with an extra "pairing" operation. Their security needs the discrete-log puzzle to be hard on every part of 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: They make very short signatures and tiny zero-knowledge proofs possible.

The details

On the map: in G1, G2 (curve DL) and GT (field DL)

Pairing-friendly elliptic curves such as BLS12-381 and BN254[1] come with a bilinear map e that combines points from two curve groups, G1 and G2, into a third group GT. Security needs the discrete log problem to be hard in all three.

G1 and G2 are curve groups, attacked with generic methods. GT lives inside a finite field, where faster number field sieve attacks apply. Improved variants (exTNFS, Kim and Barbulescu 2016)[2, 3] cut BN254 from about 128 to about 100 bits of security. BLS12-381 is estimated at about 126 bits, just under its 128-bit target (IETF CFRG pairing-curves draft)[4]. Breaking either side breaks everything pairing-based.

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 (6 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. 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
  3. Razvan Barbulescu and Sylvain Duquesne. Updating Key Size Estimations for Pairings. Journal of Cryptology, 2019. doi:10.1007/s00145-018-9280-5
  4. 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