九思札记 · 探索区块链 · AI

如果量子计算会在 20 年后打破我们今天的密码学，那"后量子密码学"（Post-Quantum Cryptography, PQC）就是今天就要埋下的种子。NIST 已于 2024 年颁布首批后量子标准，公链的密码学迁移倒计时已经开始。

11.3.1 PQC 六大候选家族

量子计算不能击破所有数学问题。以下难题在量子时代仍然困难：

数学难题	代表方案	签名大小	公钥大小	主要应用
格问题（Lattice）	CRYSTALS-Dilithium, Falcon, Kyber	2-5 KB	1-3 KB	数字签名、KEM
哈希函数	SPHINCS+	8-41 KB	32 B	无状态签名
编码理论	Classic McEliece	128 B - 1 KB	261 KB	密钥封装
多变量方程	Rainbow（已破）	—	—	—
同源（Isogeny）	SIKE（已破）	—	—	—
零知识（哈希基）	zk-STARK	O(log² N)	无	可验证计算

NIST 在 2024 年标准化的三个核心方案：

ML-KEM（Kyber 的后继）：密钥封装机制（KEM）
ML-DSA（Dilithium 的后继）：数字签名
SLH-DSA（SPHINCS+ 的后继）：无状态哈希签名

11.3.2 格密码学：Module-LWE 与 Shortest Vector

为什么格问题是量子困难的？

格（Lattice）是一个离散的向量空间，由线性无关基向量的整数线性组合构成：

\mathcal{L} = \{ v \in \mathbb{Z}^n \mid v = B \mathbf{x}, \mathbf{x} \in \mathbb{Z}^n \}

其中 $B$ 是基矩阵。格上的核心难题：

最短向量问题（SVP）：在格中找到最短的非零向量
最近向量问题（CVP）：给定一点，找到格中最接近它的向量
Module-LWE：在带噪声的线性系统中恢复秘密

Module-LWE 问题

给定公开矩阵 $A \in R_q^{k \times n}$ 和向量 $b = A \cdot s + e$ ，其中 $s$ 是短秘密向量， $e$ 是小噪声向量：

b = A \cdot s + e \mod q

找到 $s$ 。对于经典计算机，最佳攻击是 BKZ 格约化，需要指数时间。对于量子计算机，Grover 只能提供二次加速，时间复杂度仍然是亚指数级：

T_{\text{quantum}} = O(2^{0.265n}) \quad \text{（远快于经典，但仍然是指数）}

Dilithium 签名机制

Dilithium 基于 Fiat-Shamir with Aborts 范式：

密钥生成： $(A, s_1, s_2)$ ，其中 $s_1, s_2$ 为短秘密向量
签名：生成临时向量 $y$ ，计算 $w = A \cdot y$ ，基于消息 $M$ 和 $w$ 创建挑战 $c = H(M \| w)$
签名： $z = y + c \cdot s_1$ （带有"abort"机制保证 $z$ 的分布安全）
验证：检查 $z$ 足够短且 $A \cdot z - c \cdot t \approx H(M \| w)$

核心安全保证：如果可以在不知道 $s_1$ 的情况下伪造签名，那么就可以解决 Module-LWE ——这在量子下至今无解。

typescript

/**
 * 格密码学核心操作简化模拟
 * 展示 Module-LWE 的矩阵-向量运算和短向量检查
 */
function modQ(n: bigint, Q: bigint): bigint {
  return ((n % Q) + Q) % Q;
}

function vectorAdd(a: bigint[], b: bigint[], Q: bigint): bigint[] {
  return a.map((v, i) => modQ(v + b[i], Q));
}

function matrixVectorMul(M: bigint[][], v: bigint[], Q: bigint): bigint[] {
  return M.map(row => modQ(row.reduce((s, mij, j) => s + mij * v[j], 0n), Q));
}

/**
 * 小模数示例：真实 Dilithium 使用 n=256, q=8380417, k=6, l=5
 * 这里用 n=4 演示核心数学
 */
interface LWEKey {
  A: bigint[][];    // 公开矩阵
  s: bigint[];      // 短秘密向量
  b: bigint[];      // 公开: A*s + e
  q: bigint;
}

