Depot des Theses - Algebraic cryptanalysis and contributions to post-quantum cryptography based on error-correcting codes in the rank-metric

La cryptographie basée sur les codes correcteurs d'erreurs en métrique rang est un domaine prometteur de la cryptographie post-quantique, elle repose sur l'utilisation de la métrique rang au lieu de la métrique de Hamming. Le problème du décodage en métrique rang (RD) ainsi que le problème MinRank (MR) sont au cœur de la cryptographie basée sur les codes correcteurs d'erreurs en métrique rang. Pendant plusieurs décennies, les attaques combinatoires étaient considérées comme les plus efficaces pour attaquer RD; dans cette thèse nous introduisons deux attaques contre RD et MR, que nous appelons respectivement MaxMinors et SupportMinors. Il s'avère que l'attaque MaxMinors est redoutablement plus efficace que les attaques combinatoires pour une zone de paramètres souvent utilisée en cryptographie basée sur les codes correcteurs d'erreurs en métrique rang, par exemple pour les cryptosystèmes ROLLO et RQC. Dans cette thèse, nous avons également amélioré le chiffrement Rank Quasi-Cyclic (RQC) en proposant deux nouvelles versions avec des paramètres compétitifs. Plus précisément, l'un de ces nouveaux schémas a l'avantage d'avoir une sécurité reposant uniquement sur le décodage de codes aléatoires en métrique rang avec plusieurs syndromes, c'est-à-dire sur le problème Rank Support Learning (RSL), variante de RD. Pour étudier la sécurité de ces deux nouveaux schémas, nous proposons plusieurs attaques, tant combinatoires qu'algébriques, contre des variantes de RD, à savoir Non-Homogeneous RD, RSL, and Non-Homogeneous RSL. Ensuite, nous présentons la cryptanalyse de la signature RPS, une signature basée sur les codes correcteurs d'erreurs en métrique rang. Dans cette thèse, nous donnons une réduction du problème PSSI vers MinRank. Le problème PSSI est au coeur du schéma de signature en métrique rang Durandal; ainsi, cette réduction permet de bénéficier de nouvelles attaques contre ce problème. Enfin, nous concluons cette thèse en introduisant un nouveau problème difficile: SquareSpace. Nous étudions sa complexité en décrivant plusieurs attaques combinatoires et algébriques, avant de donner 4 challenges pour le niveau de sécurité 128 bits. Finalement, nous décrivons un schéma de signature dont la sécurité repose sur SquareSpace, ainsi que l'implémentation en C de ce schéma. Créé par Bros Maxime 24 janv. 2023 Version 0.1

Nature

Thèse de doctorat

Subjects

Rights

Source

Coverage

Created at

24 janv. 2023

Last modified at

24 janv. 2023

Format

PDF

Language

Author

Bros Maxime

Last Contributor

system

Contributors

system