文章总结： 文档介绍格同构问题（LIP）作为后量子密码新基础，阐述其利用随机旋转消除结构弱点并实现安全归约的原理。文中详述了基于LIP的零知识认证、KEM及签名方案构造，分析优质格的性能优势，指出寻找兼具对偶性质与解码效率的格是核心开放问题，有望突破LWE效率瓶颈。 综合评分： 85 文章分类： 安全建设,解决方案

---

【密码学】格同构问题：后量子密码学的新困难性基础

原创

Litt1eQ Litt1eQ

Coder小Q

2026年3月12日 08:31 山东

【密码学】格同构问题：后量子密码学的新困难性基础

BBob

Alice，我最近在看后量子密码学的资料，除了 LWE 和 NTRU，还有一个叫”格同构问题”（LIP）的东西，听起来挺神秘的，你能给我讲讲吗？

AAlice

当然，不过得先把”格”说清楚。你知道格（Lattice）是什么吗？

BBob

大概知道，空间里一堆按规律排布的点？

AAlice

对，更准确地说，给定  个线性无关的向量 ，格就是它们所有整数线性组合的集合：

矩阵  叫做格的基（basis）。

BBob

这和线性代数里的基差不多嘛

AAlice

有一个关键区别：系数  只能是整数，不能是任意实数。正因如此，同一个格可以有很多种完全不同的基来表示，就像同一块坐标纸，可以用不同方向的两把直尺来描述，格点完全一样，但基看起来截然不同。

EEve

而这正是问题变得有趣的地方——换一组基，同一个格看起来就面目全非了。密码学家们惦记这件事很久了。

BBob

那”格同构”是什么意思？

AAlice

两个格 和是同构的，是说存在一个正交变换（旋转或翻转），使得。几何上它们长得一模一样，只是摆放角度不同。格同构问题（LIP）就是：给定两个格的基和，找到正交矩阵和幺模矩阵（行列式为 的整数矩阵），使得：

BBob

为什么同时出现  和  两个变换？

AAlice

这是关键。 负责在同一个格内换基， 负责旋转整个格。单独处理任何一个都相对容易——判断两组基是否生成同一个格（即找  使得 ）可以用 Hermite 标准型（HNF）算法，”对齐”旋转在格已知的情况下只是矩阵运算 。但两者同时叠加，你不知道先解哪个，彼此之间完全耦合，问题的难度就爆了。

EEve

说得对。所有已知的 LIP 攻击算法，归根到底都要先找格里的短向量（SVP）。而 SVP 在量子计算机面前依然是困难的——Shor 算法依赖的是特定代数结构（离散对数、因子分解），SVP 没有这种结构，所以 Shor 对它完全无效；目前已知最好的量子 SVP 算法也只有有限的加速，远达不到 Shor 那样的指数级突破，格密码因此被认为是抗量子的。

BBob

那它和密码学有什么关系？

AAlice

密码学家有个古老的想法：选一个解码能力极强的”好”格作为私钥，把它伪装成一个看起来很”烂”的格作为公钥。知道私钥的人能高效解码，外人只看到一堆乱向量。这正是 McEliece 在纠错码[1]上做成功的事。但在格上，三十多年都没成功。

BBob

为什么在格上一直没成功？

AAlice

因为以前的方案只用了一种极特殊的格同构——坐标置换。把坐标轴顺序打乱，确实得到一个不同的格，但攻击者可以利用这种置换结构，根本不需要解 LIP，只要猜几个坐标就能重建密钥。以 Chor-Rivest 方案为例，Brickell 的攻击完全没有用格约化算法，说明方案暴露了额外结构，给了攻击者走捷径的机会。

EEve

真正好的方案应该让攻击者的唯一出路是解 SVP，没有任何别的门路。

AAlice

而 2022 年 Ducas 和 van Woerden 的论文[2] 给出了正确的框架：使用整个正交群  里的随机旋转，而不是区区坐标置换。随机旋转把坐标系彻底打乱，所有基于坐标系结构的攻击技巧全部失效。

BBob

好，那具体怎么做密码？

AAlice

先介绍一个关键简化。与其处理浮点正交矩阵 ，可以用格基矩阵 对应的 Gram 矩阵，也叫二次型：

