前面各章聚焦於今日的密碼學，本章則檢視密碼學在一個世紀以上的時間尺度上的未來——一個量子電腦存在的未來。

量子電腦是利用量子物理現象、來執行與我們所習慣者不同種類演算法的電腦。

量子電腦尚不存在，而且看起來非常難打造。但若有一天它們真的存在，它們就有潛力攻破 RSA、Diffie–Hellman 與橢圓曲線密碼學——也就是本書寫作時所有已部署或已標準化的公鑰密碼學。

為了為量子電腦帶來的風險投保，密碼學研究者已開發出能抵抗量子電腦的替代公鑰演算法，稱為後量子演算法。

  • 2015 年：NSA 呼籲轉向「即使面對量子電腦也安全」的抗量子演算法。
  • 2017 年：美國標準化機構 NIST 啟動了一個最終將標準化後量子演算法的流程。

本章脈絡#

  1. 量子電腦如何運作——qubit、疊加、糾纏、量子閘。
  2. 量子加速——Simon 問題、Shor 演算法（公鑰密碼學的殺手）、Grover 演算法。
  3. 為何量子電腦難以打造——脆弱的 qubit、極低溫、糾錯的難題。
  4. 後量子密碼演算法——基於編碼、基於格、多變數、基於雜湊。

常見錯誤#

後量子密碼學可能從根本上比 RSA 或橢圓曲線密碼學更強，但它並非萬無一失、也非無所不能。

我們對後量子方案及其實作之安全性的理解，比對非後量子密碼學的理解更有限，這帶來了增加的風險。

安全等級不明#

後量子方案可能看起來強得騙人，卻對量子與古典攻擊都不安全。

基於格的演算法——例如 ring-LWE 這一族計算問題（在多項式上運作的 LWE 問題版本）——有時就有問題。

Ring-LWE 對密碼學家很有吸引力，因為它能被用來建構「原則上與求解 Ring-LWE 問題最難實例一樣難破解」的密碼系統，而那些實例可以是 NP-hard 的。

但當安全性看起來好到不像真的，它往往就不是真的。

安全性證明的問題之一是：

然而實務上使用的參數數量小得多。

即使一個基於格的方案看起來與某個 NP-hard 問題一樣難破解，它的安全性仍然難以量化。

就基於格的演算法而言，由於我們對這些較新建構缺乏理解，我們很少能清楚掌握針對它們的最佳攻擊、以及該攻擊在計算或硬體上的成本。

這種不確定性讓基於格的方案更難與 RSA 這類被充分理解的建構比較，也嚇跑了潛在使用者。

不過研究者在這方面一直有進展，希望再過幾年，格問題能像 RSA 一樣被充分理解。

關於 Ring-LWE 問題更多技術細節，可讀 Peikert 的優秀綜述：https://eprint.iacr.org/2016/351/ ↗。

快轉：如果來不及了會怎樣#

想像一則 CNN 頭條：2048 年 4 月 2 日：「ACME 公司揭露其秘密打造的量子電腦，推出『破解密碼即服務』平台。」

好，RSA 與橢圓曲線密碼學完蛋了。然後呢？

簽章的情況：

若你仍在用 RSA-PSS 或 ECDSA 當簽章方案，你只要用後量子簽章方案重新簽發簽章來恢復簽章的信任即可。

你會撤銷較舊、不抗量子的公鑰，並為你簽署過的每則訊息重新計算簽章。忙一陣子之後，你就沒事了。

加密的情況：

這種情況下，所有傳輸過的密文都可能被攻破。顯然，此時再用後量子演算法重新加密那些明文已經沒有意義——你的資料機密性早就沒了。

金鑰協商的情況（DH 與 ECDH）：

乍看之下，情況似乎與加密一樣糟：蒐集了公鑰 g^a 與 g^b 的攻擊者，可以用他們閃亮的新量子電腦算出秘密指數 a 或 b、算出共享秘密 g^ab，再從中導出用來加密你流量的金鑰。

用來加密你資料的實際工作階段金鑰，可能是同時從 DH 共享秘密與你系統的某些內部狀態導出的。

例如最先進的行動訊息系統就是這麼運作的——這要歸功於 Signal 應用所開創的協定：當你用 Signal 送出一則新訊息給對方時，會計算一個新的 DH 共享秘密，並與依賴該工作階段先前所送訊息的某些內部秘密結合（該工作階段可能橫跨很長的時間）。

這種進階的 DH 用法讓攻擊者的工作困難得多——即使他有量子電腦。

實作問題#

實務上，後量子方案會是程式碼而非演算法——也就是跑在某個實體處理器上的軟體。

無論演算法在紙上多強，它們都不會對實作錯誤、軟體 bug 或旁道攻擊免疫。

一個演算法可能在理論上完全抗量子，卻仍被一支簡單的古典電腦程式攻破——只因為程式設計師忘了打一個分號。

此外，基於編碼與基於格的演算法高度依賴數學運算，其實作使用各種技巧來讓那些運算盡可能快。

但同樣地，這些演算法程式碼的複雜度讓實作更容易受旁道攻擊——例如根據執行時間的測量來推斷秘密值資訊的時序攻擊。

事實上，這類攻擊已經被套用到基於編碼的加密（https://eprint.iacr.org/2010/479/ ↗）與基於格的簽章方案（https://eprint.iacr.org/2016/300/ ↗）上。

延伸閱讀#

  • 量子計算基礎：Nielsen 與 Chuang 的經典《Quantum Computation and Quantum Information》（Cambridge, 2000）。
  • 較不技術性、更有趣的讀物：Aaronson 的《Quantum Computing Since Democritus》（Cambridge, 2013），涵蓋的不只是量子計算。
  • 軟體模擬器：好幾個模擬器能讓你實驗量子計算。Quantum Computing Playground（http://www.quantumplayground.net/ ↗）設計得特別好，有簡單的程式語言與直觀的視覺化。
  • 後量子密碼學的最新研究：https://pqcrypto.org/ ↗ 與相關的 PQCrypto 研討會。

接下來幾年對後量子密碼學來說會特別令人興奮，這要歸功於 NIST 的後量子密碼專案——一項發展未來後量子標準的社群努力。

記得查閱專案網站以取得相關演算法、研究論文與工作坊資訊：http://csrc.nist.gov/groups/ST/post-quantum-crypto/ ↗。

Backward TLS 安全性的強項 量子電腦如何運作 Forward