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
-
Attacking the Supersingular Isogeny Problem: From the Delfs–Galbraith algorithm to oriented graphs
Speaker : Arthur Herlédan Le Merdy - COSIC, KU Leuven
The threat of quantum computers motivates the introduction of new hard problems for cryptography.One promising candidate is the Isogeny problem: given two elliptic curves, compute a “nice’’ map between them, called an isogeny.In this talk, we study classical attacks on this problem, specialised to supersingular elliptic curves, on which the security of current isogeny-based cryptography relies. In[…]-
Cryptography
-
-
Verification of Rust Cryptographic Implementations with Aeneas
Speaker : Aymeric Fromherz - Inria
From secure communications to online banking, cryptography is the cornerstone of most modern secure applications. Unfortunately, cryptographic design and implementation is notoriously error-prone, with a long history of design flaws, implementation bugs, and high-profile attacks. To address this issue, several projects proposed the use of formal verification techniques to statically ensure the[…] -
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[…] -
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
-