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.
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.
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.
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.
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é é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.
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.
Les récentes avancées des technologies quantiques menacent les mécanismes cryptographiques utilisés aujourd’hui dans la plupart des systèmes de sécurité. Il est donc nécessaire de trouver des alternatives à ces mécanismes qui ne soient pas sujettes aux attaques d’un ordinateur quantique. La cryptographie reposant sur les réseaux euclidiens est un candidat intéressant, versatile, résistant aux attaques quantiques, et considéré comme l’une des options les plus prometteuses. Cet article décrit ses fondements, ainsi que les constructions de signature numérique et de chiffrement qui sont amenées à remplacer les standards cryptographiques actuels.