Collaborative Research: EAGER-QIA: High-Genus Code-Based Cryptography

密码学保护机密通信：电子商务、选民信息、外交通信、人权访谈、医疗记录等等。然而，今天记录消息的攻击者将能够用未来的量子计算机解密这些消息。最鼓舞人心的反应是McEliece密码系统，它具有强大的安全记录，是后量子密码学标准化的主要竞争者，但该密码系统的密钥大小约为1兆字节。目前，无法负担兆字节密钥的应用程序被迫使用安全性不太稳定的密码系统。该项目旨在构建新的后量子系统，将McEliece的安全稳定性和信心带到更广泛的应用中。McEliece密码系统中的公钥是纠错码的子字段子码的生成矩阵，特别是genus-0 Goppa码。高亏格Goppa码的子字段子码在相同码长和码维数的情况下可以纠正更多的错误，改善了效率和安全性之间的权衡。要证明由这些代码构建的密码系统可以以合理的速度运行，需要对密码系统设计、曲线选择、解码算法、计算机代数算法和矢量化软件进行垂直集成优化，该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准。

Cryptography protects confidential communications: electronic commerce, voter information, diplomatic communication, human-rights interviews, medical records, and much more. However, attackers recording messages today will be able to decrypt those messages with future quantum computers. The most confidence-inspiring response is the McEliece cryptosystem, which has a strong security track record and is a leading contender for standardization of post-quantum cryptography, but this cryptosystem has a key size around a megabyte. Applications that cannot afford megabyte keys are currently forced to use cryptosystems whose security is much less stable. This project aims to build new post-quantum systems that bring McEliece's security stability and confidence to a wider range of applications.The public key in McEliece's cryptosystem is a generator matrix for a subfield subcode of an error-correcting code, specifically a genus-0 Goppa code. Subfield subcodes of higher-genus Goppa codes can correct more errors for the same code length and code dimension, improving the tradeoffs between efficiency and security. Showing that cryptosystems built from these codes can run at reasonable speed will require vertically integrated optimization of cryptosystem design, curve selection, decoding algorithms, algorithms for computer algebra, and vectorized software, with the further challenges of ensuring security against both mathematical and microarchitectural attacks.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.