后量子密碼的發(fā)展趨勢(shì)研究

摘要

密碼是保障網(wǎng)絡(luò)通信安全的堡壘，隨著量子計(jì)算的出現(xiàn)，經(jīng)典密碼體制在維護(hù)信息安全方面面臨著巨大的挑戰(zhàn)。目前，后量子密碼算法是理論上證明可保障量子環(huán)境下通信安全的新型密碼方案。通過(guò)分析現(xiàn)有量子計(jì)算技術(shù)與后量子密碼方案設(shè)計(jì)的研究進(jìn)展，強(qiáng)調(diào)后量子密碼研究的緊迫感，表明后量子密碼的研究在信息安全中的重要性，最后指出后量子密碼下一步可能的研究方向，為我國(guó)后量子密碼技術(shù)研究提供參考。

古有飛鴿，現(xiàn)有網(wǎng)絡(luò)，在以知識(shí)經(jīng)濟(jì)為基礎(chǔ)的信息化社會(huì)中，保障網(wǎng)絡(luò)信息安全無(wú)疑成為國(guó)與國(guó)之間無(wú)形的武器。歷史上，圖靈發(fā)明電子計(jì)算機(jī)破譯了密碼機(jī)，打破了國(guó)家之間信息安全的屏障。此后在經(jīng)典計(jì)算機(jī)上，人們通過(guò)設(shè)計(jì)基于數(shù)學(xué)上 NP 難問(wèn)題的加解密算法，維護(hù)了近 50 年的網(wǎng)絡(luò)信息與通信安全。但是，1982年 Feynman首次提出將量子力學(xué)與計(jì)算機(jī)相結(jié)合的構(gòu)想，開(kāi)辟了量子時(shí)代的新紀(jì)元。1985 年Deutsch進(jìn)一步闡述了量子計(jì)算機(jī)的基本概念，并證實(shí)了在某些方面，量子計(jì)算機(jī)相比經(jīng)典計(jì)算機(jī)而言確實(shí)具有更強(qiáng)大的功能。1994 年 Shor給出了一個(gè)能夠在多項(xiàng)式時(shí)間內(nèi)解決大整數(shù)分解和離散對(duì)數(shù)問(wèn)題的 Shor 量子算法。至此，人們察覺(jué)到在功能強(qiáng)大的量子計(jì)算機(jī)面前，現(xiàn)有密碼技術(shù)搭成的“城墻”是如此的“不堪一擊”，因此設(shè)計(jì)研究能夠抵抗量子計(jì)攻擊的下一代加密算法也變得迫在眉睫。

1

量子計(jì)算機(jī)的發(fā)展現(xiàn)狀

20 世紀(jì)后期，量子計(jì)算機(jī)作為量子力學(xué)與計(jì)算機(jī)技術(shù)相結(jié)合的重要成果而備受?chē)?guó)際關(guān)注。鑒于其具有實(shí)際的戰(zhàn)略意義，世界各國(guó)都高度重視并不斷加大投入，通過(guò)陸續(xù)制定各種政策、建立一系列的研究機(jī)構(gòu)、啟動(dòng)各類(lèi)項(xiàng)目來(lái)支持量子計(jì)算機(jī)的研究，推動(dòng)了量子科技研發(fā)和技術(shù)產(chǎn)業(yè)的蓬勃發(fā)展。美國(guó)政府在此領(lǐng)域率先行動(dòng)，斥巨資推出了 5 個(gè)專(zhuān)門(mén)針對(duì)量子計(jì)算機(jī)的研究計(jì)劃，分別是由美國(guó)國(guó)防高級(jí)研究計(jì)劃局提出的“量子信息科學(xué)與技術(shù)發(fā)展規(guī)劃”、由美國(guó)國(guó)家安全局指導(dǎo)的 ARDA5 計(jì)劃、以美國(guó)科學(xué)基金會(huì)為依托的 QuBIC 計(jì)劃、由美國(guó)宇航局領(lǐng)導(dǎo)部署的 QCTG 計(jì)劃以及美國(guó)國(guó)家標(biāo)準(zhǔn)與技 術(shù) 研 究 院（National Institute of Standards and Technology，NIST）指揮的PLQI計(jì)劃。除此之外，歐盟、加拿大、中國(guó)等組織、國(guó)家和地區(qū)在量子計(jì)算機(jī)領(lǐng)域的研究也做出積極響應(yīng)并取得了一系列的研究成果。

2001 年， 一 個(gè) 由 IBM 公司成功研發(fā)的 7qubit 的示例性量子計(jì)算機(jī)成功領(lǐng)跑了該領(lǐng)域的研究。2007 年，中國(guó)科學(xué)家潘建偉首次在量子計(jì)算機(jī)上實(shí)現(xiàn)了 Shor 量子分解算法 ，該成果標(biāo)志著中國(guó)光學(xué)量子計(jì)算機(jī)的研究在國(guó)際上已經(jīng)達(dá)到了先進(jìn)水平。2008 年，加拿大的 D-wave公司對(duì)已有量子計(jì)算機(jī)系統(tǒng)進(jìn)行改進(jìn)并成功將運(yùn)算位數(shù)提高到 48 qubit。2010 年，英國(guó)布里斯托爾大學(xué)開(kāi)發(fā)出了一種新的光子芯片，該芯片速度更快、存儲(chǔ)量更大，為量子計(jì)算機(jī)的信息存儲(chǔ)提供了新的思路。同年，潘建偉團(tuán)隊(duì)與清華大學(xué)組成的聯(lián)合小組通過(guò)研究量子隱形傳態(tài)技術(shù)的特點(diǎn)，成功實(shí)現(xiàn)了世界上最遠(yuǎn)距離的量子傳輸 并將該研究成果發(fā)表在國(guó)際權(quán)威雜志 Nature Photonics 上，該成果向全球展示了基于量子計(jì)算機(jī)的量子通信網(wǎng)絡(luò)實(shí)現(xiàn)的可行性。與此同時(shí)，杜江峰教授在 Nature 上發(fā)表了一篇關(guān)于保持固態(tài)自旋比特的量子相干性研究的論文，該成果對(duì)固態(tài)自旋量子計(jì)算機(jī)的實(shí)現(xiàn)具有重要意義。后來(lái)，英國(guó)和澳大利亞的聯(lián)合研究小組設(shè)計(jì)了一種稱(chēng)為 FTQC 的容錯(cuò)量子計(jì)算方案，該方案的提出奠定了量子計(jì)算機(jī)走向?qū)嵱没幕A(chǔ)。

