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

Theoretical hardness of algebraically structured learning with errors

Katharina Boudgoust

Published Nov 16, 2021• 1 citation
Publisher

Abstract

Difficulté théorique des variantes algébriques du problème learning with errors Cette thèse de doctorat porte principale ment sur le problème d’apprentissage avec erreurs, appelé Learning With Errors (LWE). Il s’agit d’une composante essentielle de la cryptographie à base de réseaux, qui fait partie des candidats les plus prometteurs pour remplacer les protocoles cryptographiques actuels lorsque des ordinateurs quantiques à grande échelle seront disponibles. Dans cette thèse, nous étudions la difficulté théoriques des variantes algébriquement structurées de LWE qui sont utilisées dans des protocoles efficaces. D’abord, nous prouvons que le problème Module Learning With Errors (M-LWE) ne devient pas significativement plus facile à résoudre, même si le secret sous-jacent est remplacé par un vecteur binaire. Ensuite, nous présentons une réduction classique au problème M-LWE, ce qui renforce notre confiance dans sa valeur pour la cryptographie. De plus, nous définissons une nouvelle hypothèse de difficulté, le problème MP-LWR (Middle-Product Computational Learning With Rounding), qui hérite des avantages de deux variantes existantes de LWE. Enfin, nous étudions des problèmes liés à la matrice partielle de Vandermonde. Il s’agit d’une source récente d’hypothèses de difficulté pour la cryptographie à base de réseaux et son étude rigoureuse est primordiale pour gagner en fiabilité. Finalement, nous montrons que les nouvelles hypothèses de difficulté introduites auparavant servent à la construction de schémas de chiffrement à clé publique efficaces. D’une part, nous concevons un nouveau schéma de chiffrement, dont la sécurité est assurée par la difficulté du problème MP-CLWR. D’autre part, nous modifions un schéma de chiffrement existant pour lui fournir une preuve de sécurité basée sur deux problèmes de Vandermonde partiels explicitement énoncés.

DOI
10.70675/15a53424z3787z4996zb40ezcd9873cee07e

Related papers

Contributions to the hardness foundations of lattice-based cryptography

Weiqiang Wen

Contributions aux fondements de complexité de la cryptographie sur réseaux La cryptographie sur les réseaux est l’une des approches les plus compétitives pour protéger la confidentialité, dans les applications actuelles et l’ère post-quantique. Le problème central qui sert de fondement de complexité de la cryptographie sur réseaux est Learning with Errors (LWE). Il consiste à résoudre un système d’équations bruité, linéaire et surdéterminé. Ce problème est au moins aussi difficile que les problèmes standards portant sur les réseaux, tels que le décodage à distance bornée (BDD pour Bounded Distance Decoding) et le problème du vecteur le plus court unique (uSVP pour unique Shortest Vector Problem). Tous ces problèmes sont conjecturés difficiles à résoudre, même avec un ordinateur quantique de grande échelle. En particulier, le meilleur algorithme connu pour résoudre ces problèmes, BKZ, est très coûteux. Dans cette thèse, nous étudions les relations de difficulté entre BDD et uSVP, la difficulté quantique de LWE et les performances pratiques de l’algorithme BKZ. Tout d’abord, nous donnons une relation de difficulté plus étroite entre BDD et uSVP. Plus précisément, nous améliorons la réduction de BDD à uSVP d’un facteur √2, comparément à celle de Lyubashevsky et Micciancio. Ensuite, Nous apportons un nouvel élément à la conjecture que LWE est quantiquement difficile. Concrètement, nous considérons une version relâchée de la version quantique du problème du coset dièdral et montrons une équivalence computationnelle entre LWE et ce problème. Enfin, nous proposons un nouveau simulateur pour BKZ. Dans ce dernier travail, nous proposons le premier simulateur probabiliste pour BKZ, qui permet de prévoir le comportement pratique de BKZ très précisément.

•Nov 6, 2018•2 citations

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

Charbel Saliba

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.

•May 24, 2022•2 citations

Hardness of Structured Lattices Problems for Post-Quantum Cryptography

Joël Felderhoff

