cover_image

Greyhound：后量子格基SNARK

Kurt Pan XPTY
2025年06月04日 16:31

原文：https://blog.zksecurity.xyz/posts/greyhound/

作者：David Wong

译者：Kurt Pan

随着量子威胁的逼近，我们需要开始思考如何构建能够抵御量子计算机的证明系统。本文将介绍基于格的证明系统这个领域，并深入阐述其中最有前景的解决方案——Greyhound 的工作原理。

  • https://eprint.iacr.org/2024/1293

纵观历史，我们部署现代公钥密码基础设施耗时近 20 年。要确保从目前广泛使用的密码系统顺利安全地迁移到能够抵御量子计算的密码系统，需要付出巨大的努力。因此，无论我们能否预估量子计算时代到来的确切时间，我们都必须立即着手准备，使我们的信息安全系统能够抵御量子计算。——NIST 8105 号跨部门报告（2016 年 4 月） http://csrc.nist.gov/publications/drafts/nistir-8105/nistir_8105_draft.pdf

后量子零知识证明现状

到目前为止，我们知道，只要增加参数大小，对称密码学基本上是安全的。因此，不要使用 SHA-256，而要使用 SHA-512；不要使用 AES-128，而要使用 AES-256，等等。这就是为什么第一个发布的后量子签名标准是基于哈希的（*PQCRYPTO：长期安全后量子系统的初步建议 (2015)*），也是为什么基于哈希的证明系统（例如 STARK、Ligero、Aurora、Fractal、Brakedown 等）只要使用足够大的参数（而现实情况并非如此）就是安全的。

  • https://pqcrypto.eu.org/docs/initial-recommendations.pdf

请参阅 Grover 算法，了解为什么我们必须增大参数 https://www.youtube.com/watch?v=RQWpF2Gb-gU

另一方面，非对称密码学正陷入困境。最常见的非对称密码学基于大数分解的难度（RSA）或离散对数计算的难度（Diffie-Hellman）。这些问题在量子计算机上并不安全，我们需要寻找替代方案。这包括我们所有常用的基于椭圆曲线的 SNARK。

请参阅 Shor 算法以了解这种情况的原因 https://www.youtube.com/watch?v=lvTqbM5Dq4Q

想象一下十五年后。有人宣布他造出了一台大型量子计算机。RSA 已死。DSA 也已死。椭圆曲线、超椭圆曲线、类群等等，都死了，死了，死了。——丹尼尔·J·伯恩斯坦 (2016)

除了基于哈希的证明系统之外，最有前景的替代方案似乎就是基于格的证明系统。这些证明系统基于格问题的难度，而格问题被认为即使对于量子计算机来说也是困难的。

有趣的是，该主题已经有大量研究，并且成果颇为可观。不仅证明大小比基于哈希的方案更小，而且对折叠的支持似乎也比所有先前已知的方案（包括 SNARK 和 STARK）都要好。今年我们很幸运，所有折叠团队都提出了新的基于格的方案： 提出protostar的 Binyi 提出了 Latticefold+ 方案，提出 Nova 的 Srinath 提出了 Neo 方案。

  • https://eprint.iacr.org/2025/247
  • https://eprint.iacr.org/2025/294

[LatticeFold] 是第一次一个后量子 SNARK 系统展现出了优于前量子 SNARK 系统的优势。—— Dan Boneh，ZKProofs  (2025)

在证明系统方面，许多方案最初是基于一些不可靠的假设提出的，这些假设后来被推翻，但最终都收敛到基于强假设并具有良好性质的方案。Greyhound 或许是该领域多年研究的结晶，也是第一个看起来既高效又能抵御量子计算机攻击的方案：它透明，拥有一个线性证明者、一个亚线性验证者 ，以及多项式对数证明大小。具体来说，它的证明大小约为 50 KB 。

顺便说一句，与之前许多基于格的 SNARK 研究不同，Greyhound 是一个多项式承诺方案（PCS），而非完整的零知识证明系统。这意味着它本质上可以与当今所有以 PCS 为核心的证明系统（基本上所有系统）即插即用。

