EXPONENTIAL TIME/SPACE ALGORITHMS AND REDUCTIONS FOR LATTICE PROBLEMS

Abstract

Recent advances in the design and construction of quantum computers require us to develop cryptosystems that remain secure even in the era of quantum computing. Lattice-based cryptosystems stand out as the leading candidates for post-quantum cryptography due to their resistance to quantum attacks.

A lattice of rank n is defined as the set of vectors generated by integer linear combinations of n linearly independent vectors. In this thesis, our focus is on two fundamental computational problems on lattices: the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP).

We establish several reductions between the approximation of SVP and CVP over lattices in different L_p norms. Additionally, we introduce new algorithms that enhance the state-of-the-art in terms of classical and quantum algorithms for SVP. Our SVP algorithm provides a smooth tradeoff between time complexity and memory requirement, and we also present a more efficient quantum algorithm for SVP.