Difficultés de Problèmes de Réseaux Structurés pour la Cryptographie Post-Quantique La sécurité des protocoles cryptographiques repose sur la difficulté présumée de problèmes algorithmiques. Parmi ceux qui ont été identifiés jusque-là, les meilleurs problèmes pouvant servir de fondation à une cryptographie résistante aux ordinateurs quantiques sont issus des réseaux euclidiens. Les réseaux euclidiens sont une structure mathématique définie comme un ensemble de vecteurs de l’espace générés par les combinaisons entières d’un nombre fini de vecteurs réels linéairement indépendants (sa base). Un exemple typique de problème de sécurité relié est le Shortest Vector Problem (SVP). Étant donné une base d’un réseau euclidien en dimension n, trouver un vecteur court non nul. Pour des raisons d’efficacité, ces problèmes sont restreints à des réseaux issus de la théorie des nombres, dit structurés. Les hypothèses de sécurité relatives à ces réseaux particuliers étant différentes de celles des réseaux non structurés, il est nécessaire de les étudier spécifiquement, c’est l’objet de cette thèse. Nous avons étudié le cas des modules NTRU et uSVP en rang 2, prouvant que le problème SVP est équivalent sur ces deux familles de réseaux. Nous montrons également une réduction pire-cas vers cas-moyens pour les réseaux uSVP en rang 2. Ensuite nous avons démontré que résoudre SVP sur un idéal premier de petite norme n’était pas plus facile que de résoudre SVP sur n’importe quel idéal.

•Nov 26, 2024•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

Hidden Structures and Quantum Cryptanalysis

Xavier Bonnetain

Structures cachées et cryptanalyse quantique Nous étudions la sécurité de systèmes cryptographiques face à un adversaire muni d'un ordinateur quantique. En algorithmique quantique, nous avons étudié les problèmes de période et de décalage cachés, qui sont les seuls connus à ce jour ayant des applications en cryptographie et pour lesquels le meilleur algorithme quantique connu est plus que polynomialement plus rapide que le meilleur algorithme classique. Nous avons proposé des améliorations, de nouveaux compromis entre temps et mémoire classiques et quantiques, et étendu leur champ d'applications à des cas où seul un oracle classique est accessible. En cryptanalyse, en cryptographie symétrique, nous avons proposé des attaques de constructions symétriques utilisant des décalages cachés, et généralisé moult attaques exploitant des périodes cachées aux cas où l'accès à la construction est classique. Nous avons proposé une cryptanalyse quantique des différentes versions du chiffrement authentifié AEZ ainsi que des versions quantiques de multiples slide attacks, qui sont une famille classique d'attaques. Cette reformulation d'attaques dans le formalisme des périodes cachées nous ont permis de proposer de nouvelles attaques classiques sur différentes variantes du chiffrement MiMC. En cryptographie asymétrique, nous avons proposé une étude concrète et asymptotique de la sécurité quantique de schémas d'échange de clé à base d'isogénies. Enfin, nous avons étudié la sécurité dans des cadres où ces problèmes de structures cachées ne s'appliquent pas, avec la première analyse de sécurité quantique d'AES, le chiffrement symétrique le plus utilisé à l'heure actuelle.

