后量子密码学

**後量子密碼學**（英語：Post-quantum cryptography，縮寫：PQC），又稱**抗量子計算密碼學**，是密碼學的一個研究領域，專門研究能夠抵抗量子電腦的加密演算法，特別是公鑰加密（非對稱加密）演算法。不同於量子密碼學，後量子密碼學使用現有的電腦，不依靠量子力學，它依靠的是密碼學家認為無法被量子電腦有效解決的計算難題。

時至 2021 年，電腦與網際網路領域廣泛使用的公鑰加密演算法均基於三個計算難題：整數分解問題、離散對數問題或橢圓曲線離散對數問題，如 DH、ECDH、RSA、ECDSA。然而，這些難題均可使用量子電腦並應用秀爾演算法破解。雖然人類目前還不具備建造如此大型量子電腦的科學技術，但其安全隱患已經引起了學術研究者和政府機構的擔憂。許多密碼學家都在未雨綢繆，研發全新的公鑰加密演算法以應對將來的威脅。自第一屆後量子密碼學大會（PQCrypto）於 2006 年開辦以來，本領域的研究工作愈發活躍，已成為學術和業界的關注焦點。目前，許多學術機構、政府機構、網際網路公司都在開展研究，例如美國國家標準技術研究所（NIST）、歐洲電信標準機構（ETSI）、滑鐵盧大學量子計算研究所、Google、微軟等。

在公鑰加密方面，後量子密碼學的研究方向包括了格密碼學、容錯學習問題（LWE）、多變數密碼學、雜湊密碼學、編碼密碼學（Code-based Cryptography）與超奇異橢圓曲線同源密碼學。密碼學家認為，基於這些計算難題有望構建出不受量子電腦的威脅的公鑰加密系統，替代現有的方案。

除了公鑰加密，量子電腦也威脅對稱加密演算法和雜湊函式的安全，如 AES、SHA 等。但相比公鑰加密面臨的威脅而言，這一問題並不嚴重。藉助量子電腦，格羅弗演算法（Grover's algorithm）可將暴力破解的難度從 $N$ 次嘗試降低到 ${\sqrt {N}}$ 次嘗試。這樣，128 位元加密（金鑰空間 $2^{128}$ ）的安全性就變為 64 位元。但只需將金鑰長度提升一倍（如使用 256 位加密）即可抵抗這類攻擊。因此面臨量子電腦的威脅，公鑰加密需要重新設計，對稱加密則並不需要大幅度的修改。

為了推動標準化，NIST 在 2017 年向公眾徵集後量子密碼方案，並最終收到了各學者提交的共 69 個設計。

## 公鑰密碼學

目前，後量子公鑰密碼學的研究方向如下。

### 格密碼學

格密碼學（Lattice-based cryptography）是在演算法構造本身或其安全性證明中應用到格的密碼學。格（lattice），又稱點陣，是群論中的數學物件，可以直觀地理解為空間中的點以固定間隔組成的排列，它具有週期性的結構。更準確地說，是在 n 維空間 Rn 中加法群的離散子群，這一數學物件有許多應用，其中存在幾個稱為「格問題」的難題，如最短向量問題（Shortest Vector Problem）和最近向量問題（Closest Vector Problem）。許多基于格的密碼系統利用到了這些難題。

經典的格密碼學加密演算法包括 GGH 加密方案（基於 CVP，已遭破解）和 NTRU 加密方案（受 GGH 啟發，基於 SVP）。由於容錯學習問題與格問題存在聯絡，因此後來基於容錯學習問題（LWE）與環容錯學習問題（Ring-LWE）的加密演算法也屬于格密碼學的範疇。

### 編碼密碼學

編碼密碼學（Code-based Cryptography）是應用了編碼理論與糾錯碼的密碼學。

