2017 - 後量子密碼學#

案件摘要#

2017 年，美國 NIST 啟動後量子密碼學（PQC）標準化競賽：公開徵求能抵抗量子電腦攻擊的公鑰密碼演算法——因為 Shor 演算法（1994，見 1994-Shor演算法.md）在量子模型下多項式時間破解 RSA 與 ECC。2024 年結果揭曉：ML-KEM（Kyber，格密碼）、ML-DSA（Dilithium，格簽章）、SLH-DSA（SPHINCS+，雜湊簽章）勝出——整個現代公鑰密碼（RSA、ECC、DH）需要全面遷移，這是密碼學史上最大的工程換血。

前因 -- 為什麼會有這個案子#

雙重威脅：

Shor 演算法的死刑：量子電腦多項式時間分解大數、解離散對數——RSA（見 1977-RSA.md）、ECC（見 2005-橢圓曲線密碼學.md）、DH（見 1976-DiffieHellman金鑰交換.md）全部失效
先存後解（harvest now, decrypt later）：情報機構今天錄下密文，等量子電腦問世再解——需要今天就換（機密資料要保密 20 年以上）

現實壓力： - 2016 年 NSA 宣布「準備遷移到後量子密碼」 - 2019 年 Google 的量子霸權（Sycamore，53 位元）示範量子優勢 - 2020s 量子電腦從學術走向工程（IBM、Google、Quantinuum 的糾錯位元數競賽）

NIST 的決策：公開競賽（照抄 AES 競賽模式，見 2001-AES.md）——69 個提案，公開攻擊，多輪篩選。

線索與推理 -- 數學式、程式、理論#

格密碼：新的難解問題#

格（lattice）： \(n\) 維空間中向量 \(\{v_1, \dots, v_n\}\) 的整係數組合：

\[ \mathcal{L} = \{a_1 v_1 + a_2 v_2 + \dots + a_n v_n : a_i \in \mathbb{Z}\} \]

兩個難解問題：

最短向量問題（SVP）：找格中最短非零向量——LLL 演算法（1982，見 1979-MerkleHellman背包密碼.md）只能近似，高維精確解被認為指數難
帶誤差學習（LWE, Learning with Errors）（Regev 2005）：

\[ \text{給定 } (A, b = A \cdot s + e) \text{，求秘密 } s \]

其中 \(A\) 是隨機矩陣、 \(e\) 是小誤差向量——「解線性方程組 + 噪音」：沒有噪音 \(e\) 是線性代數（容易），加上噪音後被認為難。

定理（Regev 2005）：LWE 的平均難度可規約到格問題的最壞難度——Merkle–Hellman 的教訓（見 1979-MerkleHellman背包密碼.md）被正面解決：LWE 是第一個有平均-最壞規約的密碼學難解問題。

Kyber（ML-KEM）：格金鑰封裝#

ML-KEM（原 Kyber）：模格上的 LWE 金鑰封裝機制（KEM，key encapsulation mechanism）：

金鑰封裝（KEM ≈ Diffie–Hellman 的現代化）：

封裝方：隨機 \(s\) （秘密向量）、噪音 \(e\) ，公開公鑰 \((A, b = As + e)\)
封裝共享秘密 \(K\) 為密文 \((u, v)\) ： \(u = A^T r + e_1\) 、 \(v = b^T r + e_2 + \text{encode}(K)\)
解封裝（私鑰 \(s\) ）： \(v - s^T u \approx \text{encode}(K)\) （噪音抵消）

安全性：LWE 難——Shor 演算法無效（格問題沒有已知的量子多項式算法）。

效率：公鑰 1184 位元（Level 1，≈ AES-128 安全）——比 RSA-3072（384 位元組）小、封裝運算比 RSA 快數倍。已進入 TLS 1.3 的 hybrid 模式（Chrome 2024、Apple 2024——X25519+ML-KEM）。

SPHINCS+（SLH-DSA）：雜湊簽章#

雜湊簽章（hash-based signatures）：唯一被數學證明安全的簽章——安全性只依賴雜湊函數的單向性（見 1985-密碼學雜湊函數.md），不依賴任何未證明的難解假設。

Lamport 簽章（1979，雜湊簽章的鼻祖）：

私鑰： \(2b\) 個隨機數 \(x_{i,0}, x_{i,1}\)
公鑰： \(2b\) 個雜湊 \(H(x_{i,0}), H(x_{i,1})\)
簽訊息位元 \(m_i\) ：簽章包含 \(x_{i, m_i}\) ——只洩漏一半

