随着量子威胁的逼近，我们需要开始思考如何构建能够抵御量子计算机的证明系统。本文将介绍基于格的证明系统这个领域，并深入阐述其中最有前景的解决方案——**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 或许是该领域多年研究的结晶，也是第一个看起来既高效又能抵御量子计算机攻击的方案：它*透明*，拥有一个*线性证明者*、一个*亚线性验证者* $(O(\sqrt{N}))$ ，以及*多项式对数证明大小*。具体来说，它的证明大小约为 50 KB 。 顺便说一句，与之前许多基于格的 SNARK 研究不同，Greyhound 是一个**多项式承诺方案（PCS）**，而非完整的零知识证明系统。这意味着它本质上可以与当今所有以 PCS 为核心的证明系统（基本上所有系统）即插即用。 此外，当我写这些文字的时候，一个Rust 的实现刚刚发布（LattiRust），而几周前 Ingonyama 也宣布即将在他们的旗舰库 ICICLE 中支持 Greyhound。 - https://github.com/lattirust - https://x.com/OmerShlomovits/status/1920810288716079185 ## 格简介 思考格的一个好方法是先思考**向量空间**，它是所有可能向量的集合，这些向量可以通过对一组向量（通常称为基）进行线性组合而得到。如果这些向量是线性无关的（即任何一个向量都不能通过组合其他向量而生成），且有足够多的向量，那么你甚至可以张成整个空间： ![[Pasted image 20250604133612.png]] 在向量空间中，我们可以用实数（ $\mathbb{R}$ 中）缩放向量，但在格中，我们只能用整数（ $\mathbb{Z}$ 中）缩放向量。这意味着格中的向量并不密集，更像是一个网格： ![[Pasted image 20250604133659.png]] 更严格的定义是考虑 $k$ 个线性无关向量 $\mathbf{b}_i$ （代表格的基）的所有线性组合： $ \mathcal{L}:=\left\{\sum_{i=0}^k z_i \cdot \mathbf{b}_i \mid \mathbf{z} \in \mathbb{Z}^n\right\} $ > 如果定义矩阵 $\mathbf{B}:=\left[b_0|\cdots| b_{k-1}\right] \in \mathcal{R}^{n \times k}$ 并以 $\mathbf{b}_i$ 作为列，那么可以将上述内容重写为： >$ \mathcal{L}:=\left\{\mathbf{B} \cdot \mathbf{z} \mid \mathbf{z} \in \mathbb{Z}^n\right\} >$ 我们认为格中存在一些难以解决的问题，即所谓的“**困难问题**”，而我们的密码系统正是基于这些问题构建的。其中最值得关注的是**最短向量问题（SVP）** 和**最近向量问题（CVP）** ，即使对于量子计算机来说，这些问题也被认为难以解决。SVP 是要寻找格中最短的向量（零向量除外）： ![[Pasted image 20250604134404.png]] CVP 是关于寻找与给定非格点最接近的格向量： ![[Pasted image 20250604134452.png]] 这两个问题都是*最坏情况困难问题*，这意味着它们并不总是很难，但对于一些*专门设计的参数*来说，它们确实很难。 但对于我们的 PCS Greyhound，我们不会使用任何这些问题。相反，Greyhound 依赖于另一个名为 **模短整数解（M-SIS）** 的问题。 SIS 问题是关于在矩阵中找到向量的线性组合，使其结果为零向量。该线性组合不能是平凡的（即它不能是零向量），并且标量必须很小（即它们必须小于某个定义的界）。 更严格地说，如果我们有一个格 $B$ ，系数在 $\mathbb{Z}_{\mathrm{q}}$ 中，那么就要找到一个向量 $\vec{x}$ ，使得 $B \vec{x}=\overrightarrow{0} \bmod q$ 和 $\|\vec{x}\| \leq \beta$ ，对具有某些已知边界 $\beta$ 和某些定义的范数运算 $\|\|$（本文中我们将忽略这些运算）。 M-SIS 问题与之类似，只是我们不使用 $Z_q$ 中的元素，而是使用多项式环 $R_q$ 中的元素。对于本文的大部分解释来说，环的具体定义并不重要。你可以假设该环的元素看起来像次数小于 64 的多项式，且其系数为 $\mathbb{Z}_q$ ，其中素数 $q$ 约为 $2^{32}$ ，但即使这样，对于从高层次理解该协议也并不重要。 Ajtai 在 1996 年证明，如果能够破解平均情况（从给定分布中随机抽取的实例）的 SIS（和 M－SIS）问题，那么就能破解最坏情况（最难解决的实例） SVP问题的实例！这意味着要么 SIS 是安全的，要么 SIS 被攻破，同时 SVP 也被攻破。这种安全归约带来了双赢：如果成功，我们可以对密码方案获得信心；如果失败，我们可以获得洞察，甚至可能在数学上取得突破。 这是一个非常强大的性质，与 SVP 和 CVP 等最坏情况的难题不同，它可以更容易地用于构建密码系统，因为它们的安全性可以依赖于*随机生成的实例（从某些分布中采样）*。 # Greyhound 的核心：Ajtai 承诺 现在让我们深入了解 Greyhound 的工作原理。请记住，Greyhound 是一个多项式承诺方案（PCS），因此我们从一个需要承诺的多项式 $f$ 开始。 第一步是将我们的多项式 $f$ 看作一个*分块*的多项式： $ \begin{aligned} f(x) & =f_0+f_1 \cdot x+f_2 \cdot x^2+f_3 \cdot x^3+f_4 \cdot x^4+\cdots \\ & =f_0^{\prime}(x)+x^4 f_1^{\prime}(x)+x^8 f_2^{\prime}(x)+\cdots \end{aligned} $ 其中： - $f_0^{\prime}(x)=f_0+f_1 \cdot x+f_2 \cdot x^2+f_3 \cdot x^3$ - $f_1^{\prime}(x)=f_4+f_5 \cdot x+f_6 \cdot x^2+f_7 \cdot x^3$ - ... 然后我们可以将我们的多项式编码为一个矩阵，其中系数被插入到列中： $ \left[\begin{array}{llll} f_0 & f_4 & f_8 & f_{12} \\ f_1 & f_5 & f_9 & f_{13} \\ f_2 & f_6 & f_{10} & f_{14} \\ f_3 & f_7 & f_{11} & f_{15} \end{array}\right] $ 我们的多项式现在几乎准备好被承诺了。 为了承诺多项式，Greyhound 依赖于 **Ajtai 承诺**。Ajtai 承诺的工作方式是取一个短向量 $\vec{s}$ 并计算承诺为 $\vec{t}=\mathbf{A} \cdot \vec{s}$。 > 矩阵 $\mathbf{A}$ 是一个可以从种子生成的公共参数。因此无需将整个矩阵存储在内存中，也不需要可信设置。此外，这样的矩阵通常看起来宽但短，意味着它们有很多列但行数不多。这是因为矩阵的秩决定了承诺的大小，维度必须对此进行弥补。 > ![[Pasted image 20250604140136.png]] 你可以很快看到这样的方案是绑定的，因为如果你能找到两个不同的打开方式对应同一个承诺，那么你就可以破解 SIS 问题：如果有 $\vec{s} \neq \overrightarrow{s^{\prime}}$ 使得 $A \vec{s}=A \overrightarrow{s^{\prime}}$，那么 $A\left(\vec{s}-\overrightarrow{s^{\prime}}\right)=\overrightarrow{0}$，你就找到了 SIS 问题的一个非平凡解。 （此外，它们对于加法是平凡同态的，这与折叠方案配合得很好。） 由于我们的多项式系数 $f_i$ 不一定是“小”的，我们实际上不能直接用 Ajtai 承诺方案来承诺它们。因此，我们必须在承诺之前对它们进行基分解。例如，考虑二进制分解。Greyhound 论文使用一个函数 $G^{-1}$ 来执行分解，因此我们将使用它：$\vec{t}=A \cdot G^{-1}(\vec{s})$，你可以想象有一个向量 $G=\left[\begin{array}{lllll}1 & 2 & 4 & 8 & \cdots\end{array}\right]$ 可以重新组合分解后的向量 $G^{-1}(\vec{s})$。 这实际上有点烦人，Greyhound 中的许多复杂性来自于必须处理非短的向量。在本文中，我们有时可能会忽略（有意或无意地）分解和重组步骤，但严格的分析或功能实现必须确保处理好这些步骤。 现在想象一下，我们多项式矩阵的每一列都被分解为某种基下的短向量 $\vec{s}_i$，如上所述。这意味着我们现在有以下矩阵 $\left[\begin{array}{llll}\vec{s}_0 & \vec{s}_1 & \vec{s}_2 & \vec{s}_3\end{array}\right]$，它表示我们在列中分解的多项式系数。 # 求值协议 没有在多项式不同点求值的PCS 又有什么好的？让我们使用系数矩阵来写出 $f$ 在 $x$ 处的求值： $ \begin{aligned} {\left[\begin{array}{llll} 1 & x & x^2 & x^3 \end{array}\right] \cdot\left[\begin{array}{llll} f_0 & f_4 & f_8 & f_{12} \\ f_1 & f_5 & f_9 & f_{13} \\ f_2 & f_6 & f_{10} & f_{14} \\ f_3 & f_7 & f_{11} & f_{15} \end{array}\right] } & \cdot\left[\begin{array}{c} 1 \\ x^4 \\ x^8 \\ x^{12} \end{array}\right] \\ =\left[\begin{array}{llll} f_0^{\prime}(x) & f_1^{\prime}(x) & f_2^{\prime}(x) & f_3^{\prime}(x) \end{array}\right] & \cdot\left[\begin{array}{c} 1 \\ x^4 \\ x^8 \\ x^{12} \end{array}\right] \\ & =f(x) \end{aligned} $ 如果你不相信这个，我们邀请你自己写下结果。请注意，这种技术实际上在其他一些证明系统中也被使用（aurora、fractal、hyrax、ligero、vortex、brakedown 等）。 然后，Greyhound 协议让证明者首先计算矩阵乘法的左部分： $ \vec{w}=a^{\top} \cdot G \cdot\left[\begin{array}{llll} \vec{s}_0 & \vec{s}_1 & \vec{s}_2 & \vec{s}_3 \end{array}\right] $ 然后让验证者自己计算另一部分： $ y=\langle\vec{w}, \vec{b}\rangle $ 其中 $y=f(x)$ 是求值点 $x$ 的值。 但当然，这*并不安全*，因为验证者不知道左乘结果 $\vec{w}$ 是否被正确计算。 > 在上述协议中，验证者只需计算右侧的乘法，从而减少了工作量。例如，可以选择一个大小约为 $\sqrt{N} \times \sqrt{N}$ 的矩阵，其中 $N$ 是多项式 $f$ 的次数。使用这样的参数，验证者只需进行约 $\sqrt{N}$ 的工作量，这是*亚线性*的，我们对此表示满意！证明者还发送了大小约为 $\sqrt{N}$ 的向量 $\vec{w}$，这也是亚线性的证明大小。 > 这里 $N=16$，我们确实选择了 $r=\sqrt{N}=4$（其中 $r$ 是矩阵的宽度，即乘法的次数），以及 $m=4$（其中 $m$ 是矩阵的秩，即高度）。