Les avancées technologiques en matière d'informatique quantique rendent la possibilité d'avoir un ordinateur quantique de plus en plus forte. Il est donc important d'étudier la cryptographie en prenant cette menace en compte, domaine appelé cryptographie post-quantique. De nombreux schéma sont proposés dans ce contexte mais la sécurité quantique des hypothèses calculatoires sous jacentes n'est que peu étudiée. Dans cette thèse j'étudie deux problèmes importants dans ce contexte: le problème du sac-à-dos et le problème de décodage de syndrome. Pour ces deux problèmes, je montre des améliorations quantiques en utilisant des marches quantiques et je présente l'implication de ces résultats pour la cryptographie post-quantique.
Les avancées technologiques en matière d'informatique quantique rendent la possibilité d'avoir un ordinateur quantique de plus en plus forte. Il est donc important d'étudier la cryptographie en prenant cette menace en compte, domaine appelé cryptographie post-quantique. De nombreux schéma sont proposés dans ce contexte mais la sécurité quantique des hypothèses calculatoires sous jacentes n'est que peu étudiée. Dans cette thèse j'étudie deux problèmes importants dans ce contexte: le problème du sac-à-dos et le problème de décodage de syndrome. Pour ces deux problèmes, je montre des améliorations quantiques en utilisant des marches quantiques et je présente l'implication de ces résultats pour la cryptographie 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.
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.
Les cryptosystemes bases sur les codes correcteurs sont de bons candidats
pour la cryptographie post-quantique. Afin de bien choisir leurs parametres de
securite, il faut tenir compte des attaques quantiques les plus puissantes.
Bernstein avait montre en 2009 qu'il est possible d'utiliser l'algorithme de
recherche non-structuree de Grover avec l'algorithme de Prange pour obtenir un
algorithme ISD quantique dont la complexite est la racine carree de l'algorithme de
Prange classique. Nous avons reussi a faire mieux que ce resultat en considerant les
algorithmes classiques plus sophistiques et en se servant de techniques basees sur la
marche aleatoire quantique (Quantum Walk) et inspirees par les meilleurs algorithmes
quantiques de resolution du probleme de la somme des sous-ensembles (subset sum).
La recherche en informatique quantique a pris de l’ampleur dans les deux dernières décennies, notamment grâce aux financements massifs des gouvernements et de l’industrie dans les technologies quantiques. L’ordinateur quantique promet de résoudre des problèmes qui jusqu’à présent restaient insurmontables à cause du temps déraisonnable qu’il faudrait pour les résoudre sur les ordinateurs classiques les plus puissants. L’idée de l’ordinateur quantique consiste à utiliser des propriétés quantiques de la matière, telles que l’intrication et la superposition quantique des états, pour effectuer des calculs d’une nouvelle manière. L’informatique quantique requiert un nouveau type d’ordinateur où les bits d’information classique, généralement représentés par la présence ou non de courant à l’entrée d’un transistor, sont remplacés par des bits quantiques aussi appelés qubits, et qui sont représentés par l’état d’un système quantique. De plus, il est nécessaire de développer de nouveaux algorithmes capables d’être implémentés sur un ordinateur quantique et capables de tirer parti de l’avantage quantique. Cette thèse porte sur ces deux composantes complémentaires : la construction de portes logiques, un bloc fondamental de tout ordinateur, et la création de meilleurs algorithmes pour résoudre des problèmes pertinents sur ces machines. Parmi les plateformes les plus avancées pour l’ordinateur quantique, on trouve les circuits supraconducteurs, qui sont la plateforme sur laquelle ont misé Google, IBM, Alice&Bob, Nord Quantique et bien d’autres compagnies. Malgré les avancées des dernières décennies, de nombreux défis restent à être relevés pour que les machines existantes soient en mesure de résoudre des problèmes pertinents et surpassent les ordinateurs classiques. L’un des défis auquel cette thèse s’attaque est la réalisation de portes logiques à deux qubits rapides et à haute fidélité. La rapidité est cruciale pour pouvoir réaliser le plus d’opérations possible avant que les qubits ne perdent leur cohérence quantique, et une haute fidélité est requise pour minimiser les erreurs de calcul et permettre d’implémenter de la correction d’erreurs quantiques. De plus, certains qubits supraconducteurs sont connus pour être affectés par une interaction indésirable, l’interaction ZZ qui, même si relativement faible, affecte la fidélité des portes logiques quantiques, empêchant d’atteindre des fidélités supérieures à 99.9% nécessaires à la correction d’erreurs. En parallèle avec l’amélioration des composantes de l’ordinateur quantique, il est important de développer des applications pour ce nouveau type de machine. Parmi les approches étudiées, les algorithmes quantiques variationnels (VQA) sont ceux qui sont les plus susceptibles d’être déployés sur les ordinateurs quantiques de petites tailles existants. Ce sont des algorithmes hybrides qui nécessitent à la fois de la puissance de calcul classique et quantique. Ces algorithmes semblent prometteurs pour résoudre de nombreux problèmes concrets d’intérêt industriel, comme obtenir les propriétés de molécules ou trouver les solutions de problèmes d’optimisation combinatoire. En effet, ces problèmes peuvent être formulés sous forme d’un Hamiltonien et résolus en déterminant son état fondamental. Dans ce but, les VQAs utilisent un circuit quantique paramétré appelé ansatz, dont les paramètres sont optimisés pour s’approcher de l’état fondamental. Un premier défi consiste à trouver un ansatz qui permette, pour un problème donné, de converger le plus efficacement possible vers la solution. Un deuxième défi est de trouver un circuit fait de portes logiques facilement implémentables sur les plateformes physiques actuelles. Les travaux effectués dans cette thèse apportent des contributions à ces deux défis. Dans la première partie de la thèse, nous introduisons le dispositif que nous avons conçu et qui permet de réaliser des portes d’intrication paramétrique entre deux qubits supraconducteurs. Cette approche a permis à nos collaborateurs du groupe d’Andrew Houck de l’Université de Princeton de réaliser expérimentalement une opération de type √iSWAP en 15 ns avec une fidélité de 98.8%, et ce dans un dispositif où l’interaction ZZ est supprimée. Dans la seconde partie de la thèse, nous avons développé un ansatz pour les VQAs permettant de résoudre le modèle de Fermi Hubbard. Ce nouvel ansatz utilise les avantages de deux ansätze préexistants, et permet d’obtenir l’énergie et l’état fondamental du FHM avec une précision de plusieurs ordres de grandeur supérieure aux ansätze standards, et ce en réduisant significativement le nombre de portes d’intrication CNOT qui sont généralement imparfaites et longues à implémenter.
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.
La cryptographie post-quantique est une branche de la cryptographie qui vise à concevoir des systèmes cryptographiques non quantiques (c'est-à-dire classiques), qui sont protégés contre un adversaire possédant un ordinateur quantique. Dans cette thèse, nous nous concentrons sur l'étude de deux problèmes fondamentaux pour la cryptographie post-quantique : le problème du plus court vecteur (SVP) et le problème de la somme de sous-ensembles aléatoires. Le SVP demande de trouver le plus court vecteur non nul d'un réseaux euclidien donné. Il sert de jauge pour quantifier la sécurité de la cryptographie reposant sur les réseaux euclidiens, qui est considérée comme prometteuse pour l'ère post-quantique. Les principales approches pour résoudre le SVP sont les algorithmes de tamisage, qui utilisent un temps et un espace exponentiels, et les algorithmes d'énumération, qui utilisent un temps superexponentiel et un espace polynomial. Dans cette thèse, nous donnons tout d'abord un compromis temps-mémoire prouvable qui interpole approximativement entre les garanties de ressources des algorithmes de tamisage et celles des algorithmes d'énumération. Nous montrons ensuite l'algorithme quantique prouvable le plus rapide connu qui résout le SVP en temps 2^(0.9535n) et en mémoire classique 2^(0.5n+o(n)) avec seulement un nombre poly(n) de qubits. Nous montrons également le meilleur algorithme prouvable classique connu dont la complexité en mémoire est de 2^(0.5n+o(n)). Quant aux algorithmes d'énumération, on pensait auparavant qu'ils pouvaient bénéficier d'une accélération quadratique quantique grâce à l'algorithme de Grover. Nous montrons que cette accélération quadratique peut effectivement être obtenue pour l'algorithme d'énumération de base et ses variantes d'élagage cylindrique et discret, mais avec des algorithmes quantiques plus sophistiqués tels que la marche quantique sur les arbres. Notre accélération quantique s'applique également à l'élagage extrême où l'on répète le processus d'énumération sur plusieurs bases réduites. Le problème de la somme de sous-ensembles aléatoires sous-tend également certains schémas cryptographiques visant à la sécurité post-quantique, bien qu'il soit principalement de nature académique. Dans un contexte de cryptanalyse, il sert souvent d'outil car de nombreux problèmes sur lesquels se fonde la cryptographie moderne peuvent être exprimés comme des variantes (vectorielles) du problème de la somme de sous-ensembles. Plus récemment, il a également été démontré qu'il peut être utilisé comme élément de base dans certains algorithmes de décalage caché quantique, qui ont des applications dans la cryptanalyse quantique de schémas symétriques et de schémas reposant sur les isogénies. Dans cette thèse, nous présentons de nouveaux algorithmes classiques et quantiques pour la résolution du problème de la somme de sous-ensembles aléatoires. Nous obtenons d'abord l'algorithme classique le plus rapide connu en temps Õ(2^0.283n)). Ensuite, nous améliorons l'état de l'art des algorithmes quantiques pour ce problème dans plusieurs directions. Nous concevons un algorithme avec un temps asymptotique Õ(2^0.236n), avec l'avantage d'utiliser une mémoire classique avec accès aléatoire quantique. Les algorithmes connus précédemment utilisaient des marches quantique, et nécessitaient une mémoire quantique avec accès aléatoire quantique.Nous proposons également des marches quantiques plus rapides pour ce problème en temps Õ(2^0.216n). Ce temps dépend d'une heuristique concernant le temps de mise à jour dans les marches quantiques. Les algorithmes précédents pour ce problème dépendaient eux aussi de cette heuristique. Nous montrons comment surmonter partiellement cette heuristique, et nous obtenons un algorithme quantique de temps Õ(2^0.218n) ne nécessitant que les heuristiques standard du problème de la somme de sous-ensembles aléatoires.