基于格的数字签名简介

Schnorr，但用向量：基于格的签名解释

第 1 节：引言

注意

致谢。 这篇博文部分基于我在 Blockstream Research 期间进行的研究。我感谢他们的支持以及有机会研究这些主题。

另外感谢 Jonas Nick 对本博客的仔细审阅和非常有帮助的建议，以及 Mykyta Redko 发现解释中的几个重大错误。

随着 Google 量子 AI 最近论文 的发布，关于第一台密码学相关量子计算机 (CRQC) 出现的时间线引发了一场激烈的讨论（坦率地说，在某些地方变成了恐慌）。观点当然差异很大，但有一件事似乎大家都同意：我们需要尽快将量子安全算法付诸实施。

这当然包括许多现有的协议；特别是在比特币中（以及在整个区块链领域），第一步自然是构建后量子 (PQ) 安全的数字签名方案。然而，即使是这第一步也极有争议：我们有一批潜在的 PQ 方案，但它们 (a) 明显比离散对数 (DL) 构造更差（至少差一个 $16\times$ 的因子），(b) 其底层安全假设通常比前量子方案研究得更少。

目前，PQ 签名的两个主要候选方案是基于哈希和基于格的构造。对于基于哈希的密码学，Blockstream 已经开展了非常富有成效的分析和研究：例如，参见 Jonas Nick 和 Mikhail Kudinov 的 "比特币的基于哈希签名方案" 调查或 Jonas Nick 的 SHRIMPS。现在轮到基于格的构造了！

重要

我们注意到还有基于码的构造，但它们的公钥或签名都非常大：例如，一个著名的（之前的）NIST 候选方案 LESS 的公钥大小从 13.9KB 起。也就是说，目前它们看起来不像比特币的可行选项。

本博客的主题

如上所述，我们将考虑基于格签名方案背后的基本思想。特别是，读完这篇博客后，大家将扎实掌握一种称为带中止的 Fiat-Shamir（又名拒绝采样）的关键技术，该技术用于 Dilithium 或者，例如，许多基于格的证明系统（参见 基于格的乘积证明）。令人惊讶的是，这种技术与基于离散对数假设的经典 Schnorr 签名构造非常相似。在此过程中，我们将提供理解基于格方案的基本工具包，希望能使密码学这一领域的入门变得更容易。

更具体地说，在这篇博客中，我们将理解 Lyubashevsky 在其著名论文"无陷门的格签名" 中的构造，这可以说是整个基于格密码学中最有影响力的论文之一。

格简介

格

让我们介绍主要的研究对象。我们将秩为 $m$ 的格 $\Lambda\subseteq\mathbb{R}^d$ 定义为 $\mathbb{R}^d$ 中某个固定线性无关向量集 $b_1,\dots,b_m$ 的所有整数线性组合（其中 $m\leq d$）。也就是说，$\Lambda\triangleq{\sum_{i=1}^m \lambda_i b_i:\lambda_1,\dots,\lambda_m\in\mathbb{Z}}$。

作为更好地可视化此对象的具体示例，请考虑下面的二维（$m=d=2$）格。

图 1. 由向量 $b_1=(3,1)$ 和 $b_2=(2,3)$ 张成的秩 2 格示例。生成的格 $\Lambda$ 是蓝色点的集合。

当我第一次看到这个定义时，不禁纳闷"我们能从这个看似直白的定义中得到什么有用的东西？" 然而，在密码学家注意到格是大量计算困难问题的来源之前，格首先在数学中被证明是有用的，至少从 18 世纪开始就已经被使用。事实上，格自然出现在许多领域，如数论或球堆积（两者都以某种方式与格和基于码的密码学相关）。

注意

有时我会遇到一种误解，认为"与基于哈希的密码学相比，格太不成熟了。" 然而，格早在哈希函数被发明之前就已经被使用和研究过了 （后者大约可以追溯到 1950 年）。

然而，格的代数结构确实比哈希丰富得多。虽然这使得许多高级密码协议成为可能（例如，多重签名或 SNARK），但我们仍然需要非常谨慎地对待安全性。

密码学中的格问题

