计算困难假设 — DLog / RSA / LWE / SIS / 后量子

日期: 2026-11-10 方向: 密码学数学 阶段: Phase 4 - 密码学数学基础 (Day 181-194) 标签: #密码学 #LWE #SIS #后量子 #困难假设

---

今日目标

---

一、动机

NIST PQC 比赛 (2017-2024) 选定后量子算法：

• KEM: Kyber (lattice / MLWE)
• 签名: Dilithium (lattice / MLWE+MSIS), Falcon (lattice / NTRU), SPHINCS+ (hash)

经典 RSA / ECC 必被量子破。后量子选哪个假设？凭什么"格"是新主流？

---

二、五大假设全景

---

三、严格定义（关键三个）

3.1 DLog 与 ECDLP（已 Day 186 详）

略。

3.2 RSA / Factoring

Factoring 问题：给 $N = pq$（$p, q$ 大素数），求 $p, q$。

RSA 假设：给 $N, e, y$（$y = x^e \mod N$，$x$ 随机），求 $x$。

关系：Factoring 易 ⇒ RSA 易；反向未证。

强 RSA：给 $N, y$，自由选 $e \ge 2$，求 $x: x^e \equiv y$。

3.3 LWE (Learning With Errors)

Regev 2005：

问题 (Search-LWE)：给 $A \in \mathbb{Z}_q^{m \times n}$（$m > n$），$\mathbf{b} = A \mathbf{s} + \mathbf{e} \mod q$，$\mathbf{s} \in \mathbb{Z}_q^n$ 秘密，$\mathbf{e}$ 是"小"误差（如离散高斯 $\chi$）。求 $\mathbf{s}$。

Decision-LWE：区分 $(A, A\mathbf{s} + \mathbf{e})$ 和均匀 $(A, \mathbf{u})$。

关键定理 (Regev 2005)：search-LWE 至少与 worst-case lattice 问题（GapSVP, SIVP）一样难，包括量子归约。

MLWE / RLWE：模块/环版本，更结构化但更高效（Kyber 用 MLWE）。

3.4 SIS (Short Integer Solution)

问题：给 $A \in \mathbb{Z}_q^{n \times m}$，求非零 $\mathbf{z} \in \mathbb{Z}^m$, $|\mathbf{z}| \le \beta$, $A\mathbf{z} = 0 \mod q$。

关系：SIS 难 ⇔ 格上 short vector 难（worst-case 归约）。

用途：Dilithium 签名安全证明。

3.5 Isogeny (CSIDH)

问题 (CSIDH)：给两条同构曲线 $E_1, E_2$（同 endomorphism 环），求 $E_1$ 到 $E_2$ 的同源 $\phi$。

安全：经典 sub-exp，量子 sub-exp（Kuperberg）。SIDH 在 2022 被多项式破（Castryck-Decru），CSIDH 仍存活但被怀疑。

---

四、量子攻击对比

4.1 Shor (1994)

破：DLog, ECDLP, Factoring。多项式时间 $O((\log N)^3)$ in qubits + ops。

资源估计 (RSA-2048)：

• ~4000 logical qubits
• ~$10^9$ T-gates
• 估计 ~10 hours on fault-tolerant QC
• 当前最大量子机器：~1000 noisy qubits（IBM Condor 2023），距离巨大

4.2 Grover (1996)

对称密钥 / hash：根号加速。

• AES-128: $2^{128}$ → $2^{64}$（不安全）
• AES-256: $2^{256}$ → $2^{128}$（仍安全）
• SHA-256 抗 preimage: $2^{256}$ → $2^{128}$
• SHA-256 碰撞: $2^{128}$ → $2^{85}$ (BHT)

结论：对称密钥 / hash 加倍 size 即可量子安全。

4.3 LWE 量子攻击

最佳：BKZ-Q with quantum sieve，复杂度 $2^{0.265 n}$（vs 经典 $2^{0.292 n}$）。