function generateLWEKey(n: number, q: bigint): LWEKey {
  // 生成随机短秘密 s（真实中来自中心化二项分布）
  const s = Array.from({ length: n }, () => modQ(BigInt(Math.floor(Math.random() * 3) - 1), q));
  // 随机矩阵 A
  const A = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => modQ(BigInt(Math.floor(Math.random() * Number(q))), q))
  );
  // 小噪声 e
  const e = Array.from({ length: n }, () => modQ(BigInt(Math.floor(Math.random() * 3) - 1), q));
  const b = vectorAdd(matrixVectorMul(A, s, q), e, q);
  return { A, s, b, q };
}

function lweSampleEncrypt(
  key: LWEKey,
  messageBit: 0 | 1,
  errorBound: bigint,
): { u: bigint[]; v: bigint } {
  // 加密：随机短向量 r, 计算 u = A^T*r, v = b^T*r + m*q/2 + e'
  const r = Array.from({ length: key.s.length }, () => modQ(BigInt(Math.floor(Math.random() * 3) - 1), key.q));
  const u = matrixVectorMul(key.A.map((_, i) => key.A.map(row => row[i]), key.q), r, key.q);
  const v = modQ(
    u.reduce((s, ui, i) => s + ui * r[i], 0n) + (messageBit === 1 ? key.q / 2n : 0n),
    key.q,
  );
  return { u, v };
}

function lweSampleDecrypt(
  key: LWEKey,
  cipher: { u: bigint[]; v: bigint },
): 0 | 1 {
  const sTu = key.s.reduce((s, si, i) => s + si * cipher.u[i], 0n);
  const diff = modQ(cipher.v - sTu, key.q);
  // 如果 v ≈ q/2 (消息=1), diff ≈ q/2; 否则 ≈ 0
  return Number(diff > key.q / 4n && diff < (3n * key.q) / 4n) as 0 | 1;
}

// --- 演示 ---
const Q_demo = 17n;  // 小质数便于观察
const n4 = 4;
const key4 = generateLWEKey(n4, Q_demo);
const enc0 = lweSampleEncrypt(key4, 0, 1n);
const enc1 = lweSampleEncrypt(key4, 1, 1n);
console.log("bit=0 解密:", lweSampleDecrypt(key4, enc0)); // 应输出 0
console.log("bit=1 解密:", lweSampleDecrypt(key4, enc1)); // 应输出 1
console.log("秘密向量 s:", key4.s); // 短向量，值小
console.log("公钥 b = A*s+e mod 17:", key4.b); // 表面随机

11.3.3 哈希签名：SPHINCS+ 极简原理

如果格密码出了问题，SPHINCS+ 是最后的数学堡垒——它只依赖哈希函数（抗碰撞）。

无状态哈希签名核心思路

SPHINCS+ 使用大量一次性 WOTS 密钥，通过 Merkle 树和超树结构将它们聚合为单个公钥：

底层： $2^{64}$ 个 WOTS 一次性签名密钥对
中间层：Merkle 树聚合层
顶层：FORST（Few-Time Signature）用于压缩

实际密钥看起来像：

\text{公钥} = H(\text{seed}) \quad \text{（仅 32 字节！）}

但单次签名大小：~8 KB（SPHINCS+-128f）到 41 KB（SPHINCS+-256s），每个签名需要数百次哈希计算。

这对于高频交易是灾难性的，但对于可信设置仪式、后量子备份、多重签名一方等低频安全场景是可接受的。

11.3.4 公链迁移路径

比特币的保守路线

比特币开发文化极度保守。预计路径：

软分叉添加后量子地址格式（如 BIP-360 风格）
新地址使用 ML-DSA 签名
旧 UTXO 用户在量子威胁迫近前主动迁移到后量子地址
若用户不迁移，资产将面临"先收集、后解密"攻击

以太坊的激进路线

以太坊基金会已资助多个预研究：

预编译合约中的 Dilithium 验证
账户抽象（EIP-4337）允许签名方案升级
长期目标：原生支持混合签名（后量子 + 经典过渡）

mindmap
  root((PQC 迁移路线))
    比特币
      软分叉
      新地址格式
      用户自主迁移
      保守但安全
    以太坊
      账户抽象
      预编译 Dilithium
      激进实验
      智能合约层优先
    通用挑战
      密钥尺寸膨胀 10-100x
      签名尺寸膨胀 10-50x
      链上存储成本
      验证 Gas 成本

> ← 上一节：11.2 量子计算威胁 | 前往 → 11.4 区块链量子迁移路线 |*

本页目录