隨著量子計(jì)算技術(shù)與硬件設(shè)備材料的飛速發(fā)展，人們愈發(fā)堅(jiān)信量子計(jì)算機(jī)走向現(xiàn)實(shí)欠缺的不再是技術(shù)原因，而是時(shí)間的沉淀，借此各國(guó)加快針對(duì)量子計(jì)算機(jī)的研究腳步。2016 年，中國(guó)在“十三五”規(guī)劃中明確設(shè)立關(guān)于“量子通信與量子計(jì)算機(jī)”的重大科研項(xiàng)目 。同年，Shor 量子分解算法成功運(yùn)行在潘建偉團(tuán)隊(duì)研究的光量子計(jì)算機(jī)上，為紀(jì)念這一研究成果，發(fā)射了國(guó)際上第一顆名為“墨子號(hào)”的量子衛(wèi)星。2017 年，潘建偉團(tuán)隊(duì)自主研發(fā)的 10 bit 超導(dǎo)量子線(xiàn)路樣品成功實(shí)現(xiàn)了當(dāng)時(shí)世界上最大數(shù)目的超導(dǎo)量子比特糾纏和完整測(cè)量，在量子計(jì)算機(jī)的發(fā)展道路上又邁上了一個(gè)新的臺(tái)階。2018 年，歐盟正式啟動(dòng)“量子技術(shù)旗艦計(jì)劃”，該計(jì)劃擬在歐洲建設(shè)一個(gè)連接所有量子計(jì)算機(jī)、模擬器與傳感器的量子通信網(wǎng)絡(luò) 。2019 年， 谷歌團(tuán)隊(duì)在量子計(jì)算原型機(jī)“懸鈴木”上僅用了3 分 20 秒就完成了超級(jí)計(jì)算機(jī)一萬(wàn)年計(jì)算量的工作，該成果將量子計(jì)算機(jī)的處理能力又帶向新的高度，一定意義上實(shí)現(xiàn)了量子霸權(quán)。2020年，美國(guó)白宮網(wǎng)站發(fā)布的《美國(guó)量子網(wǎng)絡(luò)戰(zhàn)略構(gòu)想》提出，開(kāi)發(fā)一種由量子計(jì)算機(jī)和其他量子設(shè)備組成的量子互聯(lián)網(wǎng)的設(shè)想，并指出下一步的工作是使量子信息科學(xué)全民化。2021 年，中國(guó)提出了新的“十四五”規(guī)劃，指出這 5 年是中國(guó)量子技術(shù)實(shí)現(xiàn)“彎道超車(chē)”的關(guān)鍵時(shí)期，其目標(biāo)之一就是研制通用量子計(jì)算原型機(jī)和實(shí)用化量子模擬機(jī) 。同年 10 月，潘建偉團(tuán)隊(duì)與其他研究機(jī)構(gòu)合作，成功構(gòu)建了 113 個(gè)光子 144 種模式的量子計(jì)算原型機(jī)“九章二號(hào)”，實(shí)現(xiàn)了在高斯玻色取樣數(shù)學(xué)問(wèn)題上的快速求解。除此之外，潘建偉團(tuán)隊(duì)及其合作伙伴還成功研制出了66超導(dǎo)量子比特的“祖沖之二號(hào)”，相比于“懸鈴木”，在計(jì)算復(fù)雜度方面提高了 6 個(gè)數(shù)量級(jí)。2022 年，Huggins 等人在 Nature 上發(fā)表文章，將 QMC 方法與量子計(jì)算相結(jié)合，構(gòu)建了混合量子經(jīng)典計(jì)算模型，提供了一條實(shí)現(xiàn)實(shí)際量子優(yōu)勢(shì)的途徑，為實(shí)用化量子計(jì)算機(jī)的設(shè)計(jì)提供了理論基礎(chǔ)。

量子計(jì)算機(jī)的快速發(fā)展減少了高計(jì)算量問(wèn)題的處理時(shí)間，解決了大量復(fù)雜的數(shù)學(xué)問(wèn)題，給當(dāng)前已經(jīng)發(fā)展成熟并且應(yīng)用廣泛的現(xiàn)代公鑰密碼體制帶來(lái)了巨大的威脅與嚴(yán)峻的挑戰(zhàn)。然而，保障量子計(jì)算機(jī)下網(wǎng)絡(luò)安全與信息系統(tǒng)安全的重點(diǎn)在于密碼技術(shù)的發(fā)展，因此，在量子信息時(shí)代來(lái)臨之前，設(shè)計(jì)能夠有效抵御量子計(jì)算機(jī)攻擊的新型密碼體制就成了密碼學(xué)家們不得不面對(duì)的問(wèn)題之一。

2

抵御量子威脅時(shí)不我待

2.1抵御量子威脅的戰(zhàn)略意義

密碼技術(shù)是維護(hù)信息安全的重中之重，大量應(yīng)用于國(guó)家保密系統(tǒng)和大型國(guó)防裝備。一旦量子計(jì)算機(jī)問(wèn)世，現(xiàn)代密碼學(xué)中基于大整數(shù)分解、離散對(duì)數(shù)問(wèn)題設(shè)計(jì)的公鑰密碼將被攻破，直接威脅到當(dāng)前黨政軍民領(lǐng)域的網(wǎng)絡(luò)與信息安全，甚至威脅國(guó)家安全。

在軍事方面，“先存儲(chǔ)后破譯”是破解當(dāng)前密碼系統(tǒng)的一個(gè)重要戰(zhàn)略，即一些組織將現(xiàn)在無(wú)法破譯的信息先存儲(chǔ)起來(lái)，等到日后時(shí)機(jī)成熟再進(jìn)行破譯，如果按照“摩爾定律”的規(guī)律來(lái)看，這個(gè)成熟的時(shí)機(jī)很可能在非常長(zhǎng)的時(shí)間內(nèi)都不可能來(lái)臨，而量子計(jì)算的出現(xiàn)，加快了成熟時(shí)機(jī)的到來(lái)，對(duì)長(zhǎng)期保密性以及前向安全性都造成了致命的威脅。通常，在國(guó)家軍隊(duì)與許多重要機(jī)構(gòu)的設(shè)備中存儲(chǔ)了大量的國(guó)家安全情報(bào)，這些情報(bào)需要保存十幾年甚至更長(zhǎng)的時(shí)間不能被破解，由此可見(jiàn)，量子計(jì)算的出現(xiàn)將直接威脅到國(guó)家重要情報(bào)的安全，因此必須盡快研制出能夠抵抗量子計(jì)算機(jī)的新型加密體制，以最大限度地解除該隱患。

在日常通信方面，許多關(guān)鍵的通信協(xié)議大多以公鑰加密、數(shù)字簽名和密鑰交換為依托，然而這些公鑰密碼學(xué)算法基于的特定數(shù)論難題的困難性在量子計(jì)算面前“不值一提”，一旦量子計(jì)算機(jī)實(shí)用化，這些通信協(xié)議將紛紛變得不再安全，無(wú)法保障端到端的安全傳輸。

2.2密碼算法的實(shí)用化需要時(shí)間孵化

任何一個(gè)密碼算法的設(shè)計(jì)都是為了最終遷移到工程化。從現(xiàn)代密碼算法理論技術(shù)發(fā)展成熟到最終的標(biāo)準(zhǔn)化，人們花費(fèi)了近 20 年的時(shí)間才構(gòu)造出一套完整的公鑰密碼系統(tǒng)基礎(chǔ)設(shè)施。即使新型密碼算法的理論技術(shù)已經(jīng)發(fā)展成熟，但將現(xiàn)在廣泛應(yīng)用的密碼系統(tǒng)逐步轉(zhuǎn)化為能夠抵抗量子計(jì)算機(jī)攻擊的新型密碼系統(tǒng)也需要大量時(shí)間，更何況現(xiàn)在能夠抵抗量子計(jì)算機(jī)攻擊的新型密碼算法的理論技術(shù)還未發(fā)展成熟。因此，不管量子時(shí)代何時(shí)到來(lái)，盡快采取行動(dòng)設(shè)計(jì)新型密碼方案，保障量子計(jì)算機(jī)信息與通信系統(tǒng)的安全都十分必要。

3

全球守護(hù)量子時(shí)代下的信息安全

