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

量子计算对密码学的影响不是“所有密钥长度减半”。Shor 对 factoring/discrete logarithm 给 polynomial-time algorithms；Grover 对无结构 key search 只给 quadratic query speedup；Simon 型攻击可能在 superposition-query 模型中完全破坏特定 symmetric constructions。三类攻击的 oracle、数据、内存和输出都不同。

## 1. 先区分攻击者能力

设 keyed primitive 为 $E_K(x)$。至少要区分：

- **Q1 / offline-quantum：**攻击者只能向真实设备发送 classical queries，但可把拿到的数据交给 quantum computer。
- **Q2 / superposition-query：**攻击者可调用 coherent oracle
  $$
  O_{E_K}|x,z\rangle=|x,z\oplus E_K(x)\rangle
  $$
  并保持跨查询 coherence。
- **Public-algorithm model：**RSA、Diffie--Hellman 等公开运算可由攻击者自行 reversible 实现，不需要秘密 oracle。
- **Recorded-data threat：**今天记录的 public-key ciphertext，未来可在 fault-tolerant quantum computer 上解密；这与在线 Q2 access 无关。

Q2 严格强于普通 chosen-plaintext API。网络服务器测量 request 并返回 classical response，通常不会实现 $O_{E_K}$；因此 Q2 结果不能直接当作现实 break，但它揭示 classical security proof 在 quantum-access model 下可能失效。

## 2. Shor 如何分解 RSA modulus

给 $N=pq$，随机选 $1<a<N$。若 $\gcd(a,N)>1$ 已找到 factor；否则定义 order

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

Quantum period finding 对 modular multiplication

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

做 phase estimation，恢复 $r$。若 $r$ 为偶数且

$$
a^{r/2}\not\equiv-1\pmod N,
$$

则

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

于是

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

给出非平凡 factors。失败时换 $a$ 重试；对 semiprime，常数次数可得高成功率。

量子部分和 classical continued fractions 都是 $\operatorname{poly}(\log N)$，所以不是 Grover 式平方根改善，而是相对已知 classical factoring 的 superpolynomial/exponential-type separation。实际门数仍包含 fault-tolerant modular arithmetic、many logical qubits 和 error correction，不能把 asymptotic polynomial 等同于近期可运行。

## 3. Discrete logarithm 与椭圆曲线

在 order-$q$ cyclic group $G=\langle g\rangle$ 中，给

$$
h=g^x
$$

求 $x$。构造

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

$f(a,b)=f(a',b')$ 当且仅当

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

因此 $f$ 隐藏 subgroup

$$
H=\langle(-x,1)\rangle\le\mathbb Z_q^2.
$$

制备 $(a,b)$ 的 uniform superposition、相干计算 group element、测量/丢弃 function register，再做 $QFT_q\otimes QFT_q$，会采样与 $H$ 正交的 vectors。若 sample 为 $(u,v)$，则

$$
-ux+v=0\pmod q,
$$

在 $u\ne0$ 时恢复 $x=vu^{-1}\bmod q$。

同样思路适用于 finite-field Diffie--Hellman 和 elliptic-curve group；后者把 modular exponentiation 换为 reversible elliptic-curve point addition。故传统 RSA、finite-field DH 与 ECC 的安全问题不是简单“加长 key”：底层 hard problem 已进入 BQP。完整推导见[Shor factoring](../ch04-classic-algorithms/shors-algorithm-tutorial.md)和[Shor discrete log](../ch04-classic-algorithms/shors-discrete-log-tutorial.md)。

## 4. Grover key recovery

对 $\kappa$-bit key，用一个或多个 plaintext--ciphertext pairs 构造 predicate

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

把 key register 置为 uniform state，reversible 地计算 cipher 和比较器，再 uncompute workspace，即得到 phase oracle

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

若唯一 key 位于 $2^\kappa$ 个 candidates 中，约

$$
\frac\pi4\,2^{\kappa/2}
$$

次 Grover iterations 可恢复它。每次 iteration 不是一个 elementary gate，而是至少一次完整 reversible cipher、comparison、uncomputation 和 diffusion；AES resource estimates 因此要数 Toffoli/T gates、logical qubits、depth 与 fault-tolerant overhead。

“把 symmetric key length 翻倍”只是 exponent-level heuristic。Parallel Grover 的 time--processor tradeoff、multiple targets、circuit depth 和 attack economics 都会改变具体 parameter choice。

## 5. Hash preimage 与 collision

对 ideal $n$-bit hash：

- preimage search 的 classical work 约 $2^n$，Grover query complexity 约 $2^{n/2}$；
- classical collision search 用 birthday paradox 约 $2^{n/2}$ evaluations；
- BHT/quantum-walk collision algorithms 可到约 $2^{n/3}$ quantum queries，并使用相应 memory/data structure。

Collision speedup 不是“所有 hash security 位数也除以二”。Preimage、second preimage、collision、multi-target 和 claw finding 是不同 games；量子 memory 是否 coherent、parallelization 和 stored table access 是否计费也会改变最优 attack。

## 6. 加速已有密码分析

很多实际攻击不是全 key brute force，而是 differential、linear、meet-in-the-middle、lattice sieving 或 information-set decoding。量子版本把其中的候选 search、collision 或 random walk 换成 Grover/amplitude amplification/quantum walk。

