Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Error correction and reconciliation techniques for lattice-based key generation protocols

Charbel Saliba

Published May 24, 2022• 2 citations
Publisher

Abstract

Techniques de correction d'erreurs et de réconciliation pour les protocoles de génération de clés basés sur des réseaux de points Au cours de la dernière décennie, le développement des ordinateurs quantiques a considérablement progressé, avec des investissements massifs de la part des grandes entreprises technologiques. On suppose qu'une fois que les ordinateurs quantiques à grande échelle seront construits, de nombreux systèmes cryptographiques à clé publique couramment utilisés ne seront plus sécurisés. Pour prévenir les attaques quantiques, les chercheurs travaillent déjà à la conception de protocoles cryptographiques post-quantiques, et le National Institute of Standards and Technology (NIST) des États-Unis organise un concours international pour sélectionner de nouvelles normes cryptographiques.Les constructions cryptographiques à base de réseaux euclidiens sont des candidats prometteurs car elles offrent de fortes garanties de sécurité théoriques et peuvent être mises en œuvre efficacement. L'une des primitives cryptographiques les plus largement utilisées basées sur des réseaux est le problème d'apprentissage avec erreurs, ou en anglais emph{Learning with errors} (LWE) introduit par Regev. Des travaux ultérieurs ont proposé des variantes structurées de LWE telles que Ring-LWE et Module-LWE, qui permettent une représentation plus compacte.Dans cette thèse, nous considérons deux candidats au défi du NIST basés sur les réseaux euclidiens pour les mécanismes d'encapsulation de clé (KEM) et proposons de nouvelles techniques de correction d'erreur et de réconciliation afin d'améliorer leur efficacité, leur sécurité, ainsi que leur fiabilité. Contrairement à certains travaux antérieurs sur la correction d'erreurs pour les protocoles basés sur les réseaux, nous proposons des bornes de probabilité d'erreur rigoureuses.Nous considérons d'abord FrodoKEM, un cryptosystème basé sur LWE, et introduisons un mécanisme de correction d'erreur pour améliorer ses performances. Notre encodeur mappe la clé secrète par bloc dans le réseau de Gosset à 8 dimensions E_8. Nous proposons trois ensembles de paramètres pour notre implémentation modifiée. La première implémentation surpasse FrodoKEM en termes de sécurité plausible ; la seconde permet de réduire la bande passante en divisant par deux le module, et la troisième permet d'augmenter la taille des clés.Le deuxième KEM que nous considérons est KyberKEM, qui est basé sur Module-LWE. Nous proposons une technique de réconciliation utilisant toujours le réseau euclidien E_8, et montrons que notre schéma peut surpasser KyberKEM en termes de sécurité avec une probabilité d'erreur comparable et des exigences de bande passante similaires. Nous étudions également l'utilisation de réseaux de dimension supérieure pour la réconciliation.

DOI
10.70675/b50f31f8za784z46b1z9a7az94b9286091d6

Related papers

Extended security of lattice-based cryptography

Mélissa Rossi

Sécurité étendue de la cryptographie fondée sur les réseaux Euclidiens La cryptographie fondée sur les réseaux euclidiens représente une alternative prometteuse à la cryptographie asymétrique utilisée actuellement, en raison de sa résistance présumée à un ordinateur quantique universel. Cette nouvelle famille de schémas asymétriques dispose de plusieurs atouts parmi lesquels de fortes garanties théoriques de sécurité, un large choix de primitives et, pour certains de ses représentants, des performances comparables aux standards actuels. Une campagne de standardisation post-quantique organisée par le NIST est en cours et plusieurs schémas utilisant des réseaux euclidiens font partie des favoris. La communauté scientifique a été encouragée à les analyser car ils pourraient à l'avenir être implantés dans tous nos systèmes. L'objectif de cette thèse est de contribuer à cet effort. Nous étudions la sécurité de ces nouveaux cryptosystèmes non seulement au sens de leur résistance à la cryptanalyse en ''boîte noire'' à l'aide de moyens de calcul classiques, mais aussi selon un spectre plus large de modèles de sécurité, comme les attaques quantiques, les attaques supposant des failles d'utilisation, ou encore les attaques par canaux auxiliaires. Ces différents types d’attaques ont déjà été largement formalisés et étudiés par le passé pour des schémas asymétriques et symétriques pré-quantiques. Dans ce mémoire, nous analysons leur application aux nouvelles structures induites par les réseaux euclidiens. Notre travail est divisé en deux parties complémentaires : les contremesures et les attaques. La première partie regroupe nos contributions à l'effort actuel de conception de nouvelles protections algorithmiques afin de répondre aux nombreuses publications récentes d’attaques par canaux auxiliaires. Les travaux réalisés en équipe auxquels nous avons pris part on abouti à l'introduction de nouveaux outils mathématiques pour construire des contre-mesures algorithmiques, appuyées sur des preuves formelles, qui permettent de prévenir systématiquement les attaques physiques et par analyse de temps d'exécution. Nous avons ainsi participé à la protection de plusieurs schémas de signature fondés sur les réseaux euclidiens comme GLP, BLISS, qTesla ou encore Falcon. Dans une seconde partie consacrée à la cryptanalyse, nous étudions dans un premier temps de nouvelles attaques qui tirent parti du fait que certains schémas de chiffrement à clé publique ou d'établissement de clé peuvent échouer avec une faible probabilité. Ces échecs sont effectivement faiblement corrélés au secret. Notre travail a permis d’exhiber des attaques dites « par échec de déchiffrement » dans des modèles de failles d'utilisation ou des modèles quantiques. Nous avons d'autre part introduit un outil algorithmique de cryptanalyse permettant d’estimer la sécurité du problème mathématique sous-jacent lorsqu’une information partielle sur le secret est donnée. Cet outil s’est avéré utile pour automatiser et améliorer plusieurs attaques connues comme des attaques par échec de déchiffrement, des attaques classiques ou encore des attaques par canaux auxiliaires.