沿襲經(jīng)典計(jì)算機(jī)中設(shè)計(jì)公鑰密碼算法的思路，目前國(guó)際上應(yīng)對(duì)量子計(jì)算機(jī)攻擊的后量子密 碼（Post-Quantum Cryptography，PQC）算法主要集中在尋找一類(lèi)或多類(lèi)在量子計(jì)算機(jī)上多項(xiàng)式時(shí)間內(nèi)不可解的數(shù)學(xué)困難問(wèn)題。根據(jù)這些困難問(wèn)題設(shè)計(jì)出的 PQC 算法可以在一定程度上抵抗量子計(jì)算機(jī)的攻擊，守護(hù)量子信息時(shí)代下的通信安全。全球針對(duì) PQC 算法的研究主要集中在兩個(gè)方面：國(guó)際學(xué)術(shù)交流和算法標(biāo)準(zhǔn)化的建立。

3.1后量子密碼理論的國(guó)際學(xué)術(shù)交流

作為密碼學(xué)領(lǐng)域的分支，國(guó)際 PQC 理論和技術(shù)的研究一直以來(lái)都受到了各國(guó)關(guān)注，相關(guān)的學(xué)術(shù)交流活動(dòng)的數(shù)量和頻度逐年遞增，其影響范圍向更多的國(guó)家和領(lǐng)域輻射。

2006 年， 國(guó) 際 密 碼 研 究 協(xié) 會(huì) 舉 辦 了 第 一屆后量子密碼技術(shù)國(guó)際會(huì)議，該會(huì)議討論了PQC 在未來(lái)的研究中可能存在的潛在領(lǐng)域。此后，這項(xiàng)會(huì)議分別在北美、歐洲、東亞等多個(gè)地區(qū)連續(xù)舉辦，并通過(guò)在相鄰會(huì)議間隙舉辦夏季或冬季培訓(xùn)營(yíng)的方式，促進(jìn)了各國(guó)研究者之間的交流，增強(qiáng)了 PQC 技術(shù)的發(fā)展。

2011 年， 美 國(guó) 安 全 創(chuàng) 新 公 司 注 冊(cè) 并 擁 有NTRU 算法的專(zhuān)利，自此，該公司設(shè)計(jì)并開(kāi)發(fā)了多種 NTRU 算法實(shí)現(xiàn)的軟件庫(kù)。2013 年，歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)與加拿大滑鐵盧大學(xué)量子計(jì)算中心聯(lián)合舉辦了量子安全密碼工作組會(huì)議（IQC/ETSI Quantum-Safe Crypto Workshop），參會(huì)代表來(lái)自密碼學(xué)、數(shù)學(xué)、物理學(xué)、計(jì)算機(jī)等多個(gè)不同的研究領(lǐng)域，目標(biāo)是部署下一代密碼基礎(chǔ)設(shè)施，特別是抵御量子計(jì)算帶來(lái)的沖擊。2015 年 1 月，歐盟啟動(dòng) PQC 算法 SAFECRYPTO 應(yīng)用項(xiàng)目。借助歐洲多所企業(yè)、高校和研究機(jī)構(gòu)的力量，相繼開(kāi)展了 PQCRYPTO 項(xiàng)目 和 PROMETHEUS 項(xiàng)目，并將 PQCRYPTO 項(xiàng)目納入歐盟地平線(xiàn) 2020計(jì)劃，致力于打造新一代安全實(shí)用的 PQC 方案。2016 年 4 月，微軟公司開(kāi)發(fā)出了基于格上的困難問(wèn)題 RLWE 的格密碼庫(kù)（Lattice Crypto），微軟公司表示攻擊者無(wú)論是使用經(jīng)典計(jì)算機(jī)還是量子計(jì)算機(jī)，該軟件庫(kù)至少能夠?qū)崿F(xiàn) 128 位的安全性能。同年 7 月，谷歌公司宣布將開(kāi)始進(jìn)行 PQC 技術(shù)的測(cè)試活動(dòng)，并表明本次測(cè)試對(duì)象為基于RLWE問(wèn)題的密鑰交換協(xié)議。2019年1月，谷歌宣布將部署一種稱(chēng)為組合橢圓曲線(xiàn)和后量子密鑰交換（CECPQ2）的新的傳輸層安全性協(xié)議（Transport Layer Security，TLS）密鑰交換方法。同時(shí)，谷歌和 Cloudflare 將合作探索 PQC 如何在實(shí)踐中擊敗超文本傳輸安全協(xié)議（Hypertext Transfer Protocol Secure，HTTPS）連接。2022 年4 月，IBM 公司發(fā)布了首個(gè)基于格理論研發(fā)的量子安全系統(tǒng)——IBMz16。

亞洲密碼學(xué)研究者在后量子相關(guān)技術(shù)的發(fā)展中也在積極跟進(jìn)。2016 年 6 月，首屆亞洲后量 子 密 碼 論 壇（PQCAsia Forum）在我國(guó)成都順利召開(kāi)。鑒于 PQC 算法的飛速發(fā)展，原定于2017 年召開(kāi)的第二屆亞洲后量子密碼論壇提前到 2016 年 11 月于韓國(guó)首爾大學(xué)召開(kāi)。2020—2021 年，丁津泰所帶領(lǐng)的團(tuán)隊(duì)先后破解了兩個(gè)NIST 抗量子數(shù)字簽名候選方案，包括 Luov 和GeMMS，并將研究成果發(fā)表在 2020 年“歐洲密碼學(xué)年會(huì)”和 2021 年“美國(guó)密碼學(xué)年會(huì)”上。2022 年，上海交通大學(xué)的谷大武教授領(lǐng)導(dǎo)的LoCCS 實(shí)驗(yàn)室成功破解了 80 維格的容錯(cuò)學(xué)習(xí)問(wèn)題（Learning With Errors，LWE），創(chuàng)造了格密碼中困難問(wèn)題求解新的世界紀(jì)錄，同時(shí)該紀(jì)錄已經(jīng)在格密碼挑戰(zhàn)的官方網(wǎng)站 LWE Challenge上進(jìn)行了公布。

3.2后量子密碼方案的標(biāo)準(zhǔn)化建立

目前，全球已經(jīng)有眾多國(guó)家意識(shí)到未來(lái)量子攻擊對(duì)網(wǎng)絡(luò)安全帶來(lái)的潛在威脅，也已采取必要行動(dòng)和相關(guān)部署來(lái)應(yīng)對(duì)此威脅。類(lèi)似于現(xiàn)代密碼學(xué)中 DES、AES、RSA、ElGamal 等加密算法標(biāo)準(zhǔn)，在 PQC 理論的研究過(guò)程中，標(biāo)準(zhǔn)化的建立也逐步發(fā)展起來(lái)，越來(lái)越多的國(guó)際參與者紛紛加入 PQC 方案標(biāo)準(zhǔn)化建立的研究中。

3.2.1美國(guó)后量子密碼標(biāo)準(zhǔn)化計(jì)劃

早 在 2008 年，NTRU 加密算法就已經(jīng)被美國(guó)電氣和電子工程師協(xié)會(huì)確定為正式標(biāo)準(zhǔn)（Std1363.1—2008）。2010 年，其又被認(rèn)可標(biāo)準(zhǔn) 委 員 會(huì)（Accredited Standards Committee X9）批準(zhǔn)為可用于數(shù)據(jù)防護(hù)的新型加密標(biāo)準(zhǔn)。同時(shí)，美國(guó)國(guó)家標(biāo)準(zhǔn)學(xué)會(huì) X9.98 標(biāo)準(zhǔn)（ANSIX9.98）明確了在金融交易過(guò)程中如何使用基于諸如 NTRU等格加密算法的公私鑰加密系統(tǒng)。

