摘要

公鑰密碼學是保障現(xiàn)代通信安全與數(shù)據安全的重要基礎技術。介紹了當前量子計算發(fā)展對公鑰密碼學造成的威脅，以及密碼標準化組織和密碼學研究的應對措施，依據所使用的基礎數(shù)學困難問題分類闡述基于格、編碼、多變量、哈希函數(shù)、曲線同源的后量子密碼及其優(yōu)劣勢等特點。以當前后量子密碼標準進展為主線，從算法安全性分析、后量子遷移的技術路線、與量子通信技術結合、新的數(shù)學困難問題探索等方面提出后量子密碼學的發(fā)展方向建議。

內容目錄：

1　量子時代帶來的挑戰(zhàn)

2　后量子密碼發(fā)展現(xiàn)狀及技術路線

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

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

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

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

2.5　基于哈希函數(shù)的后量子密碼算法

2.6　基于曲線同源的后量子密碼算法

2.7　后量子密碼技術路線對比

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

3.1　后量子密碼算法的安全性評估

3.2　后量子密碼遷移應用驗證探索

3.3　后量子密碼與基于物理學的量子通信技術的融合應用探索

3.4　量子環(huán)境下新的數(shù)學問題探索

4　結　語

密碼技術是信息技術領域的重要分支，隨著科學技術的發(fā)展，密碼技術不斷進步，從機械密碼到電子密碼，再到現(xiàn)代的數(shù)字密碼，每一步都推動了人類文明的快速前行。到了互聯(lián)網時代，萬物互聯(lián)使得世界發(fā)生了顛覆性變化，虛擬空間的互認互信成為核心要素。而現(xiàn)代互聯(lián)網的互聯(lián)互信極大地依賴于公鑰密碼體系，不僅可以保證消息的機密性，還可以驗證消息的來源，提供了數(shù)據加密、身份驗證和消息完整性檢查等功能，確保了互聯(lián)網通信的安全和可靠。隨著量子計算技術及量子計算機的迅猛發(fā)展 ，當代被廣泛使用的密碼系統(tǒng)受到量子計算的嚴重威脅。公鑰密碼學也開始技術革新，迎接量子計算時代的挑戰(zhàn)，并且在密碼標準化方面已取得階段性進展。因此，有必要全面掌握當前已知抵抗量子計算的公鑰密碼，總結后量子密碼技術路線及其特點 。本文進一步新增最新的針對密碼算法的量子計算攻擊進展，分析各種類別后量子密碼的優(yōu)劣勢，提出后量子密碼研究及后量子遷移的建議，為后量子密碼的深入發(fā)展提供支撐。

1? 量子時代帶來的挑戰(zhàn)

量子計算技術及量子計算機極大地威脅著經典密碼的安全。一方面，量子計算破譯經典密碼具有顯著優(yōu)勢。為保證信息的加密傳輸，基于數(shù)學上困難問題設計的 RSA、DSA、ECC等公鑰密碼算法已經維護了近 50 年的網絡信息與通信安全。但是，隨著第二次量子革命?中的量子計算機的快速發(fā)展，以及以 Shor 算法和 Grover 算法為代表的量子計算算法的高速迭代研究，給現(xiàn)有互聯(lián)網基礎設施帶來巨大的信任危機。Shor 算法 能在多項式時間內求解給定大整數(shù)的大質因數(shù)，與經典整數(shù)分解算法相比，其能夠指數(shù)級提升效率；Grover 算法是搜索非結構化數(shù)據庫或無序列表的量子算法，應用于密碼破解使得等效于同等攻擊下密鑰長度減半。Google 在2022 年發(fā)布的資料表明，其計劃在 2030 年完成100 萬量子比特的量子專用計算機的研制；2022 年 12 月，清華大學龍桂魯教授團隊提出基于經典的 Schnorr 算法及同時依靠量子近似優(yōu) 化 算 法（Quantum Approximate OptimizationAlgorithm，QAOA）來優(yōu)化 Schnorr 算法中最耗時的部分，實現(xiàn)了僅用 10 個超導量子比特就完成了 48 位因式分解，同時提出最低僅需要372 個物理量子比特的量子計算機即可能完成RSA-2048 的破解 。

