第 10 章 彼得·秀爾與格羅弗：量子演算法對古典計算複雜度的降維打擊#
10.3 後量子密碼學（PQC）：當量子電腦即將降臨，密碼學家集體設計抗量子密碼的生死賽跑#
10.3.1 NIST 的十二馬拉松（2016–2024）#
2016 年，NIST（美國國家標準技術研究院）啟動後量子密碼標準化公開競賽：82 個初始提案、多輪公開破解淘汰、全球密碼學家互為攻防。2022 年 7 月公布入選，2024 年 8 月正式發布標準：
| 標準 | 算法 | 數學難題 |
|---|---|---|
| FIPS 203 | ML-KEM（Kyber 系） | Module 格上的 LWE |
| FIPS 204 | ML-DSA（Dilithium 系） | 格的 SIS／Fiat–Shamir |
| FIPS 205 | SLH-DSA（SPHINCS+） | 哈希函數（無結構假設） |
淘汰劇同樣重要：Rainbow（多變量）2022 年被 Beullens 以筆記本級攻擊破解；SIKE（同源密碼）2022 年被 Castryck–Decru 摧毀——公開競賽的「破解即篩選」機制證明了其價值。
10.3.2 格密碼的數學根基#
格（lattice）上最短向量問題（SVP）／帶誤差學習（LWE，Regev 2005）被認為連量子算法也難（無 Shor 式週期結構可利用）。附加紅利：FHE（全同態加密，Gentry 2009 起源於格）也以格為地基——後量子與「加密下計算」兩大前沿在此匯流。
10.3.3 「先錄後解」（Harvest Now, Decrypt Later）與真實遷移#
密碼學家的最急迫論證：政府與企業今天截存的加密流量，可在未來量子機成熟後回溯解密。遷移進度（截至 2025 的真實狀態）：
- 2023 起 Signal、Apple iMessage（PQXDH）、Chrome/Cloudflare 的 Kyber（X25519Kyber768）開始混合部署；
- 2024–25 年，NIST 遷移指南、NSA CNSA 2.0 時間表要求 2030s 前完成；
- 挑戰：簽章尺寸（ML-DSA 約 2–4 KB 對比 ECDSA 約 64 B）對協議與硬體的連鎖改動。
10.3.4 前因後果#
- 前因：10.1 的 Shor 威脅＋格理論（LLL 1982 起）＋公開標準化制度。
- 事件：2016 競賽啟動、2022 入選、2024 標準發布。
- 後果：密碼學進入雙軌時代（傳統＋PQC 混合）；本書三千年歷史的最後一課在此浮現——每當計算能力躍遷（紙筆→機械→電子→量子），人類就以新的演算法重鑄信任的鎖。