基于格的密码学 围绕可归约为求解格 $\Lambda$ 上某些困难问题的假设展开。反过来，这些问题目前被认为即使对量子计算机也是困难的。目前有大量的此类假设：例如，最短向量问题 (SVP)、最近向量问题 (CVP)、有界距离解码 (BDD)、格同构问题 (LIP)、判定性最短向量问题 (GapSVP) 等。

在这篇博文中，我们只需要这些假设中的一个。

（近似）最短向量问题（$\gamma$-SVP）。 目标是在 $\Lambda$ 上找到一个"非常短"的向量。可以（相当容易地）证明 $\Lambda$ 包含一个最短向量（即存在 $u\in\Lambda$ 使得 $|u|=\min_{v\in\Lambda}|v|$，其长度记为 $\lambda_1(\Lambda)$），但找到这样的向量被认为即使对量子计算机也是一个困难问题。我们将此问题称为 SVP。

然而，直接基于上述"原始" SVP 构建实用协议几乎是不可能的。我们放宽了这个问题的要求：假设我们接受范数低于 $\gamma\lambda_1(\Lambda)$ 的向量，对于某个因子 $\gamma>1$。事实证明，即使对于相对较大的因子，例如 $\gamma=\operatorname{poly}(d)$，这种修改后的问题仍然是困难的。我们将此修改后的问题称为 $\gamma$-SVP。

下图说明了这个问题。

图 2. $\gamma$-SVP 的说明。考虑由 $b_1=(3,8)$ 和 $b_2=(4,6)$ 张成的格 $\Lambda'$（注意，它是之前图 1 中定义的格 $\Lambda$ 的一个子格）。它的两个最短向量是 $u=(-1,2)$ 和 $-u$，每个长度为 $\lambda_1(\Lambda')=5$。对于 $\gamma\approx 2.61$ 的近似版本 $\gamma$-SVP 包括寻找长度低于 $34$ 的向量（图中用紫色标记）。例如，长度为 $20$ 的 $u'=(2,-4)$ 是近似 SVP 的解，但不是标准 SVP 的解。

短整数解

虽然直接基于格假设构建密码系统是可能的（例如，Hawk 正是这样做的），但我们通常使用其他具有格假设归约的假设。两个最著名的例子是短整数解 (SIS) 和带误差学习 (LWE)。对于这篇入门博客，我们将关注前者。

考虑线性方程 $Ax=0$，其中 $A\in\mathbb{Z}q^{n\times m}$。解这个方程很容易（例如，简单地通过高斯消元）。然而，假设我们要求解 $x\in\mathbb{Z}^m$ 是"短的"：即对于某个 $\beta\ll q$，$|x|\infty<\beta$（其中 $|x|\infty:=\min{i\in[m]}|x_i|$ 表示 $\ell_\infty$ 范数）。我们将此类问题实例称为 $SIS_{q,n,m,\beta}$，并且对于合适的参数选择 $q,n,m,\beta$，即使对量子计算机也是指数级困难的。

练习 1. 证明如果 $m>n\log q \log(1+\beta)$，则 $SIS_{q,n,m,\beta}$ 的解存在。

此外，进一步用 $S_\eta$ 表示"短"向量的集合，其中 $S_\eta:={x\in\mathbb{Z}^n:|x|_\infty\leq \eta}$。

非齐次 SIS

此假设的一个重要变体是考虑同一方程的非齐次形式：$Ax=t$。这种修改已经允许我们考虑判定性假设而不是搜索假设。具体来说，我们引入非齐次短整数解 (ISIS)，该假设指出区分以下两个分布 $D_0$ 和 $D_1$ 在计算上是困难的：

• $D_0$：从 $\mathbb{Z}_q^{n\times m}\times \mathbb{Z}_q^n$ 中随机选取一个样本；
• $D_1$：采样 $A\leftarrow_R \mathbb{Z}q^{n\times m}$，采样一个短的 $s\in\mathbb{Z}^m$（使得 $|s|\infty<\delta$），计算 $t\leftarrow As$，并输出元组 $(A,t)$。

可以证明，对于底层 $\beta$ 和 $\delta$ 之间的适当关系，ISIS 等价于 SIS。这个假设允许我们如下构建密钥生成：

