文章总结： 本文回顾了格密码学从数论起源到后量子标准化的历史，涵盖Lagrange与Gauss的理论基础、LLL算法、LWE问题及全同态加密发展。重点阐述了NIST将CRYSTALS-Kyber和Dilithium确立为后量子标准，以及我国在抗量子算法领域的进展与新一轮征集，突显格密码在未来安全中的基石作用。 综合评分： 85 文章分类： 技术标准,解决方案,网络安全,数据安全

---

【杂谈】格密码发展的时光之旅

原创

Litt1eQ Litt1eQ

Coder小Q

2026年2月4日 08:30 山东

【杂谈】格密码发展的时光之旅

❝

好了，快过年了，我们聊点简单的，这里先叠一个甲，因为有些领域我实在不熟悉，在了解发展的过程当中有可能出现错误，如果有错误，也欢迎读者和我交流，哈哈哈，就是这样~

Bob：Alice，我最近听说格密码是后量子密码学的希望之星，但”格”这个东西到底是什么？它是怎么来的？

Alice：这是个好问题。格（Lattice）的故事要从250多年前说起。1770年代初，法国数学家Lagrange开始研究二次型的数论问题。

Bob：1770年代，那时候我国正是清朝乾隆年间，乾隆皇帝刚开始要编纂《四库全书》呢。那个时代就有密码学了？

Alice：密码学倒是早就有了——从古埃及人、恺撒密码到中世纪的各种加密方法，已经有几千年历史了。但那时候的密码学都是经验性的技巧，缺乏数学理论基础。Lagrange研究的是数论问题：哪些整数可以表示成两个平方数之和 ？比如5可以（），13也可以（），但3不行。Fermat曾研究过这个问题。当时谁也没想到，这些数学研究会在200多年后成为现代密码学的基石。

Eve：这听起来和格有什么关系？

Alice：关键在于，Lagrange想要系统地研究更一般的”二次型”（quadratic forms）。1775年，他发表了著名的《算术研究》（Recherches d’Arithmétique），研究形如  的二元二次型：给定整数系数 ，哪些整数  可以表示成这个形式？Lagrange做了两件开创性的工作：一是定义了二次型的”等价”概念，二是发明了”约化”算法，可以把每个等价类简化到一个标准形式。这个约化算法，本质上就是在二维格上找”好基”，后来被称为Lagrange-Gauss算法，是人类历史上第一个格约化算法[1]。

Bob：等等，你还没告诉我什么是格呢？

Alice：你说得对。想象一下整数点  在平面上的排列——所有坐标都是整数的点，像棋盘一样均匀分布。这就是最简单的格。更一般地说，格就是空间中按某种规律均匀分布的点的集合。

Bob：哦，像晶体结构那样？

Alice：完全正确。实际上物理学家研究晶体时也会用到格。Lagrange的算法处理的是二维的情况——平面上的格。他的算法能找到一组”最好的”基向量来描述这个格。

Eve：所以这就像是给格找到最简洁的表示方式？

Alice：没错。这个思想非常重要，因为同一个格可以有无穷多种不同的基。找到”好”的基，是格理论的核心问题之一。

Bob：那后来呢？Lagrange的工作有人继续吗？

Alice：当然。28年后，1801年，年仅24岁的Gauss出版了他的惊世之作《算术研究》（Disquisitiones Arithmeticae）[2]。

Bob：Gauss，我听说过这个名字，他不是发明了正态分布的那位吗？

Alice：同一个人。Gauss在这本书里系统地研究了二次型理论，把Lagrange的工作发扬光大。有趣的是，后来人们常把这个算法叫做Lagrange-Gauss算法，虽然Lagrange才是真正的发明者。

Eve：看来学术界的归功问题从古至今都存在啊。

Alice：哈哈，确实。不过Gauss的贡献也不可小觑，他的工作为后续发展奠定了坚实基础。

Bob：到这里还都是二维的，对吧？高维的格是什么时候出现的？

Alice：到了1850年代，另一位法国数学家Hermite出场了。他做了一件了不起的事：把Lagrange的约化方法推广到了任意维度的正定二次型。

Bob：任意维度，那肯定很复杂吧？

Alice：确实。Hermite给出了高维的约化算法，虽然这个算法的复杂度可能很高（在某些情况下需要指数时间），但它在理论上非常重要。更关键的是，Hermite用这个算法证明了一个深刻的不等式：对于任何  维正定二次型 ，总存在整数点  使得：

这里  是二次型的判别式[3]。

Bob：这个式子是什么意思？

Alice：简单说，就是在格中总能找到一个”不太长”的向量，它的长度被一个只依赖于维度的常数限制住了。这个常数的最优值，就叫做Hermite常数。

Eve：听起来很抽象。有什么实际意义吗？

Alice：意义重大。Hermite常数描述了格中最短向量和格的”体积”之间的关系。更有趣的是，Hermite常数和球填充问题有着深刻联系——也就是如何用相同大小的球最紧密地填充空间。

Bob：球填充，像堆橙子那样吗？

Alice：正是。在二维，最优的填充方式是蜂窝状的六边形排列。在三维，就是你说的橙子堆叠方式。但到了四维及以上，这个问题至今仍未完全解决。而Hermite常数给出了用格来填充时的最优密度。

Bob：Alice，我注意到从Lagrange到Hermite，这些都是关于”约化”的工作。有没有从不同角度研究格的？

Alice：问得好。到了19世纪末，一位德国数学家Minkowski横空出世，他开创了一个全新的领域——几何数论（Geometry of Numbers）[4]。

Bob：几何数论？听起来像是把两个领域结合起来了。

Alice：完全正确。1896年，Minkowski出版了他的著作《几何数论》，提出了一个革命性的想法：用几何方法来研究数论问题。

Eve：具体来说呢？

Alice：Minkowski最著名的成果是Minkowski定理：如果一个凸集合的体积足够大（具体说，大于  倍的格体积），那么它必然包含至少一个非零的格点。

Bob：这听起来很简单啊，为什么重要？

Alice：别小看这个定理。它看似简单，却威力无穷。比如，Minkowski用它证明了四平方和定理的推广，还解决了许多困扰数学家多年的问题。更重要的是，它给了我们一个全新的视角：把格点问题转化为几何问题。

Eve：所以这是一个思维方式的转变？

Alice：没错。Minkowski开创的这个领域，直到今天仍然是数论研究的重要工具。格密码学的许多安全性证明，都要用到Minkowski定理的各种变体。

Bob：在Minkowski之后，还有什么重要进展吗？

Alice：1877年，两位俄国数学家Korkine和Zolotarev提出了一种比Hermite约化更强的约化方法[5]。不过这个工作的重要性在19世纪末Minkowski创立几何数论后才被充分认识。

Bob：更强是什么意思？

Alice：Hermite约化只要求第一个基向量是最短的，而Korkine-Zolotarev约化（简称KZ约化）要求更严格：不仅第一个向量最短，投影后的向量也要满足类似的最短性质。

Eve：听起来计算起来会很慢？

Alice：你说对了。KZ约化在理论上很优美，但计算复杂度非常高。不过，它的思想后来启发了许多实用算法。事实上，100年后的BKZ算法（Block Korkine-Zolotarev），就是它的直接后继者。

Bob：19世纪末到20世纪初，还有其他重要人物吗？

Alice：有的。1907到1908年，俄国数学家Voronoi研究了格的另一个重要性质——Voronoi区域[6]。

Bob：Voronoi图我听说过，那个分区域的东西对吧？

Alice：对。给定一个格，Voronoi区域就是离某个格点最近的所有点的集合。Voronoi提出了基于这个概念的约化算法，在三维及以上维度很有用。

Eve：现在密码学还用这个吗？

Alice：用得不多，但Voronoi图在格的理论研究中仍然很重要。它帮助我们理解格的几何结构。

Bob：还有一个人我在资料里看到了——Blichfeldt？

Alice：好眼力。Blichfeldt在1914年证明了一个重要定理，推广了Minkowski定理[7]。Blichfeldt定理说的是：如果一个有限集合足够大，那么必然有两个点的差是格点。

Bob：这和Minkowski定理有什么区别？

Alice：Minkowski定理处理的是凸集，Blichfeldt定理处理的是一般集合。虽然听起来微妙，但在某些证明中非常有用。

Bob：进入20世纪后，格理论往哪个方向发展了？

Alice：20世纪前半叶，格理论和其他数学分支产生了深刻的交融。首先是代数数论。

Bob：代数数论？那是什么？

Alice：研究数域扩张中的整数性质。虽然Dirichlet单位定理早在1846年就提出了[8]，但它与格理论的联系直到20世纪才被充分认识到。

Eve：它和格有什么关系？

Alice：在代数数域中，”单位”形成一个格结构。Dirichlet证明了这个格的秩（维度）可以精确计算。这个定理后来成为代数数论的基石之一。

Bob：1922年，我看到了Mordell的名字[9]。

Alice：对，Louis Mordell证明了椭圆曲线的有理点群是有限生成的——这就是著名的Mordell定理，后来被推广为Mordell-Weil定理。

Bob：这也和格有关？

Alice：是的。椭圆曲线上的点可以形成所谓的”Mordell-Weil格”。而且，Mordell还在格理论本身做出了贡献：他证明了著名的Mordell不等式，这是Hermite不等式向高维情况的推广，为现代格基约化算法提供了重要的理论基础。

Eve：所以格理论在多个领域都有应用？

Alice：正是。这就是格理论的魅力所在——它是纯数学中的”万金油”。

Bob：再往后呢？

Alice：1930到1950年代，奥地利数学家Kurt Mahler做出了重要贡献。他证明了Mahler紧性定理[10]。

Bob：紧性？这是拓扑学的概念吧？

Alice：没错。Mahler证明了在适当的度量下，所有体积为1的格构成的空间是紧的——简单说，就是”有界且封闭”。

Eve：这有什么用？

Alice：这个定理保证了很多优化问题有解。比如，找体积为1的格中最短向量最长的那个格——有了紧性，我们就知道这个最优格一定存在。

Bob：到了20世纪中叶，格理论的研究重心在哪里？

Alice：Carl Ludwig Siegel等人把格理论应用到解析数论中，研究球填充问题和相关的数论问题[11]。

Bob：球填充问题还没解决吗？

Alice：在二维和三维，最优解早就知道了。但在更高维度，这个问题异常困难。直到2016年，数学家Maryna Viazovska才证明了8维的最优解是E8格；24维的最优解是Leech格。其他维度至今未知。

Eve：听起来这是个超级难题。

Alice：确实。这也说明了格理论的深度。

Bob：到20世纪中后期，格理论已经发展得很成熟了吧？

Alice：是的。这一时期的成果后来被整理成系统教材，比如Cassels的《几何数论导论》（1959）[12]和Gruber & Lekkerkerker的《Geometry of Numbers》（1987）[13]等。但格理论最激动人心的应用还在前面——密码学。

Bob：Alice，前面都是纯数学。密码学是什么时候进来的？

Alice：故事要从1982年说起。那一年，三位数学家——Arjen Lenstra、Hendrik Lenstra和László Lovász——发表了一篇改变历史的论文[14]。

Bob：他们做了什么？

Alice：他们解决了一个多项式因式分解的问题，但副产品更加重要：一个能在多项式时间内完成格基约化的算法，后来被称为LLL算法。

Eve：等等，之前的算法不是多项式时间的吗？

Alice：不是。Hermite的算法、KZ算法，在最坏情况下都需要指数时间。而LLL算法保证在多项式时间内完成，虽然输出的不是最优解，但已经”足够好”。

Bob：什么叫”足够好”？

Alice：具体来说，LLL算法找到的向量长度最多是最短向量的  倍。虽然随着维度指数增长，但对于实际应用，这个近似已经非常有用了。

Bob：我猜密码学家很快发现可以用它来攻击某些密码系统？

Eve：你猜对了，LLL算法很快成为密码分析的利器。背包密码、某些RSA变种，都在LLL的攻击下倒下了。

Bob：所以LLL既是攻击工具，也启发了新的密码设计？

Alice：完全正确。它让密码学家意识到：格问题在计算上很困难，但又有高效的近似算法。这种”困难但可控”的特性，正是构建密码系统的理想基础。

Eve：但真正的格密码还没出现，对吧？

Alice：是的。从1982到1996年，这14年是”革命前夜”。数学家们在研究格算法，密码学家们在观察，等待时机。

Bob：1996年发生了什么？

Alice：那一年，密码学迎来了双子星爆发。6月，Miklós Ajtai在STOC会议上发表了题为”Generating Hard Instances of Lattice Problems”的论文[15]。

Bob：这篇论文重要在哪里？

Alice：Ajtai做了一件前所未有的事：他证明了可以构造一个单向函数，其安全性基于格问题的最坏情况困难性。

Eve：最坏情况？这和普通的”平均情况”有什么区别？

Alice：这是个关键区别。传统密码系统如RSA，其安全性直接基于平均情况假设——假设随机选择的问题实例是困难的，但缺乏理论保证。而Ajtai证明了一个革命性结果：通过最坏情况到平均情况的归约，只要格问题在最坏情况下困难，他构造的函数在所有随机实例上都能得到安全保证。

Bob：哇，这听起来像是更强的安全保证。

Alice：没错，这是密码学史上的重大突破。Ajtai的工作开创了格密码学这个全新领域。

Bob：你说的”双子星”，另一颗是什么？

Alice：几乎同时，Hoffstein、Pipher和Silverman提出了NTRU密码系统[16]。

Bob：NTRU？

Alice：NTRU是”Number Theory Research Unit”的缩写。它是第一个实用的基于环格的公钥加密系统。

Eve：和Ajtai的工作有什么不同？

Alice：Ajtai的工作理论深刻但效率较低；NTRU则相反——它快速、紧凑，但当时缺乏严格的安全性证明。两者互补，分别代表了格密码的两个方向：理论派和实用派。

Bob：NTRU现在还在用吗？

Alice：是的。NTRU经历了20多年的安全性检验，在2017年还被提交到NIST后量子密码标准化竞赛中。虽然最终没有入选，但它的思想深刻影响了后续方案。

Bob：1996之后，格密码快速发展了吗？

Alice：是的。1997年,又有两个重要系统提出。首先是Ajtai和Dwork合作的公钥加密方案[17]。

Bob：这和Ajtai之前的工作有什么区别?

Alice：之前的是单向函数，这次是完整的公钥加密系统，且安全性归约到Unique-SVP（唯一最短向量问题）。

Eve：Unique-SVP是什么？

Alice：Unique-SVP是SVP的一个特殊情况：要求格中最短向量与第二短向量之间有足够大的间隔（gap）。这个额外的结构性质使它成为构建密码系统的良好基础。

Bob：还有另一个系统?

Alice：对，就是GGH密码系统，由Goldreich、Goldwasser和Halevi提出[18]。

Eve：GGH基于什么问题?

Alice：基于CVP（Closest Vector Problem，最近向量问题）：给定格中的一个点附近的点，找到离它最近的格点。

Bob：这个系统成功了吗?

Alice：不幸的是，1999年，Nguyen展示了一种巧妙的攻击方法[19]，能破解GGH的原始参数。虽然系统被破解了，但它的历史意义不容忽视——很多后续方案都吸取了GGH的教训。

Eve：所以早期的格密码系统并不是都成功的。

Alice：是的。这个领域在摸索中前进。但失败的尝试同样宝贵——它们告诉我们哪些路走不通。

Bob：Alice，我注意到资料里反复提到一个东西——LWE。这到底是什么?

Alice：耐心点，我们马上就要讲到格密码学最重要的转折点了。2003年，Oded Regev发表了一篇论文，引入傅里叶分析到格密码中[20]。

Bob：傅里叶分析？那不是信号处理的工具吗?

Alice：数学工具的美妙之处就在于它们的通用性。Regev发现，用傅里叶分析可以更深刻地理解格上的随机性。这为他接下来的工作铺平了道路。

Bob：接下来就是LWE了?

Alice：2005年，Regev在STOC会议上投下了一颗重磅炸弹：论文”On Lattices, Learning with Errors, Random Linear Codes, and Cryptography”[21]。

Bob：Learning with Errors……这名字听起来和格有什么关系呢？

Alice：这正是Regev天才的地方。他定义了一个看似简单的问题：给定一些带噪声的线性方程组，能否求解？

Bob：带噪声的线性方程组？能举个例子吗?

Alice：好的。假设真实的秘密是 。你得到一些方程：

其中  是已知的， 是小的误差（噪声）， 是观测值。问题是：从这些带噪声的方程中，能否恢复秘密 ?

Eve：如果没有噪声，这就是普通的线性方程组，很容易解。噪声使它变难了?

Alice：正是。Regev证明了一个惊人的结果：在量子计算机的帮助下，求解LWE问题和求解某些格问题一样困难。

Bob：等等，”量子计算机的帮助下”？这是什么意思?

Alice：Regev的归约使用了量子算法。简单说，如果你有一个能高效求解LWE的算法，那么用量子计算机可以把它转化成求解格上最短向量问题（SVP）的算法。反过来说，如果格上的SVP困难，那么LWE也困难。

Eve：所以LWE继承了格问题的困难性，但表述更简洁?

Alice：完全正确。而且LWE的代数结构非常适合构造密码系统。Regev在同一篇论文里就给出了基于LWE的公钥加密方案。

Bob：为什么说LWE是转折点?

Alice：因为它具有三个完美的性质：

1. 简洁性：定义简单，容易理解和实现
2. 通用性：可以构造各种密码原语——加密、签名、IBE等
3. 安全性：有严格的归约到格问题的最坏情况

几乎所有现代格密码方案都基于LWE或其变种。

Eve：所以LWE之于格密码，就像RSA之于公钥密码?

Alice：很好的类比。LWE奠定了格密码的基石。

Bob：LWE解决了”硬问题”，但要构造高级的密码系统，还需要什么?

Alice：好问题。2006年，Micciancio和Regev改进了最坏到平均的归约技术[22]，使用更自然的高斯测度，让理论更优美。

Bob：然后呢?

Alice：2008年，Gentry、Peikert和Vaikuntanathan三人组发表了一篇名为”Trapdoors for Hard Lattices”的论文[23]。

Eve：陷门？这听起来像是后门。

Alice：在密码学中，”陷门”（Trapdoor）是个中性词，指的是拥有特殊信息的人可以轻松完成某个任务，而没有这个信息的人则很难完成。

Bob：就像有钥匙和没钥匙的区别?

Alice：完美的比喻。GPV（三位作者姓氏首字母）的突破在于：他们展示了如何为格构造”陷门”。具体来说，可以生成一个看似随机的格，但只有你知道一个秘密的”好基”，用这个好基可以快速解决该格上的CVP。

Eve：这有什么用？

Alice：用处太大了。有了陷门技术，GPV构造了：

• 高效的数字签名方案
• 基于身份的加密（IBE）
• 抗选择密文攻击的加密方案

Bob：身份基加密是什么？

Alice：IBE允许你用任意字符串（比如email地址）作为公钥。想象一下：你可以用”[email protected]”作为Bob的公钥直接加密，而不需要事先获取他的公钥证书。

Bob：GPV是不是让格密码一下子功能强大了很多？

Alice：正是。在GPV之前，格密码还主要停留在基础的公钥加密。GPV之后，几乎所有你能想到的密码原语都可以用格来构造了。

Bob：2008年还有其他进展吗?

Alice：有的。同年，Peikert和Waters提出了有损陷门函数（Lossy Trapdoor Functions）[24]。

Bob：有损？这是什么意思?

Alice：这是一种特殊的陷门函数，有两种模式：

1. 单射模式：函数是一一对应的，有陷门可以求逆
2. 有损模式：函数丢失信息，无法求逆，且两种模式计算上不可区分

Eve：这设计的很巧妙啊，在安全性证明中，可以切换到有损模式吗？

Alice：完全正确。这提供了一种新的证明范式，让某些安全性证明变得更简洁。

Bob：Alice，我听说2009年发生了密码学史上的大事件?

Alice：你说的是Craig Gentry的论文吧，那确实是密码学的一个里程碑时刻[25]。

Bob：全同态加密（FHE）？这是什么?

Alice：想象你把数据加密后发送给云服务器，服务器在不解密的情况下对加密数据进行计算，然后把加密的结果返回给你。你解密后得到的，正是对原始数据计算的结果。

Bob：等等，这怎么可能？加密的数据不就是乱码吗，怎么计算?

Alice：这正是FHE的神奇之处。它支持在密文上进行加法和乘法操作，且结果解密后等于明文的加法和乘法。

Eve：听起来像魔法。有什么实际应用?

Alice：太多了。想象这些场景：

• 在加密的医疗数据上进行统计分析，不泄露隐私
• 在加密的金融数据上进行机器学习
• 在加密的投票数据上进行计票

Bob：这么强大，为什么之前没人做到?

Alice：因为太难了。自1978年Rivest、Adleman和Dertouzos提出这个概念后，30年来无数密码学家尝试都失败了。Gentry是第一个成功的人。

Bob：他怎么做到的?

Alice：Gentry的方案基于理想格（Ideal Lattices）——一种具有代数结构的特殊格。关键创新是自举（Bootstrapping）技术。

Bob：自举是什么?

Alice：问题在于，每次对密文进行运算，都会积累”噪声”。噪声太大，密文就无法正确解密了。Gentry的想法是：用FHE本身来”清理”噪声。

Eve：用FHE来帮助FHE？这不是循环论证吗?

Alice：听起来是，但Gentry证明了只要方案能对自己的解密电路进行同态运算，就能实现自举，从而支持无限次运算。

Bob：哇，这个想法太巧妙了。

Alice：是的。虽然第一代FHE方案非常慢，但它证明了原理上的可行性。后续的研究就是如何提高效率。

Bob：Gentry的FHE太慢了，后来有改进吗?

Alice：当然。2010年，Lyubashevsky、Peikert和Regev三位大神联手，提出了Ring-LWE[26]。

Bob：Ring-LWE和LWE有什么区别？

Alice：LWE处理的是普通向量，Ring-LWE处理的是多项式环中的元素。简单说，就是把问题从向量空间搬到了多项式空间。

Eve：这样做有什么好处?

Alice：效率。一个环元素可以编码整个向量的信息，公钥和密文的大小大幅减小。而且，环上的乘法可以用FFT（快速傅里叶变换）高效计算。

Bob：听起来太好了，有代价吗?

Alice：代价是安全假设更强。Ring-LWE的困难性依赖于特殊的代数结构，理论上攻击面比普通LWE更大。但实际上，经过十多年的研究，Ring-LWE仍然坚挺。

Bob：Ring-LWE对FHE有帮助吗?

Alice：巨大帮助。2011年，Brakerski和Vaikuntanathan基于标准LWE构造了新的FHE方案[27]，效率大幅提升。

Bob：然后就是BGV了?

Alice：对。2011到2012年，Brakerski、Gentry和Vaikuntanathan提出了BGV方案[28]，这是第二代FHE的代表作。

Bob：什么是”第二代”？

Alice：第二代FHE的特点是分层同态（Leveled FHE）——只要事先知道计算的深度，就可以不用自举，大幅提高效率。

Eve：这意味着什么?

Alice：对于深度有限的电路（比如大多数实际应用），BGV可以跑得很快。这让FHE从理论走向了实用。

Bob：还有其他变种吗?

Alice：2012年，Langlois和Stehlé提出了Module-LWE[29]，在Ring-LWE和LWE之间取得平衡。

Bob：Module-LWE是什么意思?

Alice：想象你有一个Ring-LWE的向量——既有环的代数结构，又有向量的灵活性。这就是Module-LWE。它比Ring-LWE更安全（不依赖单个环），比LWE更高效。

Eve：后来的标准方案用的就是这个?

Alice：没错。CRYSTALS-Kyber和CRYSTALS-Dilithium都基于Module-LWE。

Bob：格签名方案呢?

Alice：2013年，Ducas等人提出了BLISS签名方案[30]，使用双峰高斯分布进行拒绝采样，大幅提高了签名效率。

Bob：双峰高斯是什么?

Alice：就是有两个峰的高斯分布。这个技巧让拒绝采样的接受率更高，签名速度更快。BLISS是第一个真正实用的格签名方案。

Bob：到2016年，格密码发展了十年。有人做总结吗?

Alice：Chris Peikert写了一篇权威综述：”A Decade of Lattice Cryptography”[31]，覆盖了2005到2015年的主要进展。

Bob：这篇文章重要吗?

Alice：非常重要。它是学习格密码的必读材料。Peikert系统地讲解了：

• SIS（Short Integer Solution）和LWE两大困难问题
• Ring-LWE和各种变种
• FHE的发展历程
• 格签名、IBE等高级原语

Eve：所以2016年是一个总结点，也是新起点？

Alice：正是。因为同年，NIST启动了后量子密码标准化进程。

Bob：NIST为什么要搞后量子密码标准化?

Alice：因为量子计算机的威胁。1994年，Shor证明了量子计算机可以快速分解大整数和计算离散对数[32]。这意味着RSA、ECC等现有公钥密码系统将全部失效。

Bob：量子计算机真的能造出来吗?

Alice：虽然大规模量子计算机还没出现，但技术在稳步进步。更重要的是，加密数据可能被存储几十年——如果未来量子计算机问世，过去截获的数据就能被解密。

Eve：所以需要提前准备抗量子的密码?

Alice：正是。2016年，美国NIST（国家标准与技术研究院）启动了后量子密码标准化进程[33]，邀请全球密码学家提交方案。

Bob：有哪些方案参赛?

Alice：第一轮收到了69个提交。其中基于格的方案有：

• CRYSTALS-Kyber（密钥封装）
• CRYSTALS-Dilithium（签名）
• FALCON（签名）
• NTRU（加密）
• 还有很多其他方案

Bob：FALCON是什么?

Alice：FALCON（Fast-Fourier Lattice-based Compact Signatures over NTRU）是2017年由Fouque等人提出的[34]。它基于NTRU格，使用快速傅里叶采样技术，签名非常紧凑。

Eve：为什么需要这么多方案?

Alice：因为不同应用有不同需求：

• Kyber优化了密钥交换的速度
• Dilithium平衡了签名大小和速度
• FALCON的签名最小，适合带宽受限的场景

Bob：CRYSTALS是什么意思?

Alice：CRYSTALS是”Cryptographic Suite for Algebraic Lattices”的缩写。它包含两个方案：

1. Kyber（KEM，密钥封装机制）：用于密钥交换
2. Dilithium（签名）：用于数字签名

两者都基于Module-LWE[35]，参数设计经过精心优化。

Bob：竞赛持续了多久?

Alice：整整6年。经过三轮筛选：

• 2019年1月：公布第二轮候选
• 2020年7月：公布决赛选手+ 替补
• 2022年7月：公布获胜者[36]

Bob：谁赢了？

Alice：共有四个算法获胜：

• CRYSTALS-Kyber（密钥封装）
• CRYSTALS-Dilithium（数字签名）
• FALCON（数字签名）
• SPHINCS+（数字签名）

Eve：SPHINCS+不是格密码吧？

Alice：对，SPHINCS+基于哈希函数，采用完全不同的数学基础。它提供了多样性——如果格密码出现问题，还有非格方案作为替代。

Eve：所以格密码大获全胜？

Alice：可以这么说。四个获胜方案中，三个基于格。这证明了格密码的成熟度和安全性。

Bob：标准最终发布了吗？

Alice：是的。2024年8月13日，NIST正式发布了三个FIPS标准[37]：

• FIPS 203：ML-KEM（Module-Lattice-Based Key-Encapsulation Mechanism）

• 基于CRYSTALS-Kyber

• 三个安全级别：ML-KEM-512、ML-KEM-768、ML-KEM-1024

• FIPS 204：ML-DSA（Module-Lattice-Based Digital Signature Algorithm）

• 基于CRYSTALS-Dilithium

• 成为官方数字签名标准

• FIPS 205：SLH-DSA（Stateless Hash-Based Digital Signature Algorithm）

• 基于SPHINCS+

• 采用哈希函数而非格，提供技术多样性

Eve：Alice，我听说我国在后量子密码标准化方面也有自己的进展？

Alice：说得对。几乎与NIST同步，中国密码学会在2018年6月就启动了全国密码算法设计竞赛，征集后量子密码算法[38]。

Bob：那时候NIST第一轮才刚开始呢。我国的进展如何？

Alice：到2019年2月，共有60个算法通过形式审查：22个分组算法和38个公钥算法。经过公开评议和专家评选，2019年10月公布了第二轮入选名单——10个分组算法和14个公钥算法[39]。

