基于格的零知识系统：专访Vadim Lyubashevsky

原播客：https://zeroknowledge.fm/podcast/359/

编译：Kurt Pan

Anna Rose：
欢迎收听 Zero Knowledge，我是主持人 Anna Rose。这档 Podcast 旨在探索零知识研究与去中心化网路的最新进展，以及那些有望改变我们线上互动与交易方式的新范式。

本週节目中，Nico 与我邀请到了 IBM Research 安全研究组的密码学家 Vadim Lyubashevsky，一同深入讨论基于格（lattice）的零知识系统。我们会聊到 Vadim 最初如何踏入这个领域、他研究的经过、格理论的演变，以及目前基于格的零知识系统最前沿的成果。

我们将了解，为何直接把格映射进现有 SNARK 架构会遇到挑战、格与现有最佳化技术之间的差异，以及研究人员为了打造有趣且高效的 SNARK 系统，往往要设计专属于格的全新技术。

Anna Rose：
节目正式开始。今天，Nico 和我邀请到 IBM Research 欧洲安全组的密码学家 Vadim Lyubashevsky。欢迎上节目，Vadim！

Vadim Lyubashevsky：
谢谢 Anna、Nico，能来到这里很高兴。

Anna Rose：
Nico，你好吗？

Nico Mohnblatt：
大家好，一切都很好，谢谢。

Anna Rose：
Nico，我们想做「格」这集已经很久了。去年年末的年终特辑里，我们还预告过要聊这主题。

Nico Mohnblatt：
确实。

Anna Rose：
花了四个月，我们终于排上日程。其实在我去年十一月访谈 Dan Boneh 的那集里，他简短提到近期基于格的 SNARK 研究，也引起了我们的兴趣。

所以 Vadim，能请你来聊这个主题我很兴奋。

Vadim Lyubashevsky：
很高兴能回答你们的所有问题。

Anna Rose：
太好了。那我们先从你的背景谈起吧：当初是什麽契机让你对密码学产生兴趣？又是怎麽被「格」这个方向吸引？

Vadim Lyubashevsky：
如果你期待我说自己热爱隐私、从小立志当密码学家——很抱歉并没有那麽浪漫。我只是以研究生身分来到 UC San Diego，碰巧遇见专精格密码学的教授 Daniele Micciancio，于是就开始做这块研究。

后来我发现自己确实很喜欢这领域，尤其偏好较偏实务的部分；当时还有许多理论与实作层面的开放问题，整个领域也相对年轻，我就一路做了下来。

Anna Rose：
很酷。格本身是个比密码学更广的数学分支，密码学只是它的一个应用。能否简述格理论在更早期、甚至在与密码学结合之前的历史？

Vadim Lyubashevsky：
当然。若追溯到数学领域，大概是二十世纪初，Minkowski 开创了「数论几何」（Geometry of Numbers）。他发现，某些具有高度代数性的数域其实能用几何方法来研究，从而引发了数学家的关注。

到了 1980 年代，格开始成为密码分析工具。着名的 LLL 演算法（由 Lenstra、Lenstra 与 Lovász 提出）用来攻击部分当时提出的加密系统；直到今天，LLL 及其后续演算法仍被用来攻击像 RSA 之类的系统。

进入 1990 年代，格开始被用来「做」密码，而不是只拿来「破」密码。Ajtai 首先证明最短向量问题（SVP）属于 NP-hard，并指出某些随机分佈与格问题同样困难，这让许多人开始将格用于构建密码方案。

Anna Rose：
也就是说，格最初用来攻击系统，后来人们意识到其中某些困难特性反而可用来「建造」系统。

Vadim Lyubashevsky：
没错。它既能当攻击工具，又能成为建立安全性的基础。

Nico Mohnblatt：
这跟我们在配对（pairings）领域看到的历程很像：一开始是攻击离散对数系统的手段，后来则成为建构新方案的工具。

Vadim Lyubashevsky：
对，类似的情况在同源（isogeny）密码中也发生了：他们的签章演算法便部分源自对早期加密方案的攻击。

Anna Rose：
那麽，在学术生涯之后，你为何选择加入 IBM？

Vadim Lyubashevsky：
除了个人搬到苏黎世的因素外，IBM 研究院的环境结合了学术自由与工业界对「五到十年内应用」的期待，我很享受这种兼具前瞻与实务的研究氛围。

Nico Mohnblatt：
这也呼应了 IBM 近年在 NIST 标准化中的努力吧？

Vadim Lyubashevsky：
没错。我们与多位合作伙伴在 NIST 后量子密码标准化（2016 年起）一开始就提交了多个演算法，最终有两个基于格的方案被选为主要标准，进一步推动格密码走向主流。

Anna Rose：
我们一直说「基于格、基于格」，也许该先让不熟悉格的听众了解它到底是什麽。能否用较直观的方式描述它，以及举个简单例子？

Vadim Lyubashevsky：
每当有人问我「格问题是什麽」，我其实不先定义格，而是举「背包问题（knapsack）」这个更容易理解的例子──它其实就是格问题。

