Schnorr签名向量版：格基签名详解

备注. 本文是我们深度研究文章和讲座的配套通俗读物。如需完整的技术解析，请参阅研究文章并观看讲座。

随着 Google Quantum AI 关于量子计算的论文的发表，围绕密码学相关量子计算机（CRQC）时间线的讨论日益激烈。尽管各方对其时间线看法不一，但密码学界已达成明确共识：我们现在就必须开始准备并考察量子安全算法。

首要任务是选择一种后量子安全的数字签名方案，以替换比特币当前使用的易受量子攻击的椭圆曲线密码学。但从 Schnorr 和 ECDSA 升级并非简单地将一种算法替换为另一种。社区目前正面临两个重大问题：我们如何安全地实施这一过渡，以及我们实际过渡到哪种后量子（PQ）方案。本文完全聚焦于“哪种”这个问题，深入剖析最有前景的 PQ 签名家族之一。

以下是对当前后量子格局的概述、Blockstream 为何大力研究“格基”密码学，以及这些签名实际的工作原理。

后量子格局

在考虑后量子签名时，密码学家通常会研究四类主要假设，它们被认为量子计算机（大概）无法破解。

1. 哈希基密码学。此类方案的安全性依赖于哈希函数不可逆的假设。这类假设被认为是迄今为止我们使用的所有密码学原语中最稳定的。

此外，有状态方案（例如 SHRINCS）可实现 324 字节的极紧凑签名，但这种紧凑性是以严格的状态管理为代价的。相反，避免状态管理会导致相对较大的无状态签名。无论哪种方式，这两种方法都存在代数灵活性不足的问题：例如，构建有效的多重签名或门限签名等修改方案目前看来不太可能。

Blockstream 已经对此类密码学进行了广泛研究：参见 Mikhail Kudinov 和 Jonas Nick 的《比特币的哈希基签名方案》以及 Jonas Nick 的 SHRIMPS。现在我们转而考虑能够解决上述部分问题的格基方法。

2. 格基密码学。此类方案的安全性涉及一种称为格的数学对象上的特定问题，格自 18 世纪以来一直为数学家所用。你可以将格想象成一个无限的点网格，如下图所示。就像你可以在椭圆曲线上将两个点相加得到第三个点一样，你也可以将该网格上的任意两个点相加得到格上的另一个有效点。

然后，人们可能会问关于这个格的不同问题：例如，网格上两点之间的最小距离是多少？或者，如果你在平面上随机选取一个点，该点到格上最近的点是什么？对于适当配置的格，在不知道格几何底层细节的情况下，回答所有这些问题被认为对量子计算机来说是困难的。

格的主要特点在于，与哈希基方案相比，它具有代数灵活性，并且无状态签名尺寸更小。我们将在下一节具体说明这意味着什么。

3. 码基密码学。纠错码（ECC）是该领域中另一个广泛使用的数学工具。例如，你可能已经通过其在 ZK-STARK 等后量子证明系统中的作用而熟悉它们。然而，当前基于 ECC 假设的签名方案，就产生的公钥和签名尺寸而言，与哈希基和格基方案相比并不实用。通常，这些尺寸轻易就能超过 10 KB，正如 NIST 候选方案 LESS 的情况。

4. 同源基密码学。此类密码学在所有先前的候选方案中产生了最紧凑的公钥和签名尺寸。例如，SQISign 实现了公钥和签名总大小仅为 213 字节的惊人指标（相比之下，Schnorr 为 96 字节）。然而，其底层数学依赖于相当高级的代数几何概念。在密码学中，复杂性往往是安全性的敌人，因为如此繁重的代数结构可能掩盖微妙的漏洞。在我们计划将这些方案集成到比特币之前，它们还需要大量的实战测试时间。

可以看出，上述四种范式在签名尺寸、安全稳健性和灵活性方面各有取舍，如下图所示。

总结来说，对于比特币严格的区块空间限制，码基签名目前过于庞大。同源基数学虽然紧凑，但极难安全实现，且仍存在激烈争论。哈希基签名非常安全且已被充分理解，但它们在代数上“僵化”。

这使得格基密码学可以说是比特币长期未来中最平衡且最有前景的候选方案之一。

为什么是格？代数灵活性

要理解为什么格对比特币如此有吸引力，我们必须看看是什么使得当前比特币的签名（Schnorr 和 ECDSA）如此有效。

当前比特币的安全性依赖于离散对数（DL）问题。DL 方法的一大优势在于它具有良好的数学结构。例如，如果你组合两个秘密，它们的公开对应部分会可预测地组合：$[x+y]G=[x]G+[y]G$。这种代数同态特性正是比特币开发者能够构建多重签名（参见 Jonas Nick、Tim Ruffing 和 Yannick Seurin 的 MuSig2）、门限签名、HD 密钥派生或适配器签名等高级协议的原因。

