后量子签名 — Lattice/Hash/NIST PQC

日期: 2026-11-23 方向: 密码学 / 经典原语 阶段: Phase 4 - 经典密码学 (Day 195-208) 标签: #密码学 #后量子 #Dilithium #Falcon #SPHINCS

---

今日目标

---

一、为什么需要后量子？

1.1 量子算法威胁

• Shor 算法 (1994): 多项式时间分解整数 + 解 ECDLP → RSA / ECC / DSA / Schnorr / BLS / KZG 全破
• Grover 算法: 把对称/哈希原像复杂度 $2^n$ 减到 $2^{n/2}$ → 安全减半但仍可挽救（升级到 256-bit）

1.2 量子计算机进展（2026 状态）

1.3 "Harvest Now, Decrypt Later"

NSA / 中国情报机构等可能现在收集加密数据，等 30 年后量子破解。Web3 长期 vault 必须 PQ-safe.

1.4 时间表

• 2016: NIST PQC competition 启动
• 2022: Round 3 选定 4 个 (Kyber, Dilithium, Falcon, SPHINCS+)
• 2024: FIPS 203 (Kyber → ML-KEM), FIPS 204 (Dilithium → ML-DSA), FIPS 205 (SPHINCS+ → SLH-DSA) 发布
• 2025: Falcon → FN-DSA (FIPS 206) finalized
• 2030: NIST 计划禁用 RSA-2048 / ECDSA-256

---

二、Lattice 困难问题

2.1 LWE (Learning With Errors)

给定 $A \in \mathbb{Z}_q^{n \times m}$, $\vec{s} \in \mathbb{Z}_q^n$, $\vec{e}$ 小 noise，知 $\vec b = A^T \vec s + \vec e$，难恢复 $\vec s$.

直觉: 解线性方程组 $A^T \vec s = \vec b$ 容易，但加噪声 $\vec e$ 后变难（高斯消元放大噪声）。

2.2 SIS (Short Integer Solution)

给定 $A \in \mathbb{Z}_q^{n \times m}$，找短向量 $\vec z$ s.t. $A \vec z = 0 \pmod q$, $|\vec z| \le \beta$.

用途: 哈希函数 (Ajtai 1996), 签名 (Dilithium)

2.3 Module-LWE / Module-LSIS

把 vector over $\mathbb{Z}_q$ 替换为 vector over polynomial ring $R_q = \mathbb{Z}_q[X]/(X^n + 1)$ — 引入代数结构。

优势: 同等安全下密钥/签名更小 (~10×)。劣势: 部分代数攻击可能更有效。

2.4 NTRU

环 $R = \mathbb{Z}[X]/(X^n - 1)$. 私钥 $f, g \in R$ 短系数，公钥 $h = g/f \pmod q$.

Falcon 用 NTRU lattice + 高斯采样.

---

三、ML-DSA (Dilithium)

3.1 数学

基于 Module-LWE + Module-SIS.

密钥生成:

• $A \in R_q^{k \times \ell}$ random
• $\vec{s_1} \in R_q^\ell, \vec{s_2} \in R_q^k$ small (uniform from ${-\eta, ..., \eta}$)
• $\vec t = A \vec{s_1} + \vec{s_2}$
• $pk = (A, \vec t)$, $sk = (\vec{s_1}, \vec{s_2})$

签名 (Fiat-Shamir 风格):

1. 选 $\vec{y}$ small mask
2. $\vec{w} = A \vec{y}$
3. $c = H(\vec{w}, m)$ (challenge)
4. $\vec{z} = \vec{y} + c \vec{s_1}$
5. 检查 $\vec z$ 范数 + reject sampling 防泄漏 → 重试
6. 输出 $(c, \vec z)$

验证: $\vec{w}' = A \vec z - c \vec t$, 验 $H(\vec{w}', m) = c$ + 范数检查.

3.2 参数

3.3 优劣

• ✓ 简单实现（仅整数运算 + sample uniform）
• ✓ 参数透明，安全裕度大
• ✗ 签名巨大 (2.4 KB vs ECDSA 64 B)
• ✗ Sign 慢（reject sampling 可能多次重试）

---

四、FN-DSA (Falcon)

4.1 数学

基于 NTRU + 高斯采样 (Hash-and-Sign 范式).

密钥生成:

• 选短 $f, g \in R$ 满足 $f g \equiv 1 \pmod q$ in some sense
• 公钥 $h = g/f$
• 私钥 = NTRU trapdoor (允许高斯采样在 lattice 中)

签名:

1. 哈希 $m$ 到 lattice 点 $c$
2. 用 trapdoor 找最近 lattice 点 $\vec v$ (高斯)
3. 签名 = $\vec v - c$ (短)

验证: 检查 $|\sigma| \le \beta$ + $\sigma + c$ 在 lattice 中.

4.2 参数

4.3 优劣

