FrodoKEM：基于带误差学习问题的密钥封装

该C语言库实现了 FrodoKEM，一种基于已被充分研究的带误差学习（LWE）问题 [1,3] 的 IND-CCA 安全密钥封装（KEM）协议，而 LWE 问题又与通用“代数非结构化”格上的猜想困难问题密切相关。本软件包还包含 Python 参考实现。FrodoKEM 被推测能够抵御量子计算机攻击。

FrodoKEM 包含两个主要变体：

• 一个 标准 变体（简称为 FrodoKEM），不对密钥对的重用施加任何限制（即，它适用于大量密文可能被加密到单个公钥的应用场景），以及
• 一个 临时 变体（称为 eFrodoKEM），适用于不会将太多密文加密到单个公钥的应用场景。

与 eFrodoKEM 相比，标准 FrodoKEM 使用扩大的种子来生成用于采样秘密矩阵和误差矩阵的种子，并在封装和解封装的一个哈希计算中包含额外的盐值。这些对策保护标准 FrodoKEM 免受某些多密文攻击。有关这两个变体的更多详细信息，请参阅 [3]。

具体来说，该库包含以下使用 AES128 生成公共矩阵“A”的 KEM 方案：

• FrodoKEM-640-AES 和 eFrodoKEM-640-AES：匹配 AES128 的后量子安全性。
• FrodoKEM-976-AES 和 eFrodoKEM-976-AES：匹配 AES192 的后量子安全性。
• FrodoKEM-1344-AES 和 eFrodoKEM-1344-AES：匹配 AES256 的后量子安全性。

以及以下使用 SHAKE128 生成公共矩阵“A”的 KEM 方案：

• FrodoKEM-640-SHAKE 和 eFrodoKEM-640-SHAKE：匹配 AES128 的后量子安全性。
• FrodoKEM-976-SHAKE 和 eFrodoKEM-976-SHAKE：匹配 AES192 的后量子安全性。
• FrodoKEM-1344-SHAKE 和 eFrodoKEM-1344-SHAKE：匹配 AES256 的后量子安全性。

标签“eFrodoKEM”对应临时变体。

该库由 FrodoKEM 团队 和 微软研究院 为实验目的而开发。

目录

• common 文件夹：随机函数、AES 和 SHA-3 的实现。
• eFrodoKEM 文件夹：eFrodoKEM 的 C 和 Python3 实现。
• estimates 文件夹：[3] 中报告的 FrodoKEM 密码分析估计。
• FrodoKEM 文件夹：标准 FrodoKEM 的 C 和 Python3 实现。
• LICENSE：MIT 许可证文件。
• README.md：本自述文件。

支持的平台

FrodoKEM 库支持广泛的平台，包括运行 Windows、Linux 或 macOS 的 x64、x86、ARM、PowerPC 和 s390x 处理器，并同时支持小端和大端格式。 我们已使用 Microsoft Visual Studio、GNU GCC 和 clang 对该库进行了测试。

许可证

本软件根据 MIT 许可证授权；详情请参阅 LICENSE 文件。 Python3 实现根据知识共享零 v1.0 通用许可证授权。 它包含一些以不同方式授权的第三方模块。特别是：

• common/aes/aes_c.c：公有领域
• common/aes/aes_ni.c：公有领域
• common/sha3/fips202.c：公有领域
• common/sha3/fips202x4.c：公有领域
• common/sha3/keccak4x：此文件夹中的所有文件均为公有领域（CC0），但以下文件除外
• common/sha3/keccak4x/brg_endian.h，其版权归 Brian Gladman 所有，并附带 BSD 3-Clause 许可证。
• <FrodoKEM_variant>/tests/ds_benchmark.h：公有领域
• <FrodoKEM_variant>/tests/PQCtestKAT_kem<#>.c：版权归 Lawrence E. Bassham 所有
• <FrodoKEM_variant>/tests/PQCtestKAT_kem<#>_shake.c：版权归 Lawrence E. Bassham 所有
• <FrodoKEM_variant>/tests/rng.c：版权归 Lawrence E. Bassham 所有

参考文献

[1] Erdem Alkim, Joppe W. Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Chris Peikert, Ananth Raghunathan, 和 Douglas Stebila, “FrodoKEM: Learning With Errors Key Encapsulation”。提交至 NIST 后量子标准化项目，2021-2023。FrodoKEM 的第 3 轮规范可在此处获取。

[2] Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, 和 Douglas Stebila, “Frodo: Take off the ring! Practical, quantum-secure key exchange from LWE”。 ACM CCS 2016, 2016。预印本版本可在此处获取。

[3] Lewis Glabush, Patrick Longa, Michael Naehrig, Chris Peikert, Douglas Stebila, 和 Fernando Virdia, “FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism”。IACR Communications in Cryptology（即将出版），2025。

贡献

本项目已采用 Microsoft 开源行为准则。更多信息请参阅行为准则常见问题解答或通过 [email protected] 联系，提出任何其他问题或评论。