Description
This talk is based on joint works with Diego Aranha, Youssef El Housni, and Simon Masson.
Elliptic curves make possible in practice very interesting mechanisms of proofs. The security relies on the difficulty of the discrete log problem and 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 G1 and one G2 elements.
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 for BLS12-381). This talk will recall the construction of particular pairing-friendly elliptic curves for SNARK, and the recent works on finding embedded curves. A generalisation of the work of Sanso and El Housni will be presented, that allows to obtain in about some hours a 2-cycle of elliptic curves with CM, given any input prime. The parameterized version will be given.
Practical infos
Next sessions
-
On the average hardness of SIVP for module lattices of fixed rank
Speaker : Radu Toma - Sorbonne Université
In joint work with Koen de Boer, Aurel Page, and Benjamin Wesolowski, we study the hardness of the approximate Shortest Independent Vectors Problem (SIVP) for random module lattices. We use here a natural notion of randomness as defined originally by Siegel through Haar measures. By proving a reduction, we show it is essentially as hard as the problem for arbitrary instances. While this was[…] -
Lightweight (AND, XOR) Implementations of Large-Degree S-boxes
Speaker : Marie Bolzer - LORIA
The problem of finding a minimal circuit to implement a given function is one of the oldest in electronics. In cryptography, the focus is on small functions, especially on S-boxes which are classically the only non-linear functions in iterated block ciphers. In this work, we propose new ad-hoc automatic tools to look for lightweight implementations of non-linear functions on up to 5 variables for[…]-
Cryptography
-
Symmetrical primitive
-
Implementation of cryptographic algorithm
-
-
Algorithms for post-quantum commutative group actions
Speaker : Marc Houben - Inria Bordeaux
At the historical foundation of isogeny-based cryptography lies a scheme known as CRS; a key exchange protocol based on class group actions on elliptic curves. Along with more efficient variants, such as CSIDH, this framework has emerged as a powerful building block for the construction of advanced post-quantum cryptographic primitives. Unfortunately, all protocols in this line of work are[…] -
Endomorphisms via Splittings
Speaker : Min-Yi Shen - No Affiliation
One of the fundamental hardness assumptions underlying isogeny-based cryptography is the problem of finding a non-trivial endomorphism of a given supersingular elliptic curve. In this talk, we show that the problem is related to the problem of finding a splitting of a principally polarised superspecial abelian surface. In particular, we provide formal security reductions and a proof-of-concept[…]-
Cryptography
-