• ✓ 签名相对小（PQ 标准下）
• ✓ 验证快
• ✗ 签名实现复杂（高斯采样 + 浮点运算 → 侧信道困难）
• ✗ 不易抗故障攻击

---

五、SLH-DSA (SPHINCS+)

5.1 设计 — 纯 Hash-based

只依赖 hash 抗碰撞 + 抗原像（量子下安全度减半）。

结构: 多层 Merkle 树 + Few-Time Signature (FORS) + Winternitz One-Time Signature (WOTS+).

5.2 工作原理

1. Master public key = root of "hyper-tree"
2. 签名时随机选 leaf → 用 leaf 的 OTS 签 message
3. • Merkle proof from leaf to root

每 leaf 的 OTS 只能用一次 → 用伪随机 derivation 保证不重复（"stateless"）。

5.3 参数

5.4 优劣

• ✓ 安全假设极保守（仅 hash）
• ✓ pk 小（32 B!）
• ✗ 签名极大（8 KB+）
• ✗ 签名慢（sec 量级）
• ✓ 真正后量子（无 lattice 假设破）

---

六、Hash-based State-ful (XMSS / LMS)

6.1 概念

预先生成 $2^h$ 个 OTS 密钥对，组织成 Merkle 树。每签名:

• 用下一未用 OTS（state 增加）
• 提供 inclusion proof to Merkle root

6.2 状态管理风险

致命陷阱: 若 OTS 私钥被使用 2 次 → 私钥暴露。

State 需要安全持久化：

• HSM 内强制单调计数器
• 备份恢复 = 灾难（恢复用旧 state → 重用 OTS）

→ XMSS / LMS 仅用于嵌入式 / 固件签名（可控环境）。

6.3 RFC 标准

• RFC 8391: XMSS
• RFC 8554: LMS (NIST 推荐用于固件)

---

七、代码示例

"""
pqc_demo.py - 用 pqcrypto / oqs 库测试 NIST PQC 签名
pip install pqcrypto liboqs-python
"""
import time
import os

# Approach 1: pqcrypto (Python wrapper)
try:
    from pqcrypto.sign import dilithium2 as ml_dsa_44
    sk, pk = ml_dsa_44.generate_keypair()
    msg = b"PQC test"

    t0 = time.time()
    sig = ml_dsa_44.sign(msg, sk)
    t1 = time.time()
    valid = ml_dsa_44.verify(msg, sig, pk)
    t2 = time.time()

    print(f"ML-DSA-44 (Dilithium 2):")
    print(f"  pk size:   {len(pk)} bytes")
    print(f"  sig size:  {len(sig)} bytes")
    print(f"  sign:      {(t1-t0)*1000:.1f} ms")
    print(f"  verify:    {(t2-t1)*1000:.1f} ms")
    print(f"  valid:     {valid}")
except ImportError:
    print("pqcrypto not installed. pip install pqcrypto")

# Approach 2: liboqs (Open Quantum Safe)
try:
    import oqs
    with oqs.Signature("Dilithium2") as signer:
        pk = signer.generate_keypair()
        sig = signer.sign(b"hello PQ")
        with oqs.Signature("Dilithium2") as verifier:
            valid = verifier.verify(b"hello PQ", sig, pk)
            print(f"\nliboqs Dilithium2: valid = {valid}")

    # Compare schemes
    schemes = [
        "Dilithium2", "Dilithium3", "Dilithium5",
        "Falcon-512", "Falcon-1024",
        "SPHINCS+-SHA2-128f-simple", "SPHINCS+-SHA2-128s-simple",
    ]
    print("\nNIST PQC signature benchmark:")
    print(f"{'Scheme':30} {'pk':>6} {'sig':>8} {'sign':>8} {'verify':>8}")
    for s in schemes:
        try:
            with oqs.Signature(s) as sig_obj:
                pk = sig_obj.generate_keypair()
                t0 = time.time()
                sig = sig_obj.sign(b"benchmark")
                t1 = time.time()
                with oqs.Signature(s) as v:
                    v.verify(b"benchmark", sig, pk)
                t2 = time.time()
            print(f"{s:30} {len(pk):>6} {len(sig):>8} {(t1-t0)*1000:>6.1f}ms {(t2-t1)*1000:>6.1f}ms")
        except Exception as e:
            print(f"{s:30} ERROR: {e}")
except ImportError:
    print("liboqs not installed: pip install liboqs-python")

预期输出（Skylake @ 3.4 GHz）:

Scheme                            pk      sig    sign  verify
Dilithium2                      1312     2420   0.5ms   0.2ms
Dilithium3                      1952     3293   0.8ms   0.3ms
Dilithium5                      2592     4595   1.2ms   0.4ms
Falcon-512                       897      666   8.5ms   0.1ms
Falcon-1024                     1793     1280  18.0ms   0.2ms
SPHINCS+-SHA2-128f-simple         32    17088   7.0ms   1.5ms
SPHINCS+-SHA2-128s-simple         32     7856 200.0ms   1.0ms

