CAREER: Lattices in Cryptography

被称为格的几何物体在数学和科学中有着无数的基本应用。最近，它们已经成为一种新的、非常吸引人的密码学基础，提供渐近效率、最坏情况下的硬度保证，以及对量子计算机的明显抵抗。这个项目致力于密码学和相关领域的格的广泛研究。具体来说，它涉及三个主要方向：(i)对格问题的最坏情况和平均情况复杂性的基础研究，以及与数论问题（如因数分解）的联系；（ii）基本密码学概念的构造，如证明系统和伪随机对象；（iii）设计高效实用的算法，以支持基于格子的方案的快速实现。这个项目的成果可能有一天会导致在各种计算和网络应用中广泛采用更快、更安全的加密技术。任何加密协议的核心都是对方案的操作环境和攻击者与之交互的假设——但更根本的是，对破解它所需的计算资源的假设。在过去的几十年里，我们看到了在使用一个叫做“数论”的数学领域来构建密码学方面取得的巨大成功，这种密码学提供了丰富的功能，同时经受住了非常强大的破解方案的尝试。例如，今天广泛使用的密码系统被认为在数百年内是安全的，即使受到有史以来最强大的计算机的攻击。然而，这种安全性是有代价的：系统在今天（或明天）的计算平台上不是特别高效。更令人担忧的是，原则上，“量子计算机”可以完全破解当今许多最广泛使用的密码系统。虽然量子计算机到目前为止只在非常小的尺度上得到了证明，但它们的长期可能性需要在密码学中采用新的方法。最近，被称为“格”的几何对象作为一种完全不同的、非常有吸引力的密码学数学基础出现了。基于点阵的方案提供了显著的实用性和效率，特别是在高度并行的机器上，并且即使面对量子攻击也显得安全。然而，由于它们的新颖性，许多基本问题没有答案或完全没有探索过。该项目对密码学中的格进行了广泛的研究，范围从对它们的难题和与其他数论问题的联系的基础研究，到基本密码对象的新设计以及它们的具体效率和安全性的研究。

Geometric objects called lattices have had countless essential applications in mathematics and the sciences. Recently, they have emerged as a new and very appealing foundation for cryptography, offering asymptotic efficiency, worst-case hardness guarantees, and apparent resistance to quantum computers.This project is dedicated to a broad study of lattices in cryptography and related areas. Specifically, it addresses three main directions: (i) a foundational investigation into the worst-case and average-case complexity of lattice problems, and connections with number-theoretic problems such as factoring; (ii) constructions of essential cryptographic notions such as proof systems and pseudorandom objects; (iii) the design of efficient, practical algorithms supporting fast implementations of lattice-based schemes. Results from this project may one day lead to wide adoption of faster and more secure cryptography in a wide variety of computing and networking applications.At the heart of any cryptographic protocol are assumptions about the scheme's operating environment and the attacker's interactions with it --- but more fundamentally, about the amount of computing resources required to break it. The past few decades have seen tremendous success in using an area of mathematics called "number theory" to build cryptography that provides rich functionality while withstanding very strong attempts at breaking the schemes. For instance, today's widely used cryptosystems are believed to be secure for hundreds of years, even when attacked by the most powerful computers ever designed. However, this security comes at a price: the systems are not especially efficient on today's (or tomorrow's) computing platforms. A further worry is that "quantum computers" can, in principle, completely break many of today's most widely used cryptosystems. While quantum computers have so far only been demonstrated at very small scales, their long-term possibility necessitates new approaches in cryptography.Geometric objects called "lattices" have recently emerged as an entirely different, and very attractive, mathematical foundation for cryptography. Lattice-based schemes offer significant utility and efficiency, especially on highly parallel machines, and appear to be secure even in the face of quantum attacks. Due to their novelty, however, many basic questions are unanswered or entirely unexplored. This project conducts a broad study of lattices in cryptography, ranging from a foundational investigation of their hard problems and connections to other number-theoretic problems, to new designs of essential cryptographic objects and studies of their concrete efficiency and security.