此外，当我写这些文字的时候，一个Rust 的实现刚刚发布（LattiRust），而几周前 Ingonyama 也宣布即将在他们的旗舰库 ICICLE 中支持 Greyhound。

  • https://github.com/lattirust
  • https://x.com/OmerShlomovits/status/1920810288716079185

格简介

思考格的一个好方法是先思考向量空间，它是所有可能向量的集合，这些向量可以通过对一组向量（通常称为基）进行线性组合而得到。如果这些向量是线性无关的（即任何一个向量都不能通过组合其他向量而生成），且有足够多的向量，那么你甚至可以张成整个空间： 

在向量空间中，我们可以用实数（  中）缩放向量，但在格中，我们只能用整数（  中）缩放向量。这意味着格中的向量并不密集，更像是一个网格：


更严格的定义是考虑  个线性无关向量  （代表格的基）的所有线性组合：

如果定义矩阵  并以  作为列，那么可以将上述内容重写为：

我们认为格中存在一些难以解决的问题，即所谓的“困难问题”，而我们的密码系统正是基于这些问题构建的。其中最值得关注的是最短向量问题（SVP） 和最近向量问题（CVP） ，即使对于量子计算机来说，这些问题也被认为难以解决。SVP 是要寻找格中最短的向量（零向量除外）：


CVP 是关于寻找与给定非格点最接近的格向量：

这两个问题都是最坏情况困难问题，这意味着它们并不总是很难，但对于一些专门设计的参数来说，它们确实很难。

但对于我们的 PCS Greyhound，我们不会使用任何这些问题。相反，Greyhound 依赖于另一个名为 模短整数解（M-SIS） 的问题。

SIS 问题是关于在矩阵中找到向量的线性组合，使其结果为零向量。该线性组合不能是平凡的（即它不能是零向量），并且标量必须很小（即它们必须小于某个定义的界）。

更严格地说，如果我们有一个格  ，系数在  中，那么就要找到一个向量  ，使得  和  ，对具有某些已知边界  和某些定义的范数运算 （本文中我们将忽略这些运算）。

M-SIS 问题与之类似，只是我们不使用  中的元素，而是使用多项式环  中的元素。对于本文的大部分解释来说，环的具体定义并不重要。你可以假设该环的元素看起来像次数小于 64 的多项式，且其系数为  ，其中素数  约为  ，但即使这样，对于从高层次理解该协议也并不重要。

Ajtai 在 1996 年证明，如果能够破解平均情况（从给定分布中随机抽取的实例）的 SIS（和 M－SIS）问题，那么就能破解最坏情况（最难解决的实例） SVP问题的实例！这意味着要么 SIS 是安全的，要么 SIS 被攻破，同时 SVP 也被攻破。这种安全归约带来了双赢：如果成功，我们可以对密码方案获得信心；如果失败，我们可以获得洞察，甚至可能在数学上取得突破。

这是一个非常强大的性质，与 SVP 和 CVP 等最坏情况的难题不同，它可以更容易地用于构建密码系统，因为它们的安全性可以依赖于随机生成的实例（从某些分布中采样）。

Greyhound 的核心：Ajtai 承诺

现在让我们深入了解 Greyhound 的工作原理。请记住，Greyhound 是一个多项式承诺方案（PCS），因此我们从一个需要承诺的多项式  开始。

第一步是将我们的多项式  看作一个分块的多项式：

其中：

  • ...

然后我们可以将我们的多项式编码为一个矩阵，其中系数被插入到列中：

我们的多项式现在几乎准备好被承诺了。

为了承诺多项式，Greyhound 依赖于 Ajtai 承诺。Ajtai 承诺的工作方式是取一个短向量  并计算承诺为 。

矩阵  是一个可以从种子生成的公共参数。因此无需将整个矩阵存储在内存中，也不需要可信设置。此外，这样的矩阵通常看起来宽但短，意味着它们有很多列但行数不多。这是因为矩阵的秩决定了承诺的大小，维度必须对此进行弥补。

你可以很快看到这样的方案是绑定的，因为如果你能找到两个不同的打开方式对应同一个承诺，那么你就可以破解 SIS 问题：如果有  使得 ，那么 ，你就找到了 SIS 问题的一个非平凡解。 （此外，它们对于加法是平凡同态的，这与折叠方案配合得很好。）

