Category: Uncategorized

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

Place : LIX, room Grace Hopper

Title : 3-Tensors: a natural way of representing rank-metric codes

Abstract : In coding theory, two important issues concern the encoding and the storage of a
code. In the most general case, given a finite set A and a positive integer n, a block
code C is a subset of A^n , endowed with a distance function (usually the Hamming one).
The space of messages M is then embedded in A^n , via an injective encoding map E,
such that E(M) = C. The need to have fast encoding and efficient representation of
codes led to look at algebraic structures on all the defining objects (the alphabet, the
space of messages and the code), and on the encoding map E. For this reason, one
usually only considers the alphabet as a field of q elements, the space of messages as
the vector space F_q^k , and the encoding map as a linear function into F_q^n , which leads
to the study of linear codes. In this framework, we can locate the generator matrix
of an [n, k] code C, which serves as a representation in order to store C, and also
as an encoding map. However, one can also read the parameters of the defining code
from its algebraic structure. This generator matrix can also be constructed for a vector
rank-metric code, and in analogous ways, one can extrapolate information on the code
from it.
In this talk we explain an analogous concept for rank-metric codes, which are con-
sidered as spaces of m × n matrices over a finite field F_q . This is the case of the
generator tensor, which is a similar object that one can use for storing, encoding and
reading the parameters of a rank-metric code. Moreover, the tensor representation
leads to the investigation of a new parameter, namely the tensor rank of an [n × m, k]
code C, that gives a measure on the storage and encoding complexity of C. This also
produces an interesting relation between rank-metric codes and algebraic complexity
theory.

It is a joint work with Eimear Byrne, Alberto Ravagnani and John Sheekey.