另一方面，量子攻擊策略具有時間優(yōu)勢，不一定只在量子計算機成熟后才發(fā)揮作用。攻擊者先將能夠獲取的所有加密狀態(tài)信息存儲起來，等到實用的量子計算機建造后再實施密碼破譯，而量子計算的快速發(fā)展極大地縮短了時間周期。按照國家保密管理要求，重要的信息管理期限甚至在 10 年以上 。這意味著，如果2033 年前研發(fā)出了可用于破譯現(xiàn)有密碼體制的量子計算機，那么在互聯(lián)網或者其他公共信息網絡傳輸?shù)男畔⒍即嬖跇O大的泄密風險。量子計算技術發(fā)展直接倒逼密碼技術的發(fā)展，換言之，目前快速發(fā)展的量子計算技術迫使密碼技術必須盡快采取應對措施。

2? 后量子密碼發(fā)展現(xiàn)狀及技術路線

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

傳統(tǒng)公鑰密碼使用經典計算機在多項式時間內無法求解的公認數(shù)學困難問題作為安全基礎。類似的，當代密碼學探尋當前量子計算機無法有效求解的困難問題作為安全基礎設計密碼體制，這些體制被稱為抗量子計算密碼（QuantumResistant Cryptography，QRC）或者后量子密碼（Post-Quantum Cryptography，PQC）。

美國將后量子密碼作為應對量子計算最具優(yōu)勢的技術手段，提出了《量子計算網絡安全準備法案》，制定了政府信息技術向后量子加密過渡的路線圖 ，并由美國國家標準與技術研究院（National Institute of Standards and Technology，NIST）自 2016 年開始啟動全球征集遴選?PQC?標準算法的工作。2022 年 9 月，美國國家安全局（National Security Agency，NSA）發(fā)布了 CNSA 2.0時間表，計劃于 2033 年完成后量子密碼遷移 。

根據底層數(shù)學困難問題分類，后量子密碼算法研究目前主要有 5 種技術路線，分別是基于格的密碼、基于編碼的密碼、基于多變量的密碼、基于哈希函數(shù)的簽名以及基于曲線同源的密碼。2022 年 7 月 NIST 公布的后量子密碼標準化遴選進展中，基于格的密碼和基于安全哈希函數(shù)的簽名算法已入選為標準，基于編碼和超奇異同源的密碼算法入選第四輪篩選并開展進一步評估，而其中基于超奇異同源的密碼算法 SIKE 被完全破解 。

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

格是實數(shù)域上線性空間中的離散子群，可表達成一組向量的整系數(shù)線性組合。給定一組線性獨立的向量它們生成的格是集合其 中 n 被稱為格的維數(shù)，被稱為這個格的一組基。一個 n 維格具有很多格基，它的任意兩組格基之間相差一個 n 階幺模矩陣。計算格中的最短非零向量是重要的困難問題，是當代格密碼的安全基石。Ajtai提出的短整數(shù)解（Short Integer Solution，SIS）問題和 Regev 提出的帶錯誤學習（Learning with Errors，LWE）問題開啟了實用的可證明安全格密碼研究。當前實用且安全的加解密格體制 、數(shù)字簽名 格密碼體制基本基于上述兩個問題設計。一方面，格密碼具有上述困難問題作為理論規(guī)約的安全基礎；另一方面，格密碼的空間時間資源消耗適中。進一步的，基于格密碼能夠設計屬性加密、同態(tài)加密?等高等密碼學應用算法。因此，業(yè)界廣泛認可格密碼是最有前景的后量子密碼技術分支。

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

經過編碼的信息在信道上傳輸，由于噪聲產生錯誤，在接收端通過譯碼算法恢復。基于編碼的密碼，其理論依據來源于隨機線性碼的譯碼是困難問題 。1978 年，McEliece 使 用 Goppa碼設計公鑰加密方案 ，以 [n,k,t]-Goppa 碼的生成矩陣 G 作為內核，在左側和右側分別施加可逆矩陣 S 和隨機置換矩陣 P 來掩蓋 G，方案的私鑰包含矩陣 S，G，P，公鑰包含矩陣 G'=SGP以及 Goppa 碼的糾錯能力 t。加密時將明文編碼成向量 m，計算密文 c=mG'+e，其中 e 是重量不超過 t 的隨機向量。解密時計算并施加譯碼操作。近年來，基于編碼的密碼考慮使用秩距離碼、極化碼等。

基于編碼的密碼具有自身優(yōu)勢，同時也面臨著挑戰(zhàn)。一方面，基于編碼的密碼相對于現(xiàn)有公鑰密碼算法表現(xiàn)出加密速度快的特點；另一方面，基于編碼的加密算法的公鑰尺寸很大，影響了算法的適用領域。另外，NIST 后量子標準化的情況表明，基于編碼的加密算法發(fā)展較好，但是基于編碼設計安全高效的實用簽名體制仍然是挑戰(zhàn)性高的研究工作。

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