由于我们的多项式系数  不一定是“小”的，我们实际上不能直接用 Ajtai 承诺方案来承诺它们。因此，我们必须在承诺之前对它们进行基分解。例如，考虑二进制分解。Greyhound 论文使用一个函数  来执行分解，因此我们将使用它：，你可以想象有一个向量  可以重新组合分解后的向量 。

这实际上有点烦人，Greyhound 中的许多复杂性来自于必须处理非短的向量。在本文中，我们有时可能会忽略（有意或无意地）分解和重组步骤，但严格的分析或功能实现必须确保处理好这些步骤。

现在想象一下，我们多项式矩阵的每一列都被分解为某种基下的短向量 ，如上所述。这意味着我们现在有以下矩阵 ，它表示我们在列中分解的多项式系数。

求值协议

没有在多项式不同点求值的PCS 又有什么好的？让我们使用系数矩阵来写出  在  处的求值：

如果你不相信这个，我们邀请你自己写下结果。请注意，这种技术实际上在其他一些证明系统中也被使用（aurora、fractal、hyrax、ligero、vortex、brakedown 等）。

然后，Greyhound 协议让证明者首先计算矩阵乘法的左部分：

然后让验证者自己计算另一部分：

其中  是求值点  的值。

但当然，这并不安全，因为验证者不知道左乘结果  是否被正确计算。

在上述协议中，验证者只需计算右侧的乘法，从而减少了工作量。例如，可以选择一个大小约为  的矩阵，其中  是多项式  的次数。使用这样的参数，验证者只需进行约  的工作量，这是亚线性的，我们对此表示满意！证明者还发送了大小约为  的向量 ，这也是亚线性的证明大小。

这里 ，我们确实选择了 （其中  是矩阵的宽度，即乘法的次数），以及 （其中  是矩阵的秩，即高度）。

修复协议的安全性：使用类似 Schwartz-Zippel 的矩阵检查

为了解决问题，验证者可以发送一组挑战向量 。这些挑战需要在证明者已通过发送求值值  和“左侧计算”结果  向验证者承诺之后发送。

利用 Schwartz-Zippel 引理，证明系统可以在一个随机点上检查多项式恒等式（即一个多项式  是否等于另一个多项式 ）。这种检查可以在明文中进行，或隐藏在承诺中（例如 KZG）。使用这个挑战向量 ，证明者可以向验证者展示计算在一个随机线性组合上是正确的，而不是在单独的向量上。因此，可以将其视为类似于矩阵的 Schwartz-Zippel 检查。

为此，证明者提供以下“打开”向量 ：

然后，验证者可以通过计算以下等式来检查  是否被正确计算：

接着，验证者可以使用承诺  来检查  是否从  正确计算得出：

证明者已发送大小为  的向量  和大小为  的向量 。

更小的承诺

在上述协议中，多项式的承诺是一系列 Ajtai 承诺 。这是一个大小为  的承诺，这并不理想。为了减少该承诺的大小，Greyhound 使用了一个额外的“外部”承诺，将所有先前的承诺（他们称之为“内部”承诺）合并为一个单一的承诺 。

在我们的协议中，这意味着证明者生成的承诺为：

其中：

  •  是一个单独的公共矩阵，类似于 ，用于外部承诺
  •  是所有分解后的  的连接（即 ）

这意味着在我们的求值协议中，证明者需要额外地将打开值  发送给验证者（每个大小约为 ），且验证者需要通过检查以下等式来验证  的正确性：

请注意，证明的大小仍然是 ，验证者的工作量也是 。

Greyhound 的早期品种：LaBRADOR

我们可以在此停止，得到  的证明大小和  的验证者工作量，但我们可以通过使用 LaBRADOR 将证明大小改进为多项式对数级别，而不改变亚线性的验证者时间 。

LaBRADOR 是 IBM 研究团队更早的一篇论文，介绍了两个内容：

  1. 一个用于“主关系”的证明系统
  2. 将 R1CS 约束系统归约到该证明系统的方法
  • https://eprint.iacr.org/2022/1341

