参考文献：EUROCRYPT2021-AH21

1 ECDSA与HNP

ECDSA 是一种基于椭圆曲线密码学的数字签名算法。它被广泛应用于现代密码系统中，例如比特币、以太坊等区块链系统，以及其他需要安全通信的场景（如TLS证书）。

ECDSA 的核心思想是利用椭圆曲线上的数学性质实现签名生成和验证，同时相比传统签名算法（如 RSA）提供更高的安全性和更短的密钥长度。

1.0 椭圆曲线理论

椭圆曲线，可以理解为一个三次曲线的解的集合。将其描绘到射影平面上，是一条光滑的曲线，在拓扑结构上等价于圆环。其通用的三次曲线方程可以表达为：

上式为 Weierstrass 方程。同时，为避免出现不可微、不平滑的奇异点，还需要约束条件 $ \Delta \neq 0 $，其中：

在素数域中，Weierstrass 方程可以进行简化。为满足单位元的需求，需引入一个无穷远点，作为单位元。于是有素数域 $ GF(p) $ 上椭圆曲线 $ E $ 的方程为：

及其约束条件为: $4a^3+27b^2 \neq 0$.

  • 注意：weierstass曲线在素数域下的形式是“化简”得到的。通过线性变换：$y = y{\prime} - \frac{c_1}{2} x - \frac{c_3}{2}, x = x{\prime} - \frac{c_2}{3}$

1.1 ECDSA 签名机制

ECDSA 签名的全局参数包括：

  • 一个椭圆曲线 $E(F_p) $，
  • $ E $ 上的一个阶为 $ n $ 的生成点 $ G $。
    • (椭圆曲线上的每个点也有一个阶，这是指最小的正整数$n$，使得$nP = O$，其中$O$是无穷远点，也就是椭圆曲线群的单位元。一个点的阶可以看作是该点生成子群大小的度量。在选择椭圆曲线进行加密操作时，通常会选择一个基点$G$，其阶$n$是一个大素数，这样可以确保相关的离散对数问题足够困难，从而保证系统的安全性)

签名密钥是一个满足 $ 0 \leq d < n $ 的整数，而公钥是点 $ dG $。（已知$dG$和G想要得到$d$是困难的）为了对消息摘要 $ h $ 生成 ECDSA 签名，签名者需要：

  1. 生成一个随机整数随机数 $ k < n $（$k$是秘密的）；
  2. 计算 $ r = (kG)_x $（其中下标 $ x $ 表示点的 $ x $-坐标），
  3. 再计算 $ s = k^{-1} \cdot (h + d \cdot r) \mod n $。

最终签名为 (r, s)。

验证签名
根据签名公开结果 $ r $ 与 $ s $，有：

将式 (a) 两边同时乘以 $ ks^{-1} $，有：

将式 (b) 的指数展开，发现 $ zs^{-1} = u_1 $，$ rd s^{-1} = u_2 $，于是有：

又 $ Q = d G $，于是得到：

如此，若满足等式 $ kG = u_1 G + u_2 Q \pmod{n} $，就可以认为签名是正确的。式 (d) 也是椭圆曲线验签步骤中的计算结果。

1.2 隐藏数问题

在隐藏数问题（HNP） 中：一个秘密整数 $\alpha$ 和一个公开的模数 $n$。

  • 关于 $\alpha$ 的信息：sample。

(1) sample生成过程（$sample_i$可以得到pair$(t_i, a_i)$）

  1. 一个oracle随机选择一个整数 $t_i$，满足 $0 < t_i < n$。
  2. 计算 $ t_i \cdot \alpha \equiv s_i\mod n$，其中 $0 \leq s_i < n$。
  3. oracle会揭示 $s_i$ 的某些最高有效位（most significant bits）以及对应的 $t_i$。

(2) 数学表示

该问题可以形式化为：$
a_i + k_i = t_i \cdot \alpha \mod n
$, 其中 $k_i < 2^\ell$，$\ell \in \mathbb{Z}$ 是问题的一个参数（未知比特数）。

  • 攻击者已知: $(t_i, a_i)$。

1.3 ECDSA 作为 HNP 问题

在对 ECDSA 的侧信道攻击中，对手可能会获知签名随机数 $ k $ 的一些最高有效位, 假设这些位均为 0。然后重新整理 ECDSA 签名公式 $ s = k^{-1} \cdot (h + d \cdot r) \mod n $，可以得到：