2015 年 8 月，美國(guó)國(guó)家安全局宣布對(duì)當(dāng)前美國(guó)政府所使用的“密碼算法 B 套件”進(jìn)行安全性升級(jí)，升級(jí)的算法將用于后量子時(shí)代過(guò)渡期的加密標(biāo)準(zhǔn)。2016 年 4 月，NIST 頒布“后量子密碼學(xué)”研究報(bào)告 ，并宣布將啟動(dòng) PQC算法標(biāo)準(zhǔn)計(jì)劃。截至 2017 年 12 月，NIST 共收到來(lái)自全球共 82 份候選密碼方案，自此開(kāi)啟了后量子密碼學(xué)標(biāo)準(zhǔn)協(xié)議的第一輪預(yù)選。2019年 1 月，NIST 揭曉第二輪的標(biāo)準(zhǔn)方案，本輪共有 26 個(gè)密碼方案脫穎而出，其中包括 17 個(gè)公鑰加密 / 密鑰交換方案和 9 個(gè)數(shù)字簽名方案。按照密碼方案的構(gòu)造方式來(lái)看，這 26 個(gè)候選算法中包括 12 個(gè)格密碼，7 個(gè)基于編碼的密碼，4 個(gè)基于多變量的密碼，2 個(gè)基于哈希的密碼和1 個(gè)基于同源曲線(xiàn)的密碼。2021 年 1 月，NIST公布的第三輪候選算法中包括 7 個(gè)決賽入選方案和 8 個(gè)備選方案，在這 7 個(gè)決賽入選方案中，有 5 個(gè)都是格密碼，這說(shuō)明當(dāng)前格密碼在所有的 PQC 算法中占據(jù)較大的優(yōu)勢(shì)，是未來(lái)最有望成為標(biāo)準(zhǔn)化的算法。2022 年 3 月，麻省理工學(xué)院與阿布扎比技術(shù)創(chuàng)新研究所合作編寫(xiě)并出版了《從今天起，直面明天的量子黑客》（Facing Tomorrow’s Quantum Hackers Today）。該報(bào)告對(duì)全球量子計(jì)算公司中的密碼學(xué)家、數(shù)學(xué)家、物理學(xué)家和高級(jí)管理人員進(jìn)行采訪，評(píng)估了一臺(tái)成熟的量子黑客計(jì)算機(jī)對(duì)如今網(wǎng)絡(luò)安全系統(tǒng)的威脅與影響，并在此基礎(chǔ)上分析了應(yīng)對(duì)威脅的解決方案，這意味著 NIST 標(biāo)準(zhǔn)化即將進(jìn)入第四輪。2022 年 7 月，NIST 已完成第三輪 PQC 標(biāo)準(zhǔn)化過(guò)程，共有 4 個(gè)候選算法被選中標(biāo)準(zhǔn)化，分別是 CRYSTALS-KYBER、CRYSTALS-Dilithium、FALCON 和 SPHINCS+，另外還有 4 種算法將繼續(xù)進(jìn)入第四輪，這一里程碑事件意味著持續(xù)6 年的標(biāo)準(zhǔn)化工作終于進(jìn)入了最后階段。

3.2.2歐洲后量子密碼標(biāo)準(zhǔn)化計(jì)劃

首先，在 NIST-PQC 算法的征集過(guò)程中，歐洲研究團(tuán)隊(duì)做出了重大的貢獻(xiàn)，在 NIST 發(fā)布的第二輪 26 個(gè)標(biāo)準(zhǔn)方案中，歐洲主導(dǎo)和參與的高達(dá) 20 多個(gè)。其次，歐洲量子密碼學(xué)術(shù)和工業(yè)界研究者聯(lián)合組織的 PQCrypto 項(xiàng)目于 2015 年發(fā)布了一份初始報(bào)告，該報(bào)告在加密算法、對(duì)稱(chēng)授權(quán)以及簽名系統(tǒng)等多個(gè)領(lǐng)域都提出了相關(guān)的標(biāo)準(zhǔn)化建議，并指出 McEliece 密碼系統(tǒng)具有發(fā)展成為替代 RSA/ECC 密碼系統(tǒng)的潛力。此外，歐洲電信標(biāo)準(zhǔn)協(xié)會(huì) ETSI 成立的“量子安全密碼工業(yè)標(biāo)準(zhǔn)工作組”主要負(fù)責(zé) PQC 算法的征集、評(píng)估以及工業(yè)標(biāo)準(zhǔn)的制定，該組織每年發(fā)布一本“量子安全白皮書(shū)”，用以公布后量子密碼研究的最新進(jìn)展。

3.2.3日本后量子密碼標(biāo)準(zhǔn)化計(jì)劃

為應(yīng)對(duì)量子計(jì)算攻擊和對(duì)加密設(shè)備的物理攻擊（例如功率分析），日本推出了 CREST 密碼數(shù)學(xué)項(xiàng)目，旨在為下一代加密系統(tǒng)的開(kāi)發(fā)奠定基礎(chǔ)。CREST 項(xiàng)目每年舉辦的后量子安全的相關(guān)會(huì)議，為日本后量子密碼學(xué)研究者交流重要成果提供了平臺(tái)。在真正的 PQC 標(biāo)準(zhǔn)公布之前，日本密碼研究與評(píng)估委員會(huì)列出了 3 個(gè)密碼清單：電子政務(wù)推薦密碼清單、候選推薦密碼清單和監(jiān)控密碼清單，并指出將啟動(dòng)最新制定的 PQC 指南。

3.2.4韓國(guó)后量子密碼標(biāo)準(zhǔn)化計(jì)劃

為及時(shí)跟進(jìn)國(guó)際后量子標(biāo)準(zhǔn)化工作，韓國(guó)于 2022 年推出了全球首個(gè)可防御量子計(jì)算機(jī)黑客攻擊的 PQC 專(zhuān)線(xiàn)，目前，該線(xiàn)路已經(jīng)過(guò)電信技術(shù)協(xié)會(huì)的測(cè)試和驗(yàn)證。

3.2.5中國(guó)后量子密碼標(biāo)準(zhǔn)化計(jì)劃

