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.
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.
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.
Conception d'algorithmes de signatures avancées post-quantiques La transition vers la cryptographie post-quantique est une tâche considérable ayant suscité un nombre important de travaux ces dernières années. En parallèle, la cryptographie pour la protection de la vie privée, visant à pallier aux limitations inhérentes des mécanismes cryptographiques basiques dans ce domaine, a connu un véritable essor. Malgré le succès de chacune de ces branches prises individuellement, combiner les deux aspects de manière efficace s'avère extrêmement difficile. Le but de cette thèse de doctorat consiste alors à proposer de nouvelles constructions visant à garantir une protection efficace et post-quantique de la vie privée, et plus généralement des mécanismes d'authentification avancés. Dans ce but, nous nous consacrons tout d'abord à l'étude de l'une des hypothèses mathématiques fondamentales utilisées en cryptographie sur les réseaux Euclidiens: Module Learning With Errors. Nous prouvons que le problème ne devient pas significativement plus facile même en choisissant des distributions de secret et d'erreur plus courtes. Ensuite, nous proposons des optimisations des échantillonneurs d'antécédents utilisés par de nombreuses signatures avancées. Loin d'être limitées à ce cas d'usage, nous montrons que ces optimisations mènent à la conception de signatures standards efficaces. Enfin, à partir de ces contributions, nous concevons des algorithmes de signatures avec protocoles efficaces, un outil polyvalent utile à la construction d'applications avancées. Nous en montrons les capacités en proposant le premier mécanisme d'accréditation anonyme post-quantique, que nous implémentons afin de mettre en exergue son efficacité aussi bien théorique que pratique.
Avec la possibilité de l’existence d’un ordinateur quantique, les primitives cryptographiques basées sur la théorie des nombres risquent de devenir caduques. Il devient donc important de concevoir des schémas résistants à ce nouveau type de menaces. Les réseaux euclidiens et les codes correcteurs d’erreurs sont deux outils mathématiques permettant de construire des problèmes d’algèbre linéaire, pour lesquels il n’existe aujourd’hui pas d’algorithme quantique permettant d’accélérer significativement leur résolution. Dans cette thèse, nous proposons quatre primitives cryptographiques de ce type : deux schémas de signatures (dont une signature traçable) basés sur les réseaux, un protocole de délégation de signature utilisant du chiffrement complètement homomorphe, et une nouvelle approche permettant de construire des cryptosystèmes très efficaces en pratique basés sur les codes. Ces contributions sont accompagnées de paramètres concrets permettant de jauger les coûts calculatoires des primitives cryptographique dans un monde post-quantique.
Concevoir des systèmes cryptographiques post-quantiques efficaces, pratiques et sûrs Cette thèse explore des stratégies d’optimisation pour la cryptographie post-quantique. Par systèmes cryptographiques post-quantiques, nous entendons des schémas classiques (non quantiques) dont la sécurité est destinée à résister à des attaques provenant d’ordinateurs quantiques.Premièrement, nous étudions des systèmes cryptographiques dans le cadre GPV avec des réseaux ou des codes non structurés qui souffrent généralement de clés de grande taille. Nous traitons ce problème avec une méthode permettant de remplacer les grandes clés publiques dans les signatures de type GPV par de plus petites clés de vérification privées. Cela réduit significativement le stockage et le temps d’exécution du vérificateur tout en préservant la sécurité. Appliquée aux schémas à signatures courtes Wave et Squirrels, notre méthode compresse les clés de Squirrels-I de 665 kB à 20{,}7 kB et les clés de Wave822 de 3{,}5 MB à 207{,}97 kB. Cela est particulièrement utile lorsque de nombreuses vérifications sont effectuées avec la même clé (par exemple, les mises à jour logicielles, les certificats racine). Deuxièmement, nous présentons quelques accélérations pour le calcul d’isogénies. L’une réorganise l’évaluation des formules de Vélu pour accélérer l’évaluation des ell-isogénies pour de nombreux nombres premiers ell, ce qui constitue un calcul de base dans de nombreux systèmes cryptographiques à base d’isogénies. Une autre vise les isogénies rationnelles dont les noyaux sont engendrés par des éléments irrationnels. Nos techniques accélèrent les schémas à base d’isogénies tels que CSIDH, CSI-FiSh et CRS.Enfin, nous proposons des algorithmes classiques de recherche parallèle de collisions pour les logarithmes discrets restreints multidimensionnels. La cryptographie basée sur les actions de groupes, et plus spécifiquement les emph{Restricted Effective Group Actions} (REGA), est profondément liée à ces problèmes. Une méthode existante pour résoudre les logarithmes discrets restreints multidimensionnels est l’algorithme de Gaudry--Schost. Cependant, il ne s’applique qu’à de faibles dimensions, ce qui ne correspond pas aux actions de groupes à base d’isogénies actuelles. Nous étendons l’algorithme de Gaudry--Schost à des dimensions plus élevées, offrant une vision plus approfondie des menaces classiques pour les échanges de clés REGA.
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.