因此得到了一个 HNP 实例，其中：

  • $ a_i = -s^{-1} \cdot h $,
  • $ t_i = s^{-1} \cdot r $,
  • $ \alpha = d $。

目标：根据泄露的$k$的比特信息计算出私钥$d$。

  • 在模 $n$ 的意义下，整数 $a$ 的 模逆元 是指一个整数 $x$，使得满足同余关系：
    根据 $B\acute{e}zout$ 定理，对于任意整数 $a$ 和 $n$，若它们的最大公因数满足：那么必然存在整数 $x$ 和 $k$，使得：这表明同余方程：$a \cdot x \equiv 1 \pmod{n}$ 一定存在整数解 $x$，即 $a$ 存在模逆元。
  • 如果 $\gcd(a, n) \neq 1$，若 $\gcd(a, n) = d \neq 1$，则 $B\acute{e}zout$ 定理表明：由于右侧为 $d$ 的倍数，而等式右侧等于 1，因此：$d \mid 1$
    显然只有 $d = 1$ 时该等式才可能成立。否则，当 $d \neq 1$ 时，方程$a \cdot x \equiv 1 \pmod{n}$ 无整数解，即：在此情况下，$a$ 不存在模 $n$ 的逆元。

1.4 从随机数比特破解ECDSA

许多文献利用 ECDSA随机数的侧信道信息，通过解决 隐藏数问题（HNP） 来攻击 ECDSA，例如 [12,19,44,53,61,63,68,69,73,78]。这一研究领域始于 Bleichenbacher [18] 和 Howgrave-Graham 与 Smart [43] 的开创性工作。

  • Bleichenbacher 的研究：采用了一种可以视为 BKW 算法 [3,20,39,47] 变体的组合算法。
  • Howgrave-Graham 与 Smart 的研究：利用格基约化方法来解决 HNP。

最新的相关研究成果是 [13]，该工作利用 Bleichenbacher 的算法在随机数比特少于 1 位的情况下成功恢复密钥。更近期的研究 [54] 则首次发现了一个 实际可行的攻击场景，能够利用 Boneh 和 Venkatesan [21] 提出的 HNP 原始应用，即针对素域 Diffie-Hellman 密钥交换的攻击。

1.5 侧信道攻击

针对 ECDSA 的实际侧信道攻击通常分为两个阶段：

  1. 攻击者通过侧信道测量收集大量签名数据。
  2. 然后，攻击者在一个精心选择的签名数据子集上运行密钥恢复算法。

根据测量的鲁棒性，数据收集阶段可能会非常昂贵。例如：

  • 在 [60] 中，研究人员报告需要重复攻击 10,000 到 20,000 次 才能获得 1 字节信息（RSA）。
  • 在 [37] 中，研究人员测量了 5,000 次签名操作（每次操作耗时 0.1 秒），从中提取了 114 条可用轨迹。
  • 在 [61] 中，研究人员描述了生成 40,000 个签名（耗时 80 分钟），以获取 35 条适用轨迹来完成攻击。
1
2
3
4
5
6
7
“Examining the denoised trace, we can now attempt to extract the DA-sequence. For this purpose, we turn to the time-frequency domain. The middle of Figure 6 depicts the spectrogram of a denoised trace, where the frequency band containing most of the energy of addition operations becomes especially clear.” .

trace 是对签名操作期间采集到的信号数据的记录，经过去噪处理后，可用于提取特定的计算序列，例如椭圆曲线加法和倍加运算。

“After performing signal denoising, we apply correlation-based detection to identify all instances where this distinct pattern occurs. We thus obtain the end points for most signing operations. We ignored some traces that ended in distorted patterns that did not correlate well.” .

这说明”trace”不仅仅是采集的数据，还需通过信号处理方法进一步提取特征，以识别特定操作的时间位置。

因此，在侧信道攻击的研究中，减少成功攻击所需的数据量 通常是一个重要的衡量指标 [44,68]。利用本文所述方法，可以实现更高效的整体攻击。

1.6 基础知识

定义 1: 高斯启发式(GH)：

我们使用符号 $\text{gh}(\Lambda)$ 表示根据高斯启发式估计的格 $\Lambda$ 中最短非零向量的长度。

在 $d-$维空间中，格点的分布可以近似视为均匀分布,在一个半径为 $r$ 的 $d-$维球中，如果大约可以找到一个格点，那么$r$可以用来估计最短非零向量的长度。

一个 $d$-维球的体积公式为：

