SaTC: CORE: Small: Multivariate Public Key Cryptosystems - Candidates for the Next Generation Post-Quantum Standards

公钥密码系统是密码学领域的革命性突破，是现代通信网络不可或缺的组成部分。Internet以及其他通信系统主要依赖于公钥密码系统，其安全性依赖于某些数字理论问题（如整数分解或“离散日志问题”）的难度。然而，现在已知量子计算机可以有效地解决这些问题，因此，如果可以建造大规模量子计算机，那么基于这些假设的所有公钥密码系统都将失效。为了解决这一问题，抗量子攻击的技术正成为信息安全领域的核心课题；这门新科学被称为“后量子密码学”。正在开发的四种主要的后量子密码系统之一被称为多变量公钥密码系统（MPKCs）。本研究项目致力于对多变量公钥密码系统进行深入研究，目的是促进对几个具有巨大网络安全潜力的多变量候选系统的分析。该项目的结果预计将为后量子计算机世界提供安全高效的替代方案，既可以解决量子计算机对现有密码系统构成的威胁，也可以满足计算资源有限的小型设备日益增长的安全需求。该项目包括一组不同的本科生和研究生，他们将通过参与研究接受培训。该项目的重点是开发更高效、更安全的mpkc及其快速实现，以及探索mpkc的可验证安全性，并分析特定mpkc的安全性。该方法结合了新的数学思想和计算机实验，主要依靠代数几何和对称理论的数学工具。由于所研究的系统不能手工分析，研究者将使用计算机实验来建立直观的理解，并将使用理论方法来研究隐藏在MPKC结构中的数学结构。研究结果有望使人们更好地理解MPKCs的基本原理，以及如何设计安全高效的MPKCs。此外，该项目应该在开发下一代后量子密码学标准方面做出重大贡献。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Public-key cryptosystems, a revolutionary breakthrough in cryptography, are indispensable for our modern communication network. The Internet, as well as other communication systems, rely principally on public-key cryptosystems that depend for security on the difficulty of certain number-theoretic problems such as integer factorization or the "discrete log problem." However, it is now known that a quantum computer could efficiently solve these problems, thus rendering all public-key cryptosystems based on such assumptions impotent if a large-scale quantum computer can be built. To address this issue, technologies resistant to such quantum attack are becoming a central topic in information security; this new science bears the moniker "post-quantum cryptography." One of the four main families of post-quantum cryptosystems under development is known as multivariate public-key cryptosystems (MPKCs). This research project is devoted to an in-depth study of multivariate public-key cryptosystems, with the goal of facilitating the analysis of several multivariate candidates that have great potential for cyber security. Results of the project are expected to produce secure and efficient alternatives for the post-quantum computer world, with application both to addressing the threat that quantum computers pose to existing cryptosystems and to the growing security needs for small devices with limited computing resources. The project includes a diverse group of undergraduate and graduate students who will receive training through involvement in the research.The focus of the project is on developing more efficient and more secure MPKCs and their fast implementations, as well as exploring provable security for MPKCs and analyzing the security of specific MPKCs. The approach is a combination of new mathematical ideas and computer experiments, relying primarily on mathematical tools from algebraic geometry and the theory of symmetry. Since the systems under study cannot be analyzed by hand, the investigator will use computer experiments to build intuitive understanding and will use theoretical methods to study the mathematical structures hidden within the MPKC constructions. The results are expected to lead to a better understanding of the fundamentals of the MPKCs and of how to design secure and efficient MPKCs. Furthermore, the project should make a significant contribution in developing the next generation of standards for post-quantum cryptography.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.