CRC Seminar Series: Aurore Guillevic

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. 

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)