---

八、Web3 后量子路线

8.1 区块链 PQ 挑战

8.2 项目动向

8.3 Hybrid 签名

过渡期方案: $\sigma = (\sigma_{\text{ECDSA}}, \sigma_{\text{Dilithium}})$, 验证两者都通过.

• 经典安全期: ECDSA 防侧信道 + small
• 量子时代: Dilithium 兜底
• 代价: 签名 ~2.5 KB, gas 成本翻倍

8.4 ZK-Friendly PQ

ZK 协议下，验证大型 PQ 签名约束数极大 (Dilithium ~10M constraints)。

替代方案: Winternitz One-Time Signatures over hash function — 用 ZK-friendly hash (Poseidon)，签名小 (~1 KB) + 在 SNARK 内验证便宜。

但 stateful — 需 OTS 计数器追踪。

---

九、PQ 在 Web3 的路线图（推测）

2026-2030: Hybrid 兼容期
  - 钱包/交易所用 hybrid (ECDSA + Dilithium)
  - 长期 vault 用 SLH-DSA / XMSS

2030-2035: PQ 主导
  - 量子计算 logical qubit 突破 1000 → ECDSA 危
  - 各链 hard fork 强制 PQ
  - Eth: smart account 自由切换
  
2035+:  Pure PQ
  - ECDSA 仅历史遗产
  - ZK-friendly Winternitz 主流

---

十、常见陷阱

1. 直接替换签名算法不够: 需重做 Merkle / commitment / KEM 全栈
2. Hybrid 顺序: 先验 PQ 还是先验 ECDSA？影响安全证明
3. State management: XMSS 状态备份 = 私钥泄漏风险
4. Side channel: Falcon 浮点 + 高斯采样难抗 timing
5. Falcon implementation bugs: 浮点不确定性导致跨平台签名不一致
6. Lattice 参数选择不当: 安全余量不足
7. PQ 不是 forward secrecy 替代: 仍需 ratchet 协议
8. Quantum-safe ≠ 简单事: 需重新审计整个 stack

---

十一、对比表

---

十二、面试题

Q1: 为什么 Web3 还没有大规模 PQ 部署？ A: (1) 签名 > 10× 大 → block size / gas 影响巨大; (2) 量子计算尚未威胁主网（10-20 年窗口）; (3) NIST 标准 2024 才完成; (4) 需重做 Merkle / commitment / Schnorr 多签等周边设施; (5) 钱包用户密钥迁移 UX 极差。但 long-term vault（如 BTC 长期持仓）已有理由考虑 PQ-safe 时间锁。

Q2: Hybrid 签名的安全假设？ A: 安全度 = max(ECDSA, Dilithium) — 攻破二者中任何一个即破。所以 hybrid 更安全 (verify both)。代价: 双倍 sig size + 双倍 verify 时间。设计上必须用正确的 hybrid 形式 (concatenate + signed both)，不能 OR (signed either)。

Q3: 哪个 PQ 签名最适合区块链？ A: 取决于约束:

• 小 sig: Falcon-512 (666 B) → BTC/ETH 类
• 简单实现 + 安全裕度: Dilithium → 最稳
• 小 pk: SPHINCS+ (32B) → cold wallet / time-lock
• ZK-friendly: Winternitz over Poseidon → 未来 Eth
• 嵌入式: XMSS (state-ful) → IoT / firmware

Q4: 量子破 ECDSA 实战要多少 qubit？ A: 估算 (Roetteler-Naehrig 2017, Gidney-Ekera 2021):

• Logical qubits: ~2,300 for ECDLP-256
• Physical qubits (with surface code): ~20 million
• 时间: 8 hours (estimate)

2026 年最大: 120 logical qubits (Google Willow). 距破 ECC 还远（ 20,000× gap），但摩尔定律乐观下 15-20 年可能。

Q5: Eth 长期 PQ 路线？ A: 暂未定，但讨论方向:

1. Smart account 自由化 (ERC-4337): EOA 仍 ECDSA, smart account 可自选 PQ 签名 → 用户自愿迁移
2. Winternitz over Poseidon: ZK-friendly, sign 在电路内验证便宜 (~10k 约束 vs Dilithium ~10M)
3. Hybrid 共识: PoS validator 渐进引入 hybrid BLS+Dilithium
4. STARK 内部已 PQ: STARK 仅用 hash → 自然 PQ-safe，未来 Eth ZK-EVM 更适合 PQ

---

十三、明日预告

Day 207: 阈值签名 — 深入 FROST (Schnorr 阈值, RFC 9591) 和 GG18/GG20 (ECDSA 阈值)。理解 DKG 与多方签名协议在 MPC 钱包/跨链桥的应用。