其中：

  • $\text{Vol}(\mathcal{B}_d(r))$：半径为 $r$ 的 $d$-维球的体积；
  • $\text{Vol}(\mathcal{B}_d(1))$：单位球的体积（半径为 1 的球）。

将球的体积与格的体积相等，即：

整理得：

定义：
对于一个满秩格$\Lambda \subset \mathbb{R}^d$，其高斯启发式定义为：

其中：

  • $\text{Vol}(\Lambda)$：格的体积，由格基向量的行列式确定；
  • $\text{Vol}(\mathcal{B}_d(1))$：单位半径的 $d$-维欧几里得球的体积。

单位半径 $d$-维球的体积公式为：

其中 $\Gamma$ 是伽马函数。

因此，高斯启发式可表示为：

在高维格中（当 $d$ 很大时），可以进一步近似为：

  • $\Lambda$：一个 $d$-维格；
  • $\mathcal{B}_d(R)$：半径为 $R$ 的 $d$-维欧几里得球；
  • $\text{Vol}(\Lambda)$：格的体积；
  • $\text{Vol}(\mathcal{B}_d(1))$：单位半径球的体积。

定义 2: 最短向量问题 (SVP)：

给定一个格基 $B$，找到格 $\Lambda(B)$ 中的最短非零向量。

在许多应用中，我们更感兴趣的是找到离目标向量最近的格向量。在这种情况下，如果目标向量距离格不是太远，我们称之为有界距离解码。

定义 3: $\alpha$-有界距离解码问题 (BDD$_\alpha$)

给定：

  • 一个格基 $B$，
  • 一个目标向量 $t$，
  • 一个参数 $0 < \alpha$，使得目标点 $t$ 与格的欧几里得距离满足：

求一个格向量 $\mathbf{v} \in \Lambda(B)$，使其为距离 $t$ 最近的格点。

唯一解的保证：为了保证解的唯一性，通常要求 $\alpha < 1/2$。但实际上，这个问题可以推广到 $1/2 \leq \alpha < 1$，在这种情况下，我们可以期望高概率找到唯一解。

  • 在渐近意义下，对于任意多项式有界的 $\gamma \geq 1$，可以通过从 BDD$_{1/(\sqrt{2}\gamma)}$ 到 uSVP$_\gamma$ 的归约解决问题。

定义 4: $\gamma$-唯一最短向量问题 (uSVP$_\gamma$)

给定一个格 $\Lambda$，假设满足：

  • 第二短向量的长度 $\lambda_2(\Lambda)$ 满足：

找到格中满足长度为 $\lambda_1(\Lambda)$ 的非零向量。

从 BDD 到 uSVP 的归约

基于Kannan嵌入：嵌入矩阵 $L$ 的构造：

其中：

  • $\tau$ 是嵌入因子，通常可以认为：$ \tau = \mathbb{E}\left[|t - \mathbf{v}| / \sqrt{d}\right]$，这是目标向量 $t$ 与格向量最近点 $\mathbf{v}$ 之间的预期距离。

解释：如果 $\mathbf{v}$ 是目标向量 $t$ 的最近向量，则新格 $\Lambda(L)$ 将包含向量：

这个向量是一个较短的向量，便于通过算法找到。

1.7 枚举

问题描述：

给定一个矩阵 $B$ 和一个范围 $R$，目标是找到满足以下条件的向量 $\mathbf{v}$：

其中至少一个 $u_i \neq 0$，并且：

枚举算法使用以下公式表示向量 $\mathbf{v}$：

因此，向量 $\mathbf{v}$ 的投影长度 $|\pi_k(\mathbf{v})|^2$ 表示为：

格点枚举是一种深度优先搜索（depth-first search），其基本流程如下：

  1. 依次为 $u_{d-1}, u_{d-2}, \dots$ 选择候选值。
  2. 检查当前子树中的节点是否满足约束条件 $|\mathbf{v}|^2 \leq R^2$：
    • 如果不满足，则回溯并选择下一个分支。
    • 如果满足，则继续枚举更低的分支。
  3. 当遍历完所有分支后，返回找到的最短向量。

枚举算法的复杂度可以通过节点数量来估计：

第$k$层：在 $d-k$ 维空间中，满足约束的节点实际上是格点的集合： $d-k$ 维球体积/每个格点的体积/2$\approx$满足约束的格点数。

