摘要：隨著量子計(jì)算技術(shù)的快速發(fā)展，目前廣泛使用的密碼技術(shù)受到嚴(yán)重威脅。本文從量子計(jì)算對(duì)密碼學(xué)的影響出發(fā)，介紹后量子密碼的主要技術(shù)路線，相關(guān)標(biāo)準(zhǔn)化進(jìn)展，最后展望相關(guān)技術(shù)發(fā)展。

量子計(jì)算對(duì)密碼學(xué)的影響

量子計(jì)算利用量子疊加與量子糾纏等量子力學(xué)原理進(jìn)行計(jì)算，在一些特定問題上具有遠(yuǎn)優(yōu)于傳統(tǒng)計(jì)算的能力。自 20 世紀(jì)八十年代提出，量子計(jì)算已取得巨大進(jìn)步。2019 年，Google 研究人員構(gòu)建 53 量子比特處理器，宣稱成功演示了“量子計(jì)算優(yōu)越性”。2020 年，我們科研團(tuán)隊(duì)構(gòu)建九章量子原型機(jī)，實(shí)現(xiàn)高斯玻色采樣任務(wù)的量子計(jì)算優(yōu)越性：在 200 秒內(nèi)生成的樣本數(shù)量對(duì)于經(jīng)典超級(jí)計(jì)算機(jī)需要進(jìn)行 25 億年的計(jì)算。IBM、微軟、Amazon、華為、阿里巴巴等國(guó)內(nèi)外科技巨頭均紛紛布局量子計(jì)算軟硬件開發(fā)，量子計(jì)算技術(shù)正快速發(fā)展中。

要發(fā)揮量子計(jì)算的優(yōu)勢(shì)，需要量子計(jì)算硬件支持，同時(shí)還需要結(jié)合量子算法。據(jù) Quantum Algorithm Zoo 網(wǎng)站統(tǒng)計(jì)，目前已有數(shù)百個(gè)量子算法用于不同問題的求解，其中對(duì)密碼學(xué)有較大影響的量子算法主要有 Shor 算法、Grover 算法、Simon 算法：Shor 算法：由 Peter Shor 于 1994 年提出，可用于求解整數(shù)分解與離散對(duì)數(shù)等問題，將求解復(fù)雜度由經(jīng)典計(jì)算機(jī)的指數(shù)規(guī)模降低到多項(xiàng)式級(jí)別，對(duì) RSA、ECC、SM2 等當(dāng)前廣泛使用的公鑰密碼算法具有嚴(yán)重威脅。

Grover 算法：由美國(guó)計(jì)算機(jī)科學(xué)家 Lov K. Grover 于 1996年提出，用于在無序數(shù)據(jù)庫(kù)中搜索特定項(xiàng)，使得搜索復(fù)雜度由經(jīng)典計(jì)算機(jī)線性時(shí)間復(fù)雜度降低為平方根時(shí)間復(fù)雜度，將使目前所有密碼算法的有效密鑰長(zhǎng)度減半。

Simon 算法：由 Daniel R. Simon 于 1994 年提出，可用于快速獲取一個(gè)函數(shù)的周期，將復(fù)雜度由經(jīng)典算法的 O(2^(n/2)) 降低到 O(n)。Simon 算法導(dǎo)致部分在經(jīng)典計(jì)算模型下可證明安全的密碼模型在量子時(shí)代不再安全，也對(duì) CBC-MAC、PMAC、GMAC等分組密碼工作模式構(gòu)成嚴(yán)重威脅。

后量子密碼技術(shù)路線

傳統(tǒng)的公鑰密碼算法（如 RSA、SM2 等）所基于的數(shù)學(xué)難題，如整數(shù)分解、離散對(duì)數(shù)等，易于被量子計(jì)算機(jī)求解，基于這些數(shù)學(xué)難題的密碼算法在量子時(shí)代將不再安全。為了應(yīng)對(duì)這一挑戰(zhàn)，后量子密碼學(xué)（Post-Quantum Cryptography，PQC）作為一種新興的密碼學(xué)技術(shù)應(yīng)運(yùn)而生。

