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.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Network Systems (CNS)
Type
Standard Grant (Standard)
Application #
1117936
Program Officer
Ralph Wachter
Project Start
Project End
Budget Start
2011-10-01
Budget End
2014-09-30
Support Year
Fiscal Year
2011
Total Cost
$500,000
Indirect Cost
Name
University of California San Diego
Department
Type
DUNS #
City
La Jolla
State
CA
Country
United States
Zip Code
92093