# 量子密码分析：Shor、Grover、Collision 与 Simon 攻击模型

量子计算对密码学的影响**不是**“所有密钥长度减半”这样一句话能概括的。本章的任务是把三类本质不同的量子攻击讲清楚：

- **Shor 算法**对整数分解（factoring）与离散对数（discrete logarithm）给出**多项式时间**算法，直接摧毁 RSA、有限域 Diffie–Hellman 与椭圆曲线密码（ECC）赖以安全的数学难题；
- **Grover 算法**对无结构的密钥穷搜只给出**平方根级（quadratic）**的查询加速，它的后果是“对称密钥要加长”，而不是“对称密码被攻破”；
- **Simon 型攻击**在更强的 **superposition-query（Q2）模型**中，可以把某些具体对称构造（如 Even–Mansour、3 轮 Feistel、CBC-MAC）的密钥恢复从指数级降到多项式级。

这三类攻击的**预言机（oracle）形式、所需数据、内存模型、输出结果**全都不同；把它们混为一谈，是量子密码分析科普中最常见的错误。本章假设读者已经学完本站第 1–8 章的内容（QFT、相位估计、Shor、Grover、Simon、QSP/QSVT 等），相关算法本身我们只引用结论，重点放在**如何把量子算法正确地“接到”密码学问题上**。

先交代一下历史脉络（对应的原始文献列在文末）。这条线从 1994 年开始：Shor 给出分解与离散对数的多项式时间量子算法，直接威胁 RSA 与刚刚兴起的椭圆曲线密码；Grover（1996）随后给出无结构搜索的平方根加速，迫使人们重新计算对称密钥的安全边际。对称密码这边，Simon 算法原本只是一个理论上的查询复杂度分离结果，直到 Kuwakado–Morii 等人发现它能攻击具体的分组密码构造、Kaplan 等人（2016）把它系统化为对 Even–Mansour、Feistel、MAC 的一族 Q2 攻击，才成为现实的设计约束。同一时期，差分/线性密码分析的量子化、AES 的量子资源估计、以及 isogeny/lattice/multivariate 方向的代数攻击陆续出现，构成了本章第 4–7 节的内容。贯穿这条线的主线是同一个问题：**量子算法到底改变了哪个安全假设、在哪个攻击模型下改变、改变了多少**——这正是本章每一节要回答的。

:::{admonition} 本课知识点
:class: tip