其中：

  • $\text{Vol}(\mathcal{B}_{d-k}(R))$：半径为 $R$ 的 $d-k$ 维球的体积；
  • $|\mathbf{b}_i^*|$：第 $i$ 个正交基向量的长度。

枚举算法的总节点数为：$\sum_{k=0}^{d-1} H_k.$

1.8 筛法

筛选算法从格点集合中选取一系列格点$L \subseteq \Lambda$ ，并搜索这些点的整数组合，目的是找到较短的向量。如果初始集合 $L$ 足够大，则可以递归执行该过程来求解SVP。集合中的每个点可以以 $d$ 的多项式复杂度进行采样。因此，初始列表的采样成本为 $|L|^{1+o(1)}$。

  • 将 $k$ 个点组合在一起的筛选算法被称为 $k$-筛选（$k$-sieves）。
  • 2-筛选算法采用形式为 $\mathbf{u} \pm \mathbf{v}$ 的整数组合，其中 $\mathbf{u}, \mathbf{v} \in L$ 且 $\mathbf{u} \neq \pm \mathbf{v}$。

假设：

  • 筛选算法基于以下假设分析：集合 $L$ 中的点在一个“薄球壳”上独立且均匀分布。这个启发式假设由 Nguyen 和 Vidick 在文献【65】中提出。

进一步的简化假设包括：

  1. 壳层非常薄并且归一化，使得 $L$ 是单位球上的子集；
  2. 对于一对向量 $(\mathbf{u}, \mathbf{v})$，只有当它们的夹角满足 $\theta(\mathbf{u}, \mathbf{v}) < \pi / 3$ 时，这对向量才可化简，即：

碰撞和列表大小

  • 在这些假设下，为了观察到足够多的“碰撞”（即化简），需要满足：
  • 格筛选算法预计会输出一个包含 $\sqrt{4/3}^{d/2+o(d)}$ 个短格向量的列表[5, 32]。

  • 理论最优筛选算法的启发式运行时间为：

  • 本文使用了 G6K 中的高性能格筛选实现[5, 76]，包括了 BGJ1[16]和 3-Sieve[41]的变种。

    • BGJ1： 启发式运行时间为 $2^{0.349d+o(d)}$，内存消耗为 $2^{0.205d+o(d)}$。
    • 3-Sieve： 启发式运行时间为 $2^{0.372d+o(d)}$，内存消耗为 $2^{0.189d+o(d)}$。

2 使用格方法求解 HNP

2.1 Boneh 和 Venkatesan

提出了以下的格，通过 BDD oracle 求解隐藏数问题（HNP）：

  • 目标向量为$(a_0, \dots, a_{m-1}, 0)$， 如果可以找到距离目标向量最近的格向量就可以确定$\alpha$。

根据$
a_i + k_i \equiv t_i \cdot \alpha \mod n
$乘$\alpha$可以得到格向量：
$
(t_0 \cdot \alpha \bmod n, \dots, t_{m-1} \cdot \alpha \bmod n, \alpha / n)
$，在 $|k_i| < 2^\ell$ 时，与目标向量的距离在 $\sqrt{m+1} \cdot 2^\ell$ 范围内。

2.2 Kannan嵌入方法

大多数研究通过 Kannan 的嵌入方法解决此 BDD 问题，即构造以下的格并求解SVP：

通过左乘$(0,0,\cdots, \alpha,-1)$得到格向量：$
(k_0, k_1, \dots, k_{m-1}, 2^\ell \cdot \alpha / n, -2^\ell)
$，其范数约为 $\sqrt{m + 2} \cdot 2^\ell$。该格子还包含向量 $(0, 0, \dots, 0, 2^\ell, 0)$，因此目标向量通常不是最短向量，可以对该格进行多种改进。

2.3 作者的进一步改进

减小 $k$ 的大小

在 ECDSA 的输入中，$k$ 通常是正数，因此有 $0 \leq k_i < 2^\ell$。
格允许在 $k$ 为正数或者负数，可以通过 $k_i’ = k_i - 2^{\ell-1}$ 来减少 $k$ 的位长一位。
[63]在实践中提供了显著的改进，但通常并未广泛应用于实际场景。

消除变量 $\alpha$

给定以下输入方程组：

消除 $\alpha$ 得到一个新的方程组：

对于每一个关系：

重新排列后得：

优化结果:

通过这种方式，sample有 $m-1$ 个关系，且：

  1. 减少格维度：维度从 $m+1$ 减少到 $m$。
  2. 移除特定的归一化向量：$(0, 0, \dots, 0, 2^\ell, 0)$ 不再属于新的格。新目标向量成为格中的唯一最短向量。

