Cryptanalyse algébrique et contributions à la cryptographie post-quantique basée sur les codes correcteurs d’erreurs en métrique rang

Discipline

Informatique

Classification

Informatique

Mots-clés libres

Cryptographie post-quantique, Code correcteur d'erreurs, Attaque algébrique, Bases de Gröbner, Cryptanalyse, Métrique Rang

Mots-clés

Cryptographie post-quantique,

Codes correcteurs d'erreurs (théorie de l'information)

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.