後量子密碼學

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

後量子密碼學（英語：Post-quantum cryptography，縮寫：PQC），又稱為防量子、量子安全、抗量子計算，是密碼學的一個研究領域，專門研究能夠抵抗量子電腦進行密碼分析攻擊的加密演算法（特別是公鑰加密演算法）。電腦與網際網路領域廣泛使用的公鑰加密演算法均基於三個計算難題：整數分解問題、離散對數問題或橢圓曲線離散對數問題。然而，這些難題均可使用量子電腦並應用秀爾演算法破解，或是比秀爾演算法更快，需求量子位元更少的其他演算法破解。

雖然到2023年為止，量子電腦的電腦效能還無法破解一般使用的加密演算法，不過密碼學研究者已在考慮Y2Q或是Q-Day，也就是可以用量子電腦破解目前使用演算法的一天，並為了那一天設計無法用量子電腦破解的新加密演算法。透過2006年起舉辦的一系列PQCrypto學術研討會，歐洲電信標準協會（ETSI）舉辦的數個Quantum Safe Cryptography工作坊，以及量子計算研究所，後量子密碼學上上的研究已受到學術界及產業界的注意。據傳目前存在，廣泛的先竊取，後解密程式也視為是早期推動後量子密碼學的動力之一，因為目前記錄的資料可能在未來都仍是敏感資料。

目前量子計算的攻擊主要是針對公鑰演算法，大部份目前使用的對稱金鑰加密以及雜湊函式比較可以抵擋量子電腦的攻擊。量子的格羅弗演算法確實可以加速對於對稱加密的攻擊，但金鑰長度加倍即可有效抵抗此攻擊。後量子的對稱密碼學和現行的對稱密碼學差異不大。

美國國家標準技術研究所（NIST）提出了頭三個後量子加密標準的正式版本。

公鑰密碼學

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

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

格密碼學

最短向量問題：格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簽章方案。

雜湊密碼學的優點：

數位簽章的安全性僅依賴於雜湊函式，而足夠長的雜湊函式能抵禦量子電腦的攻擊。並且雜湊函式自20世紀以來已在多個加密協定中廣泛使用，經過長期實踐驗證，被認為具有高度穩固的安全性基礎。相比其他後量子演算法（如格密碼）仍在接受理論與實戰檢定，雜湊密碼體系的未知風險較小，未來被新興理論或實踐手段破解的可能性也較低。

缺點則包括：

第一，金鑰體積通常較大，這一限制使得其在傳統密碼系統中長期未被廣泛採納，直到後量子密碼學的發展重新激發了相關研究興趣。

第二，許多後量子雜湊簽章方案為有狀態的（stateful），每次簽章後必須更新私鑰狀態（例如計數器），以確保每個狀態僅使用一次；若狀態被重複使用，可能導致私鑰洩露。例如，在多台裝置上同時使用同一私鑰，若狀態未能同步更新，就可能引發嚴重的安全漏洞。SPHINCS+ ，一種典型的無狀態（stateless）雜湊簽章方案解決了該問題，但代價是簽章體積更大、計算開銷也更高。

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

主條目：超奇異同源金鑰交換

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

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

安全規約

在密碼學研究中，我們希望找到與特定演算法等價、且已知的數學難題。當這個等價的數學難題之解法被提出，就意味著該密碼演算法是可行、可被計算的。這個尋找等價數學難題的研究領域就被稱為安全規約（security reductions）。