後量子密碼學

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

後量子密碼學（英語：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簽章方案。

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

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

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

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

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