量子攻击：离线西蒙算法的数据复杂度视角

### 量子攻击：离线西蒙算法的数据复杂度视角 #### 1. 引言 量子算法，如肖尔算法、格罗弗算法和西蒙算法，已成为密码分析中的强大工具。经典密码原语的安全性引发了诸多担忧，对称密钥方案抵御量子攻击的能力也备受关注。攻击者可通过在量子计算机上运行格罗弗搜索，在 $O(2^{k/2})$ 时间内恢复 $k$ 位密钥，这使得密钥的安全长度减半。近期研究表明，量子攻击在某些分组密码构造和模式上的性能远优于经典方法。 西蒙算法攻击是一种高效的量子攻击方式。例如，在 QCPA 模型中构建的 3 轮量子区分器，可利用西蒙算法在多项式时间内将 3 轮 Feistel 结构与伪随机置换区分开来（在 QCCA 模型中为 4 轮）。结合格罗弗搜索，Leander 和 May 提出的格罗弗 - 西蒙算法可用于进行量子密钥恢复攻击。一些构造在量子环境下甚至变得不安全，如 Even - Mansour 构造和 FX 构造。 量子密码分析有两种模型：量子模型（Q2 模型）和标准模型（Q1 模型）。在 Q2 模型中，攻击者可以进行叠加态查询并进行离线量子计算；而在 Q1 模型中，只允许在线经典查询，但可以进行离线量子计算。考虑到量子计算机的规模，Q2 模型的攻击假设可能难以实现，在 Q1 模型中不使用 QRAM 进行量子攻击是一种可行的硬件友好场景，且 Q2 模型的攻击可以转化为 Q1 模型。 为了在 Q1 模型中运行西蒙攻击，Bonnetain 等人提出了一种名为周期非对称搜索的新技术。他们设计了两种算法：Q2 模型中的 Alg - PolyQ2（使用多项式量子比特）和 Q1 模型中的 Alg - ExpQ1（使用指数级经典查询）。Alg - PolyQ2 攻击者首先对 $g$ 进行量子查询以准备量子数据库 $|\psi_g\rangle$，然后对 $i$ 进行格罗弗搜索，并使用西蒙算法测试 $f_i \oplus g$ 是否有隐藏周期；Alg - ExpQ1 则是先对 $g$ 进行 $2^n$ 次经典查询，然后准备量子态 $|\psi_g\rangle$。 主要贡献如下： 1. 提出一种不使用 QRAM 的量子算法，将经典数据库转换为量子叠加态。 2. 从数据复杂度的角度分析了预区分器方法和后区分器方法对西蒙算法攻击的影响，发现在 QCPA 设置中仅推荐预区分器方法。 3. 将算法应用于 Q1 模型下的 Feistel 结构攻击，攻击 $r$ 轮 Feistel 结构的时间复杂度为 $O(l \cdot 2^{n/2 + 2} + 2^{(r - 3)n/4})$，经典数据复杂度始终为 $O(2^{n/2 + 1})$，优于经典攻击。 不同轮数 Feistel 结构密钥恢复攻击的复杂度总结如下表： | 轮数 | 经典攻击（时间） | 经典攻击（数据） | Q2 攻击（时间） | Q1 攻击（时间） | Q1 攻击（数据） | | ---- | ---- | ---- | ---- | ---- | ---- | | 5 | $2^n$ | $2^{n/2}$ | $2^{n/2}$ | $l \cdot 2^{n/2 + 2} + 2^{n/2}$ | $2^{n/2 + 1}$ | | 6 | $2^{3n/2}$ | $2^{3n/2}$ | $2^{3n/2}$ | $l \cdot 2^{n/2 + 2} + 2^{3n/4}$ | $2^{n/2 + 1}$ | | 7 | $2^{3n/2}$ | $2^n$ | $2^{2n}$ | $l \cdot 2^{n/2 + 2} + 2^{n}$ | $2^{n/2 + 1}$ | | 8 | $2^{7n/4}$ | $2^{5n/4}$ | $2^{5n/2}$ | $l \cdot 2^{n/2 + 2} + 2^{5n/4}$ | $2^{n/2 + 1}$ | | 15 | $2^{7n/2}$ | $2^{2n}$ | $2^{6n}$ | $l \cdot 2^{n/2 + 2} + 2^{3n}$ | $2^{n/2 + 1}$ | #### 2. 预备知识 ##### 2.1 量子算法 - **西蒙算法**：1994 年，西蒙提出了一种量子算法，可在多项式时间内解决如下问题：给定布尔函数 $f : \{0, 1\}^n \to \{0, 1\}^n$，若存在非零值 $s$，使得 $\forall x \in \{0, 1\}^n$，$f(x) = f(x \oplus s)$，则找到 $s$。经典方法解决该问题需要 $\Omega(2^{n/2})$ 次对 $f$ 的调用，而西蒙算法只需 $O(n)$ 次叠加态查询。 - **格罗弗算法**：1996 年，格罗弗提出了一种用于在无序数据库中搜索标记项的量子算法。给定包含 $2^n$ 个元素的集合 $X$，其中 $m$ 个元素被标记，经典方法找到标记项的时间复杂度为 $2^n/m$，而使用格罗弗算法，该问题可以在 $O(\sqrt{2^n/m})$ 时间内以高概率解决。 - **QRAM**：量子随机访问存储器（QRAM）可视为经典 RAM 的量子版本，是量子计算机的重要设备。许多量子算法需要量子随机访问计算，但大规模构建 QRAM 很困难。西蒙算法的一个优点是不需要 QRAM，我们希望在离线西蒙攻击中保持这一优点。 ##### 2.2 西蒙算法对 Feistel 结构的 Q2 模型攻击 2010 年，Kuwakado 和 Morii 首次研究了西蒙算法对 3 轮 Feistel 结构的攻击，随后 Dong 等人将其扩展到 5 轮并提出量子密钥恢复攻击。其攻击思路如下： 设 $x_0^R = x$，$x_0^L = \alpha_b$（$b \in \{0, 1\}$），$\alpha_0 \neq \alpha_1$ 为两个常数。定义 $f : \{0, 1\} \times \{0, 1\}^{n/2} \to \{0, 1\}^{n/2}$ 为 $f(b, x) = F_2(k_2, x \oplus F_1(k_1, \alpha_b))$，可以验证 $f$ 有一个非平凡周期 $s = 1 \parallel F_1(k_1, \alpha_0) \oplus F_1(k_1, \alpha_1)$。应用西蒙算法，量子攻