主关系被定义为，对于许多如下形式的函数 ，证明者知道一组短向量 （与 Greyhound 无关），使得：

LaBRADOR 的证明者可以在不发送  向量的情况下说服验证者，而是发送更小的内容（并让验证者验证其是否满足主关系）。

如果我们能将 Greyhound 中的内容归约到 LaBRADOR 的主关系，那么我们就不必发送大的证明元素 ，而是发送更小的内容（并实现亚线性的证明大小）。

具体来说（这对我们来说简化了事情），Greyhound 仅使用了 LaBRADOR 主关系的一个子集：

另一种看法是，LaBRADOR 是该关系的一个证明系统，尽管其 API 相当通用，但我们只需要使用其中的一个子集。

这类似于以下矩阵乘法，其中  向量是短的：

因此，如果我们能将 Greyhound 中的内容转换为这种形式，那就太好了。

这里我们将不再讨论 LaBRADOR。如果你喜欢这篇文章，可以向我们询问有关 LaBRADOR 的内容 :)

将 Greyhound 融入 LaBRADOR

准备好最后一段了吗？让我们首先回顾一下在 Greyhound 中作为验证者需要做的事情：

  1. 完成求值计算并检查其是否正确：
  2. 验证 （左侧矩阵乘法）是否计算正确：
  3. 验证  是否计算正确：

接下来，我们将需要使用 Kronecker 积 。如果你不知道这个运算符是如何工作的，可以通过以下示例来尝试理解： 

现在，如果我们将  定义为所有  的连接，我们可以将验证者需要执行的所有检查写成矩阵乘法的形式：

你可能已经开始看到这看起来像是主关系写成矩阵乘法的形式。我们只需要：

  • 将向量  视为相同大小的向量  的连接（假设大小为 ）
  • 将矩阵的每一行视为相同大小  的  的连接

这几乎看起来像 LaBRADOR 的接口！如果我们能将其传递给 LaBRADOR，它将通过使我们不发送显然很大的 （特别是 ！）来提供更小的证明大小。

我说“几乎”，是因为我们的向量  实际上并不是短的，而 LaBRADOR 在这里期望一个短向量。所以接下来，让我们确保每个子向量都是小的！

缩小 

我们可以使用分解后的 ：

哦，顺便说一下，请记住验证者拥有的只是这些的承诺 。因此，我们还必须添加这些打开的验证：

缩小 

为了使  部分更小，我们可以使用分解后的 。仅仅这样做是不够的，我们还需要确保证明者在收到验证者的挑战之前就对其进行了承诺（因为如果不这样做，会出现典型的可靠性问题）。因此，证明者将发送一个小的承诺 （对于某个公共矩阵承诺 ）而不是 ，验证者将需要检查打开  是否匹配：

缩小 

最后，缺失的部分是使  部分变短。请记住，该向量的计算方式为：

其中  已经是短向量。解决方案是使用足够小的挑战，以免增加向量的大小。在 Greyhound 论文中，挑战是从多项式环元素中采样的，这些元素大多具有 0 系数，或者系数接近 0。

综合起来

最后，我们有以下矩阵乘法，包括验证者需要对公共值（）、声明值（）、证明者值（）、验证者值（）以及最后的见证向量  执行的所有检查：

如上所述，证明者剩下要做的就是将见证向量拆分成相同大小的子向量，而验证者必须将矩阵行拆分成相同大小的行。

希望你已经掌握了本文的大部分内容。Greyhound 论文介绍了更多同样重要的概念，因此如果你想更深入地理解该协议，我们建议你花更多时间阅读该论文。

  • https://eprint.iacr.org/2024/1293

感谢 Hoeteck Wee、Miha Stopar 和 Ngoc Khanh Nguyen 提供的帮助/反馈。


Kurt Pan: 即日起提供有偿「密码学论文代码实现和 benchmarking 服务」，语言侧重Rust / Python / C++，密码学侧重零知识证明系统和格密码方案。（具体流程正在筹备中，敬请期待！）欢迎有需要的老师同学以及对密码学感兴趣的朋友联系我，邮箱https://keys.openpgp.org/search?q=kurtpan666%40pm.me，也可关注公众号后留言。