PhD graduated
Team : PolSys
Departure date : 02/08/2021

Supervision : Jean-Charles FAUGÈRE

Co-supervision : PERRET Ludovic

Design and Cryptanalysis in Multivariate Quantum-Safe Cryptography

In this thesis, we study the design of multivariate cryptosystems, which are resistant against classical and quantum computers. In particular, we study two digital signature schemes that I submitted to the NIST Post-Quantum Cryptography standardization process: GeMSS and DualModeMS. These schemes are based on the HFE family. We propose security parameters based on a state-of-the-art of twenty years of intensive cryptanalysis. Then, we select secure parameters which maximize the practical efficiency. We measure this with a new library: MQsoft. MQsoft is a fast library in C which supports a large set of parameters for HFE-based schemes. Its performance outperforms all existing libraries. We explain in this thesis how we obtain this result. Whereas GeMSS is a scheme which has a large public-key but a very short signature, DualModeMS is based on a transformation inverting this trade-off. However, its security is based on the assumption that the AMQ problem is hard. We demonstrate that this assumption is verified, and we confirm our results with experiences using Gröbner basis. Finally, we propose the first implementation of DualModeMS. We study how to implement it efficiently, as well as how to optimize the choice of security parameters. We also extend DualModeMS to the Rainbow cryptosystem instead of HFE. This allows having interesting key sizes and signature sizes.

Defence : 02/08/2021

Jury members :

DUMAS Jean-Guillaume (Professeur à l’université Grenoble Alpes) [Rapporteur]
SMITH-TONE Daniel (Professeur associé à University of Louisville, Chercheur senior au NIST) [Rapporteur]
GOUGET Aline (Directrice et experte senior en cryptographie avancée à Thalès)
SAFEY EL DIN Mohab (Professeur à Sorbonne Université)
LOIDREAU Pierre (DGA et Chercheur associé à l'université de Rennes I)
FAUGÈRE Jean-Charles (Directeur de recherche à l'INRIA Paris)
PERRET Ludovic (Maître de conférences HDR à Sorbonne Université)

Departure date : 02/08/2021

2017-2021 Publications