La cryptographie est utilisée pour protéger la vie privée de tous quotidiennement lors de la navigation sur Internet. On observe de multiples changements en cours ces dernières années, dûs en partie à la possible arrivée prochainement d'ordinateurs quantiques capables de mettre en danger certains de nos chiffrements actuels.On remarque quatre principaux enjeux associés à ces changements :1) L'adaptation des primitives, qui doivent être remplacées par de nouvelles, post-quantiques.2) L'adaptation des protocoles, qui parfois reposent aussi sur des propriétés vulnérables aux ordinateurs quantiques.3) L'évolution des habitudes des utilisateurs, pour lesquels sont conçus ces protocoles, impliquant notamment une consommation numérique plus importante (flux vidéos en direct) et une demande de protection accrue de la vie privée.4) Les capacités des ordinateurs, qui évoluent en permanence (par exemple grâce à des accélérateurs matériels) souvent pour d'autres applications (IA, jeux), peuvent offrir des surfaces d'attaques, notamment par canaux auxiliaires.La présente thèse soutient que ces enjeux sont interdépendants et qu'une vision groupée de ces problèmes aide à garantir l'adaptation de la cryptographie à l'ère post-quantique.Ce propos est appuyé par trois pistes de recherche :1) Proposer un protocole anonymisant de live-streaming massif (contraintes utilisateurs) qui soit aussi post-quantique (contraintes sur les primitives).2) Etudier les protocoles de chiffrements commutatifs, en particulier d'interception réglementée, ainsi que la manière de les rendre post-quantiques sans créer de faiblesses ou qu'ils soient limités à des sur-chiffrements.3) Comprendre la manière dont les architectures dotées de calcul en mémoire vont affecter les performances des primitives post-quantiques, et comment un co-design est possible pour aussi réduire les fuites par canaux auxiliaires.
La cryptographie est utilisée pour protéger la vie privée de tous quotidiennement lors de la navigation sur Internet. On observe de multiples changements en cours ces dernières années, dûs en partie à la possible arrivée prochainement d'ordinateurs quantiques capables de mettre en danger certains de nos chiffrements actuels.On remarque quatre principaux enjeux associés à ces changements :1) L'adaptation des primitives, qui doivent être remplacées par de nouvelles, post-quantiques.2) L'adaptation des protocoles, qui parfois reposent aussi sur des propriétés vulnérables aux ordinateurs quantiques.3) L'évolution des habitudes des utilisateurs, pour lesquels sont conçus ces protocoles, impliquant notamment une consommation numérique plus importante (flux vidéos en direct) et une demande de protection accrue de la vie privée.4) Les capacités des ordinateurs, qui évoluent en permanence (par exemple grâce à des accélérateurs matériels) souvent pour d'autres applications (IA, jeux), peuvent offrir des surfaces d'attaques, notamment par canaux auxiliaires.La présente thèse soutient que ces enjeux sont interdépendants et qu'une vision groupée de ces problèmes aide à garantir l'adaptation de la cryptographie à l'ère post-quantique.Ce propos est appuyé par trois pistes de recherche :1) Proposer un protocole anonymisant de live-streaming massif (contraintes utilisateurs) qui soit aussi post-quantique (contraintes sur les primitives).2) Etudier les protocoles de chiffrements commutatifs, en particulier d'interception réglementée, ainsi que la manière de les rendre post-quantiques sans créer de faiblesses ou qu'ils soient limités à des sur-chiffrements.3) Comprendre la manière dont les architectures dotées de calcul en mémoire vont affecter les performances des primitives post-quantiques, et comment un co-design est possible pour aussi réduire les fuites par canaux auxiliaires.
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.
La cryptographie moderne a un ennemi de taille à l'horizon : la montée inévitable des ordinateurs quantiques. Cependant, cette même puissance de calcul permettrait également de trouver des solutions sur des tâches cryptographiques qui sont tout simplement impossibles à réaliser avec la technologie actuelle. Dans cette thèse, nous mettons les pieds dans un univers où le quantique est omniprésent en y présentant notamment deux principales contributions. Nous mettons en avant à la fois des nouveaux modèles et de nouvelles analyses de sécurité pour deux primitives cryptographiques : les chiffrements et les preuves à divulgation nulle de connaissance non interactives. Les définitions usuelles de sécurité de ces primitives requièrent intrinsèquement la capacité d'enregistrer et de comparer des chaînes classiques. Cependant, les tâches d'enregistrement et de comparaison sont extrêmement difficiles dans le monde quantique en raison du principe d'incertitude. Nous proposons deux alternatives afin de surmonter cette barrière. De plus, nos notions de sécurité sont les premières à prendre pleinement en compte les attaques quantiques dans lesquelles les attaquants peuvent interagir avec les utilisateurs finaux sur des canaux quantiques. D'autre part, nous montrons que la disponibilité des ordinateurs quantiques se révèle être également à l'avantage des cryptographes, même lorsque les utilisateurs finaux n'utilisent que des communications classiques. En particulier, nous présentons un protocole interactif entre une Alice classique et un Bob quantique. Ce dispositif permet à Alice d'envoyer un état quantique caché non clonable à Bob par des canaux classiques. En outre, cet état quantique non clonable établit une forte propriété dite de monogamie de l'intrication, qui décrit les limites de la force des corrélations multipartites quantiques. Enfin, nous appliquons notre protocole et nous donnons les premiers schémas semi-quantiques de protection contre la copie.
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.
Afin de parer à la menace que ferait peser l’essor des calculateurs quantiques sur nombre de systèmes cryptographiques (et non des moindres) en usage actuellement, d’importants efforts sont faits pour que voient le jour et se développent des systèmes dits « post-quantiques » de chiffrement, d’authentification et d’identification, analogues aux systèmes classiques mais qui résisteraient à des attaques rendues possibles par de tels calculateurs, y compris si ces derniers venaient à devenir particulièrement puissants.C’est avec l’intention de m’associer à ces efforts que je me suis penché sur les systèmes d’accréditations anonymes. Ces systèmes permettent à un fournisseur de services de vérifier les droits d’un utilisateur à bénéficier de ces services en vertu de la garantie – donnée antérieurement par une autorité de confiance – du fait que cet utilisateur possède bien les attributs requis, cela en préservant le secret des autres attributs, tels que l’identité de l’utilisateur, dont l’autorité aurait eu à prendre connaissance, et cela en permettant la levée de l’anonymat de l’utilisateur par un autre agent, disposant d’une clef secrète spéciale. Je me suis employé à étudier les systèmes d’accréditations anonymes décrits dans la littérature et j’ai participé à l’élaboration d’un schéma théorique d’accréditations anonymes post-quantiques optimisé, fondé sur les problèmes difficiles relatifs aux réseaux euclidiens, pour ensuite contribuer au développement du premier programme informatique à sources ouvertes d’accréditations anonymes post-quantiques qui soit une démonstration directe de la compatibilité d’un tel schéma avec des cas d’usages concrets.Le protocole Signal, sur lequel se fondent de nombreux systèmes de messagerie instantanée actuels, est lui aussi appelé à connaître une adaptation post-quantique. Dans un article, nous en proposons une vérification formelle réalisée avec le prouveur Tamarin en mettant l’accent sur ses deux principales composantes, le protocole d’échange de clefs X3DH et le protocole du « double cliquet » de mise à jour des clefs de session.
La mécanique quantique offre un avantage indéniable sur la mécanique classique pour la réalisation de diverses tâches cryptographiques. Cependant, elle ouvre également la voie à des attaques complexes qui compliquent l’analyse des protocoles cryptographiques. Ainsi, les cryptographes sont constamment à la recherche de nouveaux outils qui permettent de simplifier les preuves. Dans cette thèse, nous introduisons de nouvelles techniques qui permettent de simplifier l’analyse de protocoles cryptographiques quantiques et nous en démontrons l’utilité par quelques exemples d’applications. Nos techniques permettent de montrer que, sous certaines conditions, la sûreté d’un protocole cryptographique contre une attaque qui respecte plus ou moins le protocole (passive) est une condition suffisante pour montrer la sûreté contre une attaque qui peut dévier du protocole (active). Nous montrons d’abord que la sécurité d’un protocole quantique contre les adversaires sans mémoire quantique implique sa sécurité contre les adversaires disposant d’une certaine quantité de mémoire. Cette technique trouve son utilité dans le fait que les attaques ayant accès à une mémoire quantique sont généralement bien plus difficiles à analyser que celles sans mémoire. Nous introduisons ensuite la certification d’états mixtes : étant donné un registre quantique composé de n qubits, nous montrons qu’il est possible de s’assurer que ce registre est près de n copies d’une même matrice de densité φ. Cet outil offre un cadre général pour analyser une situation commune en cryptographie quantique où une source non fiable fournit un état quantique et on veut s’assurer que l’état fourni par cette source est le bon. Ces résultats ont permis de contribuer aux connaissances en cryptographie quantique par les avancées suivantes. D’abord, nous résolvons deux problèmes ouverts, l’un concernant la puissance cryptographique de la primitive cut-and-choose à un bit, et l’autre concernant la sûreté du protocole de mise en gage BCJL. Dans les deux cas, notre relation entre les adversaires quantiques et les adversaires sans mémoire joue un rôle central. Par la suite, nous introduisons une nouvelle tâche cryptographique où deux participants veulent générer une chaine de bits commune quasi uniformément distribuée, et ce même si l’un des participants est malhonnête. Nous présentons un protocole quantique qui surpasse tout protocole classique pour cette tâche.
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.