Elliptic Curves for SNARK and Proof Systems

Elliptic curves make possible in practice very interesting mechanisms of proofs. The security relies on the difficulty of the discrete logarithm problem and its variants. Succinct non-interactive arguments of knowledge (SNARK) are a very fruitful topic, so that given a sequence of instructions that can be quite large, it is possible to extract a single equation such that if satisfied, it will convince a verifier that the set of instructions were correctly executed. To ensure the zero-knowledge property, the equation is hidden ''in the exponents'', in other words, ''homomorphic hiding'' is required. Such a property is made possible with a pairing on elliptic curves: a bilinear map e : G1 x G2 -> GT, where e([a]g1, [b]g2) = e(g1, g2)^{ab}, that can multiply secret scalars/exponents together. The solution of Groth at Eurocrypt'16 (Groth16) made possible a SNARK verification in three pairings, the proof size being two elements from G1 and one from G2, with additional costs of large scalar multiplications.
The design of dedicated elliptic curves is required at different stages: finding inner pairing-friendly elliptic curves (first SNARK), finding outer pairing-friendly elliptic curves (second SNARK, a first construction was given in the Geppetto paper), finding embedded elliptic curves (such as JubJub or Bandersnatch for BLS12-381). This talk will recall the construction of particular pairing-friendly elliptic curves for SNARK, and the recent works on finding 2-chains and embedded curves.

This talk is based on joint works with Diego Aranha, Youssef El Housni, and Simon Masson: ePrint 2022/586 (A survey of elliptic curves for proof systems) and ePrint 2024/1737 (Embedded Curves and Embedded Families for SNARK-Friendly Curves)