Signatures reposant sur les réseaux euclidiens : de la construction à l'implémentation La cryptographie reposant sur les réseaux euclidiens est l'un des axes principaux pour construire des primitives à clef publique post-quantiques. Dans cette thèse, nous discutons de la construction de signatures numériques et de leur implémentation. Nous commençons par décrire une transformation de type Fiat-Shamir qui à partir d'un schéma d'identification qui utilise de l'échantillonnage par rejets permet de construire une signature prouvée dans le modèle de l'oracle aléatoire. Ensuite, nous décrivons un schéma de chiffrement basé sur l'identité et nous prouvons sa sécurité dans le modèle standard. Un schéma de chiffrement basé sur l'identité correspond à un chiffrement à clef publique classique pour lequel la clef publique d'un utilisateur est simplement son identité, comme par exemple son adresse mail ou son numéro de sécurité sociale. Un utilisateur contacte ensuite un tiers de confiance pour récupérer une clef secrète associée à son identité. Dans notre construction, cette clef secrète consiste essentiellement en une signature de l'identité de l'utilisateur. Nous décrivons également cette construction de signature numérique associée à notre chiffrement basé sur l'identité. Pour finir, nous présentons des résultats d'implémentation de ces deux schémas et comment nous avons choisi des paramètres concrets.
Signatures reposant sur les réseaux euclidiens : de la construction à l'implémentation La cryptographie reposant sur les réseaux euclidiens est l'un des axes principaux pour construire des primitives à clef publique post-quantiques. Dans cette thèse, nous discutons de la construction de signatures numériques et de leur implémentation. Nous commençons par décrire une transformation de type Fiat-Shamir qui à partir d'un schéma d'identification qui utilise de l'échantillonnage par rejets permet de construire une signature prouvée dans le modèle de l'oracle aléatoire. Ensuite, nous décrivons un schéma de chiffrement basé sur l'identité et nous prouvons sa sécurité dans le modèle standard. Un schéma de chiffrement basé sur l'identité correspond à un chiffrement à clef publique classique pour lequel la clef publique d'un utilisateur est simplement son identité, comme par exemple son adresse mail ou son numéro de sécurité sociale. Un utilisateur contacte ensuite un tiers de confiance pour récupérer une clef secrète associée à son identité. Dans notre construction, cette clef secrète consiste essentiellement en une signature de l'identité de l'utilisateur. Nous décrivons également cette construction de signature numérique associée à notre chiffrement basé sur l'identité. Pour finir, nous présentons des résultats d'implémentation de ces deux schémas et comment nous avons choisi des paramètres concrets.
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.
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.
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.
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.
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.