例如 differential trail 给某 key hypothesis 一个统计 score。Classically 可能先收集 data，再枚举 subkeys；quantumly可相干评估 score 并放大 passing candidates。但：

1. classical data collection 未必平方根加速；
2. score evaluation 可能需 QRAM 或 Q2 queries；
3. classical 最优 variant 未必 quantumly 最优；
4. attack 的 time、data、memory exponents 要一起比较。

Kaplan 等对 differential/linear cryptanalysis 的分析正说明：常可得到 quadratic improvement，但并非每种 variant 都有同样改善。Code-based 与 lattice-based primitives 也会因 quantum information-set decoding、search 或 sieving 改变安全 exponent，而非因此自动被 polynomial-time 破解。

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

### 7.1 Isogeny

Childs--Jao--Soukharev 用 quantum walk/hidden-shift ideas 在某些 ordinary elliptic-curve isogeny graph 上构造 subexponential algorithm。这攻击的是特定 isogeny problem/parameter regime，不能从标题推断所有 isogeny constructions 都被同一算法破解。

### 7.2 Lattice

Eldar--Hallgren 对带 subexponential approximation factor 的某些 lattice problems 给出 quantum algorithm；Ducas--van Woerden 指出相关参数区间可能已被 classical LLL 覆盖。正确读法是比较**同一 norm、dimension、approximation factor 与 promise**，而不是笼统写“quantum computer solves lattices”。

Quantum lattice sieving/random walks 可改善某些 SVP attack 的常数或 exponent，这仍与 Shor 的 polynomial break 不同。

### 7.3 Multivariate systems

把 polynomial equations 线性化为 Macaulay matrix $M$，再用 HHL/QSVT 求

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

看似只需 $\operatorname{polylog}(\dim M)$。但端到端复杂度依赖：

- $M$ 的 sparsity/block encoding；
- condition number $\kappa(M)$；
- 解 state 与有用 monomial coordinates 的 overlap；
- 从 $|z\rangle$ 读出 classical root 的成本；
- Macaulay degree 造成的 dimension growth。

Ding 等证明这一路线有重要限制；不能把 linear-system 子程序复杂度直接当成 multivariate cryptosystem break。

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

以 two-key Even--Mansour 为例，公开 permutation $P$，secret keys $k_1,k_2\in\{0,1\}^n$：

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

若攻击者能 coherent 查询 $E$，构造

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

则

$$
\begin{aligned}
F(x\oplus k_1)
&=P(x\oplus k_1)\oplus
  P(x)\oplus k_2\\
&=F(x).
\end{aligned}
$$

因此 $F$ 具有 hidden XOR period $k_1$（ideal-permutation 分析还需控制 accidental collisions）。运行 Simon algorithm，每次测量得到

$$
y\cdot k_1=0\pmod2.
$$

收集 $O(n)$ 个独立 equations，Gaussian elimination 恢复 $k_1$；再用一个 classical pair 得

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

这可把原本 exponential 的 key recovery 降为 polynomial quantum queries。相似 hidden-period constructions 会攻击 3-round Feistel、CBC-MAC、related-key 或某些 authenticated-encryption designs。

关键前提是攻击者能让**带固定秘密 key 的实现**接受 input superposition 并返回 coherent output。普通 remote encryption API 不满足这一条件；但若 primitive 被嵌入 adversary 可调用的 quantum circuit/protocol，Q2 就可能是正确模型。

## 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 |

“post-quantum”应理解为在已知 classical 与 quantum attacks 下选择 problems/parameters，而非数学上证明永不被量子算法攻击。安全估计必须写明 model、success probability、logical gate cost 和最新 classical baseline。

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

1. 写 security game：key recovery、IND、forgery、preimage 还是 collision？
2. 指定 Q1/Q2 与 public operations；不要把 classical API 偷换成 coherent oracle。
3. 找 algebraic period/hidden subgroup；若无，再找可被 amplitude amplification 的 bottleneck。
4. 把 whole attack reversible 化，计算 qubits、oracle depth、queries、data 和 memory。
5. 与最佳 classical attack 在相同成功率和 memory budget 下比较。
6. 若只改善一个 subroutine，重新优化整个 attack parameters；不要机械地把总 exponent 除二。

## 11. 小结与习题

- Shor polynomially breaks factoring and discrete log based public-key systems。
- Grover 和 collision algorithms 多数只改变 symmetric/hash security exponent。
- Simon Q2 attacks 很强，但需要现实中少见的 coherent secret-key access。
- Isogeny、lattice、multivariate 结论必须限定 problem promises 和 parameter regime。

1. 对 $N=15,a=2$ 求 order $r$，并计算 Shor classical postprocessing 得到的 factors。
2. 推导 discrete-log hidden subgroup $H=\langle(-x,1)\rangle$ 的 orthogonality equation。
3. 若 key space 有 $2^{128}$ 个 keys、每个 Grover oracle 深度为 $D$，写出 serial depth 的数量级。
4. 验证 Even--Mansour 的 $F(x\oplus k_1)=F(x)$，并说明何种额外 collisions 会破坏 Simon promise。
5. 分别给一个只需 Q1 和必须 Q2 的 attack 场景。

## 参考文献与 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)。