新格的构造

令 $w = 2^{\ell-1}$。通过以上两种优化，新格 $\Lambda$ 的生成矩阵为：

目标向量为：

矩阵中的值 $1$ 和 $w$ 是归一化值，确保最短向量的所有系数具有相同的长度。

不同大小的 $k_i$

我们可以通过在格的每一列乘以因子 $2^{l_{\max}} / 2^{\ell_i}$ 来适应满足 $|k_i| < 2^{\ell_i}$ 的不同大小的 $k_i$。

3.The “Lattice Barrier”

格障碍： 当目标向量长度不显著短于格中其他典型向量时，传统格算法通常失败。（泄露比特比较少，样本少）
信息论极限： 当泄露的随机数位数太少时，传统认为攻击是不可行的。

人们认为，对于隐藏数问题（HNP），当只知道随机数 $k$ 的一小部分位时，格算法基本上变得不可用。特别是，对于仅泄漏1位随机数的情况，普遍认为格算法将以高概率失败，因为对应于秘密值的格向量不再显著短于格中的其他向量[13]。

Aranha 等人在文献 [12] 中进一步详细讨论了这一点：“存在一个硬限制，限制了通过格约简所能实现的目标：由于 HNP 格的结构，攻击 (EC)DSA 中只泄漏1位随机数的场景是不可行的。在这种情况下，即使在高斯启发式的假设下，与 HNP 解对应的‘隐藏格点’也不会是最短向量，因此格技术无法奏效。” 类似的观点也出现在文献 [30, 73, 77] 中。例如，在 [77] 中估算，对于256位的椭圆曲线：

  • 3位随机数偏差是可能的，但并不容易；
  • 2位随机数偏差是不可行的。

而对于384位曲线：

  • 5位或4位随机数偏差很难；
  • 3位随机数偏差是不可行的。

为了理解为什么存在这种“格障碍”，我们需要注意格的体积（volume），定义为：

其中，格的维度为 $m+1$。根据高斯启发式，格中最短向量的长度预计为：

简化后为：

同时注意目标向量 $\mathbf{v}$ 的范数满足：

3.1 BDD 求解器的成功条件

BDD 求解器在以下情况下能够成功恢复目标向量：

  1. 高斯启发式 $\text{gh}(\Lambda)$ 表示典型短向量的长度。
  2. 如果目标向量 $|\mathbf{v}|$ 更短，它会在格算法中被优先找到。
  3. 这是判断目标向量是否可以通过格算法有效恢复的一个重要判据。

图2展示了高斯启发式 $\text{gh}(\Lambda)$ 与目标向量上界（公式3）的比较，用于256位 ECDSA 密钥恢复问题的1位、2位和3位随机数偏差场景。对应格的维度解释了文献 [77] 中估算的难度。

3.2 两项关键观察

作者有两项关键观察：

  1. 目标向量的上界是一种保守估计：

    • 上界是目标向量长度的保守估计。然而，根据启发式假设，我们的问题实例是随机采样的，因此我们使用均匀分布的向量的期望范数作为目标向量的期望范数。
    • 这一调整仅是上界的一个常数因子，却对临界点有显著影响。

    优化后的目标向量的期望平方范数：

假设随机数偏差为 $k_i - w$，首先对其平方求期望：

  • $\sum_{i=0}^{2w-1} i^2 = \frac{(2w-1)(2w)(2w+1)}{6}$

  • $\sum_{i=0}^{2w-1} i = \frac{(2w-1)(2w)}{2}$

  • $\sum_{i=0}^{2w-1} w^2 = w^2 \cdot 2w$

图3. 对格算法可行性的新估算
我们绘制了目标向量的期望长度 $\mathbb{E}[|\mathbf{v}|]$ 和高斯启发式 $\text{gh}(\Lambda)$ 的对比曲线，随样本数量 $m$ 的变化，其中 $\log(n) = 256$。与图2相比，这些临界点对应于更易处理的实例。

通过这一条件，我们观察到，先前被认为通过格算法难以解决的 ECDSA 密钥恢复问题，现在变得可行，而那些被认为无法解决的问题，则仅仅变得代价昂贵。

  1. 信息论限制： 即使在目标向量的范数满足 $|\mathbf{v}| \geq \text{gh}(\Lambda)$ 的情况下，格算法仍然可以应用。换句话说，即使“与秘密值对应的格向量不再显著短于格中的其他向量”这一条件（参见 [13]）被违反，我们也发现“格障碍”是软性的。

