CAREER: Lattices in Cryptography

职业：密码学中的格

• 批准号: 1054495
• 负责人: Chris Peikert
• 金额: $ 43.03万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-01-15 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1054495&HistoricalAwards=false
• 关键词: CAREER; Lattices; Cryptography

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.

称为晶格的几何对象在数学和科学中具有无数的基本应用。 最近，它们已成为密码学的新的且非常有吸引力的基础，提供渐近效率，最差的硬度保证以及对量子计算机的明显抵抗力。该项目致力于对密码学和相关领域的晶格进行广泛研究。 具体而言，它针对三个主要方向：（i）对晶格问题最差和平均案例复杂性的基础研究，以及与数量理论问题（例如分解）的连接； （ii）基本加密概念的结构，例如证明系统和伪随机对象； （iii）设计有效，实用算法的设计，支持基于晶格的方案的快速实现。 该项目的结果可能有一天会导致在各种计算和网络应用程序中更快，更安全的加密采用。 在过去的几十年中，在使用称为“数字理论”的数学领域来构建加密功能方面，它取得了巨大的成功，从而提供了丰富的功能，同时承受了打破方案的非常强烈的尝试。 例如，即使受到有史以来最强大的计算机的攻击，今天使用的广泛使用的密码系统被认为是安全的数百年。 但是，这种安全性是有代价的：在当今（或明天）的计算平台上，系统并不是特别有效。 另一个担心的是，“量子计算机”原则上可以完全打破当今许多最广泛使用的密码系统。 虽然到目前为止，量子计算机仅在很小的尺度上才证明，但它们的长期可能性需要在加密术中采用新的方法。几何对象称为“晶格”，最近出现了一个完全不同的，非常有吸引力的密码基础。 基于晶格的方案具有明显的实用性和效率，尤其是在高度平行的机器上，即使面对量子攻击，也似乎是安全的。 然而，由于它们的新颖性，许多基本问题尚未解决或完全没有探索。该项目对密码学领域的晶格进行了广泛的研究，从对其硬问题和联系到其他数字理论问题的基础研究到基本密码对象的新设计以及对其具体效率和安全性的研究。