• 秘密密钥 是由短元素组成的矩阵 $S\in S_\eta^{m\times k}$。
• 公钥 是 $T:=AS$，其中 $A\in\mathbb{Z}_q^{n\times m}$ 是随机的。

练习 2. 证明从公钥恢复秘密密钥的问题等价于求解 ISIS（假设 $k=\operatorname{poly}(n)$）。

与格的关系

在这里你可能要问：格在哪里？一个适合这篇博客的合理解释如下：对于矩阵 $A$ 的 $SIS_{q,n,m,\beta}$ 实例，定义以下格：$\Lambda_A^\perp={z\in\mathbb{Z}^m: Az=0 \pmod{q}}$。

观察： 求解 $SIS_{q,n,m,\beta}$ 等价于求解适当 $\gamma$ 下的 $\gamma$-SVP。这从 $\Lambda_A^\perp$ 的定义可以直接看出：这个格上的任何向量都是 $Ax=0$ 的解；如果我们能够解这个格上的 SVP，本质上就找到了这个方程的短解，这正是 SIS 所要求的。

第 2 节：带中止的 Fiat-Shamir

动机

我们刚刚看到，基于格的假设允许我们构造单向映射 $S\mapsto AS$，其中 $A$ 是公开矩阵，$S$ 是"短"矩阵。这在某种程度上类似于在循环群 $G=\langle a\rangle$ 中，给定离散对数假设成立，映射 $s\mapsto a^s$ 是单向的。这促使我们问自己以下问题：

我们能否"重现" Schnorr 签名协议，但不是使用群乘法映射 $s\mapsto a^s$，而是使用映射 $S\mapsto AS$？

答案竟然是肯定的！然而，这并不像看起来那么简单；因此才有了后缀"with aborts"。在本节的其余部分，我们将研究如何使这个想法奏效。

Schnorr 签名方案

当然，我们需要回顾一下 Schnorr 签名是如何工作的。描述签名方案就是指定三个过程：

• $\operatorname{KeyGen}(1^\lambda)\to(pk,sk)$：生成密钥对；
• $\operatorname{Sign}(sk,\mu)\to sig$：使用秘密密钥 $sk$ 对消息 $\mu$ 签名，从而产生签名 $sig$；
• $\operatorname{Verify}(pk,\mu,sig)\to{0,1}$：基于公钥 $pk$ 验证消息 $\mu$ 上的签名 $sig$。

Schnorr 签名无疑是基于离散对数假设构建签名方案的最优雅、高效、最简单的方法，目前已在比特币中广泛使用。然而，我们首先应该从 Schnorr 识别协议 开始。具体来说，假设阶为 $q$ 的群 $G$ 由 $g\in G$ 生成；那么，为了证明签名者知道对应于公钥 $h\in G$（满足 $g^\alpha=h$）的秘密密钥 $\alpha$，他参与如下所示的交互协议：

图 3. 密钥对 $(\alpha,h)$ 上的 Schnorr 识别协议（其中 $h=g^\alpha$）。

Fiat-Shamir 启发式 允许签名者通过哈希函数 $H:G^2\to\mathbb{Z}_q$ 确定性地导出 $e$，从而避免与验证者交互。具体来说，签名者计算挑战 $e$ 为 $e\leftarrow H(h,a)$；这种情况下的"证明"是 $(e,z)$。最后，要构建 签名方案，只需将消息 $\mu$ 纳入挑战 $e$ 的推导中。具体来说，$\operatorname{Sign}(h,\mu)$ 的工作方式如下：

• 像之前一样，构建对某个随机掩码标量 $r\leftarrow_R \mathbb{Z}_q$ 的承诺 $g^r$；
• 计算挑战为 $e\leftarrow H(\mu,a)$；
• 计算标量 $z=r+\alpha e$ 来掩码底层的秘密 $\alpha$；输出 $(e,z)$ 作为签名。

最后，验证者可以通过 $e\stackrel{?}{=}H(\mu,g^z h^{-e})$ 来检查签名 $(h,\mu,\sigma)$。

尝试 #1："格" Schnorr 签名

