對(duì)于如TLS流量、醫(yī)療數(shù)據(jù)庫牡借、區(qū)塊鏈拳昌，等等許多需要高度保障安全的應(yīng)用方向，前向保密絕對(duì)必不可少钠龙，但僅僅防止黑客快速解密敏感信息是遠(yuǎn)遠(yuǎn)不夠的炬藤，威脅模型還應(yīng)該考慮攻擊者在收集密文多年之后解開密文的情況。

可能打破的前方保密的潛在方式是：增加的計(jì)算能力和數(shù)量基礎(chǔ)理論的突破碴里，這會(huì)使攻擊密碼變得很簡(jiǎn)單沈矿。

但是，除非有人找到了用于分解大整數(shù)的多項(xiàng)式時(shí)間算法咬腋，否則這種風(fēng)險(xiǎn)對(duì)于當(dāng)前的密碼算法來說可能性很小羹膳，我們應(yīng)該更關(guān)注量子計(jì)算機(jī)的成功開發(fā)。

量子計(jì)算入門

量子計(jì)算機(jī)不僅僅是大規(guī)模并行的經(jīng)典計(jì)算機(jī)根竿。人們常常認(rèn)為溜徙，由于量子比特可以同時(shí)占據(jù)0和1，因此n比特量子計(jì)算機(jī)可以同時(shí)處于2 n個(gè)狀態(tài)犀填，因此可以非常快速地計(jì)算NP嗓违。

其實(shí)情況并非如此九巡，因?yàn)闇y(cè)量量子態(tài)會(huì)破壞大部分原始信息。例如蹂季，量子系統(tǒng)完全了解物體的動(dòng)量和位置冕广，但任何動(dòng)量測(cè)量都會(huì)破壞有關(guān)位置的信息疏日，反之亦然。這被稱為海森堡不確定性原理撒汉。

因此沟优，成功的量子算法由量子比特的一系列變換組成，使得在計(jì)算結(jié)束時(shí)睬辐，測(cè)量系統(tǒng)的狀態(tài)不會(huì)破壞所需的信息挠阁。事實(shí)上，已經(jīng)證明溯饵，不存在量子算法同時(shí)嘗試解決某些NP完全問題并輸出正確的量子算法侵俗。換句話說，任何用于解決硬經(jīng)典問題的量子算法都必須利用具體結(jié)構(gòu)丰刊。

今天隘谣，有兩種這樣的算法可用于密碼分析。

快速計(jì)算大數(shù)的能力將破壞RSA和離散的基于日志的加密啄巧。整數(shù)分解的最快算法是一般數(shù)字域篩寻歧，它在亞指數(shù)時(shí)間內(nèi)運(yùn)行。

在1994年秩仆，Peter Shor開發(fā)了一種用于整數(shù)分解的量子算法（Shor算法）码泛，該算法在多項(xiàng)式時(shí)間內(nèi)運(yùn)行，因此能夠破壞任何RSA或離散的基于對(duì)象的密碼系統(tǒng)（包括那些使用橢圓曲線的密碼系統(tǒng)）逗概。這意味著如果有人要構(gòu)建量子計(jì)算機(jī)弟晚，那么所有廣泛使用的公鑰密碼都是不安全的。

第二個(gè)是Grover的算法逾苫，它能夠在O（√n）時(shí)間內(nèi)反轉(zhuǎn)函數(shù)卿城。該算法會(huì)通過根因子降低對(duì)稱密鑰加密的安全性，因此AES-256只能提供128位的安全性铅搓。類似地瑟押，找到256位散列函數(shù)的前映像只需要2 128次。由于將哈希函數(shù)或AES的安全性提高兩倍并不是非常繁瑣星掰，因此Grover的算法不會(huì)對(duì)對(duì)稱加密造成嚴(yán)重威脅多望。此外，建議用于加密使用的偽隨機(jī)數(shù)發(fā)生器都不會(huì)受到量子計(jì)算機(jī)發(fā)明的影響氢烘，除非Grover算法引起的O（√n）因子怀偷。

后量子算法的類型

后量子密碼學(xué)是對(duì)密碼系統(tǒng)的研究，它可以在經(jīng)典計(jì)算機(jī)上運(yùn)行播玖，即使對(duì)手擁有量子計(jì)算機(jī)也是絕對(duì)安全的椎工。

最近，NIST啟動(dòng)了標(biāo)準(zhǔn)化后量子加密的過程，目前正在審查第一輪提交维蒙。這些提交中最有希望的包括基于格掰吕，同源，Hash函數(shù)和編碼的密碼系統(tǒng)颅痊。

