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.