既然我们已经发现 $S\mapsto AS$ 看起来像前量子对应物 $\alpha\mapsto g^\alpha$，让我们尝试简单地将这个单向映射套用到上述 图 4 的 Schnorr 识别协议中。自然的第一次尝试可能是这样的（我们选择 $r$、$a$ 和 $e$ 的维度，使得矩阵乘法有意义）：

_图 4. 密钥对 $(S,T)$ 上"格" Schnorr 识别协议的尝试 #1（其中 $T=AS$，$T\in\mathbb{Z}_q^{n\times k}$，$A\in\mathbb{Z}_q^{n\times m}$，$S\in\mathbb{Z}q^{m\times k}$）。

首先，这个方案是否正确？让我们将所有值代入验证方程：$Az=A(Se+r)=(AS)e+(Ar)=Te+a$。

因此，方案是正确的。但它可靠吗？完全不可靠。可以找到许多理由说明这个方案为何失败。例如：

1. 给定 $a\in\mathbb{Z}_q$，很容易找到 $r$ 使得承诺方程 $a=Ar$ 成立。实际上，这只是在 $\mathbb{Z}_q$ 上求解线性方程的问题。
2. 即使假设承诺 $a$ 是绑定的，即使没有秘密密钥 $S$，也有可能找到满足方程 $Az=Te+a$ 的 $z$。同样是，在找到任意 $e$ 后，只需解线性方程即可。

看来我们此时无计可施了。

尝试 #2：让一切变小

注意，尝试 #1 是不安全的，因为我们可以轻易伪造 $z$ 并从 $a$ 恢复 $r$。这是可能的，因为它们是相应线性方程组的任意解。正如我们在 SIS 假设中看到的，如果我们让 $z$ 和 $r$ 都"短"，就有望修复这个协议的可靠性。那么让我们尝试这样做。我们将从某个短分布 $\chi^m$ 中采样随机性 $r$（想象一个在 $\mathbb{Z}q$ 上的分布 $\chi$，其中采样值的 $\ell\infty$ 范数被某个小的 $\varepsilon\in\mathbb{Z}{>0}$ 所界定）。让 $z$（即 $r+Se$）变短则更棘手：虽然 $r$ 现在是短的，但我们需要确保 $Se$ 也是短的。因此，由于 $S$ 已经很小，我们需要确保 $e$ 既短又足够大。具体来说，我们将从集合 $B\kappa$ 中采样它，其中：

$B_\kappa:={x\in \mathbb{Z}_q^k: x_i\in{0,\pm1}\text{ 且非零 } x_i\text{ 的数量为 } \kappa}$。

坦率地说，这个集合是凭空出现的（就像基于格密码学中的许多其他事情一样）。使用这个集合的原因大致如下：

• 我们希望挑战集足够大；这个集合满足这一点（见下面的 练习 3）；
• 我们希望这个挑战集的元素很小；显然这成立，因为对于每个 $e\in B_\kappa$，有 $|e|_\infty=1$；
• 理想情况下，我们希望哈希到 $B_\kappa$ 的实现尽可能简单：事实也是如此，因为 $B_\kappa$ 的元素可以被视为三元字符串。

练习 3. 证明挑战集 $B_\kappa$ 的两个性质：(a) $#B_\kappa = 2^\kappa \binom{k}{\kappa}$（即这个集合相当大），(b) 对于任意 $S\in S_\eta^{m\times k}$，有 $|Se|_2 \leq \eta\kappa m$，其中 $|\cdot|_2$ 表示标准欧几里得范数（即，我们有一个关于计算 $z$ 时涉及的 $Se$ 范数的良好界限）。

现在，由于 $e$ 和 $r$ 都是短的，$z$ 也是短的。因此，为了防止敌手发送大的 $e$ 和 $r$，我们检查 $|z|2$ 是否足够小（即低于某个阈值 $\tau$；例如可以取 $\tau:=\max{e\in B_\kappa}|Se|2 + \mathbb{E}{r\sim\chi^m}[|r|_2]$，但这对于当前讨论层次无关紧要）。

考虑到这些修改，我们的第二次尝试如下：

