Lattice cryptography is a cutting-edge area of cryptology which has the potential to deliver new and better solutions to many security problems. Lattice algorithms are routinely used to attack and analyze the security of lattice cryptography. However, our current understanding of state-of-the-art lattice algorithms is weak. As a result, the usability of lattice cryptography is severely limited by the lack of high confidence security estimates. Lattice algorithms are investigated, with the goal of providing better understanding of known algorithms, and develop new algorithms as well. Specific goals of the project include: (1) the development of practical variants of the asymptotically fastest known lattice algorithms, (2) the study of analytic models that can be used to predict and explain the behavior of heuristic approaches to lattice problems, and (3) the use of the new models and algorithms to provide concrete security estimates for lattice cryptographic functions. Lattice algorithms are studied using rigorous mathematical methods that provide provable guarantees on the behavior of the algorithms, coupled with extensive practical experimentation to gauge the practical significance of the theoretical results. Computational problems on lattices arise naturally in many areas mathematics and science, from algebraic number theory and communication theory to crystallography and combinatorial optimization. The applicability of the improved lattice algorithms resulting from this project extends beyond cryptography, to reach those other areas as well. Algorithms, experimental data, and instructional material developed in the course of this investigation will be made widely available on the Internet.
