Sécurité concrète de certaines constructions cryptographiques basées sur les réseaux Euclidiens Cette thèse est préparée entre 2021 et 2024, période qui marque le début de la transition postquantique de la cryptographie à clé publique. De manière générale, la transition post-quantique se réfère à la migration de la cryptographie à clé publique classique vers une cryptographie résistante aux attaques quantiques. Cette thèse aborde certains sujets spécifiques dans la cryptographie fondées sur les réseaux Euclidiens, en particulier, la sécurité concrète de certaines constructions cryptographiques basées sur les réseaux: la signature Mitaka and le KEM Kyber. Dans l’ordre chronologique, nous avons examiné la possibilité d’améliorer la qualité de sécurité des trappes NTRU pour l’échantillonneur hybride (ce dernier étant l’échantillonneur Gaussien discret utilisé dans la signature Mitaka – une variante élégamment simplifiée du futur standard Falcon). Cela a conduit au nouveau algorithme de génération de trappes Antrag qui fournit à l’échantillonneur hybride de meilleures trappes, améliorant ainsi la sécurité des signatures produites par cet échantillonneur. La deuxième contribution concerne l’investigation de la possibilité de casser Kyber à partir d’une trace unique de puissance d’une fonction non protégée pendant le processus de génération de clés. Cela se conclut par une réponse positive pour le cas de Kyber-512.
Sécurité concrète de certaines constructions cryptographiques basées sur les réseaux Euclidiens Cette thèse est préparée entre 2021 et 2024, période qui marque le début de la transition postquantique de la cryptographie à clé publique. De manière générale, la transition post-quantique se réfère à la migration de la cryptographie à clé publique classique vers une cryptographie résistante aux attaques quantiques. Cette thèse aborde certains sujets spécifiques dans la cryptographie fondées sur les réseaux Euclidiens, en particulier, la sécurité concrète de certaines constructions cryptographiques basées sur les réseaux: la signature Mitaka and le KEM Kyber. Dans l’ordre chronologique, nous avons examiné la possibilité d’améliorer la qualité de sécurité des trappes NTRU pour l’échantillonneur hybride (ce dernier étant l’échantillonneur Gaussien discret utilisé dans la signature Mitaka – une variante élégamment simplifiée du futur standard Falcon). Cela a conduit au nouveau algorithme de génération de trappes Antrag qui fournit à l’échantillonneur hybride de meilleures trappes, améliorant ainsi la sécurité des signatures produites par cet échantillonneur. La deuxième contribution concerne l’investigation de la possibilité de casser Kyber à partir d’une trace unique de puissance d’une fonction non protégée pendant le processus de génération de clés. Cela se conclut par une réponse positive pour le cas de Kyber-512.
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.
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.
Trappes en cryptographie basée sur les réseaux euclidiens : applications et implémentation La cryptographie basée sur les réseaux euclidiens s’est imposée comme un candidat prometteur parmi les principales familles de cryptographie post-quantique, offrant un large éventail de caractéristiques attrayantes. Mes travaux s’inscrivent dans cet effort de recherche, en contribuant au développement de la cryptographie basée sur les réseaux euclidiens. Je commence par présenter le travail sur le développement et l’implémentation de techniques d’échantillonnage de préimages gaussiennes sur les réseaux modules, dont la structure algébrique conduit à une représentation plus compacte des paramètres et à une amélioration du temps d’exécution des algorithmes comparé aux réseaux euclidiens non structurés. Deux signatures et un système de chiffrement basé sur l’identité, ainsi que leur implémentation, sont donnés comme applications. Ensuite, je présente des améliorations par rapport au schéma de chiffrement basé sur l’identité précédent en utilisant des trappes approchées au lieu de trappes exactes, et je propose des implémentations concrètes de ce schéma et des algorithmes de génération de trappes approchées et d’échantillonnage gaussien. Enfin, je présente un travail sur les réseaux NTRU. J’ai notamment étudié une variante de NTRU, appelée iNTRU, qui permet de construire des schémas cryptographiques utilisant des trappes gadget.
Cryptographie post-quantique pour la protection de la vie privée Ces dernières années la cryptographie a été chamboulée par l'arrivée des ordinateurs quantiques. En effet ceux-ci possèdent un très fort avantage pour casser les schémas cryptographique utilisés actuellement dans la quasi-totalité des communications sécurisées. Nous proposons dans cette thèse plusieurs constructions cryptographiques basées sur des outils mathématiques résistants à ces ordinateurs quantique, que sont les réseaux euclidiens. Tout d'abord nous construisons une signature de groupe, permettant à chaque membre composant un groupe donné de signer au nom du groupe tout en conservant son anonymat. Nous rajoutons une propriété supplémentaire qui est la "forward secrecy" qui sépare le temps en périodes durant lesquelles les clés secrètes des utilisateurs sont mises à jour. Nous proposons également un schéma de signature aveugle qui permet à un utilisateur de générer une signature sur un message de son choix de manière interactive avec un signeur qui possède la clé de signature. Nous améliorons l'état-de-l'art en proposant un schéma sans abandon et avec une sécurité plus efficace. Enfin, comme cas d'usage de la signature aveugle nous construisons un schéma de vote électronique à partir de cette primitive.
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.
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.