Some Recent Progress on the Complexity of Lattice Problems

摘要

We survey some recent developments in the study of the complexity of lattice problems. After a discussion of some problems on lattices which can be algorithmically solved efficiently, our main focus is the recent progress on complexity results of intractability. We will discuss Ajtai's worst-case/ average-case connections, NP-hardness and non-NP-hardness, transference theorems between primal and dual lattices, and the Ajtai-Dwork cryptosystem. (This is a survey article appearing in the Conference on Computational Complexity at FCRC, May 1999.)