基于多變量的密碼的安全基礎來源于求解高次多變量方程組是 NP 難題。構造有限域上高維空間映射 F，使得它的逆運算也是容易的；在左右兩端引入兩個線性（或仿射）映射 S，T 來掩蓋 F。私鑰包括映射 S，F(xiàn)，T，公鑰是它們的復合映射 P=S○F○T，其表現(xiàn)如同隨機映射?；诙嘧兞康拇硇悦艽a算法包括 HFEv- 類型的 GeMSS 簽 名 體 制 [32] 和 UOV 類 型 的 Rainbow簽名算法 ，二者均已進入 NIST 后量子標準化遴選第三輪。但是，2020 年 Tao 等人 提出的極小秩距離攻擊，極大地降低了 GeMSS 簽名算法的安全性，緊接著 2022 年 Beullens 提出 Rainbow 簽名算法的攻擊算法，極大地提高了密鑰恢復攻擊效率。因此，GeMSS 與 Rainbow算 法 均 未 能 進 入 NIST 后 量 子 標 準 化 遴 選第四輪。

基于多變量的密碼具有資源優(yōu)勢，但需要進一步研究其安全性。一方面，基于多變量的密碼具有較高的運算速度和較小的簽名尺寸；另一方面，類似于編碼密碼，基于多變量的密碼算法的公鑰尺寸也很大，算法實用性受到限制。另外，NIST 后量子標準化的情況表明 ，基于多變量設計安全高效的加密體制是挑戰(zhàn)性高的研究工作。關于多變量密碼的一個很好的綜述見文獻 [37]。

2.5　基于哈希函數(shù)的后量子密碼算法

分組密碼和哈希函數(shù)是研究深入且具有良好標準化對象的密碼組件 。基于對稱密碼設計后量子密碼算法具有較好的工具基礎。

基于哈希函數(shù)的簽名體制，利用?Lamport提出的一次性簽名作為葉子節(jié)點，利用 Merkle樹結構構造數(shù)字簽名方案 。代表性算法包括XMSS 和 SPHINCS+，前者是有狀態(tài)的簽名，后者是無狀態(tài)的簽名，兩個算法在后量子標準化中均取得重要進展 。

NIST 后量子標準化中出現(xiàn)基于分組密碼和非交互零知識證明的簽名體制 Picnic，該體制具有所使用的對稱組件效率高，設計模塊化通用性強，公鑰尺寸小，簽名尺寸大，簽名速度快的特點。這一方案的安全性和優(yōu)化版本值得進一步研究。

2.6　基于曲線同源的后量子密碼算法

所謂同源（Isogenies），就是指兩條橢圓曲線之間保持群結構同態(tài)的映射。一個同源的表達形式常如：給定兩條定義在的橢圓曲線和記為映射分別是上的有理點）。2011 年，Jao 等人首 次 提 出 了 超 奇 異 同 源 Diffie-Hellman 問題（Supersingular Isogeny Diffie-Hellman，SIDH），并設計了基于超奇異同源的公鑰密碼系統(tǒng) SIKE，該算法也被提交到 NIST 成為唯一的同源類候選算法。與其他 4 類候選算法最大的區(qū)別在于，基于 SIDH 的算法參數(shù)尺寸非常小，計算速度較慢。但是，2022 年至今，SIDH 及其加密算法 SIKE 遭到 Castryck 等人提出的密鑰恢復攻擊，最終被完全破譯。需要指出的是，SIKE 的失敗并不意味著基于同源的密碼完全崩塌，同源問題本身并未被破解，以基于同源的簽名 SQISign為代表的算法仍然引領這一方向的研究。

2.7　后量子密碼技術路線對比

通過粗略對比，上述 5 類后量子密碼的技術特點非定量對比如表 1 所示。

表 1　5 類后量子密碼的技術特點非定量對比

3? 后量子密碼的發(fā)展趨勢

通過對后量子密碼研究現(xiàn)狀的論述，結合當前量子技術與密碼學的發(fā)展，針對后量子密碼的技術需求和發(fā)展趨勢提出一些觀點。

3.1　后量子密碼算法的安全性評估