Eve：这14个公钥算法都是基于格的吗？

Alice：大部分是。让我给你们介绍几个有代表性的：

公钥加密/密钥封装算法：

• LAC系列（LAC.PKE和LAC.KEX）：基于环LWE（R-LWE）问题
• Aigis-enc：基于模LWE和模SIS（M-LWE/M-SIS）
• AKCN-MLWE和AKCN-E8：基于模LWE的通用密钥封装方案
• TALE：基于模LWE的公钥加密算法
• SCloud：基于标准LWE的加密与密钥封装
• Piglet-1：比较特别，基于秩距离模码问题，不是格密码

数字签名算法：

• Aigis-sig：与Aigis-enc同族，基于M-LWE/M-SIS
• 木兰：基于M-LWE/M-SIS的高效签名方案
• FatSeal：基于R-LWE的高效签名
• PKP-DSS：基于排列核问题，也不是格密码

Bob：看来我国的方案也是以格密码为主啊。

Alice：没错。不过还有个有趣的插曲——当时还有一个基于超奇异同源（SIDH）的密钥交换协议SIAKE。

Eve：等等，SIDH不是在2022年7月被Castryck和Decru破解了吗？

Alice：正是。2022年7月30日，Castryck和Decru发布了一篇震惊密码学界的论文，在多项式时间内破解了SIDH和NIST第四轮候选算法SIKE[41]。SIAKE基于相同的判定SIDH假设，因此也受到影响。这再次说明了密码学研究的残酷性——今天看起来安全的方案，明天可能就被攻破。所以我们需要持续评估和改进。

Bob：这个竞赛后来有结果吗？

Alice：竞赛在2019年结束后，相关算法继续接受公开评议和实践检验。更重要的是，2025年2月5日，商用密码标准研究院发布公告，启动新一轮面向全球的密码算法征集活动[40]。

Eve：新一轮？这么快就开始了？

Alice：量子威胁日益临近，标准化工作刻不容缓。新一轮征集涵盖公钥密码、杂凑算法和分组密码，要求算法能够同时抵抗经典和量子攻击。这次强调国际合作，欢迎全球密码学者参与。

Bob：看来各国都在为后量子时代做准备。

Bob：Alice，我们从1775年的Lagrange一路走到了2025年的全球密码标准化。这250年的旅程太精彩了。

Alice：是啊。从纯数学的二次型研究，到Minkowski开创的几何数论，再到LLL算法打开计算机科学的大门，最后到格密码成为后量子时代的基石——格理论的故事堪称数学与应用完美结合的典范。

Bob：现在格密码已经标准化了，是不是意味着攻击者没戏了？

Eve：哈哈，永远别这么想。密码学就是矛与盾的较量。虽然格密码经受了考验，但研究永不停止。也许某天会发现新的攻击方法，或者量子计算机带来新的威胁。

本次对话，就这么愉快的结束了，接下来，Alice，Bob，和Eve又会遇到什么故事呢，且听下回分解。快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见~

参考资料

[1] Lagrange, J.L. (1775). “Recherches d’arithmétique”. Nouveaux Mémoires de l’Académie de Berlin.

[2] Gauss, C.F. (1801). Disquisitiones Arithmeticae.

[3] Nguyen, P.Q. “Hermite’s Constant and Lattice Algorithms”. https://www.di.ens.fr/~pnguyen/Nguyen_HermiteConstant.pdf

[4] Minkowski, H. (1896). Geometrie der Zahlen. Wikipedia: https://en.wikipedia.org/wiki/Geometry_of_numbers

[5] Korkine, A., Zolotarev, E. (1877). “Sur les formes quadratiques positives”. Mathematische Annalen 11 (2): 242–292. Wikipedia: https://en.wikipedia.org/wiki/Korkine–Zolotarev_lattice_basis_reduction_algorithm

[6] Voronoi, G.F. (1907-1908). Voronoi reduction theory.

[7] Blichfeldt, H.F. (1914). Blichfeldt’s theorem. Wikipedia: https://en.wikipedia.org/wiki/Blichfeldt’s_theorem

[8] Dirichlet, P.G.L. (1846). Unit theorem. Wikipedia: https://en.wikipedia.org/wiki/Dirichlet’s_unit_theorem

[9] Mordell, L.J. (1922). Mordell-Weil theorem. Wikipedia: https://en.wikipedia.org/wiki/Mordell–Weil_theorem

[10] Mahler, K. (1930s-1950s). Mahler compactness theorem.

[11] Siegel, C.L. Applications to analytic number theory.

[12] Cassels, J.W.S. (1959). An Introduction to the Geometry of Numbers. Springer: https://link.springer.com/book/10.1007/978-3-642-62035-5

[13] Gruber, P.M., Lekkerkerker, C.G. (1987). Geometry of Numbers (2nd edition).