在深入研究每類提交之前殖熟，我們簡(jiǎn)要總結(jié)一下每種類型的密碼系統(tǒng)固有的權(quán)衡，并與當(dāng)前（非后量子）橢圓曲線密碼學(xué)進(jìn)行比較斑响。請(qǐng)注意菱属，代碼和同基因能夠生成數(shù)字簽名，但沒有向NIST提交此類方案恋捆。

表1：提交給NIST的經(jīng)典ECC與后量子方案的比較

在安全性證明方面照皆，上述密碼系統(tǒng)都沒有減少到NP-Hard（或NP完全）問題。在格和編碼的情況下沸停，這些密碼系統(tǒng)基于NP難問題的輕微修改膜毁。基于散列的構(gòu)造依賴于良好散列函數(shù)的存在愤钾，并且不進(jìn)行其他加密假設(shè)瘟滨。

最后，基于同基因的密碼學(xué)基于一個(gè)被推測(cè)為難的問題能颁，但與NP-Hard問題或先前的加密假設(shè)不相似杂瘸。然而，值得一提的是伙菊，正如我們無法證明任何經(jīng)典算法在多項(xiàng)式時(shí)間內(nèi)都不易破碎（因?yàn)镻可能等于NP）败玉，可能是量子計(jì)算機(jī)認(rèn)為難以解決的問題。此外镜硕，一個(gè)不會(huì)減少到一些NP難或完整問題的密碼系統(tǒng)本身不應(yīng)該是一個(gè)標(biāo)記运翼。

格

在后量子加密的所有方法中，對(duì)格子的研究是最活躍和最靈活的兴枯。它們具有很強(qiáng)的安全性血淌，可以進(jìn)行密鑰交換，數(shù)字簽名以及完全同態(tài)加密等更復(fù)雜的構(gòu)造财剖。盡管格子密碼系統(tǒng)的優(yōu)化和安全性證明都需要極其復(fù)雜的數(shù)學(xué)悠夯，但基本思想只需要基本的線性代數(shù)。假設(shè)您有一個(gè)形式的線性方程組躺坟，比如說：

求解x是一個(gè)經(jīng)典的線性代數(shù)問題沦补，可以使用高斯消元法快速求解。另一種思考方式是我們有一個(gè)神秘的功能咪橙，

?給定一個(gè)向量的地方a策彤，我們看到了結(jié)果ax栓袖，而不知道x。在查詢此函數(shù)足夠多次后店诗，我們可以在很短的時(shí)間內(nèi)得到f（通過求解上面的方程組）。這樣我們就可以將線性代數(shù)問題重新定義為機(jī)器學(xué)習(xí)問題音榜。

現(xiàn)在庞瘸，假設(shè)我們引入少量噪聲到我們的功能，使相乘后x和a赠叼，我們?cè)黾右粋€(gè)誤差項(xiàng)e擦囊，降低了整個(gè)事情的一個(gè)模（中型）q

學(xué)習(xí)這種帶噪的神秘函數(shù)已經(jīng)在數(shù)學(xué)上被證明是非常困難的。直覺是在我們?cè)诜窃肼暻闆r下使用的高斯消除過程的每一步中嘴办，誤差項(xiàng)變得越來越大瞬场，直到它超越了關(guān)于函數(shù)的所有有用信息。在密碼學(xué)文獻(xiàn)中涧郊，這被稱為帶有錯(cuò)誤學(xué)習(xí)問題（LWE）贯被。

基于LWE的密碼學(xué)被稱為基于格的密碼學(xué)的原因，已知NP-Hard妆艘，LWE難以證明依賴于在稱為格子的東西中找到最短向量彤灶。我們不會(huì)在這里深入研究格子的數(shù)學(xué)，但可以認(rèn)為格子是n維空間的平鋪

格子由坐標(biāo)向量表示批旺。在上面的例子中幌陕，晶格的任何點(diǎn)可通過將達(dá)到（經(jīng)由正常矢量相加）。最短向量問題（SVP）說：給定一個(gè)點(diǎn)陣汽煮，找到長(zhǎng)度為向量的元素最短搏熄。很難的直觀原因是并非所有給定晶格的坐標(biāo)系都同樣易于使用。在上面的例子中暇赤，我們可以用三個(gè)非常長(zhǎng)且靠近的坐標(biāo)向量來表示晶格心例，這使得尋找靠近原點(diǎn)的向量更加困難。事實(shí)上翎卓，有一種規(guī)范的方法可以找到格子的“最壞可能”表示契邀。當(dāng)使用這樣的表示時(shí)，已知最短向量問題是NP-hard失暴。

