Ironclad Quantum Security of Code And Lattice-based cryptography

Since Shor’s seminal algorithm, we know that quantum computers will break deployed public-key cryptography. Fortunately, there are quantum-safe solutions based on objects known as codes and lattices. These solutions were identified by an algorithm of Regev showing that if there is an attack, then a quantum compter will enable to solve problems believed to be intractable. Apart from this result, very few quantum algorithms were designed to assess or to break the security of code and lattice-based cryptography. IQ-SCALe is here to address this gap by opening a new and uncharted area for quantum algorithms.One of the motivations behind IQ-SCALe is a recent attack I designed against advanced cryptosystems. My attack based on Regev's approach demonstrates that it had not been sufficiently exploited. I also identified tools from Regev's approach to be at the core of a fundamental research area - sphere packing bounds - for which powerful generalizations are known. However, they involve more complicated objects (non-commutative groups) and the analogous quantum tools have not yet been designed.IQ-SCALe aims to design new quantum algorithms for this broader theory. Historically, Regev’s approach not only enabled us to assess the security of some cryptosystems by identifying an intractable problem, it was also leveraged to mount attacks as I have shown. The new quantum tools that I will design in IQ-SCALe will likewise lead to both the identification of useful cryptographic problems and the design of new algorithms for attacks and proofs of hardness. It will considerably increase our trust in code and lattice-based cryptography. Current quantum algorithms to assess the security of code and lattice schemes are adaptations to the quantum setting of classical approaches. This will not be the case for innovative algorithms of IQ-SCALe. But beyond algorithms, it will also create new connections between advanced mathematical areas and code and lattice-based cryptography.