Classical and Quantum Cryptanalysis for Euclidean Lattices and Subset Sums

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 O ($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 O ($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 O ($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 O ($2^{0.218n}$) requiring only the standard subset-sum heuristics.