PQC 基于現(xiàn)有量子計(jì)算仍難以有效求解的數(shù)學(xué)難題，PQC 研究的目標(biāo)是提供一種能夠在量子計(jì)算時(shí)代仍然保持安全性的密碼算法和協(xié)議。目前，PQC 算法的主要技術(shù)路線有基于雜湊、編碼、多變量、格和同源等問題的方案：

基于雜湊（Hash-based）的方案使用 Merkle 雜湊樹等技術(shù)進(jìn)行運(yùn)算，主要用于生成數(shù)字簽名。其安全性依賴于雜湊函數(shù)的安全性，而不是依賴于數(shù)學(xué)問題的困難性假設(shè)，如果所采用的雜湊算法被攻破，只需將雜湊算法更新為更安全的算法，就能確保簽名算法的安全性。

基于編碼（Code-based）的算法利用糾錯(cuò)碼構(gòu)造單向函數(shù)，其安全性依賴于編碼理論中的 Syndrome Decoding（SD）和Learning Parity with Noise（LPN）等難解問題，可用于構(gòu)建加密算法、數(shù)字簽名和密鑰交換方案等。

基于多變量（Multivariate-based）的密碼算法使用有限域上的多變量二次多項(xiàng)式組構(gòu)建加密、簽名和密鑰交換等方案，其安全性依賴于求解多變量方程組的困難性，主要用于構(gòu)建簽名算法，代表性算法等。

基于格（Lattice-based）的密碼算法基于格中的難解問題，可以用于構(gòu)建加密、數(shù)字簽名和密鑰交換等密碼方案。這類方案具有快速計(jì)算速度和較小的通信開銷，安全性、公私鑰尺寸和計(jì)算速度方面取得了良好的平衡，有望成為標(biāo)準(zhǔn)化的選擇。

基于同源（Isogeny-based）的密碼算法利用超奇異橢圓曲線同源問題構(gòu)建加密和密鑰交換等密碼方案。這類方案具有較小的公私鑰尺寸，但運(yùn)行效率較低。代表性算法包括 SIKE 等。

關(guān)于對(duì)稱密碼算法，人們普遍認(rèn)為其在量子時(shí)代仍能夠保持一定的安全強(qiáng)度，可通過增加密鑰長(zhǎng)度或雜湊值長(zhǎng)度的方式抵抗量子攻擊。抗量子攻擊的對(duì)稱密碼研究相對(duì)較少，設(shè)計(jì)方案只有Saturnin 等少量方案。

標(biāo)準(zhǔn)化進(jìn)展

為應(yīng)對(duì)量子計(jì)算威脅，國(guó)際上各大標(biāo)準(zhǔn)化組織正積極推動(dòng)后量子密碼標(biāo)準(zhǔn)化工作，為后量子密碼應(yīng)用作儲(chǔ)備。

早在 2012 年，美國(guó) NIST 就啟動(dòng)了后量子密碼標(biāo)準(zhǔn)化工作，并于 2016 年 12 月正式啟動(dòng)后量子密碼算法征集活動(dòng)。經(jīng)過三輪評(píng)選以及額外的兩年評(píng)估，NIST 在 2022 年 7 月選出 4 個(gè)算法進(jìn)入標(biāo)準(zhǔn)化程序，包括公鑰加密與密鑰交換算法 CRYSTALS-KYBER，與數(shù)字簽名算法 CRYSTALS-Dilithium、FALCON、SPHINCS+。同時(shí)，NIST 為使算法技術(shù)路線多樣化，在標(biāo)準(zhǔn)化上述算法的同時(shí)啟動(dòng)第四輪算法評(píng)估并征集新算法。值得一提的是，第三輪終選算法之一基于多變量的算法 Rainbow 以及進(jìn)入第 4 輪評(píng)估的基于橢圓曲線同源技術(shù)的算法 SIKE 已被研究人員攻破，無法提供應(yīng)有的安全性。

