用戶:Bieraaa/後量子密碼學

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

後量子密碼學（英語：Post-quantum cryptography，縮寫：PQC），又稱抗量子計算密碼，指的是認為能夠抵抗量子計算機破解的加密算法，特別是指非對稱加密算法。不同於量子密碼學，後量子密碼學使用現有的經典計算機，本身不依靠量子力學。時至2018年，當前廣泛使用的公鑰加密算法均基於三個數學難題：整數分解問題、離散對數問題或橢圓曲線離散對數問題。然而，這些問題均可使用量子計算機並應用秀爾算法破解。目前量子計算機仍處於研發階段，缺乏足夠的計算能力，無法破解加密，但是許多密碼學家都在未雨綢繆，儘早研發全新的公鑰加密算法以應對將來的威脅。自2006年PQCrypto大會開辦以來，該領域的研究工作已成為學術和業界的關注焦點。目前，許多學術和政府機構都在開展相關的研究工作，例如美國國家標準技術研究所（NIST）、歐洲電信標準機構（ETSI）和滑鐵盧大學量子計算研究所。

除了公鑰加密，量子計算機也威脅對稱加密算法和散列函數的安全，但相比公鑰加密面臨的威脅而言，這一問題並不嚴重。藉助量子計算機，格羅弗算法（Grover's algorithm）可將暴力破解對稱加密的難度從$N$次嘗試降低到${\sqrt {N}}$次嘗試，這樣，128位加密（密鑰空間$2^{128}$）的安全性就變為64位。但格羅弗算法的加速僅僅是多項式級別的，並非指數級的，因此只需將密鑰長度提升一倍即可抵抗這類攻擊。因此面臨量子計算機的威脅，公鑰加密需要重新設計，對稱加密則並不需要大幅度的修改。

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

公鑰密碼學

目前，後量子公鑰密碼學主要有六個研究方向。

需要注意的是，下述的一些NP困難問題常常被用作難度假設，但NP困難僅限於它們的最壞情況（worst-case）。沒有一個已知的密碼系統能夠將安全性直接規約為NP困難問題。因此，和密碼學的其他領域一樣，人們對密碼系統安全性的信心不是靠NP困難證明的，而是在長期密碼分析工作的基礎上建立起來的。

格密碼學

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

主條目：格密碼學

格密碼學（Lattice-based cryptography）指的是在算法構造本身或其安全性證明中應用到格的密碼學。 格，又稱點陣（lattice），可以直觀地理解為空間中的點以固定間隔組成的排列，它具有周期性的結構。更準確地說，是在n維空間R_n中加法群的離散子群，這一數學對象有許多應用。其中還存在幾個稱為「格問題」的難題，最有代表性的是最短向量問題（Shortest Vector Problem）和最近向量問題（Closest Vector Problem），它們在隨機規約的情況下是NP困難的。

1997年發表的GGH加密方案和GGH簽名方案是一個有代表性的早期研究。它是利用CVP構造的公鑰密碼系統。不幸的是，1999年Phong Q. Nguyen的密碼分析工作發現了GGH中存在明文信息泄漏問題，而它的CVP問題則可以轉換為一個特殊形式，其解決難度大大低於一般形式，從而破解了該加密算法。

而NTRU則是基於SVP構造的公鑰密碼系統，它同樣包括簽名和加密兩個部分。其中，NTRU簽名方案NTRU簽名方案參考了GGH的設計，首個版本PASS於1999年首次發表，但隨後的密碼分析發現數字簽名會泄漏關於私鑰的信息，而且攻擊者可以輕易偽造簽名。2001年發表的新版修正了該問題。而NTRU加密方案自1996年發表以來一直未發現根本問題，同時性能高於RSA，受到了較高的評價。

數學家奧德·雷格夫（Oded Regev）在2005年證明了機器學習領域中的容錯學習問題（RWE）和最壞情況的格問題一樣困難，可用於構造公鑰密碼，開啟了新的研究方向。環容錯學習問題（Ring-RWE）是RWE的一個改進版本，解決了其中固有的二次開銷帶來的效率問題。目前，基於這一體系的有Ring-LWE密鑰交換算法與Ring-LWE數字簽名算法。Google的NewHope加密算法就是基於Ring-LWE密鑰交換的算法。

多變量密碼學

主條目：多變量密碼學

多變量密碼學（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)$

如果存在一種方式$G^{-1}$能對方程組進行逆運算，我們就可以把這個方程組$G(x_{1},...,x_{n})$本身作為密碼系統的公鑰。這樣一來，數據加密就是將明文$M=(x_{1}',...,x_{n}')$帶入方程組，得到密文$(y_{1}',...,y_{n}')$。私鑰$G^{-1}$用於解密數據，$M=G^{-1}(y_{1}',...y_{n}')=(x_{1}',...,x_{n}')$；同理，數字簽名就是將欲簽名的數據$(y_{1}',...,y_{n}')$代入$G^{-1}$求逆得到簽名$(x_{1}',...,x_{n}')$，驗證簽名就是認證$(x_{1}',...,x_{n}')$是否為方程組$G$的解。

破解密碼系統的關鍵就是對方程組進行直接求解。但是，解一般形式的多元多次方程組是NP困難問題，甚至在只涉及到二次多項式時也是如此，這就是MQ問題。我們可以將這個問題作為多變量公鑰密碼的難度假設。也可以看到，如果方程組是完全隨機的，整個系統將是完全不可逆的。因此，建立一個密碼系統的關鍵就是如何構造$G$。

為了建立這樣一個系統，我們需要先從一個二次多項式映射$Q$入手。$Q$是一個非線性映射，其逆映射容易計算，這叫做系統的中心映射（central map）。接着，我們將中心映射先後加上$S$和$T$這兩個仿射映射，以便隱藏中心映射的結構。最後，公鑰為它們的組合形式$G=T\circ Q\circ S$，並以二次多項式方程組給出，由於$S$和$T$的存在，它一個看上去就像一個完全隨機的方程組。而$Q$、$S$和$T$則構成私鑰。