Date de l'exposé : 16 septembre 2022
Elliptic curves for SNARKs
A proof system is a protocol where one party (called the prover) tries to
convince another party (called the verifier) that a given statement is
true. In the class of non-interactive proof systems, a particularly
interesting concept for proving the computational integrity is the Succinct
Non-interactive ARgument of Knowledge (SNARK). It provides a
computationally sound proof, cheap to verify and small compared to the size
of the statement or the witness. Bilinear pairings over elliptic curves
have become key ingredients for instantiating such SNARKs.
In this thesis we investigate tailored pairing-friendly elliptic curves to
efficiently implement SNARKs. We present a study at three stages of the
process: curves to instantiate a SNARK, curves to instantiate a recursive
SNARK, and also curves to express an elliptic-curve related statement. We
provide new constructions of curves for SNARKs and new families of 2-chain
curves for recursive SNARKs. We derive and implement in open-source
efficient algorithms to speed up the arithmetic on these curves: Co-factor
clearing, subgroup membership testing, multi-scalar multiplication and
pairings over 2-chains. We also study and optimize elliptic curves
arithmetic and pairings as a SNARK statement, yielding to the fastest
recursive proof generation in pairing-based settings.