我國(guó)在 2018 年啟動(dòng)全國(guó)密碼算法設(shè)計(jì)競(jìng)賽，其中非對(duì)稱算法部分征集到 38 個(gè)算法，經(jīng)過形式審查、公開評(píng)議、檢測(cè)評(píng)估和專家評(píng)選，競(jìng)賽最終評(píng)出14項(xiàng)優(yōu)勝算法：11個(gè)基于格困難問題的算法、1 個(gè)基于編碼問題的非對(duì)稱加密算法、1 個(gè)基于超奇異橢圓曲線上同源問題的密鑰交換協(xié)議和 1 個(gè)基于置換核問題的數(shù)字簽名算法。

歐洲電信標(biāo)準(zhǔn)化協(xié)會(huì)（ETSI）、國(guó)際互聯(lián)網(wǎng)工程任務(wù)組（IETF）、美國(guó)電氣和電子工程師協(xié)會(huì)（IEEE）、國(guó)際標(biāo)準(zhǔn)化組織（ISO）等均在后量子標(biāo)準(zhǔn)化方面做了大量工程，制定了系列標(biāo)準(zhǔn)，如 ETSIGR QSC 001《量子安全算法框架》、IETF RFC 8391 《XMSS:eXtended Merkle Signature Scheme》、IEEE 1363.1-2008《IEEE Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices》等。

研究展望

后量子密碼學(xué)是一個(gè)充滿挑戰(zhàn)和機(jī)會(huì)的領(lǐng)域，面對(duì)即將到來的量子計(jì)算時(shí)代，它的研究與應(yīng)用將對(duì)整個(gè)密碼學(xué)界和信息安全產(chǎn)業(yè)產(chǎn)生深遠(yuǎn)的影響。

除了后量子算法與標(biāo)準(zhǔn)化研究外，將現(xiàn)有密碼系統(tǒng)向能夠抵御量子計(jì)算攻擊的后量子密碼系統(tǒng)遷移也是一項(xiàng)重要任務(wù)。后量子遷移過程需對(duì)現(xiàn)有的密碼系統(tǒng)進(jìn)行評(píng)估和分析，確定其在量子計(jì)算機(jī)攻擊下的脆弱性，并設(shè)計(jì)出能夠抵御量子攻擊的替代方案。后量子密碼遷移是一個(gè)復(fù)雜的過程，涉及密碼算法、協(xié)議、硬件設(shè)備和網(wǎng)絡(luò)基礎(chǔ)設(shè)施等多個(gè)方面，需要密切關(guān)注量子計(jì)算技術(shù)的發(fā)展，并與密碼學(xué)研究人員、行業(yè)和標(biāo)準(zhǔn)化組織密切合作，遷移過程需要謹(jǐn)慎規(guī)劃和逐步實(shí)施，以確保安全性和平滑過渡。

海泰方圓作為一家密碼企業(yè)，為產(chǎn)業(yè)提供高質(zhì)量密碼供給是職責(zé)所在。海泰方圓后量子密碼研究小組在后量子遷移、后量子密碼算法與標(biāo)準(zhǔn)化研究等領(lǐng)域擁有充足的技術(shù)儲(chǔ)備。一方面，海泰方圓緊跟后量子密碼研究進(jìn)展，掌握后量子密碼算法和協(xié)議及其性能特點(diǎn)等，及國(guó)內(nèi)外相關(guān)標(biāo)準(zhǔn)化進(jìn)展等。其次，研究了密碼系統(tǒng)風(fēng)險(xiǎn)評(píng)估、遷移策略等，制定了一些方案。海泰方圓也與產(chǎn)學(xué)研建立了廣泛深入的合作，儲(chǔ)備了后量子密碼相關(guān)技術(shù)資源。歡迎交流探討。