Title: Asymptotic performance of G-codes and uncertainty principle.

Abstract: The uncertainty principle is a very famous inequality in Physics,
Signal Processing, and Harmonic Analysis. It compares the supports of functions
and of their complex-valued Fourier transforms. In a recent paper by Evra,
Kowalski, and Lubotzky a connection between the uncertainty principle and the
asymptotic performance of cyclic codes was pointed out. Note that the existence
of an asymptotically good family of cyclic codes is a problem open for more
than half a century.
In the first part of the talk, we will present some recent results about the asymptotic
performance of group codes, which are a generalization of cyclic codes. In the second
part, we will give an overview of conjectural and proved results about the uncertainty
principle over finite fields. A naive version of this principle, which is verified by any
finite field, implies that there exist sequences of cyclic codes of length n, arbitrary rate,
and minimum distance Ω(n^α) for all 0 < α < 1/2.

Slides:

Titre : Étude théorique de codes géométriques sur des familles de surfaces algébriques

Résumé : Nous donnons des bornes pour la distance minimale de codes
géométriques algébriques construits à partir des surfaces définies sur les
corps finis. Dans un premier temps, nous étudions les codes sur deux
grandes familles de surfaces : celles dont le diviseur anti-canonique est
strictement nef ou anti-nef et celles qui ne contiennent pas de courbes
irréductibles de petit genre. Puis, nous améliorerons ces bornes dans des
familles particulières, notamment dans le cas des surfaces fibrées et des
surfaces abéliennes, en utilisant la géométrie propre à ces surfaces.

Il s’agit de deux travaux conjoints avec Y. Aubry, F. Herbaut et M.
Perret, preprints : https://arxiv.org/abs/1912.07450 et
https://arxiv.org/pdf/1904.08227.pdf.

Slides:

Title: SQISign: Compact Post-Quantum Signature from Quaternions and Isogenies.