雖然中國(guó)在PQC標(biāo)準(zhǔn)化的研究中起步較晚，但在 NIST-PQC 算法征集活動(dòng)中也參與并貢獻(xiàn)了一定的力量。參與設(shè)計(jì)的中國(guó)團(tuán)隊(duì)包括密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室、上海交通大學(xué)、復(fù)旦大學(xué)、中科院信工所以及中國(guó)臺(tái)灣地區(qū)“中央研究院”等。其中，由中國(guó)科學(xué)院數(shù)據(jù)與通信保護(hù)研究教育中心設(shè)計(jì)的 LAC 算法，與歐洲、美國(guó)、加拿大等國(guó)家提供的 PQC 算法一起，入選了 NIST 第二輪 PQC 密碼算法名單。除此之外，中國(guó)在國(guó)內(nèi) PQC 算法標(biāo)準(zhǔn)的征集活動(dòng)中也做了一些工作。自 2019 年起，中國(guó)密碼學(xué)會(huì)（Chinese Association for Cryptologic Research，CACR）開(kāi)始舉辦全國(guó)密碼算法設(shè)計(jì)競(jìng)賽 ，該競(jìng)賽僅面向中國(guó)的密碼學(xué)者，受到了廣大密碼學(xué)家的青睞，并在公鑰密碼組的參賽作品中征集到大量的 PQC 算法。該競(jìng)賽的成功舉辦推動(dòng)了我國(guó)密碼理論與應(yīng)用技術(shù)的發(fā)展，是我國(guó)在 PQC 算法標(biāo)準(zhǔn)制定過(guò)程中的基礎(chǔ)，意味著我國(guó) PQC 技術(shù)的研究正逐步向國(guó)際先進(jìn)水平看齊，致力于通過(guò)充分調(diào)動(dòng)國(guó)內(nèi)各界研究力量，推動(dòng)國(guó)產(chǎn)化研發(fā)，保障未來(lái)后量子時(shí)代下我國(guó)的網(wǎng)絡(luò)空間安全。

綜上所述，從世界各國(guó)政府對(duì)該領(lǐng)域的投入與支持力度來(lái)看，在真正的量子信息時(shí)代到來(lái)之前，全球的目標(biāo)均是在量子通信網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信與安全認(rèn)證。

4

后量子密碼的構(gòu)造方式

在 PQC 算 法 的 設(shè) 計(jì) 方 案 中， 大 多 還 是 基于數(shù)學(xué)困難問(wèn)題的難解性，目前主流數(shù)學(xué)困難問(wèn)題主要包括格、編碼、哈希以及多變量。除此之外，基于超奇異橢圓曲線(xiàn)、量子隨機(jī)漫步等技術(shù)的 PQC 構(gòu)造方法以及較大密鑰長(zhǎng)度的對(duì)稱(chēng)密碼算法也被認(rèn)為是量子計(jì)算機(jī)條件下相對(duì)安全的。

4.1基于格的后量子密碼算法

格（lattice）是一種數(shù)學(xué)結(jié)構(gòu)，定義為一組線(xiàn)性無(wú)關(guān)的非零向量（稱(chēng)作格基）的整系數(shù)線(xiàn)性組合。具體來(lái)說(shuō)，給定一組格基對(duì)任意的整數(shù)都是屬于這個(gè)格的向量，其中 n 稱(chēng)為格的維數(shù)。對(duì)于同一個(gè)格，其可以擁有不同的格基，并且求解格中的最短向量問(wèn)題（Shortest Vector Problem，SVP）和最近向量問(wèn)題（Closest Vector Problem，CVP）是目前格理論中主要的非確定性多項(xiàng)式難題（Nondeterministic Polynomially problem，NP）。除此之外，格中還有一些其他的困難問(wèn)題，比如 LWE 問(wèn)題、有界距離解碼問(wèn)題、小整數(shù)解問(wèn)題、gap-SVP 問(wèn)題等，因此，基于格的 PQC 算法大多依托這些困難問(wèn)題而設(shè)計(jì)，但其本質(zhì)上又都可以轉(zhuǎn)化為 SVP 困難問(wèn)題和 CVP 困難問(wèn)題?；诟竦乃惴ㄅc現(xiàn)代公鑰加密算法的功能一樣，均可實(shí)現(xiàn)加解密、數(shù)字簽名、屬性加密、同態(tài)加密、密鑰交換等多種密碼學(xué)構(gòu)造。

第一個(gè)基于格的密碼方案是 1997 年由 Ajtai等人提出的 Ajtai-Dwork 密碼體制，該方案利用格問(wèn)題中 Worst-case 到 Average-case 的規(guī)約來(lái)抵抗量子計(jì)算的攻擊。第一個(gè)基于格的實(shí)用的密碼方案是 1998 年由 Hoffstein 等人提出的 NTRU 公鑰加密體制，該方案堅(jiān)持到了 NIST第三輪的候選算法中，并且目前已經(jīng)應(yīng)用在某些商用的密碼設(shè)備中，有望日后代替 RSA 加密算法。

在后量子加解密算法方面，通過(guò)總結(jié)目前主流的基于格的加解密算法，我們發(fā)現(xiàn)以 LWE困難問(wèn)題為基礎(chǔ)的格密碼方案不僅應(yīng)用廣泛，而 且 安 全 性 更 高。以 NIST 第四輪入選算法CRYSTALS-Kyber 為例，該算法基于的困難問(wèn)題是 M-LWE 問(wèn)題，即 LWE 問(wèn)題與 R-LWE 問(wèn)題的組合，該問(wèn)題相比于 LWE 問(wèn)題而言具有易于擴(kuò)展和效率高的優(yōu)點(diǎn)。M-LWE 問(wèn)題的主要思想是對(duì)于在多項(xiàng)式環(huán)中均勻隨機(jī)選取的與經(jīng)過(guò)公式計(jì)算得到的 是不可區(qū)分的，其中中s 和是從二項(xiàng)分布中隨機(jī)均勻選取的，該問(wèn)題的主要困難性在于根據(jù)已知無(wú)法計(jì)算 s 和 中的任意一個(gè)。Kyber 算法就是利用此原理，通過(guò)公式生成公私鑰對(duì) (t,s)，達(dá)到已知公鑰 t 后無(wú)法計(jì)算私鑰 s 的效果，此后再對(duì)通信的明文信息進(jìn)行加密或者對(duì)通信雙方的臨時(shí)會(huì)話(huà)密鑰進(jìn)行封裝。以 2020 年提交的第三版 Kyber算法為例，表 1 闡述了選擇明文攻擊下的不可區(qū)分性（IND-CPA）安全的 Kyber 算法的具體實(shí)現(xiàn)思路，表 2 闡述了自適應(yīng)選擇密文攻擊下的密文不可識(shí)別性（IND-CCA2）安全的 Kyber 算法的具體實(shí)現(xiàn)思路。

表 1 Kyber 算法實(shí)現(xiàn)過(guò)程（IND-CPA 安全）

表 2 Kyber 算法實(shí)現(xiàn)過(guò)程（IND-CCA2 安全）

在后量子簽名算法方面，基于格的簽名算法的構(gòu)造與現(xiàn)有的公鑰密碼體制略有不同。對(duì)于 RSA、ElGamal、橢圓曲線(xiàn)等現(xiàn)有公鑰密碼體制而言，通過(guò)調(diào)換加解密算法的公私鑰順序即可將其轉(zhuǎn)換為簽名算法；但是基于格的密碼方案不具有此種對(duì)偶特性，在設(shè)計(jì)基于格的后量子簽名算法時(shí)通常采用零知識(shí)證明協(xié)議進(jìn)行構(gòu)造，即證明者證明自己擁有與對(duì)應(yīng)身份的公鑰相匹配的私鑰，但是不泄露任何關(guān)于私鑰的信息。

2008 年，Gentry 等人提出了 GPV 框架，該框架指出了基于格的簽名算法的設(shè)計(jì)思路，如表 3 所示。

表3GPV 框架