•Sep 10, 2020•1 citation

Contribution à la cryptographie post-quantique basée sur les codes correcteurs d’erreurs en métrique rang : Hash Proof Systems et cryptographie à bas coût

Yann Connan

La conception d’ordinateurs quantiques aura un impact majeur sur la cryptographie que nous utilisons tous les jours pour sécuriser nos communications, en particulier sur la cryptographie dite asymétrique. De plus, la multiplication des objets connectés dans notre quotidien et leurs limitations en terme de capacité de calcul et de mémoire disponible en font des cibles privilégiées. Cette thèse est à la croisée des chemins de ces deux problématiques, et est découpée en trois axes d’études indépendants. Le premier porte sur la conception d’une primitive cryptographique appelée Hash Proof System (HPS). En nous basant sur le langage des chiffrés de RQC, nous allons montrer comment construire une telle primitive, puis nous en présenterons deux applications possibles : un schéma de chiffrement à témoin d’une part, puis un protocole d’échange de clés authentifié uniquement basé sur la connaissance d’un mot de passe commun, permettant ainsi de se passer d’une infrastructure à clé publique. Le deuxième axe d’étude est l’introduction d’un nouveau problème cryptographique, le problème LRE (Learning Rank with Errors), adaptation du problème LPN à la métrique rang. Nous étudierons quelques-unes de ses propriétés puis en présenterons une première application possible, un protocole d’authentification symétrique nommé HBLRE, adaptation du protocole HB au problème LRE. Enfin, le troisième axe d’étude est l’adaptation et l’implémentation de plusieurs schémas cryptographiques soumis au NIST, à savoir RQC et ROLLO (qui regroupe les schémas LAKE, LOCKER et Ouroboros-R) sur microcontrôleurs. Nous montrerons les divers algorithmes qui ont été utilisés et en décrirons leur fonctionnement. Nous présenterons la libraire RBC, une librairie mise au point afin de faciliter l’utilisation et la conception de schémas basés sur la métrique rang qui intègrent les travaux d’implémentation réalisés durant cette thèse. Enfin, nous présenterons les performances de ces implémentations sur un microcontrôleur doté d’un processeur de type ARM Cortex-M4 et les mettrons en perspective avec les performances d’autres schémas cryptographiques post-quantiques soumis à l’appel à standardisation du NIST.

•Apr 9, 2021•0 citations

Security of cryptographic protocols based on coding theory

Hervé Talé Kalachi