_图 5. 密钥对 $(S,T)$ 上"格" Schnorr 识别协议的尝试 #2（其中 $T=AS$，$T\in\mathbb{Z}_q^{n\times k}$，$A\in\mathbb{Z}_q^{n\times m}$，$S\in\mathbb{Z}q^{m\times k}$）。

这个方案正确吗？是的，原因与尝试 #1 相同。

它可靠吗？嗯，让我们检查一下"平凡"的攻击：

• 我们能否找到短的 $r$ 使得 $Ar=a$？这相当于求解 ISIS，因此似乎不可行；
• 我们能否找到短的 $z$ 使得 $Az=Te+a$？（即，不知道 $S$）同样，这是 ISIS 问题的一个实例，难以求解。

所以……我们现在能得出结论说这个方案是可靠的吗？……不能！

然而，现在的原因要微妙得多，且可以在安全性证明中看得更清楚。这里有一个简单解释：回顾一下，以这种方式计算 $z$ 的整个目的是为了"掩盖"底层的秘密 $S$。但是，我们能声称 $z$ 和 $S$ 是独立的吗？并不完全。

注意

对于记得 Schnorr 安全性证明的人来说，下面的解释可能更令人满意：回想一下，EUF-CMA 证明包括 (a) 模拟诚实的签名者，(b) 使用分叉引理提取底层秘密。在 图 5 中，完全不清楚如何做 (a)：具体来说，从哪里采样 $z$。即使我们知道 $z$ 的分布，它也可能依赖于 $S$，这会使模拟出现问题。

出于这个原因，我们需要以某种方式使 $z$ 和 $S$ 独立。但如何做呢？事实证明，以下想法是有效的：

在生成候选对 $(e,z)$ 后，检查所得到的 $z$ 是否"足够好"。如果不是，则丢弃它并重复签名过程。

这正是底层范式被称为"拒绝采样"或带中止的 Fiat-Shamir 的原因：如果我们对生成的值不满意，就中止签名过程的执行。但 $z$ "足够好"是什么意思？为此，我们将选择一个具体的分布 $\chi$，它将为我们带来一些好的性质，并分析 $z$ 与 $S$ 之间的统计距离何时可以忽略。

离散高斯分布

如果你认为挑战空间 $B_\kappa$ 的选择是随意的，那么这里有一个当初我开始学习基于格签名时对我来说完全随意的东西。介绍高斯分布 $D_{\sigma,v,\Lambda}^m$，定义在格 $\Lambda\subseteq\mathbb{R}^m$ 上，宽度参数为 $\sigma\in\mathbb{R}_{>0}$，中心为 $v\in\mathbb{R}^m$，如下：

$D_{v,\sigma,\Lambda}^m(z) := \rho_{v,\sigma}^m(z) / \rho_{v,\sigma}^m(\Lambda)$，其中 $\rho_{v,\sigma}^m(z) := \exp(-|z-v|_2^2 / 2\sigma^2)$。

这里，我们滥用符号，对于离散集合 $\Omega\subseteq\mathbb{R}^m$，用 $\rho_\sigma^m(\Omega)=\sum_{w\in\Omega}\rho_\sigma^m(w)$ 表示。当 $\Lambda=\mathbb{Z}^m$ 和 $v=0$ 时，我们在下标中省略 $\Lambda$ 和 $v$。

我相信这个定义需要一些解释。关键在于，我们分配给格 $\Lambda$ 上每个点 $z$ 的概率与 $\exp(-|z-v|2^2/2\sigma^2)$ 成正比。为了使之成为一个有效的概率分布，我们需要将这些概率除以一个归一化常数 $\sum{w\in\Lambda} \exp(-|w-v|_2^2/2\sigma^2)$。

原则上，之所以命名为离散高斯，正是因为该分布非常类似于连续高斯分布（其中密度为 $e^{-|z-v|^2/2\sigma^2} / \int_{\mathbb{R}^m} e^{-|z-v|^2/2\sigma^2} dz$；在连续情况下，分母中的积分恰好是可计算的）。此外，如果看一下这种分布的形态，会立刻认出标准多元高斯分布：