以 GPV 框架為基礎(chǔ)，基于格的簽名算法在進(jìn)行公私鑰對(duì)生成的過(guò)程中底層基于的困難問(wèn)題與后量子加解密算法類(lèi)似，即 LWE 問(wèn)題和SIS 問(wèn)題，同時(shí)為了便于簽名算法的實(shí)現(xiàn)，設(shè)計(jì)方案時(shí)大多借助 NTRU 格實(shí)例化 GPV 框架，并通過(guò)采樣完成數(shù)字簽名的創(chuàng)建，比如進(jìn)入 NIST第 四 輪 的 簽 名 算 法：FALCON 算 法。除 此 之外，另一個(gè)比較受歡迎的簽名算法 CRYSTALSDilithium 也進(jìn)入了 NIST 的第四輪中。

在具體的設(shè)計(jì)過(guò)程中，CRYSTALS-Dilithium和 FALCON 兩個(gè)算法針對(duì)算法本身的安全性和算法的運(yùn)行速度分別進(jìn)行了不同的改進(jìn)。其中 CRYSTALS-Dilithium 簽名算法在設(shè)計(jì)時(shí)采用Fiat-Shamir with Aborts 技術(shù)，該技術(shù)使用拒絕采樣的方式將基于格的 Fiat-Shamir 方案變得更加緊湊且安全；由于傳統(tǒng)的簽名算法中高斯采樣難以高效且安全地實(shí)現(xiàn)，Dilithium 簽名算法改進(jìn)了采樣方式，僅通過(guò)均勻分布采樣就完成了簽名的創(chuàng)建；同時(shí)為減小公鑰的大小，Dilithium簽名算法采用分離高低階位的新技術(shù)將其縮小了兩倍以上。對(duì)于 FALCON 簽名算法，通過(guò)在采樣過(guò)程中應(yīng)用快速傅里葉采樣技術(shù)，并在算法內(nèi)部使用真正的高斯采樣器，由此保證了在無(wú)限簽名情況下 FALCON 算法的安全性，即密鑰信息的泄露可忽略不計(jì)；同時(shí)由于快速傅里葉采樣在實(shí)現(xiàn)過(guò)程中具有速度快的優(yōu)勢(shì)，使得FALCON 算法在普通計(jì)算機(jī)上每秒可以生成數(shù)千個(gè)有效的簽名，并且驗(yàn)簽過(guò)程相比其他簽名算法而言快將近 5~10 倍。關(guān)于 Dilithium 和 FALCON簽名算法的具體過(guò)程分別如表 4 和表 5 所示。

表 4Dilithium 簽名算法的實(shí)現(xiàn)過(guò)程

表 5FALCON 簽名算法的實(shí)現(xiàn)過(guò)程

格密碼的研究雖然起步較晚，但是其簡(jiǎn)單的結(jié)構(gòu)以及眾多高復(fù)雜度的數(shù)學(xué)困難問(wèn)題使其在后量子時(shí)代廣受各國(guó)學(xué)者的歡迎。自 2013 年起，格密碼的研究成果顯著增加，在基于格的密碼體制不斷改進(jìn)的過(guò)程中，密鑰尺寸不斷縮小、運(yùn)算速度不斷提高，逐步在安全性、密鑰尺寸以及計(jì)算速度上達(dá)到更好的平衡。2022 年7 月入選 NIST 第四輪的后量子密碼中有 3 個(gè)基于格設(shè)計(jì)的密碼方案，由此足以見(jiàn)得盡管格密碼仍處于發(fā)展階段，但目前其已經(jīng)被認(rèn)為是最有前景的后量子密碼算法之一。

4.2基于編碼的后量子密碼算法

編碼理論是數(shù)學(xué)與計(jì)算機(jī)科學(xué)的一個(gè)分支，用來(lái)處理在噪聲信道中傳送信息時(shí)進(jìn)行錯(cuò)誤處理?；诰幋a的密碼體制也被認(rèn)為是在量子計(jì)算機(jī)中相對(duì)安全的密碼算法，其核心在于將一定數(shù)量的錯(cuò)誤碼字引入編碼中，糾正錯(cuò)誤碼字或計(jì)算校驗(yàn)矩陣的伴隨式是困難的。

一個(gè)較早提出且至今使用的基于編碼的加密算法是 1978 年 McEliece[27] 提出的 ClassicalMcEliece 公鑰加密方案，該方案使用隨機(jī)二進(jìn)制不可約的 Goppa 碼作為私鑰，記作 A，對(duì)私鑰 A使用可逆矩陣 S 和隨機(jī)置換矩陣 P 進(jìn)行 A'=SAP變換后得到的一般線(xiàn)性碼A'作為公鑰的一部分。最終 McEliece 公鑰加密方案的公鑰由 Goppa 碼的漢明重量 t 和矩陣 A' 組成，私鑰由生成矩陣A、可逆矩陣 S 和隨機(jī)置換矩陣 P 組成（方案的整體流程如表 6 所示）。該方案基于的困難問(wèn)題是對(duì)稱(chēng)群隱藏子群?jiǎn)栴}，也就是在加密過(guò)程中對(duì)明文信息 x 進(jìn)行的 y=y'+e=x×A'+e 操作中，從加入混淆 e（帶有 t 個(gè)錯(cuò)誤的向量）的矩陣 A'中反推 Goppa 碼是困難的。該算法相對(duì)于現(xiàn)有公鑰密碼體制而言加密速度快，但是由于其公鑰尺寸過(guò)大，該算法并不是很實(shí)用化，不過(guò)針對(duì)該算法的改進(jìn)最終也進(jìn)入到了 NIST 第三輪的候選算法中。

表 6 McEliece 公鑰加密方案過(guò)程

此后，1986 年 Niederreiter 提出了一種基于GRS 碼的背包型公鑰密碼體制——Niederreiter密碼算法，該算法與 McEliece 不同的地方在于在密鑰生成過(guò)程中，當(dāng)確定私鑰 A（生成矩陣）后，借助可逆矩陣 M 和置換矩陣 P 通過(guò) A'=MHP操作來(lái)隱藏校驗(yàn)矩陣 H 而非生成矩陣 A，從而生成算法的公鑰 A'。為證明 Niederreiter 密碼算法的安全性，1994 年，王新梅等人 證明其在安全性方面與 McEliece 是等價(jià)的。

針對(duì)基于編碼的數(shù)字簽名方案而言，王新梅于 1990 年提出了第一個(gè)基于編碼的 Xinmei數(shù)字簽名方案。次年，李興元構(gòu)造了一類(lèi)同時(shí)具有簽名、加密和糾錯(cuò)能力的公鑰體制。隨后，學(xué)者們?cè)诖嘶A(chǔ)上進(jìn)行了一系列的改進(jìn)，并指出基于編碼的公鑰密碼體制或許可以成為基于數(shù)論的公鑰密碼體制的一個(gè)很好的替代。

4.3基于哈希的后量子密碼算法