这一观察表明，违背“格障碍”只是需要花费更多的计算时间。因此，我们可以在 图3 中的交叉点位置提高成功概率，并用比交叉点建议的样本量更少的样本成功解决问题实例。

针对隐藏数问题（HNP），任何算法的适用性还受到另一个更强的限制：问题本身编码的关于秘密 $d$ 的信息量。具体而言，对于每个样本（即一次签名），$k$ 是一个随机数，长度为 $\log(n)$位，如果随机数 $k$ 泄露了 $\ell $位信息，则剩余的未知信息为$\log(n) - \ell$.

每个样本揭示了 $\log(n) - \ell$ 位与秘密 $d$ 相关的信息。

因此，我们期望需要满足以下条件才能恢复 $d$：

从启发式上看，对于随机实例，低于这一点时，我们不期望格能够唯一地确定问题的解，无论使用何种算法解决它。

4. 带谓词的有界距离解码

定义5：带谓词的 $\alpha$-有界距离解码问题（BDD$_{\alpha, f(\cdot)}$）

给定：

  • 一个格基 $B$，
  • 一个向量 $t$，
  • 一个谓词函数 $f(\cdot)$，
  • 一个参数 $0 < \alpha$，满足欧几里得距离 $\text{dist}(t, B) < \alpha \cdot \lambda_1(B)$。

找到一个格向量 $\mathbf{v} \in \Lambda(B)$，使得：

  1. $f(\mathbf{v} - t) = 1$，
  2. 该向量是最接近 $t$ 的向量。

我们将使用 Kannan 嵌入技术 来求解 BDD$_{\alpha, f(\cdot)}$。然而，注意我们构造的格不一定有唯一的最短向量。唯一性实际上是由于谓词 $f(\cdot)$ 的加入而引入的。

定义6：带谓词的唯一最短向量问题（uSVP$_{f(\cdot)}$）

给定：

  • 一个格 $\Lambda$，
  • 一个谓词函数 $f(\cdot)$，

找到格中的最短非零向量 $\mathbf{v} \in \Lambda$，满足 $f(\mathbf{v}) = 1$。

remark1

我们的命名——“BDD”和“uSVP”——可能会令人困惑，因为目标向量既不是特别接近格，也不是特别短。然而：

  1. 向量到格的距离仍然受到限制。
  2. 谓词 $f(\cdot)$ 的存在确保了唯一性。

因此，我们选择了这些名字来区别于传统的“CVP”（最近向量问题）和“SVP”（最短向量问题）。

为了明确说明如何使用求解 uSVP$_{f(\cdot)}$ 的 oracle 来解决 BDD$_{\alpha, f(\cdot)}$，我们构造了以下格：

其中：

  • $\tau \approx \mathbb{E}\left[|\mathbf{v} - t| / \sqrt{d}\right]$ 是某种嵌入因子。
  • 如果 $\mathbf{v}$ 是最接近 $t$ 的向量，则格 $\Lambda(L)$ 包含向量 $(t - \mathbf{v}, \tau)$。

此外，我们构造了谓词 $f’(\cdot)$，由 $f(\cdot)$ 给出，如 算法1 所示。

remark2

定义5和定义6比用于引入它们的场景更为通用。具体来说：

  • 这两个定义允许谓词在格中的多个向量上评估为真，并分别返回这些向量中最接近或最短的向量。
  • 在许多（但不是全部）应用中，我们还可以保证谓词只对一个向量评估为真。

定义5和定义6还可以自然扩展到一种情况，即我们需要找到一个符合谓词的、范数不超过给定值的格向量列表。

谓词的意义：

1.    限制解的范围： 谓词用于筛选出符合特定条件的格向量。
2.    确保唯一性： 某些应用场景下，格中可能有多个最短向量或最近向量，谓词帮助我们锁定一个解。
3.    结合嵌入技术： 在嵌入格的情况下，构造新的谓词 $f^{\prime}(\cdot)$ 是为了在高维格中正确应用原始条件。
特性 BDD CVP
搜索范围 仅限于 $\alpha \cdot \lambda_1(B)$ 范围内 全局搜索
错误率 较低，限制了错误解的可能性 较高，可能返回错误的最近解
计算效率 较高，限制范围后减少计算量 较低，需要全局搜索
隐藏数问题的适应性 符合随机偏差较小的特点 难以处理随机偏差大的情况