含义：参数 $n=512$（Kyber-512）：

• 经典：$2^{150}$ 安全
• 量子：$2^{135}$ 安全
• 量子加速边际，参数无需大幅扩张

---

五、参数对比（128-bit 量子安全）

观察：

• Kyber/Dilithium 公钥比 RSA 小，但比 ECC 大 30×
• McEliece 公钥极大（>200 KB）但代码成熟
• SPHINCS+ 签名极大但仅基 hash 假设（最保守）

---

六、代码：LWE 玩具实现

"""
Day 193: LWE / SIS / 困难假设演示
玩具实现, 仅教学
"""
import numpy as np
from numpy.random import default_rng

rng = default_rng(42)


# ============ LWE 演示 ============
def lwe_keygen(n: int, m: int, q: int, sigma: float = 1.0):
    """LWE 公钥 = (A, b = As + e), 私钥 = s"""
    A = rng.integers(0, q, size=(m, n))
    s = rng.integers(0, q, size=n)
    e = np.round(rng.normal(0, sigma, size=m)).astype(int) % q
    b = (A @ s + e) % q
    return (A, b), s


def lwe_encrypt(pk, mu: int, q: int, sigma: float = 1.0):
    """简化加密 mu ∈ {0, 1}: c = (r^T A, r^T b + mu * q/2)"""
    A, b = pk
    m, n = A.shape
    r = rng.integers(0, 2, size=m)
    c1 = (r @ A) % q
    c2 = (r @ b + mu * (q // 2)) % q
    return c1, c2


def lwe_decrypt(sk, c, q: int):
    """解密 c2 - c1·s mod q, 离 0 近返回 0, 离 q/2 近返回 1"""
    c1, c2 = c
    v = (c2 - c1 @ sk) % q
    return 1 if abs(v - q // 2) < q // 4 else 0


# ============ SIS 演示 ============
def sis_problem(n: int, m: int, q: int, beta: int):
    """生成 SIS 实例: 找小 z, Az = 0 mod q"""
    A = rng.integers(0, q, size=(n, m))
    print(f"SIS: 找 z, ||z|| ≤ {beta}, Az = 0 mod {q}")
    print(f"  A 维度 {n}x{m}")
    # 朴素求解 (小规模可暴力)
    if m <= 6 and beta <= 3:
        for vec in np.ndindex(*([2 * beta + 1] * m)):
            z = np.array(vec) - beta
            if np.linalg.norm(z) <= beta and np.all(z == 0):
                continue
            if np.all((A @ z) % q == 0):
                return z
    return None


# ============ 演示 ============
if __name__ == "__main__":
    # LWE 加解密
    n, m, q = 16, 32, 257
    pk, sk = lwe_keygen(n, m, q, sigma=1.0)

    correct = 0
    trials = 100
    for _ in range(trials):
        mu = rng.integers(0, 2)
        c = lwe_encrypt(pk, int(mu), q)
        mu_dec = lwe_decrypt(sk, c, q)
        if mu == mu_dec: correct += 1
    print(f"LWE 玩具加密 正确率: {correct}/{trials}")

    # SIS 小例
    print()
    z = sis_problem(2, 4, 5, 2)
    print(f"SIS 解: z = {z}")

    # 输出参数表
    print("\n=== 后量子参数对比 (128-bit) ===")
    print(f"{'Scheme':<20} {'PK':>8} {'SK':>8} {'CT/Sig':>8}")
    print(f"{'RSA-3072':<20} {'384':>8} {'384':>8} {'384':>8}")
    print(f"{'ECDH-256':<20} {'32':>8} {'32':>8} {'64':>8}")
    print(f"{'Kyber-512':<20} {'800':>8} {'1632':>8} {'768':>8}")
    print(f"{'Dilithium-2':<20} {'1312':>8} {'2528':>8} {'2420':>8}")
    print(f"{'Falcon-512':<20} {'897':>8} {'1281':>8} {'666':>8}")
    print(f"{'SPHINCS+-128f':<20} {'32':>8} {'64':>8} {'17K':>8}")

---

七、详细对比表

7.1 各假设特点

7.2 NIST PQC 选定

Standardization (2024):

• KEM: ML-KEM (Kyber) — FIPS 203
• 签名:
  • ML-DSA (Dilithium) — FIPS 204 主推
  • SLH-DSA (SPHINCS+) — FIPS 205
  • FN-DSA (Falcon) — FIPS 206 待发

第二轮候选：HQC (code), Classic McEliece (备份), BIKE.

7.3 安全级别对应

---

八、密码学应用关联

8.1 ZK + PQ

主流 ZK (Plonk, Groth16) 用 BLS12-381 → Shor 易破。后量子 ZK：

• STARK：仅靠 hash + RS code，post-quantum
• Aurora / Plonky2：FRI-based, PQ
• lattice-based SNARK：如 LaBRADOR (2023), 实验性

8.2 区块链 PQ 迁移

• Ethereum：account abstraction 让钱包升级 PQC 签名（Dilithium, SPHINCS+）
• Bitcoin：Tap-PQ 提案，hybrid ECDSA + Dilithium
• 关键：长期密钥（multi-sig 冷钱包）今天就该考虑 hybrid

8.3 Harvest Now Decrypt Later (HNDL)

攻击者今天截获密文，存到量子机器可用之时（10-30 年）解密。对长期机密敏感数据（医疗、政府）今天就需要 PQC。

NSA 2022 公告：所有 NIST level 5 PQ 算法部署 by 2035。

---

九、真实参数

9.1 Kyber-768 (NIST level 3)

n = 256 (poly degree)
q = 3329
k = 3 (rank)
模 X^256 + 1
公钥 ~1184 bytes
密文 ~1088 bytes
KEM 时间 ~50 us (Intel)

9.2 Dilithium-3 (NIST level 3)

n = 256, q = 8380417
(k, l) = (6, 5)
γ_1 = 2^19, γ_2 = (q-1)/32
公钥 ~1952 bytes
签名 ~3293 bytes
签名时间 ~150 us (期望 4-5 次 reject sampling)

9.3 SPHINCS+-128f (NIST level 1)

hash = SHAKE256
tree height h = 66, layers d = 22
公钥 32 bytes (root + seed)
签名 ~17088 bytes ← 极大!
基于 Merkle few-time signatures

---

十、常见陷阱

1. "PQC 全部更安全"是错的：PQC 算法新，密码分析积累不足；可能未发现弱点。所以 hybrid（ECC + PQC 双签）是过渡稳健方案。
2. LWE 参数选择微妙：$n, q, \sigma$ 需精确平衡。错误小则攻击易；错误大则解密失败。Kyber 团队几次微调。
3. Falcon 浮点实现侧信道：Falcon 用浮点高斯采样，浮点泄露可恢复密钥。已有 fp-attack 实证。
4. SPHINCS+ stateless 重要性：相比 XMSS（stateful），SPHINCS+ 不需追踪 nonce，但签名大。状态丢失对 XMSS 致命。
5. MLWE vs RLWE 选择：MLWE 模块更"灵活"，RLWE 单一 polynomial ring。Kyber 用 MLWE 因 trade-off 更好。
6. Quantum-resistant ≠ Quantum-secure：抗经典量子算法不代表抗未发现的量子算法。NIST 选 lattice 是最佳猜测，非证明。
7. Isogeny SIDH 崩塌教训：2022 Castryck-Decru 数小时多项式破 SIKE。提醒新假设的脆弱。CSIDH 仍可用但参数需更大。

---

十一、关键速查

算法 → 假设 → 量子安全

---

十二、面试题

Q1: 为什么 NIST 选 Kyber 作为主 KEM？

答：综合考虑：

1. 性能：Kyber 加密/解密 < 100 us，KEM 大小 ~1KB，适合 TLS 集成
2. 安全证明：MLWE worst-case 归约严格，量子归约存在
3. 简洁性：基于 module-LWE，参数清晰，实现简单
4. 2022 NIST 第三轮选定：综合评估击败 NTRU、SABER、FrodoKEM
5. 生态：CRYSTALS 团队积极维护，开源参考实现

Q2: SPHINCS+ 签名为什么那么大？

答：SPHINCS+ 是 hash-based stateless 签名，结构：

• 底层：FORS (forest of random subsets)，few-time signature
• 中层：HORS / WOTS+ 一次性签名
• 顶层：Merkle tree，根是公钥

每次签名包含：

• WOTS+ chain authentication paths：每节点 32 bytes × ~$h$ 高度
• FORS proofs：~$k$ paths
• 总计：~$d \cdot h \cdot 32$ bytes ≈ 17 KB

代价大但仅靠 hash，最保守的 PQ 假设。

Q3: 解释 LWE 的"量子归约"是什么。

答：Regev 2005 证明：任何能解 LWE 平均情况的算法，可被用于解 worst-case lattice 问题（GapSVP_γ）。归约是量子算法（用了量子傅里叶变换）。

意义：

• 即使量子机器，攻击 LWE 等价于攻击最难的 lattice 实例
• 给 LWE 提供"量子-下界"安全保证
• 这是 LWE 优于其他 PQ 假设的核心原因

后续 Peikert 2009 给出经典归约（弱版本），让经典证明也成立。

Q4: SIDH 在 2022 怎么被破的？

答：Castryck-Decru (2022) 利用 SIDH 协议公开"辅助点"$P, Q$（attacker 看到 $P, \phi(P), Q, \phi(Q)$，$\phi$ 是秘密同源）。他们用 Kani 定理 (1997) 把 SIDH 关键步骤转为找 $(d_1, d_2)$ 满足 isogeny 复合方程，多项式时间求解。

教训：

• 公开过多结构信息（辅助点）让数学攻击成为可能
• CSIDH 不发辅助点，仍存活；但被怀疑是否最终也有结构性弱点
• 提醒新 PQ 假设需要更长密码分析时间

Q5: 区块链如何 PQ 升级？

答：渐进路径：

1. Stage 1 (现在)：增 PQ 实验合约（Eth research with Falcon precompile）
2. Stage 2 (~2030)：Account abstraction 让钱包选 PQ 签名（无需协议升级）
3. Stage 3 (~2032)：硬分叉支持 PQ opcode（Bitcoin Tap-PQ 提案）
4. Stage 4 (~2035, 量子威胁实质化)：禁用 ECDSA，强制 PQ 或 hybrid

关键问题：

• 已用过的地址（pubkey 暴露）量子破后资金被偷
• BIP-32 HD 钱包派生路径量子下危险
• 需要"silent PQ upgrade"机制：让用户主动 migrate 而不破坏 UX

---

十三、明日预告

Day 194: Week 29 复习 — 把 Day 188-193 的数论 / 多项式 / 信息论 / 复杂度 / 概率 / 困难假设全部整合，完成 Phase 4 数学基础最终笔记。

核心问题：拿这两周学的能否完整答出"为什么 Plonk 在 BLS12-381 上 128-bit 安全，Shor 后退化为 0-bit"？

参考文献：

• Regev, "On lattices, learning with errors, random linear codes, and cryptography", JACM 2009.
• Bos et al, "CRYSTALS-Kyber Algorithm Specifications", NIST PQC.
• Ducas et al, "CRYSTALS-Dilithium Algorithm Specifications", NIST PQC.
• Castryck & Decru, "An efficient key recovery attack on SIDH", EUROCRYPT 2023.
• NIST PQC standardization: https://csrc.nist.gov/Projects/post-quantum-cryptography