其中最早、最有代表性是 McEliece 密碼系統：首先選擇一種有已知高效解碼演算法的糾錯碼作為私鑰，然後對私鑰進行轉換（用兩個隨機選擇的可逆矩陣 $S$ 與 $P$ 「打亂」糾錯碼的生成矩陣），得到公鑰。這樣，能高效解碼的特殊糾錯碼就被「偽裝」成了一般線性碼（general linear code）—— 一般線性碼的解碼十分困難，是 NP 困難問題。其密文就是引入隨機錯誤的碼字（codeword），有私鑰者可以進行糾錯得到明文，無私鑰者則無法解碼。

McEliece 演算法首次發表於 1978 年（僅比 RSA 晚一年），使用的是二元戈帕碼（Binary Goppa code），經歷了三十多年的考驗，至今仍未能破解。但缺點是公鑰體積極大，一直沒有被主串流加密法學界所採納。但隨著後量子密碼學提上日程，McEliece 演算法又重新成為了候選者。許多研究者嘗試將二元戈帕碼更換為其他糾錯碼，如里德 - 所羅門碼、LDPC 等，試圖降低金鑰體積，但全部遭到破解，而原始的二元戈帕碼仍然安全。

### 多變數密碼學

多變數密碼學（Multivariate cryptography）是應用了有限體 $F$ 上多元多項式的密碼學，包括對稱加密和非對稱加密。當研究物件是非對稱加密時，又叫做多變數公鑰密碼學（Multivariate Public Key Cryptography），縮寫 MPKC。此外，由於它常使用二次多項式（Multivariate Quadratic），因此又可縮寫為 MQ。

考慮 $q$ 階的有限體 $F_{q}$ 。我們在其中建立一個方程組，它由 _n_ 個變數與 _m_ 個方程組成。

　
: ${\begin{cases}y_{1}=G_{1}(x_{1},x_{2},...,x_{n})\\y_{2}=G_{2}(x_{1},x_{2},...,x_{n})\\...\\y_{m}=G_{m}(x_{2},x_{2},...,x_{n})\\\end{cases}}$

其中每個方程式都是一個多元多項式，通常為二次多項式。

　
: $G_{l}(x_{1},...,x_{n})=\sum _{1\leqslant i\leqslant j\leqslant n}a_{ij}^{(l)}x_{i}x_{j}+\sum _{1\leqslant i\leqslant n}b_{i}^{(l)}x_{i}+c^{(l)}\quad (l=1,2,...,m)$

解一般形式的多元多次方程組是一個計算難題，甚至在只有二次多項式時也是如此，這就是 MQ 問題。多變數密碼學研究的就是基於這類計算難題的密碼系統。

### 雜湊密碼學

雜湊密碼學（Hash-based Cryptography）是應用雜湊函式的數位簽章。雜湊密碼學的研究歷史也很長，最早的研究工作包括萊斯利・蘭波特於 1979 年提出的蘭波特簽章（Lamport signature），與瑞夫・墨克提出的墨克樹（Merkle tree）。後來以此為基礎，又出現了 Winternitz 簽章和 GMSS 簽章，近年來的工作則包括 SPHINCS 簽章與 XMSS 簽章方案。

雜湊密碼學的優點是：數位簽章的安全性只取決於雜湊函式，而足夠長的雜湊函式不受量子電腦威脅。其缺點是：第一，金鑰體積極大，因此一直沒有被主串流加密法學界所採納。後量子密碼學重新激發了這一領域的研究。第二，許多雜湊密碼系統的私鑰是有狀態的，簽章後都必須更新私鑰的計數器，保證同一狀態不可重用，否則簽章方案就會遭到攻擊者破解。例如，將同一私鑰同時在兩台機器上使用，就會造成巨大的安全問題。SPHINCS 簽章解決了這一問題。

### 超奇異橢圓曲線同源密碼學

超奇異橢圓曲線同源密碼學（Supersingular elliptic curve isogeny cryptography）是利用超奇異橢圓曲線與超奇異同源圖的數學性質的密碼學，可以實現超奇異同源金鑰交換（SIDH），具有前向安全性。其使用方法和現有的迪菲－赫爾曼金鑰交換相似，有望直接替代當前的常規橢圓曲線金鑰交換（ECDH）。

## 參考資料