Quantum Cryptanalysis on Lattices and Codes
Cryptanalyse quantique des réseaux et codes
Abstract
The emergence of the quantum computer requires protecting our computer systems from these new quantum attacks. Many post-quantum cryptographic schemes rely on the hardness of solving problems from theories of Euclidean lattices and codes. In this thesis, we study the complexity of finding a short vector (SVP) in a lattice. We improve the quantum attack against SVP with a new sieving algorithm using quantum walks and filtering techniques. We also propose k-sieve algorithms reaching better time-memory trade-offs by introducing a new filtering technique tailored to the k-sieve. We are also interested in the complexity of the decoding problem, on which the Wave digital signature is based. We describe a quantum attack to forge signatures and estimate its security against the best known classical and quantum attacks.
L'émergence de l'ordinateur quantique impose protéger nos systèmes informatiques face à ces nouvelles attaques quantiques. De nombreux schémas cryptographiques post-quantiques reposent sur la difficulté de résoudre des problèmes provenant des théories des réseaux euclidiens et de codes. Dans cette thèse, nous étudions la complexité du problème de trouver un vecteur court (SVP) dans un réseau. Nous améliorons l'attaque quantique contre SVP grâce à un nouvel algorithme de crible utilisant des marches quantiques et des techniques de filtrage. Nous proposons aussi des algorithmes de k-crible atteignant de meilleurs compromis temps-mémoire en introduisant une nouvelle technique de filtrage adaptée au k-crible. Nous nous intéressons aussi à la complexité du problème de décodage, sur lequel repose notamment la signature électronique Wave. Nous décrivons une attaque quantique pour contrefaire des signatures, et estimons sa sécurité face aux meilleurs attaques classiques et quantiques connues.
Origin : Version validated by the jury (STAR)