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.