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