Pairing-friendly elliptic curves, design, implementation, and discrete logarithm computations

Design and implementation of pairing-friendly curves knew a growing activity from 2000 to roughly 2014. Bilinear pairings are a building block for many cryptosystems, for example broadcast encryption, zero-knowledge proofs. Pairing-friendly curves have an inherent weakness due to the MOV attack that transfers the discrete logarithm problem from the curve to an embedding finite field GF(q). Serious attacks against the discrete logarithm problem in extension fields GF(2^n), GF(3^m) and GF(p^k) were developed from 2012, with as major milestones the quasi-polynomial time algorithm in small characteristic and so-called zig-zag descent, that made pairings in characteristic 2 and 3 obsolete. In medium-sized extensions such as GF(p12), variants of the TNFS algorithm are the most promising (Tower Number Field Sieve algorithm).

New specific needs of pairing-friendly elliptic curves emerged with the development of SNARK (succinct non-interactive argument of knowledge). The interest in finding prime-order pairing-friendly curves, developing efficient pairing computations, and also estimating precisely the complexity of TNFS in extension fields, was reactivated.

I will present two aspects: the development of a simulator for the TNFS algorithm to estimate the security of pairing-friendly curves, available at https://gitlab.inria.fr/tnfs-alpha/alpha and the development (in progress) of a Python/SageMath library of pairings, a preliminary version being at https://gitlab.inria.fr/zk-curves/snark-2-chains These are joint work with Youssef El Housni, Georgios Fotiadis, Diego Aranha.