Abstract: We introduce a new signature scheme, SQISign, (for Short Quaternion and
Isogeny Signature) from isogeny graphs of supersingular elliptic curves. The signature
scheme is derived from a new one-round, high soundness, interactive identification protocol.
Targeting the post-quantum NIST-1 level of security, our implementation results in signatures
of 204 bytes, secret keys of 16 bytes and public keys of 64 bytes. In particular, the signature
and public key sizes combined are an order of magnitude smaller than all other post-quantum
signature schemes. On a modern workstation, our implementation in C takes 0.6s for key
generation, 2.5s for signing, and 50ms for verification.
While the soundness of the identification protocol follows from classical assumptions, the
zero-knowledge property relies on the second main contribution of this paper.
We introduce a new algorithm to find an isogeny path connecting two given supersingular
elliptic curves of known endomorphism rings.
A previous algorithm to solve this problem, due to Kohel, Lauter, Petit and Tignol, systematically
reveals paths from the input curves to a `special’ curve. This leakage would break the
zero-knowledge property of the protocol. Our algorithm does not directly reveal such a path,
and subject to a new computational assumption, we prove that the resulting identification
protocol is zero-knowledge.

Slides:

Title: Cryptanalysis of the Faure-Loidreau PKE, a rank-metric code-based cryptosystem with short keys.

Abstract: In 2005, C. Faure and P. Loidreau designed a rank-metric encryption
scheme which was not in the McEliece setting. This scheme has small public and
private keys (a few kiloBytes only) and is based on the hardness of decoding some 
rank-metric codes (namely the Gabidulin codes) above half the minimum distance.
In 2016 though, this scheme was subject to a very efficient polynomial time
key-recovery attack by P. Gaborit, A. Otmani and H. Talé-Kalachi. A repaired version was
eventually proposed by A. Wachter-Zeh, S. Puchinger and J. Renner in 2018 
to resist the previous structural attack. 
In this talk, I will present a variant of a decoder for Gabidulin codes, which can be used
in an alternative attack on the original Faure-Loidreau cryptosystem. I will then show that
the repaired version is vulnerable to a practical plaintext recovery attack.

This is joint work with Alain Couvreur.

Slides:

Title: Recent progress on the computation of Riemann-Roch spaces.

Abstract: Riemann-Roch spaces are vector spaces of rational functions
whose poles and zeros are constrained by points lying on a curve. They are
important objects in algebraic geometry and have found many applications
in diophantine equations, symbolic integration and algebraic geometry
codes. In the first part of this talk, I will present the Brill-Noether
framework to compute Riemann-Roch spaces and explain how to design an
efficient subquadratic algorithm using adequate tools from computer
algebra. In a second part, we will discuss another approach used in Hess’
algorithm and provide new complexity bounds for precomputations required
by this method. The first part is joint work with Alain Couvreur and
Grégoire Lecerf.

Slides: 

Title: Fast verification of masking schemes in characteristic two

Abstract: We revisit the matrix model for non-interference (NI) probing security of masking gadgets introduced by Belaïd et al. at CRYPTO 2017. This leads to two main results. 1) We generalise the theorems on which this model is based, so as to be able to apply them to masking schemes over any finite field —in particular GF(2)— and to be able to analyse the strong non-interference (SNI) security notion. We also follow Faust et al. (TCHES 2018) to additionally consider a robust probing model that takes hardware defects such as glitches into account. 2) We exploit this improved model to implement a very efficient verification algorithm that improves the performance of state-of-the-art software by three orders of magnitude. We show applications to variants of NI and SNI multiplication gadgets from Barthe et al. (EUROCRYPT 2017) which we verify to be secure up to order 11 after a significant parallel computation effort, whereas the previous largest proven order was 7; SNI refreshing gadgets (ibid.); and NI multiplication gadgets from Groß et al. (TIS@CCS 2016) secure in presence of glitches. We also reduce the randomness cost of some existing gadgets, notably for the implementation-friendly case of 8 shares, improving here the previous best results by 17% (resp. 19%) for SNI multiplication (resp. refreshing).

Place : LIX, Salle Henri Poincaré

Title : The supersingular isogeny problem in genus 2 and beyond (with Craig Costello)

Abstract : Let A and A’ be superspecial principally polarized abelian varieties of dimension g > 1 over F_p. For any fixed prime \ell \not= ̸p, we give an algorithm that finds a path from A to A’ in the (\ell,…,\ell)-isogeny graph in \softO(p^{g-1}) group operations on a classical computer, and O(p^{(g-1)/2}) calls to a Grover oracle on a quantum computer. The idea is to find paths from A and A’ to nodes corresponding to products of lower-dimensional abelian varieties, and to recurse down in dimension until an elliptic path-finding algorithm to connect the paths in dimension g = 1. In the general case, where A and A’ are any two nodes in the graph, this algorithm presents an asymptotic improvement over all of the algorithms in the current literature. In the special case where A and A’ are a known and relatively small number of steps away from each other (as is the case in higher dimensional analogues of SIDH), it gives an asymptotic improvement over quantum claw-finding algorithms and the classical van Oorschot–Wiener algorithm.

Place : LIX, Salle Henri Poincaré

Title : A new elliptic curve point compression method based on $\F{p}$-rationality of some generalized Kummer surfaces

Abstract : It is proposed a new compression method (to $2\log_2(p) + 3$ bits) for the $\mathbb{F}_{\!p^2}$-points of an elliptic curve $E_b\!: y^2 = x^3 + b$ (for $b \in \mathbb{F}_{\!p^2}^*$) of $j$-invariant $0$. It is based on $\mathbb{F}_{\!p}$-rationality of some generalized Kummer surface $GK_b$. This is the geometric quotient of the Weil restriction $R_b := \mathrm{R}_{\: \mathbb{F}_{\!p^2}/\mathbb{F}_{\!p}}(E_b)$ under the order $3$ automorphism restricted from $E_b$. More precisely, we apply the theory of conic bundles (i.e., conics over the function field $\mathbb{F}_{\!p}(t)$) to obtain explicit and quite simple formulas of a birational $\mathbb{F}_{\!p}$-isomorphism between $GK_b$ and $\mathbb{A}^{\!2}$. Our point compression method consists in computation of these formulas. To recover (in the decompression stage) the original point from $E_b(\mathbb{F}_{\!p^2}) = R_b(\mathbb{F}_{\!p})$ we find an inverse image of the natural map $R_b \to GK_b$ of degree $3$, i.e., we extract a cubic $\mathbb{F}_{\!p}$-root. For $p \not\equiv 1 \: (\mathrm{mod} \ 27)$ this is just a single exponentiation in $\mathbb{F}_{\!p}$, hence the new method seems to be much faster than the classical one with $x$ coordinate, which requires two exponentiations in $\mathbb{F}_{\!p}$.

Place : LIX, Salle Philippe Flajolet

Title: An LLL Algorithm for Module Lattices

Abstract: A lattice is a discrete subgroup (i.e., ZZ-module) of RR^n (where ZZ and RR are the sets of integers and real numbers). The LLL algorithm is a central algorithm to manipulate lattice bases. It takes as input a basis of a Euclidean lattice, and, within a polynomial number of operations, it outputs another basis of the same lattice but consisting of rather short vectors. Lattices are used in post-quantum cryptography, as finding a shortest vector of a lattice, given an arbitrary basis, is supposed to be intractable even with a quantum computer. For practical reasons, many constructions based on lattices use structured lattices, in order to improve the efficiency of the schemes. Most of the time, these structured lattices are R-modules of small rank, where R is the ring of integers of some number field. As an example, 11 schemes among the 12 lattice-based candidates for the NIST post-quantum standardization process use module lattices, with modules of small rank. It is then tempting to try and adapt the LLL algorithm, which works over lattices (i.e., ZZ-modules), to these R-modules, as this would allow us to find rather short vectors of these module lattices. Previous works trying to extend the LLL algorithm to other rings of integers R focused on rings R that were Euclidean, as the LLL algorithm over ZZ crucially relies on the Euclidean division. In this talk, I will describe an LLL algorithm which works in any ring of integers R. This algorithm is heuristic and runs in quantum polynomial time if given access to an oracle solving the closest vector problem in a fixed lattice, depending only on the ring of integers R. This is a joint work with Changmin Lee, Damien Stehlé and Alexandre Wallet