假设我给你一千个随机的一千位数字，再随机挑其中五百个相加，然后把总和给你；你的任务是找出是哪五百个数。这就是背包问题。而这等价于在某个格中寻找一条最短向量。

用最简单的定义来说，格是由一组基向量生成的无限点阵。例如基向量 (3, 1) 与 (4, 2) 所张成的所有整数线性组合。

接下来，你可以问：「在这个格里，最短的向量是什麽？」在二维空间很简单，但若升到一千维并使用一千个基向量，就是困难问题。

如此一来，最短向量问题（SVP）便是许多格基密码学的基础。

Anna Rose：
在密码应用中，你要证明的便是「我知道一个短向量」？

Vadim Lyubashevsky：
没错。我必须证明我知道一个向量 ，使得 ，而且  要「小」（例如係数仅为 0 或 1）。这比单纯的代数关係更麻烦，因为还要证明「小」这件事，对协定设计者而言是额外难题。

Anna Rose：
在密码应用中，这种「困难问题」是要让敌手去找出格中的短向量。那你们在设计协定时，需要证明的是「我知道一个短向量」吗？

Vadim Lyubashevsky：
是的。我不只要证明自己知道  使得 ，还得证明  本身「很小」。这跟离散对数不同——离散对数只需证明代数关係（如 ）；在格里，你既要证明代数关係，又要证明几何性质（短度），因此协定会複杂许多。

举例而言，若我们想把 Schnorr 签章直接搬到格世界，就得想办法同时证明「关係成立」与「向量係数仅为  或其他的小范围」，这就造成额外负担。

Nico Mohnblatt：
所以最困难的是如何在零知识下证明「小」。这也是为何过去的格签章会又大又慢？

Vadim Lyubashevsky：
正是如此。就连 NIST 标准中的格签章（ML-DSA，前称 Dilithium）都不是在证明「係数仅 」，而是证明「係数不超过某个较大的界」。而且它实际上证明的是  与  之间仅差一个比例因子，而不是完全相等——因为完整证明太昂贵。

过去甚至只要做线性长度的零知识证明，输出就可能高达数百 MB。直到近几年，我们陆续发明出格专用技巧，才把证明缩到几十 KB 等级。

Anna Rose：
在现有 SNARK 框架里，大家常把系统拆成 IOP、承诺方案等等模组，并换用不同后端。那基于格的 SNARK 能否「直接对调」某个模组？还是得重新思考整体设计？

Vadim Lyubashevsky：
你「可以」直接去接入，例如把杂凑／承诺全部换成格版，但结果通常效率不佳。格真正的优势在于：

1.  把「小向量」映到另一个向量，其输出空间跟输入空间同样是多项式环；

2. 这让你能连续运用同一种代数操作并做线性组合——这在配对或 KZG 里并不存在。

因此，我们开发了一套「格专用工具箱」：

• Johnson–Lindenstrauss 降维：把高维向量随机映射到低维，近似保留范数，让「证明短度」所需的维度大幅降低。

• 多项式环内积＝乘法：在  中，证明两多项式内积其实就是乘法第一係数，能直接表达范数。

• 折叠（folding）与线性组合：把  拆分后线性组合，再对映射结果做折叠，可递迴减少证明尺寸。

利用这些技巧，Gregor Seiler 与 Ward Beullens 提出的 LaBRADOR 协定，把证明大小压到约 50 KB，且几乎随约束数目不增长（对数级或更低）。验证端仍是线性时间，但已比杂凑型方案（几百 KB 以上）更小。

Anna Rose：
刚提到折叠（folding）。格的结构是否让折叠操作特别简单？

Vadim Lyubashevsky：
没错。因为  本质是线性映射，你可以把  分成两半，计算  或其他线性组合，再一起映射。折叠后仍然是「小向量映射」，能继续递迴。实际难点仍旧在于「怎麽证明结果小」。

现在我们有多条路：

• Sumcheck 方式

• Johnson–Lindenstrauss 方式

• 范数分段筛选

而这些方法可以先用一种确保验证端高效，再在后期切换到压缩度更佳的方案，例如 LaBRADOR，在递迴最深处只留下数十 KB 的证明。

Anna Rose：
我第一次听到「格＋零知识」时是在 FHE（全同态加密）脉络。那麽，若底层都用格，是否能更轻松地把 FHE 与 ZK 结合？

Vadim Lyubashevsky：
绝对可以。FHE、格签章、格 SNARK 都在相同的多项式环上运算，代数相容性非常高。反之，若拿 FRI 之类杂凑型承诺去证明格关係，效率会大打折扣，因为两种代数结构不同，光转换就耗很多成本。

Nico Mohnblatt：
基于格的「简洁证明」现况如何？是否已达实用水准？

Vadim Lyubashevsky：
若只看「证明大小」，现阶段 LaBRADOR 大约 50 KB 已是最佳。若连「验证端简洁」也要，则有 Greyhound（对 LaBRADOR 的扩充）、LatticeFold、LatticeFold+ 等持续改进。