在研究如何使用LWE進(jìn)行抗量子密碼學(xué)之前坯门，我們應(yīng)該指出LWE本身不是NP-Hard。它不是直接降低到SVP逗扒，而是降到SVP的近似值古戴，推測(cè)它是不是NP-Hard。盡管如此矩肩，目前還沒有用于求解LWE的多項(xiàng)式（或次指數(shù)）算法现恼。

現(xiàn)在讓我們使用LWE問題來創(chuàng)建一個(gè)實(shí)際的密碼系統(tǒng)。最簡(jiǎn)單的方案是由Oded Regev在他的原始論文中創(chuàng)建的，證明了LWE問題的硬度叉袍。這里始锚，秘密密鑰是具有整數(shù)條目mod的n維向量q，即上面提到的LWE秘密喳逛。公鑰是A前面討論的矩陣瞧捌，以及LWE函數(shù)的輸出向量

這個(gè)公鑰的一個(gè)重要特性是，當(dāng)它乘以向量時(shí)润文，我們得到了大致的誤差項(xiàng)姐呐。(-sk,1)0

為了加密一些信息m，我們?nèi)〗Y(jié)果的最后一個(gè)坐標(biāo)中的隨機(jī)列A和編碼的總和典蝌，m加上0曙砂，如果m是0，q/2如果m是1骏掀。換句話說鸠澈，我們選擇x0或1 的隨機(jī)向量，并進(jìn)行計(jì)算

直覺上砖织，我們剛剛評(píng)估了LWE函數(shù)（我們知道它很難破解）并在此函數(shù)的輸出中編碼了我們的位款侵。

解密是有效的，因?yàn)橹繪WE秘密將允許收件人收回消息侧纯，加上一個(gè)小錯(cuò)誤術(shù)語

正確選擇錯(cuò)誤分布后新锈，它永遠(yuǎn)不會(huì)使消息失真超過q/4。接收方可以測(cè)試輸出是否更接近0或相應(yīng)地q/2 mod q解碼該位眶熬。

該系統(tǒng)的一個(gè)主要問題是它具有非常大的密鑰妹笆。要加密一位信息，需要安全參數(shù)中大小為n 2的公鑰娜氏。然而拳缠，格子密碼系統(tǒng)的一個(gè)吸引人的方面是它們非常快贸弥。

自Regev的原始論文以來窟坐，圍繞基于格的密碼系統(tǒng)進(jìn)行了大量工作。改進(jìn)其實(shí)用性的關(guān)鍵突破是Ring-LWE的開發(fā)绵疲，這是LWE問題的變體哲鸳，其中鍵由某些多項(xiàng)式表示。這導(dǎo)致密鑰大小的二次減少盔憨，加速加密和解密徙菠，僅使用n*log(n)操作（使用快速傅立葉技術(shù)）。

在考慮用于NIST PQC標(biāo)準(zhǔn)的許多基于晶格的密碼系統(tǒng)中郁岩，特別值得一提的兩個(gè)是晶體結(jié)構(gòu)婿奔，Kyber和Dilithium缺狠。

Kyber是一種密鑰封裝機(jī)制（KEM），它遵循與上述系統(tǒng)類似的結(jié)構(gòu)萍摊，但使用一些花哨的代數(shù)數(shù)論來獲得比Ring-LWE更好的性能挤茄。對(duì)于合理的安全參數(shù)，密鑰大小約為1kb（仍然很大＜遣汀）但加密和解密時(shí)間大約為0.075毫秒驮樊。考慮到這種速度是通過軟件實(shí)現(xiàn)的片酝，Kyber KEM似乎很有希望進(jìn)行后量子密鑰交換。

Dilithium是一種基于類似Kyber技術(shù)的數(shù)字簽名方案挖腰。它的詳細(xì)信息超出了本博文的范圍雕沿，但值得一提的是它也實(shí)現(xiàn)了相當(dāng)不錯(cuò)的性能。公鑰大小約為1kb猴仑，簽名為2kb审轮。它也非常高效。在Skylake處理器上辽俗，計(jì)算簽名所需的平均周期數(shù)約為200萬疾渣。驗(yàn)證平均需要390,000個(gè)周期。

編碼

糾錯(cuò)碼的研究在計(jì)算機(jī)科學(xué)文獻(xiàn)中有著悠久的歷史崖飘，可以追溯到Richard Hamming和Claude Shannon的突破性工作榴捡。我們無法在一篇簡(jiǎn)短的博文中開始研究這個(gè)深層領(lǐng)域的表面，但我們會(huì)給出一個(gè)快速概述朱浴。