Sécurité des protocoles cryptographiques fondés sur la théorie des codes correcteurs d'erreurs Contrairement aux protocoles cryptographiques fondés sur la théorie des nombres, les systèmes de chiffrement basés sur les codes correcteurs d’erreurs semblent résister à l’émergence des ordinateurs quantiques. Un autre avantage de ces systèmes est que le chiffrement et le déchiffrement sont très rapides, environ cinq fois plus rapide pour le chiffrement, et 10 à 100 fois plus rapide pour le déchiffrement par rapport à RSA. De nos jours, l’intérêt de la communauté scientifique pour la cryptographie basée sur les codes est fortement motivé par la dernière annonce de la “National Institute of Standards and Technology" (NIST), qui a récemment initié le projet intitulé “Post-Quantum cryptography Project". Ce projet vise à définir de nouveaux standards pour les cryptosystèmes résistants aux attaques quantiques et la date limite pour la soumission des cryptosystèmes à clé publique est fixée pour novembre 2017. Une telle annonce motive certainement à proposer de nouveaux protocoles cryptographiques basés sur les codes, mais aussi à étudier profondément la sécurité des protocoles existants afin d’écarter toute surprise en matière de sécurité. Cette thèse suit cet ordre d’idée en étudiant la sécurité de plusieurs protocoles cryptographiques fondés sur la théorie des codes correcteurs d’erreurs. Nous avons commencé par l’étude de la sécurité d’une version modifiée du cryptosystème de Sidelnikov, proposée par Gueye et Mboup [GM13] et basée sur les codes de Reed-Muller. Cette modification consiste à insérer des colonnes aléatoires dans la matrice génératrice (ou de parité) secrète. La cryptanalyse repose sur le calcul de carrés du code public. La nature particulière des codes de Reed-Muller qui sont définis au moyen de polynômes multivariés binaires, permet de prédire les valeurs des dimensions des codes carrés calculés, puis permet de récupérer complètement en temps polynomial les positions secrètes des colonnes aléatoires. Notre travail montre que l’insertion de colonnes aléatoires dans le schéma de Sidelnikov n’apporte aucune amélioration en matière de sécurité. Le résultat suivant est une cryptanalyse améliorée de plusieurs variantes du cryptosystème GPT qui est un schéma de chiffrement en métrique rang utilisant les codes de Gabidulin. Nous montrons qu’en utilisant le Frobenius de façon appropriée sur le code public, il est possible d’en extraire un code de Gabidulin ayant la même dimension que le code de Gabidulin secret mais avec une longueur inférieure. Le code obtenu corrige ainsi moins d’erreurs que le code secret, mais sa capacité de correction d’erreurs dépasse le nombre d’erreurs ajoutées par l’expéditeur et par conséquent, un attaquant est capable de déchiffrer tout texte chiffré, à l’aide de ce code de Gabidulin dégradé. Nos résultats montrent qu’en fin de compte, toutes les techniques existantes visant à cacher la structure algébrique des codes de Gabidulin ont échoué. Enfin, nous avons étudié la sécurité du système de chiffrement de Faure-Loidreau [FL05] qui est également basé sur les codes de Gabidulin. Inspiré par les travaux précédents et, bien que la structure de ce schéma diffère considérablement du cadre classique du cryptosystème GPT, nous avons pu montrer que ce schéma est également vulnérable à une attaque polynomiale qui récupère la clé privée en appliquant l’attaque d’Overbeck sur un code public approprié. Comme exemple, nous arrivons en quelques secondes à casser les paramètres qui ont été proposés comme ayant un niveau de sécurité de 80 bits.

•Jul 5, 2017•0 citations

Achieving practical post-quantum threshold signatures from lattices

Guilhem Niot

Constructions pratiques de signature à seuil post-quantique à partir de réseaux euclidiens La cryptographie post-quantique a gagné en importance ces dernières années, motivée par la menace que les ordinateurs quantiques font peser sur les systèmes cryptographiques classiques . Bien que le NIST ait standardisé plusieurs schémas de chiffrement à clé publique et de signature numérique post-quantiques, il subsiste un fossé important dans notre compréhension des primitives cryptographiques avancées dans ce contexte. Parmi celles-ci, les signatures à seuil se distinguent comme une primitive particulièrement importante ; elles permettent à un groupe de participants de produire conjointement une signature valide, offrant ainsi une résilience face aux défaillances et au compromis partiel. Alors que les schémas de signature à seuil classiques ont atteint un stade de maturité et sont déployés, le développement de schémas de signature à seuil post-quantiques pratiques demeure un défi ouvert. Les constructions proposées manquent souvent de robustesse face aux participants malveillants, d'une génération de clé distribuée efficace, et de compatibilité avec les standards émergents. Cette thèse fournit une boîte à outils complète pour la conception et le déploiement de signatures à seuil pratiques basées sur les réseaux euclidiens. Premièrement, nous établissons les fondations de la robustesse, en introduisant des techniques de génération de clé distribuée et de signature qui garantissent la création d'une signature valide même en présence de participants malveillants. Ensuite, nous nous tournons vers un protocole radicalement plus efficace, permettant l'identification des abandons (identifiable aborts), une propriété qui permet de détecter les comportements malveillants plutôt que de les prévenir. Finalement, nous présentons de nouvelles idées pour répondre au défi de compatibilité avec les standards, en présentant la première version à seuil pratique de ML-DSA.