•Nov 15, 2019•1 citation

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
Difficulté théorique des variantes algébriques du problème learning with errors Cette thèse de doctorat porte principale ment sur le problème d’apprentissage avec erreurs, appelé Learning With Errors (LWE). Il s’agit d’une composante essentielle de la cryptographie à base de réseaux, qui fait partie des candidats les plus prometteurs pour remplacer les protocoles cryptographiques actuels lorsque des ordinateurs quantiques à grande échelle seront disponibles. Dans cette thèse, nous étudions la difficulté théoriques des variantes algébriquement structurées de LWE qui sont utilisées dans des protocoles efficaces. D’abord, nous prouvons que le problème Module Learning With Errors (M-LWE) ne devient pas significativement plus facile à résoudre, même si le secret sous-jacent est remplacé par un vecteur binaire. Ensuite, nous présentons une réduction classique au problème M-LWE, ce qui renforce notre confiance dans sa valeur pour la cryptographie. De plus, nous définissons une nouvelle hypothèse de difficulté, le problème MP-LWR (Middle-Product Computational Learning With Rounding), qui hérite des avantages de deux variantes existantes de LWE. Enfin, nous étudions des problèmes liés à la matrice partielle de Vandermonde. Il s’agit d’une source récente d’hypothèses de difficulté pour la cryptographie à base de réseaux et son étude rigoureuse est primordiale pour gagner en fiabilité. Finalement, nous montrons que les nouvelles hypothèses de difficulté introduites auparavant servent à la construction de schémas de chiffrement à clé publique efficaces. D’une part, nous concevons un nouveau schéma de chiffrement, dont la sécurité est assurée par la difficulté du problème MP-CLWR. D’autre part, nous modifions un schéma de chiffrement existant pour lui fournir une preuve de sécurité basée sur deux problèmes de Vandermonde partiels explicitement énoncés.
Contributions aux fondements de complexité de la cryptographie sur réseaux La cryptographie sur les réseaux est l’une des approches les plus compétitives pour protéger la confidentialité, dans les applications actuelles et l’ère post-quantique. Le problème central qui sert de fondement de complexité de la cryptographie sur réseaux est Learning with Errors (LWE). Il consiste à résoudre un système d’équations bruité, linéaire et surdéterminé. Ce problème est au moins aussi difficile que les problèmes standards portant sur les réseaux, tels que le décodage à distance bornée (BDD pour Bounded Distance Decoding) et le problème du vecteur le plus court unique (uSVP pour unique Shortest Vector Problem). Tous ces problèmes sont conjecturés difficiles à résoudre, même avec un ordinateur quantique de grande échelle. En particulier, le meilleur algorithme connu pour résoudre ces problèmes, BKZ, est très coûteux. Dans cette thèse, nous étudions les relations de difficulté entre BDD et uSVP, la difficulté quantique de LWE et les performances pratiques de l’algorithme BKZ. Tout d’abord, nous donnons une relation de difficulté plus étroite entre BDD et uSVP. Plus précisément, nous améliorons la réduction de BDD à uSVP d’un facteur √2, comparément à celle de Lyubashevsky et Micciancio. Ensuite, Nous apportons un nouvel élément à la conjecture que LWE est quantiquement difficile. Concrètement, nous considérons une version relâchée de la version quantique du problème du coset dièdral et montrons une équivalence computationnelle entre LWE et ce problème. Enfin, nous proposons un nouveau simulateur pour BKZ. Dans ce dernier travail, nous proposons le premier simulateur probabiliste pour BKZ, qui permet de prévoir le comportement pratique de BKZ très précisément.
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.
Difficultés de Problèmes de Réseaux Structurés pour la Cryptographie Post-Quantique La sécurité des protocoles cryptographiques repose sur la difficulté présumée de problèmes algorithmiques. Parmi ceux qui ont été identifiés jusque-là, les meilleurs problèmes pouvant servir de fondation à une cryptographie résistante aux ordinateurs quantiques sont issus des réseaux euclidiens. Les réseaux euclidiens sont une structure mathématique définie comme un ensemble de vecteurs de l’espace générés par les combinaisons entières d’un nombre fini de vecteurs réels linéairement indépendants (sa base). Un exemple typique de problème de sécurité relié est le Shortest Vector Problem (SVP). Étant donné une base d’un réseau euclidien en dimension n, trouver un vecteur court non nul. Pour des raisons d’efficacité, ces problèmes sont restreints à des réseaux issus de la théorie des nombres, dit structurés. Les hypothèses de sécurité relatives à ces réseaux particuliers étant différentes de celles des réseaux non structurés, il est nécessaire de les étudier spécifiquement, c’est l’objet de cette thèse. Nous avons étudié le cas des modules NTRU et uSVP en rang 2, prouvant que le problème SVP est équivalent sur ces deux familles de réseaux. Nous montrons également une réduction pire-cas vers cas-moyens pour les réseaux uSVP en rang 2. Ensuite nous avons démontré que résoudre SVP sur un idéal premier de petite norme n’était pas plus facile que de résoudre SVP sur n’importe quel idéal.
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.
Structures cachées et cryptanalyse quantique Nous étudions la sécurité de systèmes cryptographiques face à un adversaire muni d'un ordinateur quantique. En algorithmique quantique, nous avons étudié les problèmes de période et de décalage cachés, qui sont les seuls connus à ce jour ayant des applications en cryptographie et pour lesquels le meilleur algorithme quantique connu est plus que polynomialement plus rapide que le meilleur algorithme classique. Nous avons proposé des améliorations, de nouveaux compromis entre temps et mémoire classiques et quantiques, et étendu leur champ d'applications à des cas où seul un oracle classique est accessible. En cryptanalyse, en cryptographie symétrique, nous avons proposé des attaques de constructions symétriques utilisant des décalages cachés, et généralisé moult attaques exploitant des périodes cachées aux cas où l'accès à la construction est classique. Nous avons proposé une cryptanalyse quantique des différentes versions du chiffrement authentifié AEZ ainsi que des versions quantiques de multiples slide attacks, qui sont une famille classique d'attaques. Cette reformulation d'attaques dans le formalisme des périodes cachées nous ont permis de proposer de nouvelles attaques classiques sur différentes variantes du chiffrement MiMC. En cryptographie asymétrique, nous avons proposé une étude concrète et asymptotique de la sécurité quantique de schémas d'échange de clé à base d'isogénies. Enfin, nous avons étudié la sécurité dans des cadres où ces problèmes de structures cachées ne s'appliquent pas, avec la première analyse de sécurité quantique d'AES, le chiffrement symétrique le plus utilisé à l'heure actuelle.
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.