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) 设计高效、实用的算法，支持基于格的方案的快速实现。 该项目的结果有一天可能会导致在各种计算和网络应用中广泛采用更快、更安全的加密技术。任何加密协议的核心都是对该方案的操作环境以及攻击者与其交互的假设——但更根本的是，关于破解它所需的计算资源量。 在过去的几十年里，我们在使用称为“数论”的数学领域来构建密码学方面取得了巨大成功，该密码学提供了丰富的功能，同时能够承受破解方案的强烈尝试。 例如，当今广泛使用的密码系统被认为在数百年内都是安全的，即使受到有史以来最强大的计算机的攻击也是如此。 然而，这种安全性是有代价的：系统在今天（或明天）的计算平台上并不是特别高效。 进一步的担忧是，“量子计算机”原则上可以完全破解当今许多最广泛使用的密码系统。 虽然量子计算机迄今为止仅在非常小的规模上得到证明，但它们的长期可能性需要密码学中的新方法。称为“晶格”的几何对象最近作为密码学的完全不同且非常有吸引力的数学基础而出现。 基于格的方案提供了显着的实用性和效率，特别是在高度并行的机器上，并且即使面对量子攻击也似乎是安全的。 然而，由于它们的新颖性，许多基本问题尚未得到解答或完全未经探索。该项目对密码学中的格进行了广泛的研究，从对其难题的基础研究以及与其他数论问题的联系，到基本密码对象的新设计以及对其具体效率和安全性的研究。