AF: Small: Complexity of Lattice Problems for Cryptography

点击翻译按钮获取中文摘要

Public-key cryptosystems are protocols that enable secure communication, even if the communicating parties have never met before. Such cryptosystems are essential to the modern Internet, where a majority of all communication is now encrypted. However, all public-key cryptosystems in widespread use today would be breakable by large-scale quantum computers. This fact, combined with recent rapid progress on quantum computing, has motivated the development and standardization of quantum-secure cryptosystems based on geometric objects called lattices, which will likely be in widespread use in the near future. This project will inform and strengthen understanding of the security of lattice-based cryptosystems, aiding ongoing standardization efforts for quantum-secure cryptography and the adoption of advanced, socially beneficial tools like encrypted computation. The security of lattice-based cryptosystems is based on the apparent intractability---even for quantum computers---of a few main computational problems on lattices. Sufficiently strong complexity results for these problems would allow for very efficient implementations of lattice based cryptosystems that simultaneously ensure high levels of security. The objective of this project is to work toward such results by showing improved hardness of approximation and fine-grained complexity results for these central problems, and to show tighter cryptographic reductions between problems assuming realistic adversaries.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.