如前文所述，后量子密碼算法主要集中在尋找一類或多類在量子計算攻擊下的 NP 數(shù)學困難問題，而目前僅是利用 Shor 算法和 Grover 算法本身或其優(yōu)化算法作為攻擊的源算法。隨著量子計算的發(fā)展，存在產生新的量子算法的可能性，或將再次顛覆現(xiàn)有的后量子密碼算法體系。因此，在后量子算法的選擇、試點探索、應用部署等任一階段，針對已知和未知攻擊的安全性評估將一直是后量子密碼研究的重要方向。

3.2　后量子密碼遷移應用驗證探索

NSA 已發(fā)布了后量子遷移時間表 ，使用已遴選出的基于格、哈希函數(shù)的簽名的后量子算法作為基礎開展后量子遷移，它們與現(xiàn)有經典密碼算法相比均存在尺寸更大、資源消耗更多的情況。因此，有必要探索后量子密碼遷移所需軟件和硬件平臺極限，提前研究能同時兼容經典密碼與后量子密碼的可自適應的密鑰管理系統(tǒng)、密鑰分發(fā)系統(tǒng)、終端硬件平臺，實現(xiàn)向后量子遷移的平穩(wěn)過渡。

3.3　后量子密碼與基于物理學的量子通信技術

的融合應用探索基于物理學的量子密鑰分發(fā)技術（Quantum Key Distribution，QKD）是目前量子通信技術研究和投入較多的一個方向 。以物理學、光學為理論基礎的量子密碼技術能夠在使用一次一密的情況下實現(xiàn)信息論證明的絕對安全，能夠抵抗量子計算的超高并行算力。而該技術方向中無論是具有遠傳輸距離優(yōu)勢的離散變量量子密鑰分發(fā)技術（Discrete Variable-QKD，DV-QKD）還是具有高速率優(yōu)勢的連續(xù)變量量子密鑰分發(fā)技術（Continuous Variable-QKD，CV-QKD），均有中國團隊占據國際領先技術優(yōu)勢。但是，目前 QKD 技術存在一些實用化技術難題亟須解決：一是小型化、低成本、高速率、遠距離的系列技術需突破；二是由于與經典密碼學的實現(xiàn)基礎完全不同，導致無法直接與現(xiàn)有通信網融合 。因此，探索 QKD 技術與 PQC 技術互補，建立具備保護特定關鍵基礎設施的對抗量子攻擊的密碼網絡，有利于未來做好網絡安全保護。

3.4　量子環(huán)境下新的數(shù)學問題探索

NIST 的 CRYSTALS-KYBER、FALCON、CRYSTALS-Dilithium 和 Sphincs+ 4 個 PQC 標 準化算法中，除了 Sphincs+ 為基于哈希函數(shù)的簽名算法，其他均為基于格的密碼算法。國內也投入了大量研究力量集中攻關基于格的密碼算法 。后量子密碼算法除了基于格、哈希函數(shù)、多變量、編碼的技術路線，還有基于同源曲線的技術路線。因此，有必要拓展更多的后量子密碼算法體制研究方向來積極應對未知的量子計算世界?；貧w本源，密碼學是數(shù)學的延伸，探索密碼學和數(shù)學的跨學科融合，利用現(xiàn)代數(shù)學的理論賦能密碼學的拓展研究，探索新的數(shù)學困難問題，有利于研制具有自主技術特色的后量子密碼體制。

4? ?結　語

本文簡要描述了后量子密碼發(fā)展現(xiàn)狀及對其未來發(fā)展的個人思考。量子計算技術是未來發(fā)展相當不確定的前沿技術，而后量子密碼技術作為防御者，理應下好先手棋。美國發(fā)布的后量子遷移計劃表明，傳統(tǒng)密碼學優(yōu)勢大國已經開始未雨綢繆，提前布局。因此，應在抗量子密碼及相關領域的科研計劃中，持續(xù)探索未來技術發(fā)展的路線，積極落地后量子密碼應用，保障國家的網絡與信息安全。

引用格式：孫奧 , 何銀 , 李海波 , 等 . 后量子密碼發(fā)展綜述 [J]. 信息安全與通信保密 ,2023(9):27-35.

作者簡介 >>>

孫　奧，男，碩士，工程師，主要研究方向為通信及網絡安全；

何　銀，男，學士，工程師，主要研究方向為網絡安全；

李海波，男，碩士，工程師，主要研究方向為保密通信；

張云蓓，女，學士，助理工程師，主要研究方向為網絡安全。

選自《信息安全與通信保密》2023年第9期（為便于排版，已省去原文參考文獻）