後量子密碼學

  提示：此條目頁的主題不是量子密碼學。

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

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

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

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

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

公鑰密碼學

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

格密碼學

最短向量問題：格L中，給定向量空間V中的一基向量和一範數N，求V中由N度量的最短非零向量。圖中藍色的是基向量，紅色的是最短向量。

主條目：格密碼學

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

然而於2022年7月，研究人員發現該演算法存在重大漏洞，並不安全。