TC: Small: Algorithmics and Security of Lattice Cryptography

TC：小：格密码学的算法和安全性

• 批准号: 1117936
• 负责人: Daniele Micciancio
• 金额: $ 50万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-10-01 至 2016-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117936&HistoricalAwards=false
• 关键词: TC; Small; Algorithmics; Security; Lattice

Lattice cryptography is a cutting-edge area of cryptology which has the potential to deliver new and better solutions to many security problems. Lattice algorithms are routinely used to attack and analyze the security of lattice cryptography. However, our current understanding of state-of-the-art lattice algorithms is weak. As a result, the usability of lattice cryptography is severely limited by the lack of high confidence security estimates. Lattice algorithms are investigated, with the goal of providing better understanding of known algorithms, and develop new algorithms as well. Specific goals of the project include: (1) the development of practical variants of the asymptotically fastest known lattice algorithms, (2) the study of analytic models that can be used to predict and explain the behavior of heuristic approaches to lattice problems, and (3) the use of the new models and algorithms to provide concrete security estimates for lattice cryptographic functions. Lattice algorithms are studied using rigorous mathematical methods that provide provable guarantees on the behavior of the algorithms, coupled with extensive practical experimentation to gauge the practical significance of the theoretical results. Computational problems on lattices arise naturally in many areas mathematics and science, from algebraic number theory and communication theory to crystallography and combinatorial optimization. The applicability of the improved lattice algorithms resulting from this project extends beyond cryptography, to reach those other areas as well. Algorithms, experimental data, and instructional material developed in the course of this investigation will be made widely available on the Internet.

格密码学是密码学的前沿领域，它有可能为许多安全问题提供新的更好的解决方案。格算法是攻击和分析格密码体制安全性的常用算法。然而，我们目前对最先进的格型算法的理解是薄弱的。因此，格密码学的可用性受到缺乏高置信度安全估计的严重限制。格算法进行了研究，其目的是提供更好地理解已知的算法，并开发新的算法以及。该项目的具体目标包括：（1）开发渐进最快已知格算法的实际变体，（2）研究可用于预测和解释格问题启发式方法行为的分析模型，以及（3）使用新模型和算法为格密码函数提供具体的安全性估计。格型算法是使用严格的数学方法来研究的，这些方法为算法的行为提供了可证明的保证，再加上广泛的实际实验来衡量理论结果的实际意义。格上的计算问题自然出现在数学和科学的许多领域，从代数数论和通信理论到晶体学和组合优化。该项目产生的改进的格型算法的适用性超出了密码学，也达到了其他领域。算法，实验数据，并在此调查过程中开发的教学材料将在互联网上广泛提供。