•May 19, 2026•0 citations

Lattice-based Signature Schemes in the Fiat-Shamir Paradigm

Julien Devevey

Signatures Fondées sur les Réseaux Euclidiens dans le paradigme de Fiat-Shamir Le paradigme de Fiat-Shamir permet la création systématique de schémas de signature à partir de protocoles d’identification. Ces derniers sont des protocoles interactifs en trois messages, entre un prouveur possédant une information secrète et un vérificateur avec une information publique corrélée. La transformation de Fiat-Shamir est simple et flexible, ce qui explique sa popularité, notamment lorsqu’elle est combinée avec des protocoles d’identification efficaces. Malheureusement, son utilisation dans le cadre de la cryptographie fondée sur les réseaux Euclidiens se révèle plus compliquée, et on lui préfère sa variante dite avec rejet. Cette thèse propose une étude de cette variante et de son utilisation en conjonction avec les réseaux Euclidiens. Nous commençons par recouvrer sa sécurité après avoir identifié des erreurs dans les précédentes preuves de sécurité proposées. On étudie aussi le temps d’exécution d’une signature ainsi que les propriétés de non-divulgation de connaissance du protocole de Lyubahsevsky, qui est le plus célèbre à reposer sur les réseaux Euclidiens.Nous l’étudions ensuite plus en détail. Ce protocole repose sur l’échantillonnage par rejet, qui peut être utilisée avec une très grande variété de paires “proches” de distributions : on échantillonne depuis l’une pour rejeter vers l’autre. Étant donné un nombre moyen d’itérations du protocole, nous minimisons la norme Euclidienne moyenne de la signature résultante, en choisissant soigneusement la paire de distributions source et cible. Cela diminue la taille de la signature, et la rend plus résistante aux attaques, ce qui permet de réduire les paramètres pour la même sécurité.Nous proposons ensuite HAETAE, une implémentation de la version bimodale avec des distributions uniformes sur des boules Euclidiennes de la signature de Lyubashevsky. Si nous la comparons rapidement avec les signatures réseaux sélectionnées par le NIST pour être standardisées, on s’aperçoit que nous avons des tailles de signatures près de 40% plus petite que Dilithium, même si nous signons jusqu’à 8 fois plus lentement. Cela reste pourtant plus grand en taille mais plus rapide en vitesse de signature que Falcon. De plus, notre implémentation est en temps constant etn’utilise que de l’arithmétique à virgule fixe.Enfin, nous proposons d’éviter l’échantillonnage par rejet en utilisant à la place des convolutions de Gaussiennes discrètes. Contrairement aux autres techniques connues, cette solution semble préserver les tailles de signatures et de clés de vérification du protocole pour des paramètres concrets, et elles sont même meilleures asymptotiquement. Bien que cette technique requiert d’échantillonner à partir d’une Gaussienne discrète elliptique, celle-ci est indépendante du message. Pour corriger cette distribution du premier message, un centre aléatoire est choisi et le résultat sera cette distribution du premier message, un centre aléatoire est choisi et le résultat sera indépendant du secret, ce qui est le problème critique qui avait mené à l’introduction du rejet en premier lieu.

•Sep 18, 2023•0 citations

Lattice-based cryptography in a quantum setting : security proofs and attacks

Pouria Fallahpour

Cryptographie fondée sur les réseaux euclidiens dans une contexte quantique : preuves de sécurité et attaques L'émergence des machines quantiques crée des défis et des opportunités pour la cryptographie. En particulier, les preuves de sécurité doivent être révisées en raison des capacités quantiques des adversaires. Cette thèse propose deux contributions à cet égard : un résultat positif et un résultat négatif. La transformation de Fiat-Shamir avec des rejets est l’un des principaux paradigmes pour concevoir des schémas de signature post-quantiques. Une partie de cette thèse consiste en une analyse détaillée de cette transformation dans le modèle de l’oracle aléatoire quantique. Tous les travaux précédents proposant une analyse de sécurité de cette transformation ont négligé des détails subtils, compromettant la correction des preuves. Par conséquent, notre preuve de sécurité est la première de son genre à être correcte. De plus, nous analysons le temps d'exécution et la correction des signatures obtenues à partir de cette transformation. Le problème learning with errors (LWE) a été largement utilisé pour construire des schémas cryptographiques sécurisés contre les adversaires quantiques. Une hypothèse liée à LWE stipule que la génération d'une instance LWE sans connaître son secret est difficile pour tous les algorithmes polynomiaux. On peut utiliser cette hypothèse pour prouver la sécurité de certains arguments de connaissance succints. Bien que cela semble être une tâche difficile pour les algorithmes classiques, nous présentons un algorithme quantique polynomial qui génère des instances LWE sans connaître le secret. Notre algorithme invalide ainsi les analyses de sécurité de ces arguments de connaissance succints dans le contexte quantique.

