CAREER: Concrete Hardness in Lattice-based Cryptography

随着量子计算的最新进展，量身定制的量子安全密码系统引起了人们的极大兴趣。后量子密码学最有前途的候选者之一是基于格的密码学。然而，基于格的密码学的安全性依赖于某些基于格的假设的计算硬度。该项目的中心目标是了解这些假设的具体硬度，研究最坏情况和平均情况下晶格问题的算法。该项目旨在为晶格算法的具体行为提供新的见解，并了解其详细的资源需求。该项目的综合教育部分包括指导、课程（重新）设计和科学传播活动的结合，有助于培养多样化的STEM劳动力。项目的主要研究活动包括：(1)理解和改进晶格约简算法，包括底层的枚举和筛分算法，重点研究它们的具体复杂性；(2)研究经典算法和量子算法在格约简中的应用影响，并估算其详细的资源需求；(3)建立鲁棒模型来指导基于格的密码系统的参数选择。研究结果为定量理解晶格假设的固有硬度提供了一种系统的方法。这些结果有助于后量子加密的标准化进程，指导参数选择，并为基于格的加密的开发人员和最终用户提供系统的工具。研究成果将发表在学术界同行评议的出版物上，并通过教育和外联活动向更广泛的受众传播。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

With recent advances in quantum computing, cryptosystems tailored to be quantum-safe are of great interest. One of the most promising candidates for post-quantum cryptography is lattice-based cryptography. The security of lattice-based cryptography however relies on the computational hardness of certain lattice-based assumptions. The central goal of this project is to understand the concrete hardness of these assumptions, investigating algorithms for the worst-case and average-case lattice problems. The project aims to provide new insights into the concrete behavior of lattice algorithms and understand their detailed resource requirements. The integrated educational component of the project involves a combination of mentoring, course (re)-design and science communication activities, contributing to the development of a diverse STEM workforce.The main research activities in the project include: (1) understand and improve the lattice reduction algorithms, including the underlying enumeration and sieving algorithms, with a focus on their concrete complexities; (2) investigate the impacts of deploying classical and quantum algorithms in lattice reduction, and estimate their detailed resource requirement; (3) develop robust models to guide the parameter selection for lattice-based cryptographic systems. The research findings provide a systematic approach to quantitatively understand the intrinsic hardness of lattice assumptions. These results contribute to the standardization process for post-quantum cryptography, guide the parameter selection, and provide a systematic tool to the developers and end-users of lattice-based cryptography. The research outcomes are to be published in peer-reviewed publications for the academic community and to be disseminated to a broader audience through the education and outreach activities.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.