1. **[攻击者能力模型：Q1、Q2 与 recorded-data](#attacker-models-q1-q2)**——能列出 Q1、Q2、公开算法与 recorded-data 四种模型下攻击者的能力边界，并解释 Q2 为何严格强于 Q1、recorded-data 威胁为何不需要在线量子访问。
2. **[Shor：从分解到周期寻找](#shor-period-finding)**——能写出阶 $r$ 的定义，说明 $f(x)=a^x\bmod N$ 的周期性与 $U_a$ 的酉性来源，并指出相位估计加连分数展开如何把求 $r$ 降到 $\operatorname{poly}(\log N)$。
3. **[Shor：从周期到因子的经典后处理](#shor-classical-postprocessing)**——能推导 $(a^{r/2}-1)(a^{r/2}+1)\equiv0\pmod N$ 蕴含的因子分离论证，解释两条检查条件各自排除的失败情形，并对 $N=15$ 手算完整后处理流程。
4. **[离散对数的隐藏子群归约](#dlog-hidden-subgroup)**——能构造 $f(a,b)=g^{a+bx}$，推导隐藏子群 $H=\langle(-x,1)\rangle$ 及其陪集结构，并说明 QFT 采样方程 $-ux+v\equiv0\pmod q$ 如何给出 $x\equiv vu^{-1}$。
5. **[Grover 密钥恢复的迭代与成本](#grover-key-search-cost)**——能写出相位预言机并计算迭代次数 $\frac{\pi}{4}2^{\kappa/2}$，说明每次迭代的真实代价组成与“密钥翻倍”启发式的适用边界。
6. **[Hash 原像、碰撞与 BHT 算法](#hash-preimage-collision)**——能比较原像、第二原像与碰撞三个任务的经典/量子复杂度，推导生日界 $2^{n/2}$ 并计算 BHT 的参数平衡点 $r=2^{n/3}$。
7. **[Simon 攻击与 Even–Mansour 构造](#simon-even-mansour)**——能从 Even–Mansour 定义推导 $F(x\oplus k_1)=F(x)$，并说明 Simon 采样加高斯消元如何以多项式次查询恢复 $k_1$ 与 $k_2$。
8. **[三类攻击对照与后量子边界](#three-attack-classes)**——能按预言机形式、加速量级与防御对策三个维度比较三类量子攻击，并解释“后量子”安全估计必须写明模型与成本的原因。

:::

(attacker-models-q1-q2)=
## 1. 先区分攻击者能力：Q1、Q2 与 recorded-data

讨论任何量子攻击之前，必须先回答一个问题：攻击者到底能做什么？设带密钥的密码原语为 $E_K(x)$（例如分组密码加密、MAC 签名），密钥 $K$ 固定在目标设备内部。至少要区分以下几种模型：

- **Q1 / offline-quantum（经典查询 + 量子离线计算）：**攻击者只能像经典攻击者一样，向真实设备发送**经典**输入 $x$、收到**经典**输出 $E_K(x)$；但他可以把收集到的数据交给一台量子计算机做离线处理。这是对“现实世界的远程加密服务”最诚实的模型。
- **Q2 / superposition-query（叠加查询）：**攻击者可以调用密码原语的**相干预言机**
  $$
  O_{E_K}|x,z\rangle=|x,z\oplus E_K(x)\rangle,
  $$
  即把 $E_K$ 实现为一个可逆量子电路，允许输入是 $\sum_x \alpha_x|x\rangle$ 这样的叠加态，并且**跨多次查询保持相干性**（coherence）。这等价于攻击者拿到了“内嵌秘密 $K$ 的量子电路”，可以对它做任意酉操作。
- **Public-algorithm model（公开算法模型）：**RSA 加密、Diffie–Hellman 的模幂运算等**公钥**操作，其算法与公开参数本来就是公开的，攻击者可以**自己**把它们实现成可逆电路，不需要访问任何带秘密的预言机。Shor 攻击就属于这一类——这是它现实威胁远大于 Q2 攻击的根本原因。
- **Recorded-data threat（先存后解 / harvest now, decrypt later）：**攻击者今天记录下来的公钥密文（例如 TLS 握手中用 RSA 或 ECDH 保护的会话密钥），可以在未来的容错量子计算机造好之后解密。这个威胁**完全不需要在线量子访问**，它只依赖 Shor 算法的存在性和“今天的数据多年后仍有保密价值”这一事实。这正是各国推动后量子密码迁移的现实动机。

**Q2 严格强于 Q1，也强于普通的 chosen-plaintext 攻击。** 原因很直接：一个经典的服务器收到查询时会**测量**输入（它在经典比特上工作），返回的也是经典字符串——物理上它根本不会实现 $O_{E_K}$ 这个酉映射。叠加查询要求攻击者能把 $E_K$ 的**实现**（而不只是输入输出行为）拿来做相干演化，这在“远程调用一个加密 API”的场景里通常不成立。

但这不意味着 Q2 结果没有价值。它揭示的是：许多**经典安全性证明**（在经典查询模型下归约到某个困难假设的证明）在 quantum-access model 下**直接失效**——证明的归约步骤无法模拟一个回答叠加查询的预言机。因此 Q2 攻击应被读作“这类构造的设计原理在量子世界中不成立”，而不是“明天就能远程破解”。本章第 8 节的 Simon 攻击就属于这一类，届时我们会再强调这个前提。

## 2. Shor 如何分解 RSA 模数

### 2.1 问题背景与经典瓶颈

RSA 的安全性归约到整数分解：给定两个大素数的乘积 $N=pq$，求出 $p$ 与 $q$。已知的最好经典算法（general number field sieve）是**次指数**时间的，粗略形如 $\exp\!\big(O((\log N)^{1/3}(\log\log N)^{2/3})\big)$——这就是 RSA 密钥要取 2048 位甚至更长的原因：安全性来自“多项式与次指数之间的鸿沟”。Shor（1994/1995）证明，这个鸿沟在量子计算机上不存在：分解可以在 $\operatorname{poly}(\log N)$ 时间内完成。

Shor 算法的量子部分我们在[Shor 分解教程](../ch04-classic-algorithms/shors-algorithm-tutorial.md)中已经完整推导过，本节的重点是**密码分析视角下的完整链条**：从“分解 $N$”如何归约为“求周期”，到经典后处理为什么有效，再到资源估计上不能犯的错误。

(shor-period-finding)=
### 2.2 从分解到周期寻找

给定 $N=pq$，随机选取整数 $1<a<N$。第一步先做一件经典的事：计算 $\gcd(a,N)$。若 $\gcd(a,N)>1$，那么 $a$ 与 $N$ 有公因子，而对 $N=pq$ 来说这个公因子只能是 $p$ 或 $q$——**分解已经完成**，不需要任何量子计算。若 $\gcd(a,N)=1$，则 $a$ 是模 $N$ 乘法群中的可逆元，定义它的**阶（order）**为

$$
r=\min\{r>0:a^r\equiv1\pmod N\}.
$$

由初等数论（有限群中任何元素的幂次必循环），这样的 $r$ 一定存在且 $r\le \varphi(N)<N$。问题在于：经典地求 $r$ 并不比直接分解 $N$ 容易——逐一试幂需要指数多次乘法。

量子部分做的是**周期寻找（period finding）**。构造函数 $f(x)=a^x\bmod N$，它显然以 $r$ 为周期：$f(x+r)=a^{x+r}\equiv a^x\cdot a^r\equiv f(x)\pmod N$。把模乘实现为酉算子

$$
U_a|x\rangle=|ax\bmod N\rangle
$$

（这一步可行是因为 $\gcd(a,N)=1$ 保证 $x\mapsto ax\bmod N$ 是 $\{0,\dots,N-1\}$ 上的置换，而置换总可以可逆地实现），然后对 $U_a$ 做**相位估计（phase estimation）**。$U_a$ 的特征值形如 $e^{2\pi i s/r}$（$s=0,\dots,r-1$），相位估计以高概率输出某个 $\frac{s}{r}$ 的足够精确的二进近似；经典后处理用**连分数展开（continued fractions）**从这个近似有理数中把分母 $r$ 提取出来。整个量子 + 经典流程的门数都是 $\operatorname{poly}(\log N)$。

(shor-classical-postprocessing)=
### 2.3 从周期到因子：经典后处理

拿到 $r$ 之后，做两步检查：

1. $r$ 必须是**偶数**；
2. 必须满足 $a^{r/2}\not\equiv-1\pmod N$。

若两条都成立，分解立刻完成。推导只有一步代数恒等式，但每一步都值得说清楚。由 $r$ 的定义，$a^r\equiv1\pmod N$，即 $N\mid a^r-1$。把 $a^r-1$ 用平方差公式拆开：

$$
a^r-1=(a^{r/2}-1)(a^{r/2}+1)\equiv0\pmod N.
$$

这意味着 $N$ 整除乘积 $(a^{r/2}-1)(a^{r/2}+1)$。现在看两个因子分别与 $N$ 的关系：

- 由 $r$ 的**极小性**（它是使 $a^r\equiv1$ 成立的最小正整数），$a^{r/2}\not\equiv1\pmod N$，即 $N\nmid(a^{r/2}-1)$；
- 由检查条件 2，$a^{r/2}\not\equiv-1\pmod N$，即 $N\nmid(a^{r/2}+1)$。

于是 $N$ 整除两个整数的乘积，却**不整除其中任何一个**。对 $N=pq$ 来说，这只有一种可能：$p$ 与 $q$ 分别藏在两个因子中。因此两个最大公因子

$$
\gcd(a^{r/2}-1,N),\qquad \gcd(a^{r/2}+1,N)
$$

各自给出 $N$ 的一个非平凡因子（一个约为 $p$，另一个约为 $q$，或者其中之一是 $p$、$q$ 而另一个算出 $N$ 本身的情况已被上面两条排除）。$\gcd$ 用欧几里得算法在 $O(\log N)$ 次算术运算内完成，$a^{r/2}\bmod N$ 用快速幂在 $O(\log r)=O(\log N)$ 次模乘内完成，全部是多项式时间。

**如果两条检查有失败的呢？** 换一个随机 $a$ 重试。对 $N$ 为奇素数幂乘积（semiprime）的情形，数论分析表明随机 $a$ 通过两条检查的概率有正常数下界，因此期望常数次重试即可成功——这正是“Shor 是多项式时间**随机**算法”中随机性的来源。

### 2.4 一个可手算的小例子

取 $N=15$（即 $p=3,q=5$），随机选 $a=7$。

- $\gcd(7,15)=1$，进入周期寻找。
- 逐次计算 $7$ 的幂模 $15$：$7^1\equiv7$；$7^2=49\equiv4$；$7^3\equiv4\cdot7=28\equiv13$；$7^4\equiv13\cdot7=91=6\cdot15+1\equiv1\pmod{15}$。所以 $r=4$。
- 检查：$r=4$ 是偶数；$a^{r/2}=7^2\equiv4\not\equiv-1\equiv14\pmod{15}$。两条都通过。
- 后处理：$\gcd(4-1,15)=\gcd(3,15)=3$，$\gcd(4+1,15)=\gcd(5,15)=5$。得到 $15=3\times5$。

在这个尺度的例子里“量子部分”被手算幂次替代了，但逻辑链条——**随机选 $a$、求阶、两条检查、两次 gcd**——与 2048 位模数的情形完全相同。

### 2.5 复杂度解读：不是什么，是什么

Shor 的复杂度 $\operatorname{poly}(\log N)$ 意味着相对已知经典分解算法是**超多项式（superpolynomial）级别的分离**——不是 Grover 式的平方根改善。但有两件事必须同时记住：

1. **渐近多项式 $\ne$ 近期可运行。** 真实的资源估计包含容错（fault-tolerant）模幂算术、数千个逻辑量子比特、以及表面码等纠错方案带来的巨大物理比特开销。“多项式”描述的是 scaling，不是今天的工程可行性。
2. **多项式 $\ne$ 即时。** recorded-data 威胁的时间尺度由“数据保密期”与“容错机出现时间”的竞争决定，这正是密码迁移（migration）讨论的核心。

## 3. 离散对数与椭圆曲线

### 3.1 问题与经典瓶颈

设 $G=\langle g\rangle$ 是阶为 $q$ 的循环群（例如有限域乘法群的大型素数阶子群，或椭圆曲线上的点群）。离散对数问题：给定

$$
h=g^x,
$$

求 $x\in\mathbb Z_q$。经典通用攻击（如 Pollard rho）需要 $O(\sqrt{q})$ 次群运算——指数级；对有限域情形有次指数的 index calculus，但椭圆曲线情形已知的最好经典攻击仍是 $\sqrt{q}$ 级别的通用算法。Diffie–Hellman 密钥交换、DSA、ECDSA、ECDH 的安全性全部建立在这上面。

(dlog-hidden-subgroup)=
### 3.2 归约为隐藏子群问题

Shor 的离散对数算法把一个二维周期结构藏在下面这个函数里。定义

$$
f(a,b)=g^a h^b=g^{a+bx},
\qquad
(a,b)\in\mathbb Z_q^2,
$$

其中第二个等号就是把 $h=g^x$ 代入：$g^a h^b=g^a(g^x)^b=g^{a+bx}$（注意这里指数在 $\bmod\ q$ 下做运算，因为 $g$ 的阶是 $q$）。

**关键观察：**$f(a,b)=f(a',b')$ 当且仅当 $g^{a+bx}=g^{a'+b'x}$，而 $g$ 的阶为 $q$ 意味着两个群元素相等当且仅当指数模 $q$ 同余，即

$$
(a-a')+x(b-b')\equiv0\pmod q.
$$

换句话说，$f$ 在哪些输入对上取值相同，完全由差向量 $(a-a',b-b')$ 是否满足上述线性方程决定。所有使 $f$ 取相同值的差向量构成 $\mathbb Z_q^2$ 的一个子群——**隐藏子群（hidden subgroup）**

$$
H=\{(a,b)\in\mathbb Z_q^2: a+xb\equiv0\}=\langle(-x,1)\rangle\le\mathbb Z_q^2,
$$

第二个等号是因为方程 $a=-xb$ 的通解正是 $(a,b)=t(-x,1)$（$t\in\mathbb Z_q$）。于是 $f$ 在 $H$ 的每个**陪集（coset）**上取常值、在不同陪集上取不同值——这正是阿贝尔隐藏子群问题的标准输入形态，而秘密 $x$ 就编码在 $H$ 的生成元里。

### 3.3 量子采样与恢复 $x$

算法流程与 Simon/Shor 一族完全一致（细节见本站 Simon 与 HSP 相关教程），我们逐步写出并说明每步依据：

1. **制备均匀叠加**：$\frac{1}{q}\sum_{a,b}|a,b\rangle|0\rangle$。
2. **相干计算 $f$**：第二寄存器变为 $\frac{1}{q}\sum_{a,b}|a,b\rangle|f(a,b)\rangle$。这需要可逆的群运算电路——有限域情形是模幂，椭圆曲线情形是可逆的**点加（point addition）**与倍点。
3. **测量或丢弃函数寄存器**：由第 3.2 节的分析，测量结果把第一寄存器坍缩到**某一个陪集上的均匀叠加** $\frac{1}{\sqrt q}\sum_{t\in\mathbb Z_q}|(a_0,b_0)+t(-x,1)\rangle$（陪集代表元 $(a_0,b_0)$ 随机且未知）。
4. **作用 $QFT_q\otimes QFT_q$**：阿贝尔群上的傅里叶变换把“陪集上的均匀叠加”映射为“与 $H$ 正交的字符上的叠加”。具体地，测量结果 $(u,v)\in\mathbb Z_q^2$ 出现的概率非零仅当相位在陪集上不产生相消干涉，条件正是（这里用到 $\mathbb Z_q^2$ 的特征标 $(a,b)\mapsto e^{2\pi i(ua+vb)/q}$ 在生成元 $(-x,1)$ 上取值为 $1$ 的要求）

$$
-ux+v\equiv0\pmod q.
$$

5. **恢复 $x$**：若采样到的 $u\ne0$ 且 $u$ 在 $\bmod\ q$ 下可逆（$q$ 为素数时 $u\ne0$ 即可），则

$$
x\equiv v\,u^{-1}\pmod q.
$$

每次运行给出 $H$ 的正交补中的一个采样；一旦采到可逆的 $u$（对素数 $q$，$(u,v)\ne(0,0)$ 且 $u\neq 0$ 的事件以显著概率发生），一次采样就足够。期望常数次运行即可。

### 3.4 密码学含义

同样的思路适用于**有限域 Diffie–Hellman**（群运算是模幂）与**椭圆曲线群**（把模幂换成可逆的椭圆曲线点加，电路更复杂但仍是多项式规模）。结论是：传统 RSA、有限域 DH 与 ECC 的安全问题**不是简单“把 key 加长”能解决的**——底层的困难问题已经整个落入 $\mathsf{BQP}$。这与后文 Grover 对对称密码的影响形成鲜明对比。完整推导见[Shor 分解教程](../ch04-classic-algorithms/shors-algorithm-tutorial.md)与[Shor 离散对数教程](../ch04-classic-algorithms/shors-discrete-log-tutorial.md)。

## 4. Grover 密钥恢复

### 4.1 把“穷搜密钥”写成搜索问题

设攻击者拿到一个或多个明密文对 $(P_i,C_i)$（known/chosen plaintext，这在 Q1 模型下是现实假设），目标是在 $2^\kappa$ 个候选中找出密钥 $K$。构造验证谓词

$$
V(k)=
\begin{cases}
1,&E_k(P_i)=C_i\ \text{对所有验证对};\\
0,&\text{否则}.
\end{cases}
$$

这里有一个容易忽略的细节：**单个明密文对通常不足以唯一确定密钥**。分组密码的分组长度为 $n$ 比特时，一个 $n$ 比特密文平均会把候选空间筛掉约 $2^n$ 倍；若 $\kappa>n$，用一个对平均还剩约 $2^{\kappa-n}$ 个“碰巧也对”的假阳性密钥。因此验证对的数量要取得足够多（大致使 $\kappa$ 比特的密钥被所有对联合唯一确定），这属于经典密码分析中的 unicity 估计，与量子部分无关但影响 oracle 的构造。

### 4.2 相位预言机

把 Grover 搜索套到谓词 $V$ 上：把密钥寄存器制备为均匀叠加 $|s\rangle=2^{-\kappa/2}\sum_k|k\rangle$；**可逆地**计算密码 $E_k(P_i)$、与 $C_i$ 比较、把比较结果写入相位、再 **uncompute**（反向运行）所有工作比特。净效果就是相位预言机

$$
|k\rangle\mapsto(-1)^{V(k)}|k\rangle.
$$

这一步在理论上总是可行的（任何经典可计算函数都可做成带垃圾比特的可逆电路再反算清除），但**工程上极其昂贵**：整个分组密码（如 AES）要被翻译成量子电路，密钥调度的每一轮都要可逆化，还需要足够的工作比特和 uncomputation 深度。

(grover-key-search-cost)=
### 4.3 迭代次数与真实成本

由 Grover 算法的标准分析（本站第 3 章），若唯一目标位于 $2^\kappa$ 个候选中，所需迭代次数约为

$$
\frac{\pi}{4}\,2^{\kappa/2}.
$$

$\frac{\pi}{4}$ 来自“把态从初始角度 $\theta\approx2^{-\kappa/2}$ 旋转到 $\frac{\pi}{2}$ 所需步数 $\frac{\pi/2}{2\theta}$”，不是随便塞进来的常数。但**每次迭代不是一个基本门**，而是至少包含：

- 一次完整的可逆密码计算（oracle）；
- 比较器与相位翻转；
- 一次 diffusion 算子（$2^{-\kappa}$ 量级的多比特受控相位，代价可忽略地低于密码本身）；
- 以及为保持相干性所需的全部 uncomputation。

因此 AES 类目标的严肃资源估计要数 **Toffoli/T 门数、逻辑量子比特数、电路深度（depth）与容错开销**，而不是只报告 $2^{\kappa/2}$ 这个查询数。文献中的 AES-128/192/256 量子资源估计正是按这种方式做的。

### 4.4 “密钥长度翻倍”只是启发式

流行的说法“Grover 让对称安全性减半，所以密钥翻倍即可”是 **exponent-level heuristic**，只在“串行、单目标、oracle 深度固定”的理想化下成立。实际的攻击经济学更复杂：

- **并行 Grover 的 time–processor tradeoff 很差。** 把候选空间均分给 $P$ 台处理器，每台搜索 $2^\kappa/P$ 大小的子空间，各自需要约 $\frac{\pi}{4}\sqrt{2^\kappa/P}$ 次迭代，于是**挂钟时间**只缩短为原来的 $1/\sqrt P$，而总处理器-时间乘积反而按 $\sqrt P$ 增长。也就是说，并行化在 Grover 上只有平方根回报——这与经典穷搜“$P$ 台机器 $P$ 倍速”完全不同，是量子攻击对防御方有利的一面。
- **多目标（multi-target）与单目标不同。** 攻击一个密钥库中“任意一个”密钥比攻击指定密钥便宜，这会改变大规模监控场景下的成本模型。
- **深度上限约束。** 物理机器能维持的相干深度有限；若限制总深度，Grover 的优势会被进一步压缩。

这些都改变具体参数选择，但不改变“平方根”这个渐近结论。

(hash-preimage-collision)=
## 5. Hash 原像与碰撞

对理想 $n$ 比特 hash 函数（随机预言机行为），三类任务的经典与量子复杂度完全不同，必须分开讨论：

- **原像搜索（preimage）：**给定 $y$，找 $x$ 使 $H(x)=y$。经典暴力约 $2^n$ 次求值；这正是无结构搜索，Grover 给出约 $2^{n/2}$ 次量子查询，且已证明是最优的。
- **第二原像（second preimage）：**给定 $x$，找 $x'\ne x$ 使 $H(x')=H(x)$。对理想 hash 与原像同阶。
- **碰撞搜索（collision）：**找任意一对 $x\ne x'$ 使 $H(x)=H(x')$。经典地用**生日悖论（birthday paradox）**只需约 $2^{n/2}$ 次求值。

**为什么生日攻击是 $2^{n/2}$？** 求值 $t$ 个随机输入，共有 $\binom{t}{2}\approx\frac{t^2}{2}$ 对候选；每对发生碰撞的概率约为 $2^{-n}$。于是“没有碰撞”的概率约为

$$
\prod_{i<j}\left(1-2^{-n}\right)\approx\exp\!\left(-\frac{t^2}{2}\cdot2^{-n}\right),
$$

其中用了 $1-x\le e^{-x}$ 并把 $\binom t2$ 近似为 $t^2/2$。取 $t\sim2^{n/2}$ 时指数部分变成常数，碰撞以显著概率出现——这就是 $2^{n/2}$ 的来源：它来自**对数（pair counting）**，与 Grover 的振幅放大毫无关系。

**BHT 碰撞算法**（Brassard–Høyer–Tapp）把两者结合，是参数平衡的好例子：

1. 经典地求值 $r$ 个随机输入，建立表 $\{(x_i,H(x_i))\}$；
2. 对函数“$x$ 是否与表中某项碰撞（且 $x$ 不在表中）”跑 Grover：目标在 $2^n$ 个输入中约有 $r$ 个，故迭代次数约 $\sqrt{2^n/r}$；
3. 总查询数为两项之和
   $$
   T(r)=r+\sqrt{\frac{2^n}{r}}.
   $$

平衡两项使它们同阶：令 $r=\sqrt{2^n/r}$，两边平方得 $r^2=2^n/r$，即 $r^3=2^n$，解出

$$
r=2^{n/3},\qquad T=O\!\left(2^{n/3}\right).
$$

这就是 $2^{n/3}$ 的完整来历。但要注意括号里的代价：算法需要存储并**查询**一张 $2^{n/3}$ 大小的表。若表放在经典内存中、每次 Grover 迭代的查表按访问成本计费，或者要求相干访问（QRAM）才能实现标准分析，那么 $2^{n/3}$ 就不再是完整的成本刻画——后续的 quantum-walk 类碰撞算法以及 “collision search 是否真的比经典便宜” 的争论，核心都在内存与访问模型的计费上。

**结论：碰撞加速不是“所有 hash 安全位数也除以二”。** 原像、第二原像、碰撞、多目标、claw finding 是不同的 game；量子内存是否相干、并行化如何计费、存储表访问是否收费，都会改变最优攻击。给一个 $n$ 比特 hash 标“量子安全强度”时，必须写明是哪一个 game、哪一种内存模型。

## 6. 加速已有的经典密码分析

现实世界的密码分析很少是全密钥暴力破解。主流攻击是**差分（differential）**、**线性（linear）**密码分析、**中间相遇（meet-in-the-middle）**、格筛（lattice sieving）、信息集译码（information-set decoding）等结构化方法。量子化这些攻击的通用套路是：把其中“枚举候选”“找碰撞”“随机游走”这类瓶颈子程序换成 Grover / 振幅放大 / quantum walk。

以差分攻击为例：一条差分路线（differential trail）给每个候选子密钥一个统计得分（score），得分超过阈值的是候选。经典做法是：收集足够多的明密文数据，然后枚举子密钥、逐个打分。量子做法是把“枚举 + 打分 + 阈值筛选”相干化——在子密钥的均匀叠加态上相干地评估 score，再用振幅放大突出通过阈值的候选。若枚举空间为 $2^m$，期望加速是平方根级：$O(2^{m/2})$ 次相干打分。

但下面四个保留条款一个都不能省：

1. **经典数据收集未必有平方根加速。** 获取明密文对是 Q1 过程，量子计算机不能加速“和目标设备通信”这一步；数据复杂度（data complexity）通常原样保留。
2. **score 的相干评估可能需要 QRAM 或 Q2 查询。** 若打分函数依赖一张大数据表（例如差分分布表、计数器数组），相干读取它就要求 QRAM；若打分本身需要查询目标设备，那就滑向 Q2 模型。两者都是额外假设。
3. **经典最优变体未必是量子最优变体。** 一个攻击的多个经典变体（不同数据/时间/内存权衡点）量子化后的加速比不同，量子最优策略可能需要重新选取，而不是把经典最优参数直接搬过来。
4. **time、data、memory 三个指数要一起比较。** 只报告“时间从 $2^a$ 降到 $2^{a/2}$”而隐瞒 data 或 memory 膨胀，是量子密码分析文献中最常见的夸大手法。

Kaplan 等人对差分/线性密码分析的量子化分析正说明了这一点：**常常**能得到 quadratic improvement，但并非每种变体都有同样的改善，有些场景下经典攻击仍占优。同理，code-based 与 lattice-based 原语的安全指数会被量子信息集译码、量子搜索/筛法**改变**（通常是把某个安全指数从 $c$ 降到 $c'$，$c'<c$ 但仍是指数的），而不是因此自动被多项式时间破解——这与 Shor 对 RSA 的打击有本质区别。

## 7. 其他代数攻击：结论为何必须局部化

本节三个例子的共同教训是：**论文标题里的问题名 ≠ 密码系统实际依赖的问题实例。** 量子算法的适用范围由精确的 promise（问题的数学约束）与参数区间决定。

### 7.1 Isogeny（同源）

Childs–Jao–Soukharev 利用 quantum walk / hidden-shift 的思想，在某些 **ordinary（普通）椭圆曲线**的 isogeny graph 上构造了**次指数**时间算法。要点有两层：

- 它攻击的是**特定的 isogeny 问题实例**（普通曲线上的特定参数区间），其结构允许归约到二面体群型的 hidden-shift 问题；
- 不能从标题推断“所有 isogeny 构造都被同一算法破解”。后续基于超奇异（supersingular）曲线或其他变体的构造，其底层问题不满足该算法需要的 promise，安全性要单独分析。

### 7.2 Lattice（格）

Eldar–Hallgren 对**带子指数近似因子（subexponential approximation factor）**的某些格问题给出了量子算法。但 Ducas–van Woerden 随后指出，该算法覆盖的参数区间**可能已经被经典 LLL 算法覆盖**——也就是说量子算法做的那部分问题，经典算法本来就会做。

这个来回的正确读法是：比较量子与经典算法时，必须固定**同一个范数（norm）、同一个维数、同一个近似因子与同一个 promise**，逐项对齐后再比复杂度，而不是笼统地写“quantum computer solves lattices”。与此同时，quantum lattice sieving / quantum random walk 确实能改善某些 SVP 攻击的**常数或指数**（把某个指数 $c$ 降到 $c'<c$）——这仍然与 Shor 式的多项式时间破解是两回事，格基密码目前没有被多项式时间量子算法攻破。

### 7.3 Multivariate systems（多元方程组）

多元公钥密码（MPKC）的困难问题是求解有限域上的多元二次方程组。一条诱人的量子路线是：把多项式方程组在某一 **Macaulay 次数**下线性化，得到一个大线性系统 $M z=b$（$M$ 是 Macaulay 矩阵，行是乘以各单项式后的方程，列是单项式），然后用 HHL/QSVT 求解

$$
M|z\rangle=|b\rangle,
$$

表面上线性系统求解只需 $\operatorname{polylog}(\dim M)$。但端到端复杂度取决于一串彼此相乘的因子，每个都可能把优势吃掉：

- $M$ 的 **sparsity / block encoding** 成本——HHL 类算法的输入模型不是免费的；
- **条件数 $\kappa(M)$**——HHL 的复杂度含 $\kappa$（或其多项式），而 Macaulay 矩阵通常病态；
- 解态 $|z\rangle$ 与“有用的单项式坐标”之间的 **overlap**——$|z\rangle$ 是全部单项式上的叠加，真正想要的只是其中少数几个分量的值；
- 从量子态 $|z\rangle$ **读出**经典根的成本——读取本身可能指数昂贵；
- **Macaulay 次数增长导致的维数膨胀**——方程组越难，需要的 Macaulay 次数越高，$\dim M$ 指数增长。

Ding 等人证明这一路线有重要限制。教训是普遍的：**不能把某个线性系统子程序的复杂度直接当成整个多元密码系统的破解复杂度**；端到端分析里每个因子的来源都要单独交代。

## 8. Q2 模型下的 Simon 攻击

### 8.1 Even–Mansour 构造

Even–Mansour 是最简洁的分组密码设计之一：取一个**公开**的 $n$ 比特置换 $P$（所有人都知道、都能计算），秘密是两个 $n$ 比特密钥 $k_1,k_2\in\{0,1\}^n$，加密定义为

$$
E_{k_1,k_2}(x)=P(x\oplus k_1)\oplus k_2.
$$

安全性来自密钥对公开置换输入输出的“掩蔽”：经典攻击者即使能任意查询 $P$ 和 $E$，在理想置换模型下恢复密钥仍需要指数级的查询/时间（已知的经典最好攻击也是指数级别的），总共 $2n$ 比特的密钥材料看似提供了指数级的工作因子。

(simon-even-mansour)=
### 8.2 构造隐藏周期函数

现在假设攻击者处于 **Q2 模型**：他能对固定的 $k_1,k_2$ 相干地查询 $E$（同时 $P$ 是公开的，本来就能自己相干计算）。构造函数

$$
F(x)=P(x)\oplus E_{k_1,k_2}(x).
$$

计算 $F$ 在 $x\oplus k_1$ 处的值（逐步代入定义）：

$$
\begin{aligned}
F(x\oplus k_1)
&=P(x\oplus k_1)\oplus E_{k_1,k_2}(x\oplus k_1)
&&\text{（$F$ 的定义）}\\
&=P(x\oplus k_1)\oplus P\big((x\oplus k_1)\oplus k_1\big)\oplus k_2
&&\text{（$E$ 的定义）}\\
&=P(x\oplus k_1)\oplus P(x)\oplus k_2
&&\text{（$k_1\oplus k_1=0$）}\\
&=P(x)\oplus \big(P(x\oplus k_1)\oplus k_2\big)
&&\text{（XOR 交换律/结合律）}\\
&=P(x)\oplus E_{k_1,k_2}(x)
&&\text{（$E$ 的定义）}\\
&=F(x).
&&\text{（$F$ 的定义）}
\end{aligned}
$$

因此 $F$ 具有 **hidden XOR period $k_1$**：$F(x\oplus k_1)=F(x)$ 对所有 $x$ 成立。这正是 Simon 问题的输入形态（本站第 3 章已完整分析 Simon 算法，这里直接调用）。

**一个诚实的保留条款：** Simon 算法要求函数满足周期 promise——$F(x)=F(x')$ 蕴含 $x'=x$ 或 $x'=x\oplus k_1$。对随机的公开置换 $P$，除了由 $k_1$ 造成的“结构性”碰撞外，还可能存在**偶然碰撞（accidental collisions）**：某些 $x\ne x'$（且 $x'\ne x\oplus k_1$）碰巧满足 $F(x)=F(x')$。严格的理想置换模型分析需要证明这类偶然碰撞足够稀少、不会破坏 Simon 算法的采样分布；完整的攻击分析里这一步是显式处理的，我们在此指出它的存在而不展开。

### 8.3 用 Simon 算法恢复密钥

对 $F$ 运行 Simon 算法，每次运行输出一个随机的 $y\in\{0,1\}^n$，满足

$$
y\cdot k_1=\bigoplus_{i=1}^n y_i\,(k_1)_i=0\pmod 2,
$$

即每次测量给出关于未知向量 $k_1$ 的**一个线性方程**（系数向量 $y$ 已知）。收集 $O(n)$ 次独立采样后，以高概率得到 $n-1$ 个线性无关的方程；对 $\mathbb F_2$ 上的方程组做 **Gaussian elimination**，把解空间缩小到 $\{0,k_1\}$（平凡解 $0$ 对应全零行空间），即可读出非零解 $k_1$。全部成本是 $O(n)$ 次相干查询加 $O(n^3)$ 的经典线性代数——**多项式**。

拿到 $k_1$ 后，$k_2$ 用一个经典明密文对即得：

$$
k_2=E_{k_1,k_2}(x)\oplus P(x\oplus k_1),
$$

这就是把 $E$ 的定义移项：$E_{k_1,k_2}(x)=P(x\oplus k_1)\oplus k_2$ 两边同时 XOR $P(x\oplus k_1)$。

于是整个攻击把原本指数级的密钥恢复降为**多项式次量子查询**。同样的 hidden-period 构造还可以攻击 3 轮 Feistel 网络、CBC-MAC、PMAC 一类的 MAC、related-key 模型下的某些构造、以及部分认证加密设计——它们的共性是“公开的轮结构 + 秘密的 XOR 掩码”，恰好能拼出一个带隐藏周期的函数。

### 8.4 前提条件再强调

这整条攻击链的关键前提是第 1 节的 Q2 假设：攻击者能让**带固定秘密密钥的实现**接受输入叠加态并返回相干输出。普通的远程加密 API 不满足这个条件——服务器在经典比特上工作。但若原语被嵌入到攻击者可以调用的**量子电路或量子协议**内部（例如某些量子化协议、或对密码模块实现本身做相干分析的场景），Q2 就是正确模型。判断标准只有一条：**秘密 $K$ 是否被“冻”在一个攻击者可相干操作的电路里**。

(three-attack-classes)=
## 9. 三类结论对照

| 类别 | 代表 primitive | 核心量子工具 | 典型影响 | 主要边界 |
|---|---|---|---|---|
| Algebraic public-key | RSA、DH、ECC | QFT / abelian HSP | polynomial-time break | 大型 fault-tolerant arithmetic |
| Generic/quantized attack | symmetric key、hash、code/lattice attack | Grover、collision、quantum walk | quadratic 或 exponent 改善 | reversible oracle、data/memory |
| Superposition-query | Even–Mansour、Feistel、MAC variants | Simon | 某些 construction 的 polynomial query break | 需要 Q2 secret-key oracle |

读这张表的方式：第一行是“难题落入 $\mathsf{BQP}$”，第二行是“安全指数打折”，第三行是“模型升级后的构造性崩溃”。三者的防御对策完全不同：第一行要求换难题（后量子迁移），第二行要求加大参数，第三行要求重新设计可证明抗 Q2 的构造。

最后，“post-quantum（后量子）”的正确理解是：在**已知的**经典与量子攻击下选取问题与参数，使得两种模型下的最好攻击都超出预算；它**不是**数学上证明永不被量子算法攻击。任何安全估计都必须写明模型（Q1/Q2）、成功概率、逻辑门成本，以及用于对照的最新经典基线攻击。

## 10. 分析一个新 primitive 的步骤

面对一个新的密码构造，按下面的顺序做量子安全分析，可以避免本章提到的大多数错误：

1. **写出 security game**：目标是 key recovery、IND 区分、forgery、preimage 还是 collision？不同 game 的量子化路径完全不同。
2. **指定攻击模型**：Q1 还是 Q2？哪些操作是 public 的、可由攻击者自行可逆实现？不要把经典 API 偷偷换成相干预言机。
3. **找代数结构**：是否存在周期、隐藏子群、hidden shift？若存在，走 Shor/Simon 一族；若没有，再找攻击中可被振幅放大或 quantum walk 加速的瓶颈子程序。
4. **把整个攻击可逆化并记账**：数量子比特数、oracle 深度、查询次数、经典数据量和内存——五项缺一不可。
5. **与最佳经典攻击公平比较**：固定相同的成功率与内存预算，而不是拿量子理想模型对经典受限模型。
6. **重新优化整体参数**：若量子只改善了攻击的一个子程序，要重新做完整的参数平衡（如第 5 节 BHT 的 $r=2^{n/3}$ 那样解极小化问题），不要机械地把总指数除以二。

## 11. 本课小结

**小结：**

- Shor 算法多项式时间破解基于整数分解与离散对数的公钥体制（RSA、DH、ECC）；这是难题层面的崩塌，靠加长密钥无法修复，也是 recorded-data 威胁与后量子迁移的根源。
- Grover 与碰撞算法大多只改变对称密码与 hash 的安全**指数**：穷搜密钥约 $2^{\kappa/2}$，理想 hash 原像约 $2^{n/2}$，碰撞在理想化查询模型下约 $2^{n/3}$（BHT），但内存与访问模型会实质影响结论。
- Simon 型 Q2 攻击能把特定对称构造（Even–Mansour、3 轮 Feistel、CBC-MAC 等）的密钥恢复降到多项式次查询，但需要现实中少见的相干 secret-key 访问。
- Isogeny、lattice、multivariate 方向的量子结论必须限定在具体的 problem promise 与参数区间内理解；“某类问题有量子算法”不等于“基于该问题的密码被破解”。

## 练习题

**练习 1【攻击者能力模型：Q1、Q2 与 recorded-data】**（→ [第 1 节](#attacker-models-q1-q2)）

1. 分别用一句话写出 Q1 与 Q2 模型中攻击者对 $E_K$ 的访问方式，并指出相干预言机 $O_{E_K}|x,z\rangle=|x,z\oplus E_K(x)\rangle$ 属于哪一种。
2. 说明 recorded-data（先存后解）威胁为什么完全不需要在线量子访问，以及它为何是推动后量子密码迁移的现实动机。
3. （建模）各给一个“只需 Q1 即可实施的攻击”与“本质上必须 Q2 的攻击”的具体场景，并说明判断依据。

> 提示：判断标准是秘密 $K$ 是否被“冻”在一个攻击者可相干操作的电路里。

**练习 2【Shor：从分解到周期寻找】**（→ [2.2 节](#shor-period-finding)）

1. 写出元素阶 $r$ 的定义，并解释为什么 $\gcd(a,N)>1$ 时无需任何量子计算即可完成分解。
2. 证明 $f(x)=a^x\bmod N$ 以 $r$ 为周期，并说明 $\gcd(a,N)=1$ 为何保证 $U_a|x\rangle=|ax\bmod N\rangle$ 可以实现为酉算子。
3. 在“随机选 $a$ → 求阶 $r$ → 连分数展开 → 两次 $\gcd$”的完整链条中指出哪些步骤由量子计算机完成、哪些由经典后处理完成，并解释为什么说经典地求 $r$ 并不比直接分解 $N$ 容易。

> 提示：量子部分只承担周期寻找；逐一试幂求阶需要指数多次模乘。

**练习 3【Shor：从周期到因子的经典后处理】**（→ [2.3 节](#shor-classical-postprocessing)）

1. 写出经典后处理的两条检查条件，并分别说明每一条排除了哪种使 $\gcd$ 只给出平凡结果的失败情形。
2. （手算）对 $N=15$、$a=2$：求阶 $r$，检查 Shor 经典后处理的两条条件，并算出两次 $\gcd$ 得到的因子。
3. 证明：由 $r$ 的极小性必有 $N\nmid(a^{r/2}-1)$；若 $a^{r/2}\equiv-1\pmod N$，则两个最大公因子都只能给出平凡结果。

> 提示：把 $a^r-1$ 用平方差公式拆成 $(a^{r/2}-1)(a^{r/2}+1)$ 后，逐项检查 $N$ 整除哪一个因子。

**练习 4【离散对数的隐藏子群归约】**（→ [3.2 节](#dlog-hidden-subgroup)）

1. 写出离散对数问题的定义，并给出经典通用攻击与椭圆曲线情形最好经典攻击的复杂度量级。
2. 验证 $f(a,b)=g^a h^b=g^{a+bx}$（代入 $h=g^x$），并推导 $f(a,b)=f(a',b')$ 当且仅当 $(a-a')+x(b-b')\equiv0\pmod q$。
3. （推导）从第 3 节的 $f(a,b)=g^{a+bx}$ 出发，补全“$f$ 在 $H=\langle(-x,1)\rangle$ 的陪集上取常值”的证明，并推导 QFT 采样结果 $(u,v)$ 满足的正交方程 $-ux+v\equiv0\pmod q$。

> 提示：正交方程来自特征标 $(a,b)\mapsto e^{2\pi i(ua+vb)/q}$ 在生成元 $(-x,1)$ 上取值 $1$ 的要求。

**练习 5【Grover 密钥恢复的迭代与成本】**（→ [4.3 节](#grover-key-search-cost)）

1. 写出相位预言机 $|k\rangle\mapsto(-1)^{V(k)}|k\rangle$ 的构造步骤，并说明最后一步 uncompute 为什么不可省略。
2. （计算）设 $\kappa=128$ 且目标密钥唯一，计算所需 Grover 迭代次数的数量级，并写出 $\frac{\pi}{4}$ 这个常数的几何来源。
3. （复杂度）设密钥空间有 $2^{128}$ 个候选、每次 Grover 迭代的 oracle 深度为 $D$。写出串行总深度的数量级；若有 $P=2^{20}$ 台理想并行处理器，挂钟深度变为多少？由此说明并行 Grover 的 tradeoff。

> 提示：$P$ 台处理器把候选空间均分后，每台各搜 $2^\kappa/P$ 大小的子空间。

**练习 6【Hash 原像、碰撞与 BHT 算法】**（→ [第 5 节](#hash-preimage-collision)）

1. 列出理想 $n$ 比特 hash 的原像、第二原像与碰撞三个任务在经典与量子模型下的复杂度量级。
2. 推导生日界：求值 $t$ 个随机输入后“无碰撞”的概率约为 $\exp\!\big(-\frac{t^2}{2}\cdot 2^{-n}\big)$，并说明为何取 $t\sim2^{n/2}$ 时碰撞以显著概率出现。
3. （参数平衡）在第 5 节 BHT 算法中，把表大小改为 $r=2^{n/4}$，总查询数 $T(r)=r+\sqrt{2^n/r}$ 变成多少？与 $r=2^{n/3}$ 比较，说明为什么 $2^{n/3}$ 是平衡点。

> 提示：分别写出 $r$ 与 $\sqrt{2^n/r}$ 两项的指数，平衡点在两项同阶处。

**练习 7【Simon 攻击与 Even–Mansour 构造】**（→ [8.2 节](#simon-even-mansour)）

1. 写出 Even–Mansour 加密 $E_{k_1,k_2}(x)=P(x\oplus k_1)\oplus k_2$ 的定义，并说明 Simon 算法每次测量输出的 $y$ 满足哪个关于 $k_1$ 的线性方程。
2. （验证）补全第 8.2 节 $F(x\oplus k_1)=F(x)$ 的推导，并说明：哪些“偶然碰撞”会破坏 Simon 算法要求的 promise？为什么理想置换模型下期望它们稀少？（定性即可）
3. 解释为什么 $O(n)$ 次独立采样加高斯消元能把候选缩小到 $\{0,k_1\}$，以及拿到 $k_1$ 后如何用单个明密文对求出 $k_2$。

> 提示：把 $E_{k_1,k_2}(x)=P(x\oplus k_1)\oplus k_2$ 两边同时异或 $P(x\oplus k_1)$。

**练习 8【三类攻击对照与后量子边界】**（→ [第 9 节](#three-attack-classes)）

1. 仿照第 9 节的表格，按“核心量子工具、典型影响、主要边界”三列默写三类攻击（代数公钥、通用量化、Q2 Simon）的对照。
2. 比较三类攻击对应的防御对策，并解释为什么“换难题、加大参数、重新设计构造”三者互不通用。
3. 解释“post-quantum（后量子）”的正确含义，并列举一份合格的量子安全估计必须写明的要素。

> 提示：三类的分界在预言机形式与加速量级——难题落入 $\mathsf{BQP}$、安全指数打折、模型升级后的构造性崩溃。

## 参考文献与 Zoo 覆盖

- Zoo 编号 14、82、109、125：Boneh--Lipton hidden linear functions、Shor factoring/discrete log 与 elliptic-curve implementation。
- Zoo 编号 283、537--541：isogeny、lattice 与 multivariate algebraic attacks，以及适用范围/限制。
- Zoo 编号 262、284--285、287--288、315--316、536：AES/hash、block-cipher、NTRU、lattice sieving 和 collision 的 quantized attacks。
- Zoo 编号 286、289--292：differential/linear cryptanalysis，以及 Feistel、Even--Mansour、related-key 与 Simon symmetric-key attacks。
- 主要原文：[Shor](https://arxiv.org/abs/quant-ph/9508027)、[isogeny attack](https://arxiv.org/abs/1012.4019)、[AES resource estimates](https://arxiv.org/abs/1512.04965)、[quantum differential/linear cryptanalysis](https://arxiv.org/abs/1510.05836)、[Simon symmetric-key attacks](https://arxiv.org/abs/1603.07856)与[Macaulay/HHL limitations](https://arxiv.org/abs/2111.00405)。