基于 Hash 函數(shù)設(shè)計(jì)的后量子密碼算法主要集中在數(shù)字簽名算法中，Hash 函數(shù)具有一個(gè)很好的性質(zhì)就是抗碰撞性，當(dāng) Hash 函數(shù)能抗強(qiáng)碰撞時(shí)，設(shè)計(jì)的數(shù)字簽名算法便可有效抵抗量子計(jì)算的攻擊。在基于 Hash 函數(shù)的數(shù)字簽名算法中，具有代表性的是 1989 年 Merkle 從一次性簽名方案出發(fā)，借鑒 Lamport 和 Diffie 的工作，發(fā)明的 Merkle 數(shù)字簽名方案（MSS）。MSS 的基本思想是利用 Hash 樹(shù)將多個(gè)一次性驗(yàn)證密鑰（Hash樹(shù)的葉子）的有效性降低到一個(gè)公鑰（Hash樹(shù)的根）的有效性。由于其良好的抗強(qiáng)碰撞性，使得其可以有效抵抗量子計(jì)算的攻擊，因此，MSS 受到了學(xué)者們的青睞。從 2006 年舉辦的第一屆國(guó)際后量子密碼會(huì)議開(kāi)始，就不斷有人提出針對(duì) MSS 的改進(jìn)，例如 2006 年，Michael Szydlo提出了一種使 Merkle 樹(shù)的構(gòu)建更加有效和實(shí)用的方法；2008 年，基于 Szydlo’s 算法，JohannesBuchmann 等人提供了一種計(jì)算數(shù)字簽名機(jī)制中認(rèn)證路徑的新方法，并大大減少了最壞情況下算法的運(yùn)行時(shí)間；2011 年，Buchmann 等人 在 MSS 的基礎(chǔ)上提出了一種具有更小簽名的可證明安全的 XMSS 數(shù)字簽名方案。

在 MSS 的 研 究 之 外，2016 年，Targhi 等人估計(jì)出了尋找一個(gè)函數(shù)碰撞的量子查詢(xún)復(fù)雜度。2017 年，SPHINCS+ 算法被提交到 NIST PQC 競(jìng)賽中，經(jīng)過(guò)層層篩選，該算法進(jìn)入到了NIST 第三輪候選算法中，后續(xù)通過(guò)進(jìn)一步的安全性分析，該算法在 NIST 第四輪評(píng)估中脫穎而出，成為正式候選的簽名算法之一。SPHINCS+簽名算法采用了一種被稱(chēng)為 SPHINCS 超樹(shù)的結(jié)構(gòu)進(jìn)行構(gòu)造，SPHINCS 超樹(shù)是一種在 Merkle 樹(shù)和 Goldreich 樹(shù)之間相折中的結(jié)構(gòu)，其外層結(jié)構(gòu)是一個(gè) k 叉樹(shù)，一共有 d 層；k 叉樹(shù)的每個(gè)節(jié)點(diǎn)是一個(gè)高度為 h' 的 Merkle 樹(shù)，Merkle樹(shù)的每個(gè)子節(jié)點(diǎn)是一個(gè)密鑰，其中葉子節(jié)點(diǎn)用來(lái)給外層結(jié)構(gòu)的子節(jié)點(diǎn)生成公鑰，非葉子節(jié)點(diǎn)用來(lái)給 FORS 密鑰生成公鑰；外層結(jié)構(gòu)的葉子結(jié)點(diǎn)也是 Merkle 樹(shù)， 用 來(lái) 給 消 息 進(jìn) 行 簽 名。SPHINCS+ 簽名算法通過(guò)一個(gè)偽隨機(jī)數(shù)生成器和一個(gè)隨機(jī)種子構(gòu)造一個(gè) SPHINCS 超樹(shù)，然后根據(jù) SPHINCS 超樹(shù)生成公私鑰對(duì)。在進(jìn)行消息簽名時(shí)，首先計(jì)算消息 m 的哈希值 H(m)，然后取出 H(m) 的 h 個(gè)比特用來(lái)確定使用哪一個(gè) FORS密鑰，再取出 kα 個(gè)比特用于 FORS 簽名，最終將 SPHINCS 超樹(shù)從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)連在一起的簽名鏈作為消息 m 的簽名。在進(jìn)行簽名驗(yàn)證時(shí)，接收者依次驗(yàn)證簽名鏈上的每個(gè)簽名即可。

盡管目前基于 Hash 函數(shù)的數(shù)字簽名方案成果并不多，但是考慮 Hash 函數(shù)獨(dú)特的屬性及其實(shí)用性，在量子時(shí)代，基于 Hash 函數(shù)的簽名算法有望成為最有前途的數(shù)字簽名方案之一。

4.4基于多變量的后量子密碼算法

作為后量子密碼算法的最早成員之一，基于多變量的后量子密碼算法相比其他 3 種主流構(gòu)造方式而言具有更多的研究成果。一個(gè)基于多變量的公鑰密碼系統(tǒng)將有限域上一組二次多項(xiàng)式作為它的公鑰映射，其主要安全假設(shè)為求解有限域上非線(xiàn)性方程組這個(gè) NP 難問(wèn)題。

最早的多變量公鑰密碼體制由 Matsumoto 等人 于 1988 年提出，在隨后的 20 多年時(shí)間里，諸如清華大學(xué)丘成桐數(shù)學(xué)科學(xué)中心的丁津泰、日本的 Kohtaro Tadaki 和我國(guó)臺(tái)灣地區(qū)的 Bo-Yin Yang 等很多知名學(xué)者在多變量公鑰密碼領(lǐng)域展開(kāi)激烈討論并取得了不錯(cuò)的研究成果。2010 年以來(lái)，學(xué)者們針對(duì)多變量公鑰密碼體制的研究主要集中在 3 個(gè)方面：對(duì)包括加密、簽名等方案中基本理論的深入研究與改進(jìn)優(yōu)化，對(duì)類(lèi)似全同態(tài)加密（Fully Homomorphic Encryption，F(xiàn)HE）等熱點(diǎn)領(lǐng)域的重點(diǎn)攻關(guān)，對(duì)全新算法設(shè)計(jì)結(jié)構(gòu)的嘗試與探索。據(jù)統(tǒng)計(jì)，自 2006 年起，在全八屆國(guó)際后量子密碼會(huì)議收集的論文中，有 39%的論文是針對(duì)多變量密碼算法的設(shè)計(jì)與改進(jìn)[36]，遠(yuǎn)遠(yuǎn)高于基于其他方式設(shè)計(jì)的后量子密碼算法，由此可見(jiàn)多變量公鑰密碼體制在后量子時(shí)代的地位和意義。

在 眾 多 的 多 變 量 公 鑰 密 碼 體 制 中， 進(jìn) 入NIST 第三輪的多變量簽名算法就是由丁津泰教授于 2005 年設(shè)計(jì)的 Rainbow 數(shù)字簽名算法。該算法由于采用相對(duì)小的有限域以及基礎(chǔ)的邏輯運(yùn)算而具有較高的運(yùn)算速度，同時(shí)該算法相較于其他簽名算法而言因其較短的簽名長(zhǎng)度而更為實(shí)用。該算法采用非平衡油醋（Unbalanced Oil and Vinegar，UOV）體制創(chuàng)建簽名，核心是一個(gè)多層的 UOV 結(jié)構(gòu)的中心映射。UOV 體制是油 醋（Oil and Vinegar，OV） 體 制 的 擴(kuò) 展，OV體制在簽名過(guò)程中隨機(jī)選取一組醋變量代入油醋多項(xiàng)式中，然后結(jié)合簽名消息 m 求解一個(gè)關(guān)于油變量的線(xiàn)性方程組，而 UOV 體制是一種多層的油醋體制，即每一層都是油醋多項(xiàng)式，而且上一層的所有變量是下一層的醋變量。Rainbow數(shù)字簽名算法的具體流程如表 7 所示。

表 7 Rainbow 數(shù)字簽名算法的實(shí)現(xiàn)過(guò)程

