Current
The seminar is organized by Xavier Caruso and Aurel Page and currently takes place online. To get announcements, you can subscribe to the mailing-list.- 2021-05-1110:00OnlineWeiqiang Wen (Inria Rennes, Irisa)On algorithms for solving Euclidean lattice problems in cryptography
In this talk, we will try to review the state-of-the-art of the algorithms for solving the Euclidean lattice problems underlying cryptography. In more details, this talk contains two parts. In the first part, we will focus on the lattice problems such as approximate Shortest Vector Problem (approx-SVP) and the lattice reduction algorithms as the best known solving algorithms so far. In particular, I will present an improved enumeration-based lattice reduction algorithm, which is shown to be (potentially) relevant to cryptanalysis. In the second part, we will instead consider a quantum problem that is computationally equivalent to approx-SVP. By directly solving a quantum problem, we may expect to have a more powerful use of the quantum computation. However, the best known algorithms for solving approx-SVP via solving this quantum problem, is not better than lattice reduction yet.
- 2021-05-1810:00OnlineAurore Guillevic (Inria Nancy, Loria)Computing Murphy-alpha in the special tower number field sieve algorithm and applications to pairing-based cryptography
Pairings on elliptic curves are involved in signatures, NIZK, and recently in blockchains (ZK-SNARKS). These pairings take as input two points on an elliptic curve $E$ over a finite field, and output a value in an extension of that finite field. Usually for efficiency reasons, this extension degree is a power of 2 and 3 (such as 12, 18, 24), and moreover the characteristic of the finite field has a special form. The security relies on the hardness of computing discrete logarithms in the group of points of the curve and in the finite field extension.
In 2013-2016, new variants of the function field sieve and the number field sieve algorithms turned out to be faster in certain finite fields related to pairing-based cryptography, in particular those which had a very efficient arithmetic. Now small characteristic settings are discarded. The situation for $GF(p^k)$ where $p$ is prime and $k$ is small is still quite unclear. We refine the work of Menezes-Sarkar-Singh and Barblescu-Duquesne to estimate the cost of a hypothetical implementation of the Special-Tower-NFS in $GF(p^k)$ for small $k$, and deduce parameter sizes for cryptographic pairings.
Joint work with Shashank Singh, IISER Bhopal, India.
References
On the alpha value of polynomials in the tower number field sieve algorithm, Aurore Guillevic and Shashank Singh, Mathematical Cryptology, Vol 1 No 1 (Feb 2021), journal version, preprint.
A short list of pairing-friendly curves at the 128-bit security level, Aurore Guillevic, presented at PKC’2020 recorded talk, ePrint 2019/1371.
Implementation available with MIT licence on gitlab. Alpha in Magma, alpha and TNFS simulation in SageMath. - 2021-05-2510:00OnlineRazvan Barbulescu (CNRS, IMB)TBA
TBA
- 2021-06-0810:00OnlineStéphane Ballet (I2M, Université Aix-Marseille)TBA
TBA
- 2021-06-1510:00OnlineFabien Narbonne (IRMAR, Université de Rennes)TBA
TBA
- 2021-06-2210:00OnlineVandita Patel (University of Manchester)TBA
TBA
- 2021-06-2910:00OnlinePierre Briaud (Inria Paris)TBA
TBA
- 2021-07-0610:00OnlineAnna Somoza (IRMAR, Université de Rennes 1)TBA
TBA
- 2021-09-1410:00OnlineBenjamin Wesolowski (CNRS, IMB)TBA
TBA