Hardness of Lattice Problems for Use in Cryptography

Abstract

Lattice based cryptography has recently become extremely popular due to its perceived resistance to quantum attacks and the many amazing and useful cryptographic primitives that can be constructed via lattices. The security of these cryptosystems relies on the hardness of various lattice problems upon which they are based. In this thesis, we present a number of known hardness results for lattice problems and connect these hardness results to cryptography. In particular, we show NP-hardness results for the exact versions of the lattice problems SVP, CVP, and SIVP. We also discuss the known hardness results for approximate versions of these problems and the fastest known algorithms for both exact and approximate versions of these problems. Additionally, we prove several new exponential time hardness results for these lattice problems under reasonable complexity assumptions. We then detail how some of these hardness results can be used to construct provably secure cryptographic schemes and survey some of the recent breakthroughs in lattice based cryptography.