CAREER: Concrete Hardness in Lattice-based Cryptography

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

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.