5 算法

我们提出了两种解决 uSVP$_{f(\cdot)}$ 的算法：

  1. 基于枚举（enumeration）的算法——可以简单参数化以支持任意目标向量的范数。
  2. 基于筛选（sieving）的算法——当目标向量的范数 $|\mathbf{v}| \leq \sqrt{4/3} \cdot \text{gh}(\Lambda)$ 时可以求解 uSVP$_{f(\cdot)}$。

5.1 Baseline

当目标向量 $\mathbf{v}$ 预计比格中任何其他向量短时，我们可以简单地使用 uSVP 求解器来恢复它。特别是，我们可以使用带块大小 $\beta$ 的 BKZ 算法，满足公式（2）中的成功条件。

根据块大小 $\beta$ 的选择：

  • 当 $\beta < 70$ 时，可以使用枚举法（Enumeration）。
  • 当 $\beta \geq 70$ 时，可以使用筛选法（Sieving）来调用 SVP 求解器。

当 $\beta = d$ 时，该算法会计算一个 HKZ 化简基（第一个向量是最短的），并特别关注基中最短的向量。文献中普遍认为，可以通过在化简基中搜索目标向量来解决问题。

在后续对比算法时，我们也将采取这种方式。我们认为：

  • 如果目标向量包含在化简基中，则算法成功。

我们将这类算法称为：

  • BKZ-Enum（基于枚举的 BKZ）。
  • BKZ-Sieve（基于筛选的 BKZ）。

5.2 枚举法

我们的第一个算法是增强格点枚举（lattice-point enumeration）。这是一个穷举法，在给定半径的球体内搜索所有格点，同时使用谓词对结果进行筛选。具体来说：

  1. 该算法会在球体内枚举所有点，找到满足给定谓词的解。
  2. 如果谓词对某个解返回真值，则该解被接受并返回。
  3. 如果谓词不成立，算法将继续搜索其他候选解。

这一增强的枚举算法可以直接应用于解决目标向量的期望范数对应的半径 $R$。它的核心改动是，在传统枚举法的基础上，添加了一个谓词检查步骤，以筛选满足条件的解。

定理 1：设 $\Lambda \subseteq \mathbb{R}^d$ 是一个包含向量 $\mathbf{v}$ 的格，满足：

  • $|\mathbf{v}| \leq R = \xi \cdot \text{gh}(\Lambda)$，
  • $f(\mathbf{v}) = 1$。

在满足高斯启发式的情况下，带谓词的枚举算法能够以 $\xi^d \cdot d^{d/(2e) + o(d)}$ 的复杂度找到满足条件的最短向量。

5.3 筛法

核心思想：论文提出了一种基于筛法的方法，主要分为以下两个步骤：

  1. 使用经典的 2-sieve 算法生成一个包含短向量的数据库$L$ 。
  2. 在数据库中的每个向量上运行谓词检查，筛选出满足特定谓词的目标向量。

筛法的主要作用是高效生成大量短向量，并利用这些向量解决格问题（如 BDD 或 SVP）。

假设 1：当 2-sieve 算法运行结束时，数据库 $L$ 满足以下性质：

其中 $\text{gh}(\Lambda)$ 是高斯启发式预测的最短向量长度。

定理 2： 筛法的性能保证如下：

  • 假设格 $\Lambda \subset \mathbb{R}^d$ 包含目标向量 $v$，且：
  • 在满足假设的情况下，筛选算法在 $2^{0.292d + o(d)}$ 步中找到满足谓词 $f(v) = 1$ 的目标向量。
  • 计算谓词 $f(\cdot)$ 的调用次数为 $(4/3)^{d/2 + o(d)}$。

与D4F的冲突：

筛选算法在实践中受益于文献【32】中提出的“free dimensions”技术（简称 D4F 技术）。该技术启发了本文的算法，筛选算法会输出模长 $\sqrt{4/3} \cdot \text{gh}(\Lambda)$ 的所有向量。

这一观察被用于在维度 $d’$ 中解决最短向量问题（SVP），其中：

文献【32】中对 $d’$ 的“乐观”预测如下：

具体而言：

  • 如果最短向量 $\mathbf{v}$ 的投影 $\pi_{d-d’}(\mathbf{v})$ 满足：$ |\pi_{d-d’}(\mathbf{v})| \leq \sqrt{4/3} \cdot \text{gh}(\Lambda_{d-d’})$, 其中 $\Lambda_{d-d’}$ 是通过正交投影到前 $d-d’$ 个基向量获得的格，那么可以通过 Babai 提升找到 $\mathbf{v}$。