值得高兴的是，传统零知识社群与格社群正逐渐交织：前者学习格技术，后者吸收折叠、递迴组合等经验。我相当乐观，未来 5~10 年内，基于格的证明会得到质的飞跃。

Anna Rose：
刚才你谈到杂凑型系统（hash-based）与基于格的比较。杂凑型 SNARK 通常也被视为具抗量子能力；那为何还需要格？两者在安全性或效率上有何消长？

Vadim Lyubashevsky：
若只论「被破解机率」，杂凑型方案胜出——它们仅假设如 SHA 或 AES 的抗碰撞、抗第二前像等基本性质，几乎没有可供量子演算法利用的结构。

而基于格的方案依赖明确的代数／几何结构，理论上量子电脑可能更容易「抓住线索」进行攻击。换言之，若要下注谁比较不会出事，多数人会押在杂凑型系统。

然而，杂凑型证明量级通常达数百 KB 甚至更大；格系统藉由结构化运算，能把证明压到仅数十 KB，计算速度也更快。所以两者其实是「安全假设较弱 vs. 实际效率更高」的权衡。

Nico Mohnblatt：
不过杂凑型证明通常在「随机预言机模型（random oracle）」内证明安全；格证明呢？

Vadim Lyubashevsky：
同样依赖随机预言机。若想脱离该模型，经常需要做「知识假设（knowledge assumptions）」——在格领域里，这类假设近来被证明在量子世界容易失效。因此，相比冒险使用不稳定的知识假设，我更倾向继续採用随机预言机模型。

Nico Mohnblatt：
你参与了 NIST 的后量子标准制定，特别是 ML-KEM（加密／密钥封装）与 ML-DSA（签章）。它们与现有离散对数或椭圆曲线方案有何根本差异？

Vadim Lyubashevsky：
先看传统 Diffie–Hellman：双方分别选 ，计算  公开，最后各自算  作为共享祕钥。

在格世界，对应的一步会是「选取小向量 ，公开 （ 为公开矩阵， 为误差）」。但若直接模彷 DH，双方最后得到的是 ，其中交叉误差项无法彼此抵消，导致协定失败。

因此我们改用「公钥加密／密钥封装」模式：

• ML-KEM 基本上是把 ElGamal 移植到格，同时设计「解码」机制把误差吸收、对齐；计算上快得多，但需要额外的误差处理逻辑。

• ML-DSA 可视为「格版 Schnorr」。为了在可接受讯息长度下证明「签名向量够小」，我们引入多重抽样、截断等技巧，最终得到 NIST 採用的 Dilithium/ML-DSA。

两者在 C/AVX2 甚至 ARM 向量化下皆能达到极高吞吐；代价是公钥、密文或签章尺寸比 ECC 大约数十倍，但仍在网路可承受范围。

Vadim Lyubashevsky：
谈到部署，我很好奇区块链／ZK 社群对「量子就绪」的紧迫感。有些协定——例如盲签式电子现金——一旦量子电脑出现就完全无法升级；使用者持有的旧签章会瞬间变得可伪造、资产蒸发。你们怎麽看？

Anna Rose：
在支付链层面，确实有人提出「建立平行的后量子链，诱导使用者迁移」；但这更多是社群与激励问题。

在 ZK 领域，过去两年为了伺服器端大量验证计算，杂凑型证明大行其道，自然就顺带获得一定抗量子能力。但若回到用户端、需要小证明的场景，又常回到配对／椭圆曲线。

Nico Mohnblatt：
关于旧链签章，我们曾在节目里讨论 Or Sattath 的「signature lifting」：把原本当作公钥的杂凑输出改为私钥种子本身，临时应急迁移。虽不完美，却能在量子威胁成真时紧急把资产转移。

总之，若能及早把协定设计为「量子就绪」──哪怕仅是保留未来替换钥匙的管道──都比事到临头再重构要好得多。

Anna Rose：
最后，能否分享你与团队目前的研究重点，以及你对未来的期许？

Vadim Lyubashevsky：
三大方向：

1. 更紧凑的格 SNARK：结合折叠、递迴与我们的工具箱，进一步缩小证明并优化验证端。

2. 真正零知识（隐私）：将 LaBRADOR 等协定完整加上 ZK 性质，再用于匿名凭证、数位货币等应用。

3. 形式验证与攻击研究：格系统日益複杂，我们急需工具验证实作正确性；同时，也鼓励更多人投入格密码的攻击分析，巩固基础。

我对此领域非常乐观——零知识社群与格社群的融合已经开始，未来五到十年我们极可能看到既高效又抗量子的主流方案。

Anna Rose：
Vadim，非常感谢你的精彩分享！

Vadim Lyubashevsky：
谢谢 Anna、Nico，讨论很愉快。

Nico Mohnblatt：
也期待两大社群持续融合。

Anna Rose：
再次感谢 Dan Boneh 的牵线，并感谢我们的製作团队 Rachel、Henrik 与 Tanya，也谢谢各位听众的收听！