•Jul 5, 2024•1 citation
Techniques de correction d'erreurs et de réconciliation pour les protocoles de génération de clés basés sur des réseaux de points Au cours de la dernière décennie, le développement des ordinateurs quantiques a considérablement progressé, avec des investissements massifs de la part des grandes entreprises technologiques. On suppose qu'une fois que les ordinateurs quantiques à grande échelle seront construits, de nombreux systèmes cryptographiques à clé publique couramment utilisés ne seront plus sécurisés. Pour prévenir les attaques quantiques, les chercheurs travaillent déjà à la conception de protocoles cryptographiques post-quantiques, et le National Institute of Standards and Technology (NIST) des États-Unis organise un concours international pour sélectionner de nouvelles normes cryptographiques.Les constructions cryptographiques à base de réseaux euclidiens sont des candidats prometteurs car elles offrent de fortes garanties de sécurité théoriques et peuvent être mises en œuvre efficacement. L'une des primitives cryptographiques les plus largement utilisées basées sur des réseaux est le problème d'apprentissage avec erreurs, ou en anglais emph{Learning with errors} (LWE) introduit par Regev. Des travaux ultérieurs ont proposé des variantes structurées de LWE telles que Ring-LWE et Module-LWE, qui permettent une représentation plus compacte.Dans cette thèse, nous considérons deux candidats au défi du NIST basés sur les réseaux euclidiens pour les mécanismes d'encapsulation de clé (KEM) et proposons de nouvelles techniques de correction d'erreur et de réconciliation afin d'améliorer leur efficacité, leur sécurité, ainsi que leur fiabilité. Contrairement à certains travaux antérieurs sur la correction d'erreurs pour les protocoles basés sur les réseaux, nous proposons des bornes de probabilité d'erreur rigoureuses.Nous considérons d'abord FrodoKEM, un cryptosystème basé sur LWE, et introduisons un mécanisme de correction d'erreur pour améliorer ses performances. Notre encodeur mappe la clé secrète par bloc dans le réseau de Gosset à 8 dimensions E_8. Nous proposons trois ensembles de paramètres pour notre implémentation modifiée. La première implémentation surpasse FrodoKEM en termes de sécurité plausible ; la seconde permet de réduire la bande passante en divisant par deux le module, et la troisième permet d'augmenter la taille des clés.Le deuxième KEM que nous considérons est KyberKEM, qui est basé sur Module-LWE. Nous proposons une technique de réconciliation utilisant toujours le réseau euclidien E_8, et montrons que notre schéma peut surpasser KyberKEM en termes de sécurité avec une probabilité d'erreur comparable et des exigences de bande passante similaires. Nous étudions également l'utilisation de réseaux de dimension supérieure pour la réconciliation.
Sécurité étendue de la cryptographie fondée sur les réseaux Euclidiens La cryptographie fondée sur les réseaux euclidiens représente une alternative prometteuse à la cryptographie asymétrique utilisée actuellement, en raison de sa résistance présumée à un ordinateur quantique universel. Cette nouvelle famille de schémas asymétriques dispose de plusieurs atouts parmi lesquels de fortes garanties théoriques de sécurité, un large choix de primitives et, pour certains de ses représentants, des performances comparables aux standards actuels. Une campagne de standardisation post-quantique organisée par le NIST est en cours et plusieurs schémas utilisant des réseaux euclidiens font partie des favoris. La communauté scientifique a été encouragée à les analyser car ils pourraient à l'avenir être implantés dans tous nos systèmes. L'objectif de cette thèse est de contribuer à cet effort. Nous étudions la sécurité de ces nouveaux cryptosystèmes non seulement au sens de leur résistance à la cryptanalyse en ''boîte noire'' à l'aide de moyens de calcul classiques, mais aussi selon un spectre plus large de modèles de sécurité, comme les attaques quantiques, les attaques supposant des failles d'utilisation, ou encore les attaques par canaux auxiliaires. Ces différents types d’attaques ont déjà été largement formalisés et étudiés par le passé pour des schémas asymétriques et symétriques pré-quantiques. Dans ce mémoire, nous analysons leur application aux nouvelles structures induites par les réseaux euclidiens. Notre travail est divisé en deux parties complémentaires : les contremesures et les attaques. La première partie regroupe nos contributions à l'effort actuel de conception de nouvelles protections algorithmiques afin de répondre aux nombreuses publications récentes d’attaques par canaux auxiliaires. Les travaux réalisés en équipe auxquels nous avons pris part on abouti à l'introduction de nouveaux outils mathématiques pour construire des contre-mesures algorithmiques, appuyées sur des preuves formelles, qui permettent de prévenir systématiquement les attaques physiques et par analyse de temps d'exécution. Nous avons ainsi participé à la protection de plusieurs schémas de signature fondés sur les réseaux euclidiens comme GLP, BLISS, qTesla ou encore Falcon. Dans une seconde partie consacrée à la cryptanalyse, nous étudions dans un premier temps de nouvelles attaques qui tirent parti du fait que certains schémas de chiffrement à clé publique ou d'établissement de clé peuvent échouer avec une faible probabilité. Ces échecs sont effectivement faiblement corrélés au secret. Notre travail a permis d’exhiber des attaques dites « par échec de déchiffrement » dans des modèles de failles d'utilisation ou des modèles quantiques. Nous avons d'autre part introduit un outil algorithmique de cryptanalyse permettant d’estimer la sécurité du problème mathématique sous-jacent lorsqu’une information partielle sur le secret est donnée. Cet outil s’est avéré utile pour automatiser et améliorer plusieurs attaques connues comme des attaques par échec de déchiffrement, des attaques classiques ou encore des attaques par canaux auxiliaires.
La conception d’ordinateurs quantiques aura un impact majeur sur la cryptographie que nous utilisons tous les jours pour sécuriser nos communications, en particulier sur la cryptographie dite asymétrique. De plus, la multiplication des objets connectés dans notre quotidien et leurs limitations en terme de capacité de calcul et de mémoire disponible en font des cibles privilégiées. Cette thèse est à la croisée des chemins de ces deux problématiques, et est découpée en trois axes d’études indépendants. Le premier porte sur la conception d’une primitive cryptographique appelée Hash Proof System (HPS). En nous basant sur le langage des chiffrés de RQC, nous allons montrer comment construire une telle primitive, puis nous en présenterons deux applications possibles : un schéma de chiffrement à témoin d’une part, puis un protocole d’échange de clés authentifié uniquement basé sur la connaissance d’un mot de passe commun, permettant ainsi de se passer d’une infrastructure à clé publique. Le deuxième axe d’étude est l’introduction d’un nouveau problème cryptographique, le problème LRE (Learning Rank with Errors), adaptation du problème LPN à la métrique rang. Nous étudierons quelques-unes de ses propriétés puis en présenterons une première application possible, un protocole d’authentification symétrique nommé HBLRE, adaptation du protocole HB au problème LRE. Enfin, le troisième axe d’étude est l’adaptation et l’implémentation de plusieurs schémas cryptographiques soumis au NIST, à savoir RQC et ROLLO (qui regroupe les schémas LAKE, LOCKER et Ouroboros-R) sur microcontrôleurs. Nous montrerons les divers algorithmes qui ont été utilisés et en décrirons leur fonctionnement. Nous présenterons la libraire RBC, une librairie mise au point afin de faciliter l’utilisation et la conception de schémas basés sur la métrique rang qui intègrent les travaux d’implémentation réalisés durant cette thèse. Enfin, nous présenterons les performances de ces implémentations sur un microcontrôleur doté d’un processeur de type ARM Cortex-M4 et les mettrons en perspective avec les performances d’autres schémas cryptographiques post-quantiques soumis à l’appel à standardisation du NIST.
Sécurité des protocoles cryptographiques fondés sur la théorie des codes correcteurs d'erreurs Contrairement aux protocoles cryptographiques fondés sur la théorie des nombres, les systèmes de chiffrement basés sur les codes correcteurs d’erreurs semblent résister à l’émergence des ordinateurs quantiques. Un autre avantage de ces systèmes est que le chiffrement et le déchiffrement sont très rapides, environ cinq fois plus rapide pour le chiffrement, et 10 à 100 fois plus rapide pour le déchiffrement par rapport à RSA. De nos jours, l’intérêt de la communauté scientifique pour la cryptographie basée sur les codes est fortement motivé par la dernière annonce de la “National Institute of Standards and Technology" (NIST), qui a récemment initié le projet intitulé “Post-Quantum cryptography Project". Ce projet vise à définir de nouveaux standards pour les cryptosystèmes résistants aux attaques quantiques et la date limite pour la soumission des cryptosystèmes à clé publique est fixée pour novembre 2017. Une telle annonce motive certainement à proposer de nouveaux protocoles cryptographiques basés sur les codes, mais aussi à étudier profondément la sécurité des protocoles existants afin d’écarter toute surprise en matière de sécurité. Cette thèse suit cet ordre d’idée en étudiant la sécurité de plusieurs protocoles cryptographiques fondés sur la théorie des codes correcteurs d’erreurs. Nous avons commencé par l’étude de la sécurité d’une version modifiée du cryptosystème de Sidelnikov, proposée par Gueye et Mboup [GM13] et basée sur les codes de Reed-Muller. Cette modification consiste à insérer des colonnes aléatoires dans la matrice génératrice (ou de parité) secrète. La cryptanalyse repose sur le calcul de carrés du code public. La nature particulière des codes de Reed-Muller qui sont définis au moyen de polynômes multivariés binaires, permet de prédire les valeurs des dimensions des codes carrés calculés, puis permet de récupérer complètement en temps polynomial les positions secrètes des colonnes aléatoires. Notre travail montre que l’insertion de colonnes aléatoires dans le schéma de Sidelnikov n’apporte aucune amélioration en matière de sécurité. Le résultat suivant est une cryptanalyse améliorée de plusieurs variantes du cryptosystème GPT qui est un schéma de chiffrement en métrique rang utilisant les codes de Gabidulin. Nous montrons qu’en utilisant le Frobenius de façon appropriée sur le code public, il est possible d’en extraire un code de Gabidulin ayant la même dimension que le code de Gabidulin secret mais avec une longueur inférieure. Le code obtenu corrige ainsi moins d’erreurs que le code secret, mais sa capacité de correction d’erreurs dépasse le nombre d’erreurs ajoutées par l’expéditeur et par conséquent, un attaquant est capable de déchiffrer tout texte chiffré, à l’aide de ce code de Gabidulin dégradé. Nos résultats montrent qu’en fin de compte, toutes les techniques existantes visant à cacher la structure algébrique des codes de Gabidulin ont échoué. Enfin, nous avons étudié la sécurité du système de chiffrement de Faure-Loidreau [FL05] qui est également basé sur les codes de Gabidulin. Inspiré par les travaux précédents et, bien que la structure de ce schéma diffère considérablement du cadre classique du cryptosystème GPT, nous avons pu montrer que ce schéma est également vulnérable à une attaque polynomiale qui récupère la clé privée en appliquant l’attaque d’Overbeck sur un code public approprié. Comme exemple, nous arrivons en quelques secondes à casser les paramètres qui ont été proposés comme ayant un niveau de sécurité de 80 bits.
Constructions pratiques de signature à seuil post-quantique à partir de réseaux euclidiens La cryptographie post-quantique a gagné en importance ces dernières années, motivée par la menace que les ordinateurs quantiques font peser sur les systèmes cryptographiques classiques . Bien que le NIST ait standardisé plusieurs schémas de chiffrement à clé publique et de signature numérique post-quantiques, il subsiste un fossé important dans notre compréhension des primitives cryptographiques avancées dans ce contexte. Parmi celles-ci, les signatures à seuil se distinguent comme une primitive particulièrement importante ; elles permettent à un groupe de participants de produire conjointement une signature valide, offrant ainsi une résilience face aux défaillances et au compromis partiel. Alors que les schémas de signature à seuil classiques ont atteint un stade de maturité et sont déployés, le développement de schémas de signature à seuil post-quantiques pratiques demeure un défi ouvert. Les constructions proposées manquent souvent de robustesse face aux participants malveillants, d'une génération de clé distribuée efficace, et de compatibilité avec les standards émergents. Cette thèse fournit une boîte à outils complète pour la conception et le déploiement de signatures à seuil pratiques basées sur les réseaux euclidiens. Premièrement, nous établissons les fondations de la robustesse, en introduisant des techniques de génération de clé distribuée et de signature qui garantissent la création d'une signature valide même en présence de participants malveillants. Ensuite, nous nous tournons vers un protocole radicalement plus efficace, permettant l'identification des abandons (identifiable aborts), une propriété qui permet de détecter les comportements malveillants plutôt que de les prévenir. Finalement, nous présentons de nouvelles idées pour répondre au défi de compatibilité avec les standards, en présentant la première version à seuil pratique de ML-DSA.
Signatures Fondées sur les Réseaux Euclidiens dans le paradigme de Fiat-Shamir Le paradigme de Fiat-Shamir permet la création systématique de schémas de signature à partir de protocoles d’identification. Ces derniers sont des protocoles interactifs en trois messages, entre un prouveur possédant une information secrète et un vérificateur avec une information publique corrélée. La transformation de Fiat-Shamir est simple et flexible, ce qui explique sa popularité, notamment lorsqu’elle est combinée avec des protocoles d’identification efficaces. Malheureusement, son utilisation dans le cadre de la cryptographie fondée sur les réseaux Euclidiens se révèle plus compliquée, et on lui préfère sa variante dite avec rejet. Cette thèse propose une étude de cette variante et de son utilisation en conjonction avec les réseaux Euclidiens. Nous commençons par recouvrer sa sécurité après avoir identifié des erreurs dans les précédentes preuves de sécurité proposées. On étudie aussi le temps d’exécution d’une signature ainsi que les propriétés de non-divulgation de connaissance du protocole de Lyubahsevsky, qui est le plus célèbre à reposer sur les réseaux Euclidiens.Nous l’étudions ensuite plus en détail. Ce protocole repose sur l’échantillonnage par rejet, qui peut être utilisée avec une très grande variété de paires “proches” de distributions : on échantillonne depuis l’une pour rejeter vers l’autre. Étant donné un nombre moyen d’itérations du protocole, nous minimisons la norme Euclidienne moyenne de la signature résultante, en choisissant soigneusement la paire de distributions source et cible. Cela diminue la taille de la signature, et la rend plus résistante aux attaques, ce qui permet de réduire les paramètres pour la même sécurité.Nous proposons ensuite HAETAE, une implémentation de la version bimodale avec des distributions uniformes sur des boules Euclidiennes de la signature de Lyubashevsky. Si nous la comparons rapidement avec les signatures réseaux sélectionnées par le NIST pour être standardisées, on s’aperçoit que nous avons des tailles de signatures près de 40% plus petite que Dilithium, même si nous signons jusqu’à 8 fois plus lentement. Cela reste pourtant plus grand en taille mais plus rapide en vitesse de signature que Falcon. De plus, notre implémentation est en temps constant etn’utilise que de l’arithmétique à virgule fixe.Enfin, nous proposons d’éviter l’échantillonnage par rejet en utilisant à la place des convolutions de Gaussiennes discrètes. Contrairement aux autres techniques connues, cette solution semble préserver les tailles de signatures et de clés de vérification du protocole pour des paramètres concrets, et elles sont même meilleures asymptotiquement. Bien que cette technique requiert d’échantillonner à partir d’une Gaussienne discrète elliptique, celle-ci est indépendante du message. Pour corriger cette distribution du premier message, un centre aléatoire est choisi et le résultat sera cette distribution du premier message, un centre aléatoire est choisi et le résultat sera indépendant du secret, ce qui est le problème critique qui avait mené à l’introduction du rejet en premier lieu.
Cryptographie fondée sur les réseaux euclidiens dans une contexte quantique : preuves de sécurité et attaques L'émergence des machines quantiques crée des défis et des opportunités pour la cryptographie. En particulier, les preuves de sécurité doivent être révisées en raison des capacités quantiques des adversaires. Cette thèse propose deux contributions à cet égard : un résultat positif et un résultat négatif. La transformation de Fiat-Shamir avec des rejets est l’un des principaux paradigmes pour concevoir des schémas de signature post-quantiques. Une partie de cette thèse consiste en une analyse détaillée de cette transformation dans le modèle de l’oracle aléatoire quantique. Tous les travaux précédents proposant une analyse de sécurité de cette transformation ont négligé des détails subtils, compromettant la correction des preuves. Par conséquent, notre preuve de sécurité est la première de son genre à être correcte. De plus, nous analysons le temps d'exécution et la correction des signatures obtenues à partir de cette transformation. Le problème learning with errors (LWE) a été largement utilisé pour construire des schémas cryptographiques sécurisés contre les adversaires quantiques. Une hypothèse liée à LWE stipule que la génération d'une instance LWE sans connaître son secret est difficile pour tous les algorithmes polynomiaux. On peut utiliser cette hypothèse pour prouver la sécurité de certains arguments de connaissance succints. Bien que cela semble être une tâche difficile pour les algorithmes classiques, nous présentons un algorithme quantique polynomial qui génère des instances LWE sans connaître le secret. Notre algorithme invalide ainsi les analyses de sécurité de ces arguments de connaissance succints dans le contexte quantique.