Skip to content
返回搜索结果

基于格的密码学

提出者
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 算法在内的量子计算机攻击
  • 基于成熟的格问题,具有强大的数学基础
  • 在同一框架内支持加密和数字签名
  • 具有可行的实现,对现代硬件而言计算成本合理

应用

  • 后量子传输安全,以保护通信免受未来量子解密
  • 用于必须保密数十年的文件和数据的长期归档加密
  • 能够抵御量子威胁的政府和军事通信系统
  • 为实现量子抗性安全而设计的区块链和加密货币系统
  • 作为设计要求需要量子抗性的物联网和嵌入式系统
  • 在密码过渡期间结合了基于格和传统算法的混合密码系统

使用方式

使用方式

1

选择格的维度 n、模数 q 和误差分布。生成一个秘密短基,并通过格变换从其导出公用基。

2

公钥是从困难格基派生出来的;从计算角度来看,它不提供关于秘密基的任何信息。

3

加密时,将明文添加到公用基向量的带噪声线性组合中,从而创建一个带噪声的格点。

4

使用秘密短基,对带噪声的格点进行约化并提取明文。

常见陷阱

  • 选择格参数(维度、模数、误差分布)并非易事;强烈建议使用标准的 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 标准化的基于格的算法。处理具有长期保留期敏感数据的组织应开始规划迁移。

相关方法

参考文献

  1. 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.

    打开出版物文献
    已复制。
  2. Regev, O. (2005). On lattices, learning with errors, hard instances, and public key cryptography. In Proceedings of STOC 2005, pp. 84-93.

    打开出版物文献
    已复制。