美國NIST公布首批后量子密碼標準算法
隨著量子計算技術的發展，相關運算操作在理論上實現從指數級向多項式級別的轉變，量子計算機有望攻破現有的公鑰密碼體制。為應對出現的新型威脅，后量子密碼（PQC）應運而生，旨在研究密碼算法在量子環境下的安全性。
美國為維護國家安全，進一步搶占量子領域全球領導地位，早先于2017年開始推動PQC算法標準化研究。2022年7月5日，美國國家標準與技術研究院（NIST）宣布CRYSTALS-KYBER、FALCON、CRYSTALS-Dilithium等4個項目提前入選其PQC項目標準化算法結果，并宣布BIKE、Classic McEliece等4個候選算法進入下一輪算法篩選。這一里程碑事件標志著NIST PQC標準化工作經過6年的發展即將進入最后階段。
一 背 景
（一）量子計算給現有密碼體制帶來的威脅與日俱增
近年來量子計算取得多項重大突破，IBM、谷歌、微軟公司等多家科技巨頭公布量子計算發展路線圖，密集推出革命性量子硬件、軟件，種種跡象表明量子計算正逐步邁入規模化應用階段。在百萬比特級加密量子計算機的沖擊下，現有公鑰密碼體制（如RSA、ECC及DH密鑰交換技術）都將被完全破解，對稱密碼算法（如AES、SHA1、SHA2等）的安全性將被顯著降低。網絡攻擊者可利用量子計算機輕松打破世界上任一數字防御系統、破解公鑰密碼系統，進而對國家安全造成嚴重威脅。
（二）美國政府積極引導傳統密碼體制向后量子密碼過渡
為應對量子計算發展給國家安全帶來的威脅，美國政府密集出臺一系列應對量子技術風險相關政策法案（如表1），進一步加快PQC技術布局，推動PQC技術遴選和標準化工作。相關法案指出聯邦政府現有的信息系統需要向PQC技術遷移，政府和產業界需要優先開發可以容易升級到PQC的應用、硬件和軟件。
表1.美國PQC遷移相關政策
為此，美國國家網絡安全卓越中心（NCCoE）于2021年8月正式啟動PQC遷移項目，邀請各部門、企業撰寫PQC遷移意向書，描述產品和技術性內容，從而為PQC遷移項目提供安全平臺支持和演示；7月5日當天，美國網絡安全和基礎設施安全局（CISA）宣布建立PQC計劃，將向后量子加密過渡確定為網絡安全愿景的優先事項。
（三）借力學術、產業界開展后量子密碼研發及應用測試
美國《國家戰略計算倡議戰略計劃》強調通過“整體型政府與工業界、學術界共同建立高性能計算系統的跨機構戰略遠景和投資”。美國政府積極聯合學術界、產業界開展PQC技術和產品研發，積極進行多場景抗量子密碼應用測試，推出相關商業服務和升級產品等。例如，2022年7月，后量子安全公司QuSecure宣布產品QuProtectTM基于Kyber標準算法建立量子安全通道，實現100%正常運行時間保護美國政府空域的加密通信和數據；2022年4月，韓國移動運營商LG Uplus推出了世界上首個后量子密碼專線服務，可以實現對量子計算網絡攻擊的有效防御；2021年8月，德國慕尼黑工業大學研究人員設計生產了一種基于RISC-V技術的PQC芯片，旨在展示其阻止黑客使用量子計算機解密通信的能力。
二 美國后量子密碼標準進展
2016年12月，NIST正式面向全球征集具備抗擊量子計算機攻擊能力的新一代PQC算法，以期逐漸取代以經典RSA為代表的不可抗量子計算機攻擊的公鑰加密算法，并最終成為標準化加密算法。PQC算法評估工作分為三輪進行，每輪18個月左右，預計2024年前完成。
PQC標準化算法篩選只選擇了無狀態數字簽名、非對稱加密和密鑰封裝機制（KEMs）兩種密碼體制，并將算法安全性、效率和性能、其他因素（如知識產權要求、實施難度）作為評估標準因素。
（一）PQC標準化項目進程
1.第一輪篩選結果
2017年12月，NIST公布PQC標準協議的第一輪預選結果，期間共收到82個基礎方案，篩選收錄63個完整方案，其中包括44個非對稱加密和KEMs方案及19個數字簽名方案。
表2.NIST第一輪標準方案情況表
2.第二輪篩選結果
2019年1月，NIST公布PQC標準協議的第二輪預選結果，共計26個算法進入下一輪進程，其中包括17個非對稱加密和KEMs方案（BIKE、Classic McEliece、CRYSTALS-KYBER、FrodoKEM、HQC、LAC、LEDAcrypt、NewHope、NTRU、NTRU Prime、NTS-KEM、ROLLO、Round5、RQC、SABER、SIKE、Three Bears）及9個數字簽名方案（CRYSTALS-DILITHIUM、FALCON、GeMSS、LUOV、MQDSS、Picnic、qTESLA、Rainbow、SPHINCS+）。
表3.NIST第二輪標準方案情況表
3.第三輪篩選結果
2021年1月，NIST公布的第三輪審查共有7個算法入圍，其中包括4種非對稱加密和KEMs（Classic McEliece、CRYSTALS-KYBER、NTRU、SABER）及3種數字簽名算法（CRYSTALS-DILITHIUM、FALCON、Rainbow）。此外，NIST還保留了8個備選算法，包括5種備選公鑰加密和密鑰生成算法（BIKE、FrodoKEM、HQC、NTRU Prime、SIKE）和3種數字簽名算法（GeMSS、Picnic、SPHINCS+）。
表4.NIST第三輪標準方案情況表
4.標準化算法結果
2022年7月5日，NIST公布提前選中并將進行標準化的算法，其中包括用于非對稱加密和KEMs的CRYSTALS-KYBER、用于數字簽名的CRYSTALS-Dilithium、FALCON及SPHINCS+。其中，NIST推薦CRYSTALS-Kyber算法用于保護通過公共網絡交換信息的通用加密，推薦其余三種算法用于身份認證。以上四種算法均在2024年之前支持NIST未來的加密標準。
此外，NIST推薦將BIKE、Classic McEliece、HQC、SIKE算法進入第四輪篩選進程。
（二）標準化算法情況
1.非對稱加密和密鑰封裝機制（KEMs）
CRYSTALS-Kyber是基于格理論的PQC算法，其安全性基于假定的硬件模塊的容錯性學習 (MLWE) 問題。在保障安全性的同時兼具加密密鑰相對較小、交換數據量小、運行速度快的特點。同時，Kyber的硬件、軟件及混合設置、抗側信道攻擊等性能在同類型算法中位于前列，專利障礙問題較少，在未來具有較大的使用前景。
2.數字簽名
Crystals-Dilithium是基于格理論的數字簽名方案，其安全性依賴于MLWE和模塊短整數的強度解決問題 (MSIS) 并遵循Fiat-Shamir與中止技術。該算法在密鑰和簽名大小方面具有強大而平衡的性能，并且密鑰生成、簽名和驗證算法的效率在實際驗證中表現良好。
Falcon是一種利用“散列和符號”范式的基于格的簽名方案，其安全性依賴于短整數解（SIS）問題在NTRU格算法上的難度，以及隨機預言機模型 (ROM) 和QROM 中的安全證明遞減。該算法提供了最小的帶寬，提供非常好的整體性能。
Sphincs+是一種基于散列的無狀態簽名方案，其安全性依賴于關于底層散列函數安全性的假設。該算法提供了可靠的安全保證，但會導致性能上的巨大成本。NIST 將該算法視為極其保守的選擇，同時也是標準化算法中的唯一哈希算法，成為其余格密碼受威脅背景下的備選方案。
表5.NIST標準化算法數字簽名方案比較表
三 影 響
（一）格密碼將成為后量子密碼中的主流路線
PQC算法中，格密碼算法可在安全性、公私鑰大小、計算速度方面達到較好的平衡。同時在相同安全強度下，格密碼的公私鑰大小比其他三種（編程密碼、多變量密碼、哈希密碼）方案更小，計算速度更快且更適用于多應用場景。在NIST公布的4種標準化算法中就包含3個格密碼，足見其巨大潛力。美國家安全局網絡安全局（NSA CSD）指出，基于格的加密方案進行參數化可保證安全，該密碼方案是當前最高效的后量子算法。該機構預計，基于NIST篩選的格密碼算法將被批準用于國家安全系統（NSS）。
（二）短期內將開發和使用混合密鑰協議
目前，NIST選定的PQC標準化算法只包括了公鑰加密和數字簽名兩種常用的密碼算法，但這些算法已趨于成熟，優化改進余地較小。短期內，PQC算法要與傳統安全密碼技術結合形成一種“混搭”模式以適用當前的安全需求。亞馬遜AWS公司首席安全官指出，混合密鑰交換方案在實際應用中具有廣泛的前景，其中ECDHE+Kyber混合方案的性能最佳。
（三）標準化后量子算法已開啟商用化應用
新型密碼體系的成熟離不開企業界的長期測試研究與商業應用。西方多家科技巨頭既是PQC算法的設計者，又是應用落地的催化者。當前，PQC標準算法已然開啟商業化應用，部分企業將PQC標準算法集成至公司產品中，進一步提升其安全性能。例如Cloudflare公司將CRYSTALS-Kyber與其他PQ算法集成到其加密數據庫CIRCL；Crypto Quantique公司推出CRYSTALS-Kyber算法的后量子物聯網安全平臺。