在傳遞二進(jìn)制消息時(shí)吊圾，錯(cuò)誤可能以位翻轉(zhuǎn)的形式發(fā)生。糾錯(cuò)碼提供了以消息緊湊性為代價(jià)承受一定數(shù)量的位翻轉(zhuǎn)的能力翰蠢。例如项乒，我們可以通過將0編碼為000而將1編碼為111來防止單比特翻轉(zhuǎn)。這樣梁沧，接收器可以通過對(duì)三個(gè)比特進(jìn)行多數(shù)表決來確定101實(shí)際上是111檀何，或者001是0。但是廷支，這個(gè)編碼無法糾正兩個(gè)位被翻轉(zhuǎn)的錯(cuò)誤频鉴，因?yàn)檗D(zhuǎn)換為001的111將被解碼為0。

最突出的糾錯(cuò)碼類型稱為線性碼酥泞，可以用k x n矩陣表示砚殿，其中k是原始消息n的長(zhǎng)度，是編碼消息的長(zhǎng)度芝囤。通常似炎，在不知道底層線性編碼的情況下解碼消息在計(jì)算上是困難的辛萍。這種硬度鞏固了McEliece公鑰密碼系統(tǒng)的安全性。

在高級(jí)別羡藐，McEliece系統(tǒng)中的秘密密鑰是G來自稱為Goppa碼的一類代碼的隨機(jī)碼（表示為矩陣）贩毕。公鑰是矩陣SGP，其中S是具有二進(jìn)制條目的可逆矩陣并且P是置換仆嗦。為了加密消息m辉阶，發(fā)送方計(jì)算c = m(SGP) + e，其中e是隨機(jī)錯(cuò)誤向量瘩扼，其中包含編碼能夠糾正的錯(cuò)誤數(shù)量谆甜。為了解密，我們進(jìn)行計(jì)算集绰，這樣就可以糾正添加的錯(cuò)誤術(shù)語规辱。通過計(jì)算可以輕松恢復(fù)該消息。cP-1 = mSG + eP-1mSGemSS-1

與格子一樣栽燕，基于代碼的密碼術(shù)也存在密鑰是大矩陣的事實(shí)罕袋。使用推薦的安全參數(shù)，McEliece公鑰大約為1 MB碍岔，私鑰為11 kb浴讯。目前正在嘗試使用稱為準(zhǔn)循環(huán)中等密度奇偶校驗(yàn)碼的特殊類代碼，這些代碼可以比Goppa代碼更簡(jiǎn)潔地表示蔼啦，但是這些便阿門的安全性比Goppa碼的研究更少榆纽。

同源

橢圓曲線密碼學(xué)領(lǐng)域因使用相當(dāng)多的奧術(shù)數(shù)學(xué)而臭名昭著。同基因?qū)⑦@一點(diǎn)提升到一個(gè)全新的水平询吴。在橢圓曲線加密中掠河，我們使用Diffie-Hellman類型協(xié)議來獲取共享秘密，但是我們不是將組元素提升到某個(gè)冪猛计，而是遍歷橢圓曲線上的點(diǎn)唠摹。在基于同源的密碼學(xué)中，我們?cè)俅问褂肈iffie-Hellman類型協(xié)議奉瘤，但我們不是通過橢圓曲線上的點(diǎn)遍歷勾拉，而是通過一系列橢圓曲線本身。

同種映射變換盗温，使得上述第一曲線的組結(jié)構(gòu)被反映在第二橢圓曲線到另一個(gè)的功能藕赞。對(duì)于那些熟悉群論的人來說，它是一個(gè)群同態(tài)卖局，有一些附加的結(jié)構(gòu)來處理每條曲線的幾何斧蜕。當(dāng)我們將注意力限制在超奇異橢圓曲線（我們?cè)诖瞬粫?huì)定義）時(shí)，每條曲線都保證從其到其他超奇異曲線具有固定數(shù)量的同胚砚偶。

現(xiàn)在批销，考慮通過從我們的起始曲線檢查該形式的所有同基因洒闸，然后從這些曲線中檢查所有同基因來創(chuàng)建的圖，以此類推均芽。這個(gè)圖表在高度結(jié)構(gòu)化的意義上說丘逸，如果我們從第一條曲線開始隨機(jī)游走，擊中特定其他曲線的概率可以忽略不計(jì)（除非我們采取指數(shù)級(jí)的步驟）掀宋。在數(shù)學(xué)術(shù)語中深纲，我們說通過檢查所有這些同源生成的圖是一個(gè)擴(kuò)展圖（以及Ramanujan）。這種擴(kuò)展特性正是使基于同源的密碼學(xué)安全的原因劲妙。