然而，在我们的设置中，目标向量本身的模长被假定为大于 $\text{gh}(\Lambda)$，因此该优化可能无法适用。

在需要构造一个 uSVP 格或一个较低维度的 uSVP 格时，应比较较小维度格的筛选维度 $d’$ 与原始全维格的性能。

在 G6K 实现中，通过“on the fly” 的提升技术【5】，可以“免费”获得额外的几个维度。

6 ECDSA 密钥恢复的应用

6.1 调整样本数量$m$的实验分析

我们在常见椭圆曲线长度和从签名随机数中泄露的最高有效位数的场景下，进行了实验，评估不同算法的成功率。通过调整样本数量 $m$，实验展示了目标向量的期望长度与格中最短向量的长度比值对成功率的影响。

理论预测

  • 最短向量技术的局限性：
    • 当目标向量的期望长度超过高斯启发式预测值时，传统的最短向量技术通常失败。
    • 随着目标向量长度相对于格中最短向量的长度减小，成功率逐渐提高。

  • 实验结果：

    • 当目标向量的长度超过高斯启发式预测值时，筛选算法和枚举算法仍然在一定成功率下工作。
    • 这表明论文的方法突破了“格障碍”（lattice barrier）。

  • 成功率分析

    • 图 4 展示了对于不同的样本数量下，每种算法的成功率。
    • 每个数据点对应：
      • 较小实例的 32 次实验；
      • 较大实例的 8 次实验。
    • 我们对枚举算法中的谓词参数进行了设置，使其成功率为 50%。
    • 对于更高维度的格，枚举算法在某些参数下变得不可行，因此我们未报告相关结果

6.2 固定样本数量$m$

在某些攻击场景中，攻击者可能在样本数量上有严格的限制。通过使用带谓词的枚举和筛选算法，可以增加攻击成功的概率，并扩大参数范围，使得在这些限制下仍然有可能实现可行的攻击。

案例场景
这种情况出现在文献【22】中，作者通过将格攻击应用于从公共数据源（如加密货币区块链和互联网协议扫描）中收集的 ECDSA 签名，寻找有缺陷的 ECDSA 实现。这些协议包括 TLS 和 SSH。在这种情况下，攻击者可以访问由给定公钥生成的固定数量的签名样本，并希望在已知随机数位数尽可能少的情况下，对这些固定样本执行成功攻击的概率最大化。

文献【22】中的结果

  • 文献【22】报告使用小维度的 BKZ 算法，成功恢复了 287 个不同的密钥。这些密钥使用了随机数$k$长度分别为 160、128、110、64 和少于 32 位的 ECDSA 签名（针对 256 位 secp256k1 椭圆曲线，用于比特币）。
  • 在 128 位随机数长度的两次签名中，他们成功恢复了 2 个不同的密钥。

实验结果对比

nonce bits = 256
BKZ方法的实验结果：

  • 对于两次签名样本，BKZ 算法仅有 70% 的成功率能够恢复 128 位随机数的私钥。
  • 随着未知随机数比特数量的增加，成功率会迅速下降。

筛选算法的实验结果：

  • 筛选算法带谓词可以在随机数未知位数高达约 132 位时，保持 100% 的成功率。

对比分析：

  • 图5 对比了两种算法在固定签名数量和不同未知随机数比特数量时的成功率。

假设与验证
我们假设文献【22】的失败率可能导致某些脆弱密钥未被发现。为了验证这一点，我们将带谓词的筛选算法应用于 2018 年 9 月从比特币区块链快照中提取的数据：

  • 目标：仅针对 128 位随机数，使用两组签名对。
  • 数据：快照中包含 569,396,463 个签名，这些签名由私钥生成，其中每个私钥生成了两次或更多签名。

对于生成的 $m$ 组签名集合，我们对每个签名对应用带谓词的筛选算法，将问题转换为处理 $2m$ 对签名的实例。然后检查长度小于 128 位的随机数，成功恢复了 9 个不同的私钥。

6.3 处理错误

实验总结

  • 在样本数量不足以提供足够信息以恢复私钥的场景下，带谓词的筛选和枚举算法成功解决了隐藏数问题。
  • 通过引入谓词，目标向量被唯一确定，使得传统“信息论极限”成为可突破的界限。