[14] Lenstra, A., Lenstra, H., Lovász, L. (1982). “Factoring polynomials with rational coefficients”. Wikipedia: https://en.wikipedia.org/wiki/Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm

[15] Ajtai, M. (1996). “Generating Hard Instances of Lattice Problems”. STOC 1996. https://eccc.weizmann.ac.il/eccc-reports/1996/TR96-007/

[16] Hoffstein, J., Pipher, J., Silverman, J.H. (1996). “NTRU: A Ring-Based Public Key Cryptosystem”. https://www.ntru.org/f/hps98.pdf

[17] Ajtai, M., Dwork, C. (1997). “A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence”. STOC 1997.

[18] Goldreich, O., Goldwasser, S., Halevi, S. (1997). “Public-key cryptosystems from lattice reduction problems”. CRYPTO 1997. Wikipedia: https://en.wikipedia.org/wiki/GGH_encryption_scheme

[19] Nguyen, P.Q. (1999). “Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97”. CRYPTO 1999.

[20] Regev, O. (2003). “New Lattice Based Cryptographic Constructions”. STOC 2003. https://arxiv.org/abs/cs/0309051

[21] Regev, O. (2005). “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography”. STOC 2005. https://cims.nyu.edu/~regev/papers/qcrypto.pdf

[22] Micciancio, D., Regev, O. (2006). “Worst-case to Average-case Reductions based on Gaussian Measures”. https://cims.nyu.edu/~regev/papers/average.pdf

[23] Gentry, C., Peikert, C., Vaikuntanathan, V. (2008). “Trapdoors for Hard Lattices and New Cryptographic Constructions”. STOC 2008. https://eprint.iacr.org/2007/432

[24] Peikert, C., Waters, B. (2008). “Lossy Trapdoor Functions and Their Applications”. STOC 2008.

[25] Gentry, C. (2009). “Fully Homomorphic Encryption Using Ideal Lattices”. STOC 2009. PhD Thesis: https://crypto.stanford.edu/craig/craig-thesis.pdf

[26] Lyubashevsky, V., Peikert, C., Regev, O. (2010). “On Ideal Lattices and Learning with Errors over Rings”. EUROCRYPT 2010. https://eprint.iacr.org/2012/230.pdf

[27] Brakerski, Z., Vaikuntanathan, V. (2011). “Efficient Fully Homomorphic Encryption from (Standard) LWE”. https://eprint.iacr.org/2011/344.pdf

[28] Brakerski, Z., Gentry, C., Vaikuntanathan, V. (2012). “(Leveled) Fully Homomorphic Encryption without Bootstrapping”. https://eprint.iacr.org/2011/277.pdf

[29] Langlois, A., Stehlé, D. (2012). “Worst-case to Average-case Reductions for Module Lattices”. https://perso.ens-lyon.fr/damien.stehle/downloads/MSIS.pdf

[30] Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V. (2013). “Lattice Signatures and Bimodal Gaussians”. CRYPTO 2013. https://eprint.iacr.org/2013/383.pdf

[31] Peikert, C. (2016). “A Decade of Lattice Cryptography”. https://eprint.iacr.org/2015/939.pdf

[32] Shor, P. (1994). “Algorithms for quantum computation: discrete logarithms and factoring”. FOCS 1994.

[33] NIST Post-Quantum Cryptography Standardization. https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization

[34] Fouque, P.A., et al. (2017). “Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU”. https://falcon-sign.info/

[35] CRYSTALS suite (Module-LWE). Wikipedia (Kyber): https://en.wikipedia.org/wiki/Kyber

[36] NIST (2022). “NIST Announces First Four Quantum-Resistant Cryptographic Algorithms”. https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms

[37] NIST (2024). “NIST Releases First 3 Finalized Post-Quantum Encryption Standards”.

• https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards
• FIPS 203: https://csrc.nist.gov/pubs/fips/203/final
• FIPS 204: https://csrc.nist.gov/pubs/fips/204/final

[38] 中国密码学会 (2018). “关于举办全国密码算法设计竞赛的通知”. https://sfjs.cacrnet.org.cn/site/content/309.html

[39] 中国密码学会 (2019). “全国密码算法设计竞赛第二轮入选名单”. https://sfjs.cacrnet.org.cn/site/term/77.html

[40] 商用密码标准研究院 (2025). “关于开展新一代商用密码算法征集活动的公告”. https://www.niccs.org.cn/symmbzyjy/tzgg/pc/content/1937422988373135360/content_1937422988373135360.html

[41] Castryck, W., Decru, T. (2022). “An efficient key recovery attack on SIDH”. Cryptology ePrint Archive, Paper 2022/975. https://eprint.iacr.org/2022/975

---

免责声明：

本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。

任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。

本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。

本文转载自：Coder小Q Litt1eQ Litt1eQ《【杂谈】格密码发展的时光之旅》