對(duì)于超奇異同源 Diffie-Hellman（SIDH）方案湃鹊，密鑰是同源鏈，公鑰是曲線镣奋。當(dāng)Alice和Bob組合這些信息時(shí)涛舍，他們會(huì)獲得不同的曲線，但具有相同的不變量唆途。對(duì)于加密的目的而言，j-invariant不是那么重要掸驱，而是它是Alice和Bob完成密鑰交換后可以很容易地計(jì)算的數(shù)字肛搬。

與其他后量子方案相比，基于同源的密碼學(xué)具有極小的密鑰大小毕贼，僅使用330個(gè)字節(jié)用于公鑰温赔。不幸的是，在這篇文章中討論的所有技術(shù)中鬼癣，它們是最慢的陶贼，對(duì)于密鑰生成和共享秘密計(jì)算都需要11-13毫秒。然而待秃，他們確實(shí)支持完美的前向保密拜秧，這不是其他后量子密碼系統(tǒng)所擁有的。

基于Hash的簽名

已經(jīng)有許多基于哈希的簽名的友好介紹章郁，所以我們對(duì)它們的討論相當(dāng)高級(jí)枉氮。簡(jiǎn)而言之，哈希簽名使用哈希函數(shù)的輸入作為密鑰并輸出作為公鑰暖庄。這些密鑰僅適用于一個(gè)簽名聊替，因?yàn)楹灻旧頃?huì)顯示密鑰的一部分∨嗬基于散列的簽名的極端低效導(dǎo)致區(qū)塊鏈?zhǔn)褂肕erkle樹來減少空間消耗（是的惹悄，比特幣中使用的相同Merkle樹）。

不幸的是肩钠，用哈希構(gòu)造KEM或公鑰加密方案是不可能的泣港。因此暂殖，基于散列的簽名不是完整的后量子密碼學(xué)的解決方案。而且爷速，它們不是空間有效的; 一種更有前途的簽名方案SPHINCS產(chǎn)生41kb的簽名和1kb的公鑰/私鑰央星。另一方面，基于散列的方案非潮苟快莉给，因?yàn)樗鼈冎恍枰?jì)算散列函數(shù)。它們還具有極強(qiáng)的安全性證據(jù)廉沮，完全基于存在具有抗沖突和抗圖像抗性的散列函數(shù)的假設(shè)颓遏。由于沒有任何跡象表明當(dāng)前廣泛使用的哈希函數(shù)（如SHA3或BLAKE2）容易受到這些攻擊，因此基于哈希的簽名是安全的滞时。

小貼士

后量子密碼學(xué)是一個(gè)令人難以置信又令人興奮的研究領(lǐng)域叁幢，在過去十年中已經(jīng)取得了巨大的增長(zhǎng)。雖然這篇文章中描述的四種類型的密碼系統(tǒng)已經(jīng)得到了很多學(xué)術(shù)上的關(guān)注坪稽，但是沒有一種被NIST批準(zhǔn)曼玩，因此不推薦用于一般用途。許多方案的原始形式不具備性能窒百，并且受到各種優(yōu)化的影響黍判，這些優(yōu)化可能會(huì)或可能不會(huì)影響安全性。實(shí)際上篙梢，已經(jīng)證明多次嘗試為McEliece系統(tǒng)使用更節(jié)省空間的代碼是不安全的顷帖。就目前而言，從后量子密碼系統(tǒng)中獲得最佳安全性需要犧牲一些空間或時(shí)間渤滞”岫眨基于環(huán)形點(diǎn)陣的密碼學(xué)是靈活性方面最有前途的工作途徑（簽名和KEM，也是完全同態(tài)加密）妄呕，但它所基于的假設(shè)僅在幾年內(nèi)得到了強(qiáng)烈的研究√瘴瑁現(xiàn)在，最安全的賭注是使用McEliece和Goppa代碼趴腋，因?yàn)樗呀?jīng)經(jīng)受了數(shù)十年的密碼分析吊说。

*本文由Trailofbits團(tuán)隊(duì)首發(fā)于blog，由獵豹區(qū)塊鏈安全團(tuán)隊(duì)翻譯與編輯*

獵豹區(qū)塊鏈安全以金山毒霸的技術(shù)為依托优炬，結(jié)合人工智能颁井、nlp等技術(shù)，為區(qū)塊鏈用戶提供合約審計(jì)蠢护、情感分析等生態(tài)安全服務(wù)雅宾。

Ratingtoken官網(wǎng)：https://www.ratingtoken.io/?from=z