後量子密碼學這個領域，是關於設計無法被量子電腦攻破的公鑰演算法——也就是量子安全（quantum safe）的演算法，能在「現成量子電腦一眨眼就攻破 4096 位元 RSA 模數」的未來取代 RSA 與橢圓曲線演算法。

這類演算法不該依賴任何已知能被 Shor 演算法有效率求解的困難問題——Shor 演算法終結了因式分解與離散對數問題的困難性。

區塊密碼與雜湊函式這類對稱演算法，面對量子電腦只會損失一半的理論安全性，不會像 RSA 那樣被徹底攻破，因此它們可能構成後量子方案的基礎。

以下是四種主要的後量子演算法類型。

基於編碼的密碼學#

基於編碼（code-based）的後量子演算法建立在糾錯碼之上——那是為了在有噪音的通道上傳輸位元而設計的技術。糾錯碼的基本理論可追溯到 1950 年代。

第一個基於編碼的加密方案（McEliece 密碼系統）於 1978 年開發，至今仍未被攻破。

基於編碼的方案可用於加密與簽章。它們的主要限制是公鑰的大小——通常是數百 KB 的量級。

但當一個網頁的平均大小約為 2 MB 時，這真的是問題嗎？

糾錯碼是什麼#

假設你想以 3 位元的字為單位傳輸一連串位元，但傳輸不可靠，你擔心有一個或多個位元被傳錯：你送出 010，接收方卻收到 011。

一個非常基本的糾錯碼做法是：不傳 010，而傳 000111000（每個位元重複三次），接收方對每三個位元取多數值來解碼。例如 100110111 會被解碼成 011，因為每三位元組中該樣式各出現兩次。

但如你所見，這個糾錯碼只能修正每個 3 位元塊中至多一個錯誤——若同一個 3 位元塊中出現兩個錯誤，多數值就會是錯的。

線性碼#

線性碼（linear codes）是較不平凡的糾錯碼。待編碼的字被視為一個 n 位元向量 v，編碼就是把 v 與一個 m × n 矩陣 G 相乘算出碼字：

w = vG      （m 大於 n，意味碼字比原始字更長）

G 可以被結構化，使得對某個給定的數 t，w 中任何 t 位元的錯誤都能讓接收者還原出正確的 v。t 就是可被修正的最大錯誤數。

McEliece 密碼系統#

為了用線性碼加密資料，McEliece 密碼系統把 G 建構成三個矩陣的秘密組合，並藉由計算 w = vG 加上某個隨機值 e（固定數量的 1 位元）來加密。

• 公鑰：G
• 私鑰：矩陣 A、B、C，滿足 G = ABC

知道 A、B、C 就能可靠地解碼訊息、取回 w。

基於格的密碼學#

格（lattices）是本質上由 n 維空間中一組具有某種週期性結構之點所構成的數學結構。

格理論導出了看似簡單得離譜的密碼方案。

兩個困難問題#

短整數解問題（SIS，short integer solution）：給定 (A, b) 使得 b = As mod q，找出由 n 個數組成的秘密向量 s。其中 A 是隨機的 m × n 矩陣、q 是質數。

帶錯誤學習問題（LWE，learning with errors）：給定 (A, b)，其中 b = As + e mod q，找出秘密向量 s。其中 A 是隨機的 m × n 矩陣、e 是隨機的噪音向量、q 是質數。

最近向量問題#

SIS 與 LWE 在某種程度上是等價的，而且都能重述為格上的最近向量問題（CVP，closest vector problem）——也就是「藉由組合一組基底向量，找出格中距離某給定點最近之向量」的問題。

但這不會直接轉化為安全的密碼系統：

• 有些問題只在最壞情況（也就是最難的實例）下困難，而非在平均情況下——而密碼學需要的是平均情況的困難性。
• 此外，雖然找出 CVP 的精確解很難，但找出解的近似值可能容易得多。

多變數密碼學#

多變數密碼學是關於建構「破解難度等同於求解多變數方程組」的密碼方案。

考慮下面這個含四個未知數 x₁, x₂, x₃, x₄ 的方程組：

x₁x₂ + x₃x₄ + x₂ = 1
x₁x₃ + x₁x₄ + x₂x₃ = 12
x₁² + x₃² + x₄ = 4
x₂x₃ + x₂x₄ + x₁ + x₄ = 0

這些方程式由若干項之和構成，每項要嘛是單一未知數（如 x₄，一次項），要嘛是兩個未知值的乘積（如 x₂x₃，二次項）。

方程式可以定義在所有實數、僅整數，或有限的數集上。但在密碼學中，方程式通常定義在某質數模下的數，或二元值（0 與 1）上。

給定一個隨機的二次方程組，找出解是 NP-hard 的。