两个格同构，当且仅当它们的二次型满足 （ 是幺模整数矩阵）。这样实数正交矩阵就消失了，LIP 变成了纯粹的整数运算，方便得多。

BBob

所以正交变换  其实被”吸收”进 Gram 矩阵里了？

AAlice

对，从二次型的角度看，两个格等价就只剩整数变换 ——正交矩阵完全从方程里消失。LIP 因此有两个版本：搜索版（sLIP）要找到这个 ；区分版（LIP）给你一个 ，让你判断它来自等价类  还是 。

EEve

区分版是密码应用的核心。设计 LIP 的挑战是：选两个格，让它们的所有”廉价特征”完全相同——行列式、最大公因子、奇偶性、有理数等价类、-进整数等价类（整体称为格的算术指纹，其中后两项 和  合称为格的”genus”）——让攻击者唯一的区分手段只有找短向量。

BBob

那从最坏情形到平均情形的归约是怎么回事？

AAlice

密码系统的公钥是随机生成的，安全性依赖平均情形的困难性。Ducas 和 van Woerden 用离散高斯采样解决了这个问题。离散高斯分布把连续高斯限制在整数格上：

其中 ，参数  控制宽度。

BBob

这个分布和选哪个基矩阵代表格有关吗？如果换了代表元，分布会变吗？

AAlice

恰恰不会——这是这个构造最精妙的地方。对等价类  定义分布 ：从当前  采样若干高斯短向量，用这些向量重构出等价类里一个”随机”代表元。可以证明这个分布只依赖等价类本身，和选哪个代表元无关。

由此可以证明：当  足够大时，平均情形 sLIP 和最坏情形 sLIP 等价[3]。

EEve

从攻击者角度，这意味着我碰到的每一个公钥实例，本质难度都和最难情形一样，指望运气遇到简单实例是没有用的。

BBob

理论基础说好了，具体协议呢？先说最简单的。

AAlice

最简单是零知识身份认证，基于 sLIP。私钥是幺模矩阵 ，公钥是 ，其中 。证明者向验证者证明”我知道 “，但不透露  本身，协议分三步：

第一步，证明者采样 ，连同  满足 ，把  发给验证者。

第二步，验证者抛硬币 ，发给证明者。

第三步，证明者回应 ，验证者检查 。

BBob

等等，为什么这三步能证明知道 ？

AAlice

当  时，，验证 ：

如果有人能同时对 和给出合法回应和，那就是到 的同构，也就直接破解了 sLIP。

EEve

零知识性来自：协议里传递的只有 （固定分布 ）和 （均匀随机的同构）。不知道  也能模拟这两件事，所以验证者学不到任何关于  的信息。

BBob

妙，那密钥封装（KEM）是怎么做的？

AAlice

KEM 基于 LIP。选一个解码半径的好格，是最短非零向量的长度。密钥生成：采样和变换使得，公钥是，私钥是。

封装：发送方采样误差  满足 ，发出 ，密钥  从  提取。

解封装：用私钥  把问题变换到  的坐标系，调用高效解码恢复 ，再提取 。

BBob

安全性怎么证？

AAlice

另外构造一个格 ，算术指纹和完全一样，但含有一个密集子格。在LIP 困难的前提下，攻击者没法区分公钥来自还是。如果公钥来自，同一个附近有指数多个候选的，密钥 在统计上不可恢复。

EEve

从攻击者角度，密集子格是个绝妙设计。一旦公钥是”坏”格伪装，我找到的所有”最近向量”都只是噪声，根本没法恢复真正的密钥。

BBob

签名方案呢？

AAlice

签名和 KEM 思路有点”对偶”。同样选好格 ，但要求能以小高斯宽度  做离散高斯采样（而不是解码）。公钥 ，私钥 。

签名时：对消息  哈希得目标 ，用私钥在  坐标系里对  附近高斯采样得 ，变换回得签名 。

BBob

那怎么验证？

AAlice

验证者只需检查 ——签名离目标足够近就通过。安全性同样依赖 LIP：如果把公钥换成”对偶格里有密集子格”的坏格，随机目标  附近根本没有格点，伪造签名在统计上不可能。

EEve