图 6. 二维离散高斯分布。图取自 Ducas、Durmus、Lepoint 和 Lyubashevsky 的论文 "格签名和双峰高斯"。

为什么选择离散高斯？

我相信，对于"为什么选择这个特定的分布"这个问题的答案，类似于我们为什么在统计中使用连续高斯分布。这是一个自然的选择，因为它在许多运算下表现良好（例如，在傅里叶变换、Rollup下；离散高斯的和在统计上接近于单个离散高斯等）。

然而，就我们的问题（使 $z$ 和 $S$ 独立）而言，我们需要离散高斯的以下两个性质。

性质 (A)（来自 $D_\sigma^m$ 的样本以压倒性概率是短的）。对于任意 $\beta>1$，有：$\Pr[|z|2 > \beta\sigma m \mid z\leftarrow_R D\sigma^m] < \beta^m e^{m(1-\beta^2)/2}$。

性质 (B)（中心化和非中心化高斯的比率几乎总是有界的。）对于任意 $v\in\mathbb{Z}^m$，如果 $\sigma = \alpha|v|$，有：$\Pr[D_\sigma^m(z) / D_{v,\sigma}^m(z) < e^{12/\alpha + 1/(2\alpha^2)} \mid z\leftarrow_R D_\sigma^m] > 1 - 2^{-100}$。

这两个事实的证明都是纯机械的。例如，参见 Lyubashevsky 的原始论文 第 4 节。我们将进一步将"神奇"常数 $e^{12/\alpha + 1/(2\alpha^2)}$ 记为 $M_\alpha$。

练习 4. 假设 $\alpha>1$，$M_\alpha$ 的可能范围是多少？

虽然我相信 性质 (A) 是直观的（我们将对略微大于 $1.0$ 的 $\beta$ 使用它），但你可能想知道为什么我们需要 性质 (B)。我们将在下一小节中揭示这一点。

拒绝采样

现在让我们在 图 6 中设置 $\chi^m := D_\sigma^m$。$z$ 具体是如何分布的？由于 $z=Se+r$ 且 $r\sim D_\sigma^m$ 是中心化的离散高斯，$z$ 是带有小偏移向量 $Se$ 的"有偏"高斯分布 $D_{Se,\sigma}^m$。

这正是问题所在：$z$ 的分布依赖于小的偏移 $Se$；因此，通过观察具有相同 $S$ 的多个 $z$，敌手可能获得关于 $S$ 的信息。

如果能消除这个偏移就好了……以下引理将会拯救我们：

引理。 设 $f$ 和 $g$ 是两个概率分布，支集为 $\Omega$，并且对于所有 $z\in\Omega$ 和某个固定常数 $M\in\mathbb{R}_{\geq 1}$，满足 $f(z)\leq M g(z)$。那么，以下分布（称为 $\tilde{f}$）与分布 $f$ 相同：

1. 采样 $z\leftarrow_R g$。
2. 以概率 $f(z)/Mg(z)$ 输出 $z$，否则回到步骤 1。

该引理的大致思想是，如果 $f$ 是我们的"目标分布"，而 $g$ 是"真实分布"，那么如果 $f$ 和 $g$ 之间逐点存在一个良好的不等式，我们可以通过以依赖于采样值的概率丢弃来自 $g$ 的样本来模拟 $f$ 的分布。

这个过程有一个很好的可视化效果，如下所示（类似于 图 7，取自 BLISS 论文，该论文的插图非常出色）。假设 $f$ 和 $g$ 满足引理中的不等式，使得 $Mg$ 位于 $f$ 之上。那么，拒绝采样包括首先在 $Mg$ 下选择一个点，然后进一步以概率接受它是否在 $f$ 之下。

图 7. 拒绝采样过程说明。图取自 Ducas、Durmus、Lepoint 和 Lyubashevsky 的论文 "格签名和双峰高斯"。

这个引理让你想起了什么？关键的技巧是如下应用这个引理：

1. 我们的"目标"分布 $f$ 是无偏的离散高斯 $D_\sigma^m$；
2. 我们的"真实"分布 $g$ 是有偏的高斯 $D_{Se,\sigma}^m$。