缺點：簽章巨大（ \(2b \times n\) 位元）。SPHINCS+：Merkle 樹（見 1985-密碼學雜湊函數.md）壓縮公鑰，狀態無關（stateless）——唯一被「完全證明」的後量子簽章（若雜湊安全，則簽章安全——無條件的安全基礎）。

程式碼：LWE 與格密碼的概念#

import random

def lwe_keygen(n=8, q=97):
    """LWE：公開 (A, b = A·s + e)，秘密 s"""
    A = [[random.randint(0, q-1) for _ in range(n)] for _ in range(n)]
    s = [random.randint(0, q-1) for _ in range(n)]       # 秘密
    e = [random.randint(-2, 2) for _ in range(n)]        # 小噪音！
    b = [sum(A[i][j] * s[j] for j in range(n)) % q for i in range(n)]
    b = [(b[i] + e[i]) % q for i in range(n)]
    return A, b, s

random.seed(42)
A, b, s = lwe_keygen()
print(f"LWE 公鑰 b = {b}")
print(f"秘密 s = {s}（噪音 e 使 A·s + e 難反推 s）")
# 無噪音 e：解線性方程組（Gaussian 消去）容易
# 有噪音：被認為難（Regev 2005：平均難度 = 最壞格問題難度）
# 量子攻擊：未知有效算法——Shor 演算法無效 ✓

NIST 競賽的結果（2024）#

69 個提案 → 26 個進入第二輪 → 7 個進入第三輪 → 4 個標準化：

標準	原名	類型	數學基礎
ML-KEM（FIPS 203）	Kyber	金鑰封裝	模格 LWE
ML-DSA（FIPS 204）	Dilithium	簽章	模格 LWE
SLH-DSA（FIPS 205）	SPHINCS+	簽章	雜湊（無條件安全）
FN-DSA（FIPS 206，草案）	Falcon	簽章	格 NTRU

2024 年的 hybrid 模式：Chrome、Firefox、Apple、Cloudflare、Google 全部部署 X25519 + ML-KEM 的 hybrid 金鑰交換——新舊並用（若舊的被破或新的有隱藏缺陷，另一半仍安全）。

遷移的工程挑戰： - 憑證變大：ECC 憑證 ~64 位元組 → ML-DSA 簽章 ~2420 位元組——TLS 握手變大 - 演算法替換：所有 RSA/ECC 程式碼需要替換——20 年工程債 - 雜湊簽章的短處：SLH-DSA 簽章巨大（~8KB）——不適合 TLS，適合軟體簽章

偵探筆記：後量子密碼學的推理是「新的數學，舊的原則」——難解問題從分解/離散對數換成格/雜湊，但 Kerckhoffs 原則（見 1883-Kerckhoffs原則.md）、公開競賽（見 2001-AES.md）、證明式安全（見 1989-零知識證明.md）的原則全部保留。LWE 是 Merkle–Hellman 失敗的正面教訓：同樣用格問題，但這次有平均-最壞規約的證明。

結案 -- 後果與影響#

密碼學史上最大換血：RSA/ECC → ML-KEM/ML-DSA——20 年的全球遷移工程。
2024 hybrid 部署：Chrome、Apple、Cloudflare 已部署 X25519+ML-KEM——今天就開始（先存後解的威脅）。
LWE 的地位：第一個有平均-最壞規約的密碼學難解問題——密碼學理論的新基石。
格密碼的帝國：Kyber、Dilithium、Falcon、NTRU——格問題從「破解工具」（LLL 破背包，見 1979-MerkleHellman背包密碼.md）變成「密碼基礎」。
FHE 的基礎：格密碼也是全同態加密（見 2009-全同態加密.md）的數學基礎——一個數學結構同時承擔後量子與同態。
現實的賽跑：量子電腦的糾錯位元數 vs 密碼遷移的速度——誰先到終點？（2024 年估計：RSA-2048 分解需 2000 萬物理位元，仍遠；但遷移需要 20 年。）

關鍵人物與文獻#

Oded Regev（1975–）：LWE (2005)——格密碼的理論基礎；2024 年 Gödel 獎
NIST：PQC 競賽 (2017–2024)、FIPS 203/204/205
Peter Schwabe 等：Kyber/Dilithium 團隊
Daniel J. Bernstein 等：SPHINCS+ 團隊
Craig Gentry：理想格上的 FHE (2009)——格密碼的先驅
NSA：2016 年宣布後量子遷移
交叉參照：1994-Shor演算法.md、1979-MerkleHellman背包密碼.md、2001-AES.md、2009-全同態加密.md、1985-密碼學雜湊函數.md