我注意到 KEM 用的是原格的密集子格，签名用的是对偶格的密集子格——这个对偶性很精巧。这也意味着，格  需要既有好的解码/采样性质，又有好的对偶性质，要求其实挺苛刻的。

BBob

那现在有没有特别好的格可以用？

AAlice

有，但不完美。衡量一个格”好”的程度，可以用它的最短向量与 Minkowski 界的比值 ——对于体积为 1 的格：

 越小，格越接近理论最优。

BBob

现有的格表现怎么样？

AAlice

平凡格 的，安全性对应大约近似因子的 SVP。Barnes-Wall 格把三个因子（、解码因子、对偶因子）都降到，这是实质性的改进。Chor-Rivest 格和 Barnes-Sloane 格理论上能达到，但它们的对偶格太差，仍是，目前还不能直接用。

EEve

格越特殊，攻击也越难。论文给出了一批挑战格，看看它们的亲吻数（与最短向量等长的向量数量）——

| 格 | 维数 | 亲吻数 | | — | — | — | | Leech 格 | 24 | | | | 72 | | | （Barnes-Wall） | | |

BBob

这亲吻数也太大了……

EEve

正是。亲吻数越大，同构搜索的候选数就越多，破解 sLIP 所需的时间可以达到 ，比指数级还要高[4]。

BBob

LIP 和现在主流的 LWE 比起来怎么样？

AAlice

LWE 本质上用的是最平凡的格——，最短向量就是坐标轴方向，解码性能相当平庸。LIP 的目标是：用真正”好”的格，让方案在相同安全级别下有更短密文、更高效率。这篇论文提供了第一个正式的框架，让任何好格都可以”插进来”使用。

EEve

不过，LIP 的密码分析历史比 LWE 短得多，经历的考验还不够多。所有已知攻击都只能通过找短向量来打 LIP，没发现别的门路。但这并不代表没有，也许某些特殊格还有没被发现的弱点。LWE 也是经历了二十年的分析，才逐渐建立起大家的信任。

BBob

那接下来最核心的开放问题是什么？

AAlice

最重要的是：能不能找到一个格，既能高效解码到接近 Minkowski 界（），同时对偶格也同样优秀（）？如果有，KEM 方案的安全性近似因子就能从  降到 ，这会是一个比现有 LWE 方案强得多的安全基础。

BBob

还有其他方向吗？

AAlice

还有一个有趣的方向是模 LIP（Module-LIP），类似于从 LWE 发展出 Module-LWE 的思路——给格加上代数结构，让密钥更短，方案更高效。

EEve

看来属于我的好日子还没到头。格密码从 LWE 到现在走了近二十年，LIP 的旅程才刚刚起步。在找到理想的”好格”之前，我还有时间慢慢研究它的每一个细节。

BBob

好，让我来总结一下：LIP 利用了”同一个格在不同坐标描述下看起来完全不同”这件事，把这种几何模糊性变成了密码学的安全基础，而且可以利用不同的”好格”来不断提升安全性和效率——说得对吗？

AAlice

很到位。更形式地说，安全性来自双商空间  的困难性——同时模去了连续的旋转变换和离散的换基变换，让问题既无法用连续分析处理，也无法用离散算法处理。这是格密码学里一个全新的困难性来源。

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

参考资料

[1] Robert J. McEliece. “A Public-Key Cryptosystem Based on Algebraic Coding Theory.” Deep Space Network Progress Report

[2] Léo Ducas and Wessel van Woerden. “On the Lattice Isomorphism Problem, Quadratic Forms, Remarkable Lattices, and Cryptography.” In dvances in Cryptology – EUROCRYPT 2022. IACR Cryptology ePrint Archive, Report 2021/1332, 2021. https://eprint.iacr.org/2021/1332

[3] Daniele Micciancio and Oded Regev. “Worst-Case to Average-Case Reductions Based on Gaussian Measures.” SIAM Journal on Computing

[4] Ishay Haviv and Oded Regev. “On the Lattice Isomorphism Problem.” In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)

---

免责声明：

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

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

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

本文转载自：Coder小Q Litt1eQ Litt1eQ《【密码学】格同构问题：后量子密码学的新困难性基础》