量子密码分析：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和Shor discrete log。

4. Grover key recovery¶

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

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

把 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。但：

classical data collection 未必平方根加速；
score evaluation 可能需 QRAM 或 Q2 queries；
classical 最优 variant 未必 quantumly 最优；
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{split} \begin{aligned} F(x\oplus k_1) &=P(x\oplus k_1)\oplus P(x)\oplus k_2\\ &=F(x). \end{aligned} \end{split}\]

因此 $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 的步骤¶

写 security game：key recovery、IND、forgery、preimage 还是 collision？
指定 Q1/Q2 与 public operations；不要把 classical API 偷换成 coherent oracle。
找 algebraic period/hidden subgroup；若无，再找可被 amplitude amplification 的 bottleneck。
把 whole attack reversible 化，计算 qubits、oracle depth、queries、data 和 memory。
与最佳 classical attack 在相同成功率和 memory budget 下比较。
若只改善一个 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。

对 $N=15,a=2$ 求 order $r$，并计算 Shor classical postprocessing 得到的 factors。
推导 discrete-log hidden subgroup $H=\langle(-x,1)\rangle$ 的 orthogonality equation。
若 key space 有 $2^{128}$ 个 keys、每个 Grover oracle 深度为 $D$，写出 serial depth 的数量级。
验证 Even--Mansour 的 $F(x\oplus k_1)=F(x)$，并说明何种额外 collisions 会破坏 Simon promise。
分别给一个只需 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、isogeny attack、AES resource estimates、quantum differential/linear cryptanalysis、Simon symmetric-key attacks与Macaulay/HHL limitations。