基于格的密码学
- 提出者
- Miklós Ajtai
- 年份
- 1996
- 类型
- public-key cryptosystem based on lattice hardness
- 类别
- Post-quantum cryptography
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
基于格的密码学是一类密码系统,其安全性源于格问题(特别是最短向量问题 SVP 和带错误学习问题 LWE)的计算困难性。该方法由 Miklós Ajtai 于 1996 年首次提出,现已成为后量子密码学的主要候选者。与易受量子计算机攻击的 RSA 和 ECC 不同,格问题被认为即使面对量子算法也依然困难。
方法背后的直觉
格是欧几里得空间的一个离散子群,由基向量的整数线性组合构成。基于格的密码学利用了两个问题之间的差异:在格中找到一个短向量在计算上是困难的,但有了附加信息(一个秘密基),就可以快速找到短向量。公钥密码体制通过发布一个困难基并保守一个容易基的秘密来构建。添加小的随机噪声(带错误学习范式)通过使问题类似于一个难以求解的带噪声线性系统,进一步增强了安全性。
历史学
Ajtai 在 1996 年的开创性工作将格的困难性与密码学联系起来。Regev 在 2005 年提出的带错误学习 (LWE) 框架为基于格的密码学提供了实用且通用的基础。在学术界和政府机构认识到量子计算对当前密码基础设施的威胁后,该领域得到了加速发展。2022 年,NIST 将基于格的方案(CRYSTALS-Kyber 用于加密,CRYSTALS-Dilithium 用于签名)标准化为主要的后量子算法推荐。
何时使用
基于格的密码学对于旨在抵御未来量子计算机的系统至关重要。建议将其用于敏感数据的长期保密、政府和军事通信以及必须保持数十年安全的关键基础设施。随着标准化后量子算法的成熟(NIST 最近标准化了 ML-KEM 和 ML-DSA),基于格的方法正在成为现代密码系统的主流。
局限与注意事项
- 与传统的 RSA 或 ECC 相比,密钥和密文尺寸更大,增加了存储和传输开销
- 比 RSA 或 ECC 更新,部署经验较少,因此实际部署经验有限
- 一些基于格的方案存在微妙的参数选择,这些选择会显著影响安全性;不正确的参数可能导致灾难性后果
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 据信能抵抗包括 Shor 算法在内的量子计算机攻击
- 基于成熟的格问题,具有强大的数学基础
- 在同一框架内支持加密和数字签名
- 具有可行的实现,对现代硬件而言计算成本合理
应用
- 后量子传输安全,以保护通信免受未来量子解密
- 用于必须保密数十年的文件和数据的长期归档加密
- 能够抵御量子威胁的政府和军事通信系统
- 为实现量子抗性安全而设计的区块链和加密货币系统
- 作为设计要求需要量子抗性的物联网和嵌入式系统
- 在密码过渡期间结合了基于格和传统算法的混合密码系统
使用方式
使用方式
选择格的维度 n、模数 q 和误差分布。生成一个秘密短基,并通过格变换从其导出公用基。
公钥是从困难格基派生出来的;从计算角度来看,它不提供关于秘密基的任何信息。
加密时,将明文添加到公用基向量的带噪声线性组合中,从而创建一个带噪声的格点。
使用秘密短基,对带噪声的格点进行约化并提取明文。
常见陷阱
- 选择格参数(维度、模数、误差分布)并非易事;强烈建议使用标准的 NIST 批准参数
- 基于格的操作的侧信道攻击(计时、功耗分析)需要仔细实现;恒定时间算法至关重要
- 错误地混合基于格和经典算法可能导致具有意外弱点的混合系统
常见问题
什么是带错误学习 (LWE) 问题?
LWE 是一个计算问题,其中给定有限域上的带噪声线性方程。给定形式为 a·x + e (mod q) 的方程,其中 a 是随机的,x 是秘密的,e 是小的噪声,在不知道 e 的情况下恢复 x 在计算上是困难的。
为什么基于格的密钥比 RSA 密钥大?
格基及其编码矩阵包含比单个复合数更多的信息。以密码学方式编码格基需要更多的比特,尽管最近的方案已经优化了表示。
格问题是量子抗性的吗?
目前没有已知的量子算法比经典算法在 SVP 或 LWE 等格问题上更快,尽管这仍然是一个活跃的研究领域。格的困难性被推测可以抵抗量子计算机。
NIST 对基于格的密码学有何建议?
NIST 在 FIPS 203 和 FIPS 204 中将 ML-KEM(模块化基于格的密钥封装机制)作为加密算法,将 ML-DSA(模块化基于格的数字签名算法)作为签名算法,标准化为主要的后量子算法。
我今天可以使用基于格的密码学吗?
是的。许多现代密码库现在支持 NIST 标准化的基于格的算法。处理具有长期保留期敏感数据的组织应开始规划迁移。
相关方法
参考文献
Ajtai, M. (1996). Generating hard instances of the short basis problem. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 99-108.
打开出版物文献已复制。Regev, O. (2005). On lattices, learning with errors, hard instances, and public key cryptography. In Proceedings of STOC 2005, pp. 84-93.
打开出版物文献已复制。