2020年10月16日下午，中共中央政治局舉行第二十四次集體學(xué)習(xí)，主題是“量子科技研究和應(yīng)用前景”。為更好地了解國內(nèi)外量子密碼科技發(fā)展態(tài)勢，更好地推進(jìn)我國量子科技發(fā)展，本專委會邀請廣東工業(yè)大學(xué)的教授專門撰文介紹后量子密碼技術(shù)。
一、后量子密碼技術(shù)的發(fā)展歷程
后量子密碼技術(shù)是指可以抵抗量子計(jì)算機(jī)攻擊的密碼技術(shù)。所謂“后”，是指在大規(guī)模穩(wěn)定的量子計(jì)算機(jī)出現(xiàn)后，現(xiàn)有的絕大多數(shù)公鑰密碼算法（RSA、Diffie-Hellman、橢圓曲線等）將會被攻破，只有能抵抗這種攻擊的密碼算法可以在進(jìn)入量子計(jì)算時代之后存活，因此也稱為“抗量子密碼技術(shù)”。
近年來，量子計(jì)算機(jī)的發(fā)展非常迅速，許多大學(xué)或企業(yè)如加州大學(xué)、Google、IBM、Intel等為之都投入了大量人力物力[1]。
2007年，加拿大一家名為D-Wave System的公司已經(jīng)造出了一臺量子計(jì)算機(jī)D-Wave，盡管人們還在爭論這臺計(jì)算機(jī)是否能達(dá)到原理上所要求的特性與效果（即無法使所有量子比特發(fā)生糾纏），但NASA和Google已經(jīng)測試出這臺計(jì)算機(jī)在解決某些問題上比傳統(tǒng)的單核計(jì)算機(jī)快1億倍 [2]。
2014年，Google的研究團(tuán)隊(duì)宣布建成9量子比特的可編程量子機(jī)器，直到2018年3月，該研究團(tuán)隊(duì)發(fā)布了新的72量子比特的量子處理器Bristlecone，標(biāo)志著量子計(jì)算技術(shù)的發(fā)展進(jìn)入了一個極速發(fā)展的階段。與此同時，IBM公司也宣稱他們已經(jīng)成功開發(fā)出一臺50量子比特的原型機(jī)，該50量子比特的量子計(jì)算機(jī)能模擬傳統(tǒng)計(jì)算機(jī)的所有操作。
在國內(nèi)，2017年5月，阿里巴巴與中科院、中科大合作團(tuán)隊(duì)研發(fā)出10 量子比特的線路樣品。
2018年2月，阿里合作團(tuán)隊(duì)宣布11量子比特超導(dǎo)量子計(jì)算服務(wù)將在阿里的量子計(jì)算云平臺上線。
一般來說，密碼系統(tǒng)在開發(fā)過程中都會考慮到破解其的計(jì)算技術(shù)發(fā)展的速度和水平，傳統(tǒng)密碼的安全性依賴于某些問題對現(xiàn)代計(jì)算機(jī)的難解性，例如，RSA依賴于大數(shù)因式分解難題。傳統(tǒng)的計(jì)算機(jī)采用二進(jìn)制數(shù)即0和1來處理信息，因此處理一個1024位的大數(shù)（0-21024）因式分解是一個難解問題。但量子計(jì)算機(jī)不同，它利用量子力學(xué)，并使用 “量子位元”而不是0和1來處理信息。因此，在處理大數(shù)因子分解時，量子計(jì)算機(jī)會有更好的效果。圖1展示了量子計(jì)算機(jī)對現(xiàn)有密碼標(biāo)準(zhǔn)的影響。
圖1 量子計(jì)算機(jī)對現(xiàn)有密碼標(biāo)準(zhǔn)的影響
其中：紅色叉，代表量子計(jì)算機(jī)可以完全攻破，需要后量子密碼算法代替；藍(lán)色框，不那么緊迫需要新算法代替，可以通過調(diào)整算法參數(shù)解決。
總的來說，量子計(jì)算機(jī)對現(xiàn)有密碼標(biāo)準(zhǔn)的影響有以下幾個要點(diǎn)：
1.對于公鑰密碼算法，量子計(jì)算機(jī)對安全性的影響包括：
（1）完全攻破目前廣泛使用的公鑰密碼算法。公鑰密碼算法安全性依賴的數(shù)學(xué)問題可以被高效的量子算法所解決。由于底層依賴的數(shù)學(xué)問題被解決，所以這些公鑰密碼算法不再安全。這些數(shù)學(xué)問題包括：離散對數(shù) (及橢圓曲線版本)、大整數(shù)分解等。這直接影響目前使用的 RSA、Diffie-Hellman、橢圓曲線等算法。著名的量子算法是1994年的Shor's algorithm[4]。
（2）增大密鑰參數(shù)的長度沒有用。增大密鑰長度對于現(xiàn)有的傳統(tǒng)計(jì)算機(jī)和攻擊算法是可以的，但對于量子計(jì)算機(jī)和算法，這是徒勞的。
（3）需要全新的公鑰密碼算法即后量子密碼算法。
2.對于對稱密碼算法，量子計(jì)算機(jī)對安全性的影響：
（1）降低現(xiàn)有算法的安全性：安全性減半。關(guān)于對稱密碼算法和哈希函數(shù)（例如 AES、SHA1、SHA2 等），雖然有量子算法可以理論上攻破，但這個算法的影響有限，且有很多限制條件。著名的量子算法是1996年的Grover's algorithm[5]，可將安全性從k-bit 降低為k/2-bit。
（2）增大參數(shù)的長度有用，把密鑰長度或哈希的長度加倍即可，例如：AES-128升級至AES-256，SHA-256升級至SHA-512等。
3.量子計(jì)算機(jī)具有強(qiáng)大的算力，但利用的前提是：存在能高效解決問題的量子算法，否則量子計(jì)算機(jī)沒什么用，反而因?yàn)槠涓甙旱某杀編砹觿荨?/p>
4.量子比特?cái)?shù)量重要，但更重要的是質(zhì)量。目前建造的量子計(jì)算機(jī)（例如 Google 的 72 量子位芯片）中，量子物理比特的質(zhì)量較差。由于量子相干等物理機(jī)制，必須引入糾錯機(jī)制，但需要成百上千個量子物理比特進(jìn)行糾錯，來實(shí)現(xiàn)一個量子邏輯比特的功能。
5.攻破現(xiàn)有的公鑰密碼算法需要幾千甚至幾萬個邏輯比特，而建造量子計(jì)算機(jī)目前仍處在很初級的階段。
6.對于某些量子算法（例如 Grover），需要指數(shù)級別的內(nèi)存，因此 Grover 算法的威脅不如Shor的算法那么緊迫。
二、后量子密碼的技術(shù)現(xiàn)狀
密碼學(xué)界在研究可以抵抗量子計(jì)算機(jī)攻擊的密碼算法方面，最早可以追溯到 1978年的 McEliece加密、Merkle哈希簽名等算法。但那時量子計(jì)算機(jī)對密碼算法的威脅并沒有很明確，也沒有“后量子”的概念，直到最近十幾年，后量子密碼的重要性逐漸顯現(xiàn)出來。
2016年秋，美國國際標(biāo)準(zhǔn)技術(shù)研究所（NIST）發(fā)布后量子領(lǐng)域標(biāo)準(zhǔn)化方案征求稿[6]，正式在全球范圍征集后量子密碼學(xué)標(biāo)準(zhǔn)協(xié)議。2017年12月，NIST公布后量子密碼學(xué)標(biāo)準(zhǔn)協(xié)議的第一輪預(yù)選協(xié)議，協(xié)議均為后量子密碼學(xué)基礎(chǔ)方案，即加密（含密鑰交換KE或密鑰封裝KEM）和簽名方案。此次共收到82個基礎(chǔ)方案，其中公開69個被認(rèn)為是完整的方案，隨后6個被撤銷。第一輪標(biāo)準(zhǔn)中基于格的密碼學(xué)方案有26個，基于編碼的密碼學(xué)方案有18個，多變量密碼學(xué)方案有9個，基于哈希的密碼學(xué)方案有3個，以及其他類型密碼學(xué)方案有7個。具體情況如表1所示。
2018年11月，NIST再次發(fā)布第二輪的標(biāo)準(zhǔn)方案，從第一輪標(biāo)準(zhǔn)方案以及最新研究成果中遴選出26個進(jìn)入第二輪，其中包括17個公鑰加密和密鑰交換方案及9個數(shù)字簽名方案。具體情況如表2所示。
在NIST候選方案中，主要包括以下四種數(shù)學(xué)方法構(gòu)造的后量子密碼算法：基于哈希的公鑰密碼學(xué)、基于編碼的公鑰密碼學(xué)、基于多變量的公鑰密碼學(xué)以及基于格的公鑰密碼學(xué)。
1. 基于哈希 (Hash-based)的公鑰密碼學(xué)
基于哈希的簽名算法最早出現(xiàn)于1979年，被認(rèn)為是傳統(tǒng)數(shù)字簽名 (RSA、DSA、ECDSA等)的可行代替算法之一[7]。該方案使用哈希函數(shù)的輸入作為私鑰，輸出作為公鑰。這些密鑰僅適用于一個簽名，因?yàn)楹灻旧頃@示密鑰的一部分。基于哈希的簽名會使用Merkle樹認(rèn)證機(jī)制來減少空間消耗。使用Merkle樹認(rèn)證后，哈希樹的根是公鑰，一次性的簽名密鑰是樹中的葉子節(jié)點(diǎn)。基于哈希的簽名算法的安全性依賴哈希函數(shù)的抗碰撞性，由于沒有有效的量子算法能快速找到哈希函數(shù)的碰撞，因此（輸出長度足夠長的）基于哈希的構(gòu)造可以抵抗量子計(jì)算機(jī)攻擊。此外，基于哈希的數(shù)字簽名算法的安全性不依賴某一個特定的哈希函數(shù)。即使目前使用的某些哈希函數(shù)被攻破，也可以用更安全的哈希函數(shù)直接代替被攻破的哈希函數(shù)。
例如，一個經(jīng)典的基于哈希的簽名方案設(shè)計(jì)如下圖2所示。
圖2 基于哈希的簽名方案設(shè)計(jì)圖
方案中的Xi和Yi分別為一次性密鑰的私鑰和公鑰，對消息的簽名增加了兩個狀態(tài)參數(shù)i和Auth，i用來保證所有葉子不會被使用超過1次，Auth是路徑，用來存儲中間結(jié)果，能使簽名快速運(yùn)行。
基于哈希的代表算法有：Merkle 哈希樹簽名、XMSS、Lamport簽名等。
2.基于編碼 (Code-based) 的公鑰密碼學(xué)
基于編碼的算法最早出現(xiàn)于1978年，主要用于構(gòu)造加密算法。目前技術(shù)方向主要分為兩種：基于海明度量（Hamming metric）的編碼方案和基于秩度量（Rank metric）的編碼。
基于海明度量的編碼方案的數(shù)學(xué)困難假設(shè)是校驗(yàn)子譯碼問題（Syndrome Decoding Problem）。校驗(yàn)子譯碼問題已被證明為NP完全（NP-Complete）問題[8]。此方向一個著名的加密算法是 McEliece [9]，該方案使用了Goppa Codes，迄今為止仍然是安全的設(shè)計(jì)方案。但該方案最大的缺點(diǎn)就在于其公鑰需要1MB左右的大小才能達(dá)到256bit的安全度。
目前NIST標(biāo)準(zhǔn)預(yù)選方案中，大部分是基于秩度量的編碼方案。基于此技術(shù)而建構(gòu)的加密或密鑰交換方案包括Loi17[10]、RQC[11]、ROLLO[12]、LG[13]和McNie [14]等等。我國在秩度量加密方案的設(shè)計(jì)方面也有進(jìn)展，如中科院信工所研究員設(shè)計(jì)的兩項(xiàng)加密方案：Piglet[15]和Loong[16]。
基于編碼的代表算法有：McEliece、Loi17、ROLLO等。
3. 基于多變量 (Multivariate-based) 的公鑰密碼學(xué)
基于多變量的算法使用有限域上具有多個變量的二次多項(xiàng)式組構(gòu)造加密、簽名、密鑰交換等算法[17]。多變量密碼的安全性依賴于求解非線性方程組的困難程度，即多變量二次多項(xiàng)式問題。該問題已被證明為非確定性多項(xiàng)式時間（NP）困難。目前沒有已知的經(jīng)典和量子算法可以快速求解有限域上的多變量方程組。與經(jīng)典的基于數(shù)論問題的密碼算法相比，基于多變量的算法的計(jì)算速度快，但公鑰較大，因此適用于無需頻繁進(jìn)行公鑰傳輸?shù)膽?yīng)用場景（如物聯(lián)網(wǎng)設(shè)備等）。
多變量密碼的基礎(chǔ)方案設(shè)計(jì)就形式來說，可以分為兩種形式。
一種是既基于MQ 又基于IP （Isomorphism of Polynomials，多項(xiàng)式同構(gòu)）問題的MPKC 加密或簽名方案設(shè)計(jì)，該方向的設(shè)計(jì)思路和密碼分析方法等都較為成熟，因而產(chǎn)生了較多的研究成果，如Rainbow[18]，UOV[19]，LUOV[20]，PFlash[21]等，以及近年基于大域上變量平方構(gòu)造的SQUARE[22]，EFC[23]，使用了雙重HFE 的ZHFE[24]，Simple Matrix（ABC）加密方案[25]，Cubic ABC 加密方案[26]，基于中間域(大域小域特點(diǎn)結(jié)合的思想)的多變量加密方案有中國的[27][28]等。
另一種是基于新設(shè)計(jì)思路、困難問題的方案設(shè)計(jì)。雖然目前基于IP問題設(shè)計(jì)MPKC方案依然是主流，但在設(shè)計(jì)思路與安全分析都相對成熟的情況下，取得突破性的成就反而不容易。因此MPKC 也需要提出一些新的設(shè)計(jì)思路，提出一些新的困難性假設(shè)來保持這個領(lǐng)域的活力和創(chuàng)新性。比如在PKC2012，有文獻(xiàn)結(jié)合格密碼中LWE的一些特性提出了一種新的困難性假設(shè)問題[29]，并在此困難性假設(shè)下提出了一種安全的加密方案。而在2014 年的Asia crypt會上有學(xué)者提出了一種不同于IP或者IP1S 的全新MPKC 設(shè)計(jì)結(jié)構(gòu)ASASA [30]，設(shè)計(jì)結(jié)合了對稱密碼中的S盒（使用二次多項(xiàng)式構(gòu)造）以及A（仿射的）的構(gòu)造特點(diǎn)。在國際頂級會議CRYPTO 2011 上，則有文獻(xiàn)提出了一種身份識別方案[31]，它的安全性依賴于非交互的承諾方案的存在性, 并給出了形式化的可證安全。從該身份識別方案出發(fā)，有學(xué)者通過Fiat-Shamir轉(zhuǎn)換構(gòu)造了后量子第一輪標(biāo)準(zhǔn)簽名方案MQDSS[32]。該類型的密碼方案還包括最近基于新困難問題的第一輪標(biāo)準(zhǔn)協(xié)議Giophantus[33]。此外，我國方面，基于Hyper-Sphere 超球面方程的多變量方案則可以用于群組簽名的設(shè)計(jì)并提出了相關(guān)的安全性證明[34]，武漢大學(xué)有教授提出了一個可證安全的基于多項(xiàng)式同態(tài)（Morphism of polynomials, MP）的密鑰交換協(xié)議[35]等等。
基于多變量的代表算法有：LUOV、Rainbow、MQDSS等。
4. 基于格 (Lattice-based) 的公鑰密碼學(xué)
在后量子加密的所有方法中，對格的研究是最活躍和最靈活的。這是因?yàn)榛诟竦乃惴ㄔ诎踩?、公私鑰大小、計(jì)算速度上達(dá)到了更好的平衡[36]。與基于數(shù)論問題的密碼算法構(gòu)造相比，基于格的算法可以實(shí)現(xiàn)明顯提升的計(jì)算速度、更高的安全強(qiáng)度和略微增加的通信開銷 [37]。與其他幾種實(shí)現(xiàn)后量子密碼的方式相比，格密碼的公私鑰更小，并且安全性和計(jì)算速度等指標(biāo)更優(yōu)。此外，基于格的算法可以實(shí)現(xiàn)加密、數(shù)字簽名、密鑰交換、屬性加密、函數(shù)加密、全同態(tài)加密等各類功能的密碼學(xué)構(gòu)造。
基于格的算法的安全性依賴于求解格中問題的困難性。這些問題在達(dá)到相同的安全強(qiáng)度時，基于格的算法的公私鑰大小比上述三種結(jié)構(gòu)的方法更小，計(jì)算速度也更快，且能被用于構(gòu)造多種密碼學(xué)原語，因此更適用于真實(shí)世界中的應(yīng)用。
近年來，基于LWE(Learning with Errors) 問題 [38] 和 RLWE (Ring-LWE) 問題[39]的格密碼學(xué)構(gòu)造發(fā)展迅速，被認(rèn)為是最有希望被標(biāo)準(zhǔn)化的技術(shù)路線之一。
基于格的代表算法有：Kyber、Dilithium、NTRU系列、NewHope(Google 測試過)、一系列同態(tài)加密算法 (BGV、GSW、FV等)。
下表中給出了四種后量子密碼算法的簡要對比：
表中的對比反映出該類后量子密碼算法的平均性能指標(biāo)。在實(shí)際應(yīng)用中具體采用哪個類別/哪個算法更好，需要針對應(yīng)用場景進(jìn)行詳細(xì)分析。例如，在一些頻繁需要交換公鑰的場景（例如 HTTPS），可以使用 Lattice-based 的算法等。
除這四種類型的后量子密碼技術(shù)之外，還有基于超奇異橢圓曲線 (Supersingular elliptic curve isogeny)、量子隨機(jī)漫步 (Quantum walk)等技術(shù)的后量子密碼構(gòu)造方法。
三、后量子密碼的發(fā)展前景
近年來，歐洲國家的“安全密碼”（SafeCrypto）項(xiàng)目和日本的CREST密碼數(shù)學(xué)項(xiàng)目都取得了顯著成果，美國NIST的“后量子密碼”（PQCrypto）項(xiàng)目和處于后量子密碼研究和應(yīng)用領(lǐng)域的領(lǐng)先地位。
對于后量子密碼的發(fā)展前景大致如下。
1. 公鑰密碼系統(tǒng)向后量子密碼系統(tǒng)的穩(wěn)步推進(jìn)
傳統(tǒng)計(jì)算技術(shù)和量子計(jì)算技術(shù)的進(jìn)步,推動了對更強(qiáng)大密碼技術(shù)的需求。為了抵御對傳統(tǒng)計(jì)算的攻擊，NIST已經(jīng)建議從提供80位安全性的密鑰大小和算法過渡到提供112位或128位安全性的密鑰大小和算法。而為了提供抵御量子攻擊的安全性，未來還需要進(jìn)行一個過渡，即把公鑰密碼系統(tǒng)過渡到新的后量子密碼系統(tǒng)。
歐洲電信標(biāo)準(zhǔn)協(xié)會與加拿大滑鐵盧大學(xué)量子計(jì)算中心聯(lián)合舉辦的量子安全密碼工作組會議（IQC/ETSI Quantum-Safe Crypto Workshop）也在國際后量子密碼研究領(lǐng)域產(chǎn)生了重要影響。該會始于2013年，參會代表來自于數(shù)學(xué)、密碼學(xué)、物理學(xué)、計(jì)算機(jī)等不同研究領(lǐng)域，目標(biāo)是實(shí)現(xiàn)標(biāo)準(zhǔn)化和部署下一代密碼基礎(chǔ)設(shè)施，特別是抵御量子計(jì)算能力威脅的沖擊。
2. 后量子密碼技術(shù)標(biāo)準(zhǔn)制定逐步受到政府組織的重視
后量子密碼學(xué)標(biāo)準(zhǔn)的制定將需要大量的資源分析候選的抗量子計(jì)劃，為了確保對算法的信任，需要大量的研究人員參與密碼分析。國際上對量子計(jì)算和后量子密碼學(xué)領(lǐng)域的興趣最近有所增加，這跟量子計(jì)算硬件的發(fā)展和各國國家安全局最近對后量子標(biāo)準(zhǔn)的政策制定有關(guān)，大致總結(jié)如下。
美國方面，2015年8月，美國國家安全局公開宣布由于面臨量子計(jì)算的威脅，其計(jì)劃將聯(lián)邦政府各部門目前使用的ECC/RSA算法體系向后量子算法進(jìn)行遷移。而負(fù)責(zé)標(biāo)準(zhǔn)制定的NIST則在2016年2月正式面向全球公開了后量子密碼標(biāo)準(zhǔn)化的路線圖，并在同年秋正式公布征集密碼方案建議的計(jì)劃，其中包括公鑰密碼、數(shù)字簽名以及密鑰交換算法。2017年12月獲得第一輪的建議方案；2018年12月征集后得到第二輪的建議方案；NIST會利用3-5年時間分析這些建議并發(fā)布相關(guān)分析報(bào)告，最終的標(biāo)準(zhǔn)擬制工作也將耗時1-2年。換言之，美國國家標(biāo)準(zhǔn)與技術(shù)局的后量子密碼算法標(biāo)準(zhǔn)最終可能會在2021-2023年出臺。
歐洲量子密碼學(xué)術(shù)和工業(yè)界研究者聯(lián)合組織“后量子密碼”項(xiàng)目（PQCrypto）在2015年發(fā)布了一份初始報(bào)告，在對稱加密、對稱授權(quán)、公鑰加密以及公鑰簽名系統(tǒng)領(lǐng)域都提出了相關(guān)標(biāo)準(zhǔn)化建議。
我國方面，從2018年12月開始，中國密碼學(xué)會在國家密碼管理局的指導(dǎo)下，啟動全國密碼算法設(shè)計(jì)競賽[40]，其中包含分組密碼算法設(shè)計(jì)和公鑰密碼算法設(shè)計(jì)兩部分。而后者則主要是后量子密碼算法的設(shè)計(jì)，當(dāng)年即收到第一輪共38個公鑰密碼算法設(shè)計(jì)，并于2019年10月從中遴選出第二輪12個算法。
3. 企業(yè)界將在后量子密碼發(fā)展應(yīng)用過程中發(fā)揮重要影響力
從以往的密碼系統(tǒng)標(biāo)準(zhǔn)化發(fā)展歷史來看，任何密碼系統(tǒng)都必須在應(yīng)用過程中增強(qiáng)和完善性能，后量子密碼也不例外。因此，通過新型密碼產(chǎn)品的商業(yè)化推廣使用活動，企業(yè)界能夠不斷積累和分析用戶數(shù)據(jù)，從而促進(jìn)后量子密碼系統(tǒng)安全性能和運(yùn)行效應(yīng)的提升。
美國安全創(chuàng)新公司（Security Innovation）注冊并擁有NTRU算法的專利，其提供兩種授權(quán)選項(xiàng)：開源GNUGPL v2授權(quán)以及商業(yè)授權(quán)。從2011年起，該公司發(fā)布了多種實(shí)現(xiàn)NTRU算法的軟件庫，其中包括安全套接字協(xié)議層（SSL）和ARM7/9處理器庫等。NTRU工程（NTRUProject）網(wǎng)站中已經(jīng)存在使用NTRU加密算法的Java和C程序應(yīng)用。目前，NTRU算法已經(jīng)在處理能力有限的移動設(shè)備以及大容量服務(wù)器中得到應(yīng)用。
微軟公司2016年發(fā)布了基于格密碼庫（Lattice Crypto），這種可移植軟件的底層機(jī)制是基于環(huán)上帶誤差學(xué)習(xí)問題（Ring Learning With Errors）。無論對于使用經(jīng)典計(jì)算機(jī)或者量子計(jì)算機(jī)的攻擊者，該軟件庫至少能夠?qū)崿F(xiàn)128位安全性能。谷歌公司在對當(dāng)前后量子密碼技術(shù)發(fā)展進(jìn)行調(diào)查后，也提出了基于環(huán)上帶誤差學(xué)習(xí)問題的密鑰交換協(xié)議。這些工作都對量子密碼系統(tǒng)的標(biāo)準(zhǔn)化具有重要影響。