我们可以应用这个引理吗？这就是离散高斯的 性质 (B) 发挥作用的地方：我们有一个神奇常数 $M_\alpha$，使得 $D_\sigma^m(z) \leq M_\alpha D_{Se,\sigma}^m(z)$ 以压倒性概率成立！（此外，从 $|Se|_2 \leq \eta\kappa m$ 的事实可以很容易地确定 $\alpha$：参见 练习 3）。

警告

为了完全严谨，需要调整引理，使得不等式 $f(z)\leq M g(z)$ 以压倒性概率 $1-\varepsilon$ 成立。然后可以证明，在这种情况下，分布 $\tilde{f}$ 与分布 $f$ 的统计距离为 $\varepsilon/M$。

尝试 #3：Lyubashevsky 签名

最后，为了修复 图 2 中的方案，我们只需以概率 $D_\sigma^m(z) / M_\alpha D_{Se,\sigma}(z)$ 接受 $(e,z)$。这修复了整个方案。参见下面的图示。

图 8. 修复后的基于格的 Schnorr 协议（本质上是 Lyubashevsky 论文中的原始方案）。

安全性证明概要*

注意

以下内容完全是可选的。

回顾一下，要证明签名方案是安全的，我们需要 (a) 模拟一个诚实的签名者，以及 (b) 使用分叉引理提取某个困难问题实例的解。

步骤 (a) 是拒绝采样引理的一个简单应用：不再先采样 $r\leftarrow_R D_\sigma^m$，计算挑战 $e\leftarrow H(Ar,\mu)\in B_\kappa$，然后输出候选 $(e,z:=Se+r)$，而是先采样 $z\leftarrow_R D_\sigma^m$ 和 $e\leftarrow_R B_\kappa$，然后将随机预言机重编程为 $H(Az-Te,\mu)\leftarrow e$。

步骤 (b) 假设敌手以不可忽略的概率 $\delta$ 输出一个有效的签名 $(z,e)$，根据分叉引理，他以 $\propto \delta^2$ 的概率输出另一个有效的签名 $(z^,e^)$。此外，底层随机性相同，即 $Az-Te = Az^-Te^$。

利用 $T=AS$ 的事实，我们得到 $A((z-z^)+S(e^-e))=0$，其中 $(z-z^)+S(e^-e)$ 是 $Ax=0$ 的一个短解。因此，我们构建了从破解签名到求解适当 SIS 实例的归约。

性能

坦率地说，上述方案非常低效。原始论文提出的参数中，签名大小为 19.9KB，公钥大小为 128KB。尽管如此，上面提出的想法可以大量优化。具体来说：

• 几乎所有论文都使用环 $R_q:=\mathbb{Z}_q[X]/(X^d+1)$（其中 $d$ 是 2 的幂）而不是 $\mathbb{Z}_q$。至于为什么这个环更高效，超出了本博客的范围。
• 可以选择不同于离散高斯的分布。例如，BLISS 签名方案 提出使用双峰高斯分布，并几乎直接重用上述构造。生成的签名大小为 5.6KB，公钥大小为 7KB。不幸的是，该方案被发现对侧信道攻击不安全。

如果将离散高斯改为均匀分布，则得到 Dilithium。然而，不出所料，拒绝采样的想法会显著不同（并且在某种程度上简化了）。

下一步

在这篇博客中，我们考虑了基于格签名的一个关键范式：带中止的 Fiat-Shamir。虽然它涵盖了众多构造（并且隐含地用于大多数论文中），但还有另一个称为哈希然后签名的范式，对于理解 Falcon 或 Hawk 是必要的。这些方案直接利用格的几何结构：首先将消息 $\mu$ 哈希到 $\mathbb{Z}^{2n}$ 中的一个点，然后使用格的某种秘密几何特征来变换这个点（在 Hawk 的情况下，秘密密钥是某个特定格的短基 $B$，而公钥是二次型 $B^\top B$；在 Falcon 的情况下，公钥是格基，而秘密密钥是正交格的基）。

这个方向无论是在学术界还是工业界都持续吸引着大量关注，这是有充分理由的。我们正在积极探索这些想法，并将在未来的博文和 Blockstream 的材料中再次讨论它们。

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