Author: Thomas DEBRIS

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: