在深入研究每一類提交的方案之前，我們簡要地總結了每種密碼體制固有的權衡，並將其與當前（非後量子）橢圓曲線密碼學進行了比較。請注意，編碼和isogenies是能夠設計數字簽名的，但沒有向NIST提交這樣的方案。
在安全性證明方面，上述任何一種密碼體制都不能歸約到NP-hard（或NP-complete）問題上。就格和編碼而言，這些密碼體制是基於輕微修改的NP-hard問題。基於雜湊函式的密碼體制依賴於良好的雜湊函式，並且無需其它的加密假設。最後，基於isogenies的密碼體制是基於一個被推測為很難的問題，但與NP-hard問題或之前的加密假設不同。然而，值得一提的是，正如我們不能證明任何經典演算法在多項式時間內都是不可破解的（因為P可以等於NP），同樣這也是量子計算機所面臨的難題。此外，一個不能歸約為NP-hard或NP-complete問題的密碼體制並不意味著就要放棄它，例如整數分解和離散對數問題，它們並不被認為是NP-complete問題。
2、格
在所有後量子密碼體制中，格是研究最活躍和最靈活的。它們具有很強的安全性，能夠進行金鑰交換、數字簽名，以及構造出像全同態加密這樣複雜的演算法。儘管格密碼體制的最佳化和安全性都需要非常複雜的數學證明，但基本思想只需要基本的線性代數。假設你有一個如下線性方程組：
求解x是一個經典的線性代數問題，可以用高斯消元法快速求解。另一種思考方式是我們有一個神秘的函式，
給定向量a，我們在不知道x的情況下，得到了ax的結果，在查詢這個函式足夠多次之後，我們可以在短時間內學習f（透過求解上面的方程組）。透過這種方式，我們可以將線性代數問題重新定義為機器學習問題。
現在，假設我們在函式中引入了少量噪音，即在x和a相乘之後，我們加上一個誤差項e，然後整體模上一個（中等大小的）素數 q，最後我們包含噪音的神秘函式看起來是這樣的：
學習這種帶噪音的神秘函式已經在數學上被證明是極其困難的。直覺告訴我們，在這種情況下使用高斯消元，它的每一步都會使誤差項e變得越來越大，直到它超過關於函式的所有有用資訊。在密碼學文獻中，這被稱為錯誤學習問題（LWE）。
基於LWE的密碼學之所以被稱為是基於格的密碼學，是因為LWE的困難性證明依賴於這樣一個事實，即在格中找到最短向量，已知它屬於NP-hard問題。在這裡，我們不會深入討論格的數學問題，但我們可以把格看作是n維空間的平鋪圖：
格是由座標向量表示的。在上面的例子中，透過結合e1、e2和e3（透過法向量加法）可以到達格中的任何點。最短向量問題（SVP）：給定一個格，找到向量長度最短的元素。這很難直觀的原因是因為並非所有給定格的座標系都同樣易於使用。在上面的例子中，我們可以用三個非常長且非常接近的座標向量來表示格，這使得找到接近原點的向量變得更加困難。事實上，有一種規範的方法可以找到格的“最壞可能”表示。當使用這種表示時，已知最短向量問題為NP-hard問題。
在討論如何使用LWE進行抗量子密碼研究之前，我們應該指出的是LWE本身並不是NP-hard問題。它不是直接歸約為SVP，而是歸約為SVP的近似值，根據推理，它實際上不是NP-hard問題。儘管如此，目前還沒有多項式（或次指數）時間內的演算法來求解LWE。
現在讓我們使用LWE問題來構建一個實際的密碼體制。最簡單的方案是由Oded Regev在他最初的論文中構造的，同時他也證明了LWE問題的困難度。這裡，金鑰是一個n維的整係數模q的向量，也就是上面提到的LWE私鑰。公鑰是前面討論的矩陣A，以及LWE函式的輸出向量。
這個公鑰的一個重要特性是，當它乘以向量(-sk，1)時，我們得到誤差項，大約為0。
為了加密一位訊息m，我們取A的隨機列之和，並在結果的最後一個座標中編碼m，即如果m為0，就加0，如果m為1，就加q/2。換句話說，我們選擇一個元素為0或1的隨機向量x，然後計算：
直觀地說，我們已經求解了LWE函式（我們知道它很難被破解）的值，並在這個函式的輸出中編碼了m。
解密是有效的，因為知道了LWE私鑰就將允許接收方收回訊息，外加一個小的錯誤項。
正確選擇錯誤分佈後，它將不會使訊息失真超過q/4。接收方可以測試輸出是否接近於0或q/2 mod q，並相應地解碼出m。
該體制的一個主要問題是它需要很大的金鑰。要加密一位訊息，需要在安全引數中使用大小為n2的公鑰。然而，格密碼體制的一個吸引人的方面是它們的速度非常快。
自從Regev的第一篇論文發表以來，圍繞基於格密碼體制的研究進行了大量工作。其中關於改進其實用性的一個關鍵突破是Ring-LWE，Ring-LWE是LWE問題的一個變體，其中金鑰是由若干多項式表示的。這導致了金鑰大小的二次減少，加速了加密和解密，僅使用n*log(n)次操作（使用快速傅立葉變換，FFT）。
NIST PQC標準考慮了許多基於格密碼體制的方案，特別值得一提的兩個基於格構造的方案是Kyber和Dilithium。
Kyber是一種金鑰封裝機制（KEM），它遵循與上述系統類似的構造，但是使用了一些奇特的代數數論來獲得比Ring-LWE更好的效能。對於合理的安全引數，金鑰大小約為1kb（仍然很大），但加密和解密時間大約為0.075毫秒。考慮到這種速度是透過軟體實現的，Kyber KEM似乎很有希望用於後量子密碼中的金鑰交換。
Dilithium是一種基於與Kyber類似技術的數字簽名方案。它的細節超出了本文的範圍，但值得一提的是，它也實現了相當不錯的效能。公鑰大小約為1kb，簽名為2kb。這也非常高效。在Skylake處理器上，計算簽名所需的平均週期約為200萬次。驗證的平均週期為39萬次。
3、編碼
糾錯碼的研究在電腦科學文獻中有著悠久的歷史，可以追溯到Richard Hamming和Claude Shannon的突破性研究。雖然我們甚至無法在一篇簡短的博文中觸及這一深層領域的表層，但我們給出了一個快速的概述。
在傳遞二進位制訊息時，錯誤可能以位翻轉的形式出現。糾錯碼提供了以犧牲訊息緊湊性為代價來承受一定數量的位翻轉的能力。例如，我們可以透過編碼將0（000）和1（111）來防止單位元位的翻轉。這樣接收方就能透過對三個位元位進行多數表決的方式確定101實際上是111，或者001是0。但該編碼不能糾正兩個位被翻轉的錯誤，因為當111變成001時，解碼結果為0，而不是1。
糾錯碼中最為突出的是線性碼，可以用k * n的矩陣表示，其中k是原始訊息的長度，n是編碼訊息的長度。通常，在不知道底層線性碼的情況下解碼訊息在計算上是困難的。這種困難度是McEliece公鑰密碼體制安全性的基礎。
在較高層次上，McEliece體制中的私鑰是一組稱為Goppa碼的隨機碼（表示為矩陣G）。公鑰是矩陣SGP，其中S是一個具有二進位制項的可逆矩陣，P是一個置換矩陣。為了加密訊息m，傳送方計算c = m(SGP) + e，其中e是一個隨機錯誤向量，精確地表示編碼能夠糾正的錯誤數量。為了解密，我們計算cP-1 = mSG + eP-1，使mS是G的碼字，其可以校正新增的錯誤項e，透過計算mSS-1可以很容易地恢復訊息。
與格一樣，基於編碼的加密技術也面臨著金鑰是大矩陣這一事實。使用推薦的安全引數，McEliece公鑰大約為1 mb，私鑰為11 kb。目前正在嘗試使用一種稱為準迴圈中等密度奇偶校驗碼（quasi-cyclic moderate density parity-check codes）的特殊編碼，這種編碼可以比Goppa碼更簡潔地表示，但這些編碼的安全性比Goppa碼研究得要少。
4、Isogenies
橢圓曲線密碼學領域因使用大量晦澀難懂的數學理論而臭名昭著。isogenies更是如此。在橢圓曲線密碼學中，我們使用Diffie-Hellman型協議來獲取共享的秘密，但是我們不是將群中元素提升到某個冪，而是遍歷橢圓曲線上的點。在基於isogenies的密碼學中，我們再次使用Diffie-Hellman型協議，但不是遍歷橢圓曲線上的點，而是透過一系列橢圓曲線。
isogeny是一個將一條橢圓曲線轉換為另一條橢圓曲線的函式，使得第一條曲線的群結構在第二條曲線中得到反映。對於那些熟悉群理論的人來說，它是一個同態群，有一些附加的結構來處理每條曲線的幾何形狀。當我們把注意力限制在超奇異橢圓曲線上時（我們不會在這裡定義它），每條曲線都保證從它到其他超奇異曲線都有固定數量的isogenies。
現在，我們來看看這個圖，它是透過檢查從起始曲線得到的所有的isogenies，然後是這些曲線的所有isogenies，以此類推。這張圖被證明是高度結構化的，因為如果我們從第一個曲線開始隨機遊走，碰到另一個曲線的概率會很小（除非我們呈指數級地走很多步）。在數學術語中，我們說透過檢查所有這些isogenies生成的圖是一個擴充套件圖（也是Ramanujan）。這種擴充套件特性正是使基於isogenies的密碼學安全的原因。
對於Supersingular Isogeny Diffie-Hellman（SIDH）方案，私鑰是一條由isogenies構成的鏈，公鑰是曲線。當Alice和Bob組合這些訊息時，他們得到的曲線是不同的，但是有相同的不變數j。對於密碼學來說，j是什麼並不重要，重要的是，一旦Alice和Bob完成金鑰交換，就可以很容易地計算出這個數字。
與其他後量子方案相比，基於isogeny的密碼學擁有非常小的金鑰大小，公鑰只使用330bytes。不幸的是，在本文討論的所有技術中，它們是最慢的，在金鑰生成和共享秘密計算中都需要11-13毫秒。然而，他們確實支援完美的前向保密，這是其他後量子密碼體制所不具備的。
5、基於雜湊的簽名
已經有很多關於基於雜湊的簽名的介紹，因此我們將對它們進行簡單的討論。簡而言之，雜湊簽名使用雜湊函式的輸入作為私鑰，輸出作為公鑰。這些金鑰僅適用於一個簽名，因為簽名本身包含了私鑰的一部分。這種極端低效的簽名方案通常使用Merkle樹來減少空間消耗（是的，與比特幣中使用的Merkle樹相同）。
遺憾的是，無法使用雜湊構造KEM或公鑰密碼方案。因此，基於雜湊的簽名並不是一個完整的後量子密碼解決方案。此外，它們不是空間有效的；一個比較有前途的簽名方案是SPHINCS，它產生的簽名大小為41kb，公鑰/私鑰大小為1kb。另一方面，基於雜湊的方案非常快，因為它們只需要計算雜湊函式。它們還具有非常強的安全性證明，僅僅基於存在具有抗碰撞和抗原像性的雜湊函式的假設。由於沒有跡象表明像SHA3或BLAKE2這樣當前廣泛使用的雜湊函式容易受到這些攻擊，因此基於雜湊的簽名是安全的。
6、小貼士
後量子密碼學是一個令人難以置信又令人興奮的研究領域，在過去的十年裡已經取得了巨大的進展。儘管這篇文章中描述的四種密碼體制受到了學術界的廣泛關注，但沒有一種密碼體制得到NIST的批准，因此目前不推薦用於一般用途。許多方案的最初版本都不具備效能，並且受到各種最佳化的影響，這些最佳化可能會影響安全性，也可能不會影響安全性。事實上，多個為McEliece體制使用更節省空間而設計的編碼方案都已經被證明是不安全的。就目前而言，從後量子密碼體制中獲得最佳安全性需要犧牲一定的空間或時間。基於格密碼學的研究在靈活性方面是最有前途的（簽名和KEM和全同態加密），但其所基於的假設只是經過了幾年的深入研究。目前，最安全的做法是將McEliece與Goppa碼一起使用，因為它已經經受了幾十年的密碼分析。
然而，每個用例都是唯一的。如果您認為您可能需要後量子密碼，請與您關係不錯的密碼學專家聯絡。其他人應該等待NIST完成後量子密碼的標準化。
轉自：公眾號（格密鏈）
更多區塊鏈資訊：www.qukuaiwang.com.cn/news