這個稱為**多變數二次式（MQ）**的困難問題，因此是後量子系統的潛在基礎——因為量子電腦無法有效率地解決 NP-hard 問題。

但建構起來不簡單#

以簽章為例：私鑰可能由三個方程組 L₁、N、L₂ 組成，依序組合後得到另一個方程組 P，也就是公鑰。

依序套用 L₁、N、L₂ 等價於套用 P——把 x₁, x₂, x₃, x₄ 變換成 y₁, y₂, y₃, y₄：

y₁ = x₁x₂ + x₃x₄ + x₂
y₂ = x₁x₃ + x₁x₄ + x₂x₃
y₃ = x₁² + x₃² + x₄
y₄ = x₂x₃ + x₂x₄ + x₁ + x₄

其中 L₁ 與 L₂ 被選為可逆的線性變換（方程式中各項只相加、不相乘），N 則是同樣可逆的二次方程組。

這使得三者的組合是一個同樣可逆的二次方程組，但在不知道 L₁、N、L₂ 之反函式的情況下，其反函式難以決定。

計算簽章就是對訊息 M（視為一連串變數 x₁, x₂, ...）套用 L₁、N、L₂ 的反函式：

S = L₂⁻¹( N⁻¹( L₁⁻¹(M) ) )

驗證簽章則是驗證 P(S) = M。

攻擊者若能算出 P 的反函式、或從 P 判定出 L₁、N、L₂，就能攻破這個密碼系統。

求解這類問題的實際困難度取決於方案的參數（所用方程式數量、數的大小與型態等），但挑選安全的參數很難，已經有不只一個被認為安全的多變數方案被攻破。

不過多變數簽章方案有一個實際好處：它產生短簽章。

基於雜湊的密碼學#

與前述方案不同，基於雜湊的密碼學建立在密碼學雜湊函式已充分確立的安全性之上，而非數學問題的困難性。

作者最偏愛這一類，因為它簡潔且有強大的安全保證。

WOTS：一次性簽章#

基於雜湊的方案相當複雜，這裡只看它最簡單的建構元件：一次性簽章——約 1979 年發現的技巧，以其發明者命名為 Winternitz 一次性簽章（WOTS）。

這裡的「一次性」意味著一把私鑰只能用來簽署一則訊息，否則該簽章方案就不安全。

運作方式（設訊息被視為 0 到 w − 1 之間的數，w 是方案的參數，私鑰是隨機字串 K）：

簽署訊息 M（0 ≤ M < w）：S = Hash^M(K)   （把 Hash 巢狀套用 M 次）
公鑰：Hash^w(K)                          （從 K 開始巢狀迭代 Hash w 次）
驗證：檢查 Hash^(w−M)(S) 是否等於公鑰 Hash^w(K)

為什麼驗證會成功？因為 S 是 K 經過 M 次 Hash 的結果，再做 w − M 次 Hash，就會得到 K 被雜湊 M + (w − M) = w 次的值——也就是公鑰。

三個嚴重限制#

這個方案看起來相當笨，而且確實有顯著的限制。

一、簽章可被偽造

從 Hash^M(K)（M 的簽章），你可以算出 Hash(Hash^M(K)) = Hash^(M+1)(K)——那是訊息 M + 1 的有效簽章。

修補方式：不只簽 M，也用第二把金鑰簽 w − M。

二、只適用於短訊息

若訊息長 8 位元，就有多達 2^8 − 1 = 255 種可能訊息，你得計算 Hash 高達 255 次才能建立簽章。

這對短訊息或許可行，但對更長的訊息就不行——例如 128 位元訊息，簽署 2^128 − 1 這則訊息會花上永遠。

替代做法：把較長的訊息切成較短的。

三、只能用一次

若一把私鑰被用來簽署超過一則訊息，攻擊者就能還原足夠的資訊來偽造簽章。

例如 w = 8，你用前述避免平凡偽造的技巧簽署數字 1 與 7：

• 1 的簽章：Hash¹(K) 與 Hash⁷(K′)
• 7 的簽章：Hash⁷(K) 與 Hash¹(K′)

從這些值，攻擊者可以算出任何 x ∈ [1, 7] 的 Hash^x(K) 與 Hash^x(K′)，因而能代表 K 與 K′ 的擁有者偽造簽章。

這個問題沒有簡單的修補方式。

現代方案#

業界最先進的基於雜湊方案，依賴更複雜的 WOTS 版本，結合樹狀資料結構與精巧的技術，用不同的金鑰簽署不同的訊息。

遺憾的是，所得方案產生的簽章很大（數十 KB 的量級，例如本書寫作時最先進的方案 SPHINCS），而且它們有時對能簽署的訊息數量有上限。