Cryptanalyse classique et quantique pour les réseaux euclidiens et les sommes de sous-ensembles

Post-quantum cryptography refers to a branch of cryptography aimed at designing non-quantum (ie. classical) cryptographic systems which are secure against an adversary having a quantum computer. In this thesis we focus on the study of two fondamental problems for post-quantum cryptography: the Shortest Vector problem (SVP) and the random Subset-Sum problem.The SVP asks to find the shortest non-zero vector of a given lattice. It serves as a gauge to quantify the security of lattice-based cryptography which is widely considered to be promising for the post-quantum era. The main approaches to solve the SVP are the sieving algorithms, which use exponential time and space, and the enumeration algorithms, which use superexponential time and polynomial space. Even though sieving algorithms are asymptotically the fastest known algorithms for SVP, the memory requirement, in high dimension, has historically been a limiting factor to run these algorithms. Some recent works have shown how to use new tricks to make it possible to use sieving on high-dimensional lattices in practice and benefit from their efficient running time. Nevertheless, it has been a long standing open question to obtain an algorithm that achieves the ``best of both worlds'', i.e. an algorithm that runs in exponential time and requires only polynomial amount of memory. In the absence of such an algorithm, it is desirable to have a smooth tradeoff between time and memory requirement that interpolates between the current best sieving algorithms and the current best enumeration algorithms. In this thesis, we first give a provable time memory trade-off which roughly interpolates between the resource guarantees of sieving algorithms and those of enumeration algorithms. We then show the fastest state-of-the-art provable quantum algorithm that solves SVP using $2^{0.9535n+o(n)}$ time and requires $2^{0.5n+o(n)}$ classical memory but only poly(n) qubits. We also provide the fastest classical algorithm in the provable setting whose memory is $2^{0.5n+o(n)}$.As for the enumeration algorithms, it was previously commonly believed that they can benefit from a quantum quadratic speed-up using Grover's algorithm. We show that the quadratic speed-up can indeed be achieved for lattice enumeration and its cylinder and discrete pruning variants, but with more sophisticated quantum algorithms such as quantum walk on trees. Our quantum speed-up applies further to extreme pruning where one repeats enumeration over many reduced bases: a naive approach would only decrease the classical cost $m t$ (where $m$ is the number of bases and $t$ is the number of operations of a single enumeration) to $m \sqrt{t}$ quantum operations, but we bring it down to $\sqrt{mt}$. The random subset-sum problem also underlies some cryptographic schemes aiming at post-quantum security, although it is mostly of academic nature. In a cryptanalysis context, it often serves as a cryptanalytic tool as many problems on which modern cryptography is build can be expressed as some (vectorial) versions of the subset sum problem. More recently it is also shown that it can be used as a building block in some quantum hidden shift algorithms, which have applications in quantum cryptanalysis of isogeny-based and symmetric cryptographic schemes.In this thesis, we present new classical and quantum algorithms for solving random subset-sum instances. We first show the fastest state-of-the-art classical algorithm using Õ ($2^{0.283n}$) time. Next, we improve the state of the art of quantum algorithms for this problem in several directions. We devise an algorithm with asymptotic running time Õ ($2^{0.236n}$), with the advantage of using \emph{classical} memory with quantum random access. The previously known algorithms all used the quantum walk framework, and required \emph{quantum} memory with quantum random access. We also propose faster quantum walks for subset-sum with time complexity Õ ($2^{0.216n}$). This time is dependent on a heuristic on quantum walk updates that is also required by the previous algorithms. We show how to partially overcome this heuristic, and we obtain a quantum algorithm with time Õ ($2^{0.218n}$) requiring only the standard subset-sum heuristics.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. Même si les algorithmes de tamisage sont asymptotiquement les algorithmes connus les plus rapides pour le SVP, la complexité en mémoire, en grande dimension, a historiquement été un facteur limitant pour exécuter ces algorithmes. Certains travaux récents ont montré comment utiliser de nouvelles astuces pour rendre possible l’utilisation du tamisage sur des réseaux euclidiens à haute dimension dans la pratique et bénéficier de leur temps de fonctionnement efficace. Néanmoins, la question de l’obtention d’un algorithme qui réalise le « meilleur des deux mondes », c’est-à-dire un algorithme qui fonctionne en temps exponentiel et ne nécessite qu’une quantité polynomiale de mémoire, reste ouverte depuis longtemps. En l’absence d’un tel algorithme, il est souhaitable d’avoir un compromis entre le temps et la quantité de mémoire requise qui interpole entre les meilleurs algorithmes de tamisage actuels et les meilleurs algorithmes d’énumération actuels.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+o(n)}$ 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 : une approche naïve ne ferait que réduire le coût classique de mt (où m est le nombre de bases et t est le coût d’un seul processus d’énumération) à m√t opérations quantiques, mais nous le ramenons à √mt.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éatoire