另一方面，哈希函数（如 SHA256 或 BLAKE）则像随机搅拌机。如果你有一个哈希函数 $H$，将输入相加会破坏与输出的任何关系：例如，$H(x+y)$ 不等于 $H(x)+H(y)$。虽然缺乏结构正是哈希函数安全的原因，但也使得在上面构建高级协议变得极其困难。

然而，格可以恢复那种数学结构。格密码学不是对椭圆曲线上的点进行乘法，而是涉及将数字网格（矩阵）与数字列表（向量）相乘。如果你有一个公开矩阵 $\mathbf{A}$ 和两个秘密 $\mathbf{x}$ 和 $\mathbf{y}$，则有 $\mathbf{A}(\mathbf{x} + \mathbf{y}) = \mathbf{A}\mathbf{x} + \mathbf{A}\mathbf{y}$（这看起来完全像 DL 设置中使用的 $(x+y)G = xG + yG$）。

有一个重要的注意事项：在格中，我们通常使用短的秘密。当你组合格方程时（例如计算 $\mathbf{x} + \mathbf{y}$），底层“聚合”秘密的尺寸会增加。但只要我们正确管理这个误差的大小，结构属性仍然有效。这意味着格可能为后量子多重签名、零知识证明和机密资产等高级修改打开大门。

格签名的工作原理：带有向量的 Schnorr

如果你了解当前比特币中 Schnorr 签名的工作原理，那么你已经对理解某些格签名（例如 Dilithium）有了 50% 的了解。最突出的格签名设计使用了一种我们非正式称之为“Schnorr，但带向量”的技术。

在经典 Schnorr 签名中，使用私钥 $x$ 的签名过程如下：

1. 生成一个随机数 $r$。
2. 创建对该随机数的“承诺”。
3. 对承诺和数据进行哈希，得到随机挑战 $e$。
4. 使用该挑战掩盖你的私钥，生成最终响应：$z = r + xe$。

在基于格的签名中，我们执行完全相同的步骤，只是使用矩阵和向量。方程类似：例如，许多早期基于格签名的研究使用方程 $\mathbf{z} = \mathbf{r} + \mathbf{S}\mathbf{e}$，其中 $\mathbf{S}$ 是秘密矩阵，$\mathbf{e}$ 是挑战向量，$\mathbf{r}$ 是随机性向量。

拒绝采样*

这里存在一个重大的安全问题。为了使格方程对量子计算机难以求解，向量 $\mathbf{z}$ 和 $\mathbf{r}$ 中的数字必须保持较小（这被称为短整数解问题）。

但是当我们计算 $\mathbf{z} = \mathbf{r} + \mathbf{S}\mathbf{e}$ 时，它会在签名 $\mathbf{z}$ 和底层秘密 $\mathbf{S}$ 之间产生统计依赖性（这在 Schnorr 中并非如此，因为 $r$ 和 $e$ 可以是任意的）。如果攻击者观察你足够多的签名，他们会注意到这种统计偏移，并可能危及私钥。

作为一个简化的例子，请考虑下图。由于 $\mathbf{r}$ 可以被视为小噪声，$\mathbf{z}$ 围绕中心 $\mathbf{S}\mathbf{e}$ 分布，并带有一些噪声（用实蓝线标记）。如果从该分布中获取足够多的样本，通过平均可以得出该分布的近似中心，从而向对手泄露大量信息。

为了解决这个问题，格基密码学采用了一种巧妙的技巧，称为 带中止的 Fiat-Shamir（也称为拒绝采样）。

这个想法出奇地简单：签名者生成签名 $\mathbf{z}$ 后，他们会检查私钥的加法是否使该值偏移过大。如果签名看起来有“偏差”并存在泄露密钥的风险（如上图所示），他们直接丢弃它，然后使用新的随机数重试。这个过程重复多次，直到生成的签名完美掩盖私钥（如上图中的虚线所示）。

备注. 在实践中，中心 $\mathbf{S}\mathbf{e}$ 本身也是一个随机分布。但这原则上不改变要点：分布的偏移会泄露关于底层秘密 $\mathbf{S}$ 的一些信息，我们必须消除这些信息（事实证明这样做相当直接）。

下一步

格密码学是后量子密码学中一个深邃且有前景的方向，其能力远不止于替换数字签名。它提供了我们所需的数学基础，使比特币既具备量子安全性，又可能升级到更有效的聚合和门限方案。

要深入探讨更底层的机制，包括离散高斯、最短向量问题和拒绝采样背后的数学，请务必阅读完整的研究文章，并在此处观看完整演示：

格基签名详解：Blockstream 研究研讨会第 1 集

• 原文链接： blog.blockstream.com/sch...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～