Rainbow 簽名算法自 1999 年起一直經(jīng)受各種密碼分析，例如 MinRank 攻擊，HighRank 攻擊，Billet-Gilbert 攻擊等 。直到 2022 年，Beullens再次對(duì) Rainbow 簽名算法進(jìn)行了進(jìn)一步的改進(jìn)，并表明對(duì)于給定的 NIST 第二輪提交的 SL 1 參數(shù)集的公鑰，通過(guò)密鑰恢復(fù)攻擊，在標(biāo)準(zhǔn)筆記本電腦上平均 53 小時(shí)即可返回相應(yīng)的密鑰。

盡管在 NIST 第四輪的標(biāo)準(zhǔn)化候選算法中沒(méi)有多變量公鑰密碼體制，但是在某些注重算法效率的應(yīng)用場(chǎng)景中，多變量公鑰密碼體制或許會(huì)進(jìn)入一個(gè)新的高度。

4.5其他后量子密碼算法

除上述 4 種主流算法外，基于量子密碼和基于同源的密碼體制也在密碼學(xué)家的研究范圍內(nèi)。2012 年，Kashefi 等 人提出了量子單向函數(shù)的候選方案，Mosca 等人研究了經(jīng)典認(rèn)證密鑰交換框架下量子密鑰的分配問(wèn)題。2006年，Couveignes介紹了困難的同質(zhì)空間（Hard Homogeneous Spaces，HHS）的概念并延伸介紹了相關(guān)理論，為基于橢圓曲線(xiàn)同源的密碼系統(tǒng)奠定了基礎(chǔ)。同年，Rostovtsev 等人 提出了一個(gè)新的適用于公鑰密碼系統(tǒng)的通用數(shù)學(xué)問(wèn)題：對(duì)于有限域上的橢圓曲線(xiàn)，計(jì)算給定橢圓曲線(xiàn)之間的同源（代數(shù)同態(tài)），與此同時(shí)，ElGamal公鑰加密和 Diffie-Hellman 密鑰協(xié)議被提出用于同源密碼系統(tǒng)。2014 年，Jao 等人 公布了一個(gè)在橢圓曲線(xiàn)同源基礎(chǔ)上不可否認(rèn)的數(shù)字簽名方案。2017 年，Gélin 等人 和 Ti分別對(duì)超奇異同源密碼系統(tǒng)的循環(huán)終止故障攻擊和第一類(lèi) 故 障 攻 擊 進(jìn) 行 了 討 論。2022 年，Castryck、Maino 和 Chi-Domínguez 針對(duì)超奇異同源密鑰交換協(xié)議（SIDH），分別提出了不同的密鑰恢復(fù)攻擊方案。盡管這些后量子密碼算法并未像其他主流算法一樣形成體系，但是在不久的將來(lái)，這些后量子密碼算法或者其他新的后量子算法也會(huì)逐步登上舞臺(tái)。

5

后量子密碼的發(fā)展趨勢(shì)

量子計(jì)算機(jī)的出現(xiàn)可以看成新一代的技術(shù)革命，作為計(jì)算機(jī)下一輪迭代的發(fā)展方向，量子計(jì)算機(jī)在密碼破解、機(jī)器學(xué)習(xí)、量子模擬等多個(gè)領(lǐng)域具有得天獨(dú)厚的優(yōu)勢(shì)，日后量子計(jì)算機(jī)也極有可能成為人們?nèi)粘Ｉ钪械囊徊糠?。后量子密碼算法作為應(yīng)對(duì)量子計(jì)算攻擊的新型密碼方案，研究時(shí)間不過(guò)短短 30 年左右，仍有許多問(wèn)題亟須探索。

5.1經(jīng)典后量子密碼算法的優(yōu)化與拓展

量子計(jì)算的發(fā)展對(duì)密碼技術(shù)提出了更高的要求，同時(shí)也促成了密碼分析技術(shù)的進(jìn)步。盡管目前已經(jīng)設(shè)計(jì)研究出眾多類(lèi)型的后量子密碼算法，但是針對(duì)這些密碼算法的理論攻擊仍然存在，例如面向 NIST 第三輪入選算法中 Kyber 的密鑰不匹配攻擊等，因此在未來(lái)對(duì)已有的后量子密碼算法的改進(jìn)之路仍需繼續(xù)前行。除此之外，針對(duì)算法的實(shí)用化改進(jìn)同樣具有重要意義。通過(guò)不斷優(yōu)化算法的參數(shù)設(shè)計(jì)，提高算法的運(yùn)行效率，降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度，使算法在實(shí)際應(yīng)用中發(fā)揮作用。

5.2量子算法與密碼算法的結(jié)合

量子算法的設(shè)計(jì)目標(biāo)是解決某一類(lèi)特定的問(wèn)題或者縮短某些算法的運(yùn)行時(shí)間，例如 Shor算法的發(fā)明解決了大整數(shù)分解問(wèn)題，Grover 算法的提出提高了搜索的速度，Simon 算法的出現(xiàn)提供了一種求解函數(shù)周期的方法。研究量子算法與密碼算法相結(jié)合的新型算法，一方面，將量子算法應(yīng)用于后量子密碼的設(shè)計(jì)中可以提高算法的運(yùn)行效率，增強(qiáng)其可用性；另一方面，將量子算法應(yīng)用于密碼分析方法中可以從某個(gè)角度發(fā)現(xiàn)算法潛在的攻擊可能性，優(yōu)化算法參數(shù)，提高算法的安全性。

5.3密碼算法量子安全性的評(píng)估

量子計(jì)算中的一些算法已經(jīng)被證實(shí)對(duì)經(jīng)典密碼算法存在有效的理論攻擊，這種攻擊針對(duì)后量子密碼算法而言是否有效目前還未知。同時(shí)，新的量子算法的出現(xiàn)是否會(huì)對(duì)現(xiàn)有后量子算法造成威脅也同樣未知，因此評(píng)估密碼算法的量子安全性是未來(lái)的一個(gè)研究方向。

5.4量子環(huán)境下新的數(shù)學(xué)問(wèn)題探索

除了目前基于格、哈希、多變量、編碼的后量子密碼算法，研究設(shè)計(jì)更多的基于同源曲線(xiàn)或者量子隨機(jī)漫步的后量子密碼算法也是很有必要的。除此之外，研究設(shè)計(jì)在量子計(jì)算機(jī)優(yōu)勢(shì)外的數(shù)學(xué)困難問(wèn)題也是一種新的探索方向。

6

結(jié)語(yǔ)

針對(duì)量子計(jì)算的發(fā)展，美國(guó)已經(jīng)在實(shí)施龐大的量子計(jì)劃，并公開(kāi)宣布當(dāng)項(xiàng)目進(jìn)行到一定程度后便不再向全球公開(kāi)，意味著我們將無(wú)從獲知其他各國(guó)最新的研究進(jìn)展，這將在一定程度上影響我國(guó)的戰(zhàn)略決策。同時(shí)，根據(jù)量子計(jì)算對(duì)網(wǎng)絡(luò)空間安全方面帶來(lái)的威脅，全球目標(biāo)統(tǒng)一在抗量子密碼的研究上，但是國(guó)與國(guó)之間還存在一定差距，此后，我國(guó)應(yīng)延續(xù)在量子計(jì)算、抗量子密碼領(lǐng)域的科研計(jì)劃，縮小與西方的差距，切實(shí)保障國(guó)家的網(wǎng)絡(luò)與信息安全。