文/郁昱 張江

?

淺談量子計算與后量子密碼

文/郁昱 張江

郁昱

上海交通大學特別研究員，博士生導師。主要從事密碼學基礎(chǔ)理論的研究工作，2010年回國后曾分別在華東師范大學和清華大學任教，多項研究成果發(fā)表在密碼三大會（CRYPTO/EUROCRYPT/ ASIACRYPT）和CCS, TCC, CHES, CT-RSA, ESORICS等密碼與信息安全的代表性會議上。目前服務(wù)于國際密碼學會理事會（IACR board）擔任觀察員并負責學會官網(wǎng)www.iacr.org的日常管理事務(wù)，2015年獲得中國密碼學會優(yōu)秀青年獎。

張江

信息安全博士，主要關(guān)注于可證明安全、公鑰加密和密碼協(xié)議的研究，現(xiàn)為密碼科學技術(shù)國家重點實驗室助理研究員，在國際重要密碼會議和期刊 EUROCRYPT、ASIACRYPT、PKC、DCC、TCS等發(fā)表了多項研究成果。個人主頁：jiangzhang.net

最近一些新聞媒體報道了量子信息/量子計算將對傳統(tǒng)密碼技術(shù)（也稱為現(xiàn)代密碼或經(jīng)典密碼）構(gòu)成嚴峻挑戰(zhàn)甚至將是徹底的顛覆。作為密碼學的研究人員，我們拋磚引玉談?wù)剬Α傲孔佑嬎鉽s密碼技術(shù)”這一問題的看法，同時簡單介紹一下近期正在開展的后量子密碼方面的研究工作。

生活中的“密碼”

隨著信息技術(shù)的發(fā)展和互聯(lián)網(wǎng)的普及，密碼技術(shù)被廣泛用于網(wǎng)絡(luò)和信息系統(tǒng)安全的各個方面，保護著信息的秘密性、完整性、不可抵賴性等信息安全的重要屬性，也是網(wǎng)絡(luò)空間安全學科的一個重要組成部分［1］。由于翻譯和使用習慣的原因，絕大多數(shù)民眾理解的密碼僅限于登錄各種應(yīng)用賬號（如郵箱、支付寶、微信等）需要輸入的若干數(shù)字和字母組合，即所謂的口令（英文為password/passphrase）。通常來說，口令只是用于實現(xiàn)服務(wù)器對用戶的身份認證，然而密碼學（Cryptology）的意義則廣泛得多，生活中常用的手機SIM卡、銀行U盾、比特幣、網(wǎng)絡(luò)證書、TLS/ SSL等協(xié)議甚至包括公交卡、二代身份證等都需要不同密碼技術(shù)的支持。

量子密碼技術(shù)對傳統(tǒng)密碼技術(shù)的“威脅”

相對于現(xiàn)代密碼技術(shù)，目前量子密碼的應(yīng)用相對較少，主要包括量子密鑰分發(fā)和量子比特承諾等，其中量子密鑰分發(fā)可用于實現(xiàn)信息的安全傳輸，是目前最受關(guān)注的量子密碼應(yīng)用。接下來，將圍繞安全的信息傳輸，簡要介紹一下傳統(tǒng)的密碼系統(tǒng)。經(jīng)典的密碼系統(tǒng)主要由密鑰和密碼算法兩部分組成，密碼算法通常是公開的，而密碼系統(tǒng)的安全性只決定于密鑰的保密性。如圖1所示，在一個加密系統(tǒng)中，加密算法Enc和解密算法Dec都是公開的，而加密者Alice和解密者Bob則分別擁有加密密鑰k1和解密密鑰k2，Eve是傳輸信道上的攻擊者。當Alice想要發(fā)送數(shù)據(jù)m給Bob時，Alice將加密密鑰k1和數(shù)據(jù)m作為加密算法Enc的輸入，計算得到密文c=Enc（k1，m）并發(fā)送給解密者Bob。當接收到密文c后，Bob將解密密鑰k2和密文c作為解密算法Dec的輸入，計算得到明文m=Dec（k2，c）。

根據(jù)密鑰使用方式的不同，加密系統(tǒng)又分為對稱加密系統(tǒng)和公鑰加密系統(tǒng)。在對稱加密系統(tǒng)中，加密和解密是用同一個密鑰，即k1=k2，該密鑰是對外保密的。對稱加密系統(tǒng)主要包括流密碼和分組密碼，其中分組密碼較為常用，我們熟知的美國的分組加密標準DES、AES以及我國的商用分組加密標準SM1、SM4等。這類算法通常是密碼學家在一些現(xiàn)有的設(shè)計原則和分析方法上設(shè)計出來的，而不是基于已知的數(shù)學和計算復雜性理論方面的困難問題。據(jù)我們所知，在量子計算模型下，目前針對對稱密碼系統(tǒng)最高效的Grover算法，也只是將密鑰的有效長度減少為原來的一半。換句話說，真正意義上的量子計算機，即使能夠?qū)崿F(xiàn)，其破解AES-256仍然需要2128量級的計算代價。

使用對稱加密有個前提，即加密者和解密者必須事先共享一個較短（例如128比特）的密鑰，這在一些應(yīng)用場景下是不現(xiàn)實的。公鑰加密系統(tǒng)的出現(xiàn)，解決了這個問題。最具開創(chuàng)性的Diffie-Hellman密鑰交換協(xié)議可以確保通信雙方在不共享任何保密信息的前提下建立共享的密鑰，之后又出現(xiàn)了RSA和ElGamal公鑰加密，我國也有相應(yīng)的公鑰密碼標準SM2。由于公鑰類的加密效率相對較低，現(xiàn)實應(yīng)用中，在通信雙方建立共享密鑰之后，一般都會使用更為高效的對稱加密算法對大量數(shù)據(jù)進行加密。公鑰加密的特點是，它們的安全性都是建立在一些著名的計算困難問題之上，如RSA大數(shù)分解，離散對數(shù)等等，目前研究學者沒有找到在圖靈機模型下高效求解大整數(shù)分解和離散對數(shù)問題的經(jīng)典算法，但美國科學家Peter Shor在1995年卻給出了能夠在多項式時間內(nèi)高效求解大整數(shù)分解和離散對數(shù)的量子算法。即借助于量子計算機，攻擊者可以高效地破解基于大整數(shù)分解和離散對數(shù)問題的RSA和Diffie-Hellman等公鑰密碼方案。雖然目前量子計算機還局限在幾個量子比特的原型階段，在其上面運行Shor算法也僅能分解兩位的合數(shù)，科學家們都在為迎接“后量子時代”做準備。量子信息技術(shù)對以上問題給出的解決方案是通過量子密鑰分發(fā)技術(shù)在傳輸雙方建立共享密鑰，然后再通過香農(nóng)一次一密或類似的方法對稱地加密實現(xiàn)無條件的安全性。然而目前量子密鑰分發(fā)的速率仍是實現(xiàn)高速率信息傳輸?shù)钠款i。而且，與傳統(tǒng)的密碼技術(shù)一樣，理論上可論證的安全性并不等同于實際系統(tǒng)的安全性，密碼系統(tǒng)在實現(xiàn)時硬件和系統(tǒng)的非理想性也可成為能被攻擊者利用的漏洞。

圖1　現(xiàn)代加密系統(tǒng)的工作原理圖（由黃晨歌繪制）

后量子密碼技術(shù)

量子算法對于傳統(tǒng)密碼系統(tǒng)的沖擊是由于量子算法相對于經(jīng)典算法在一些問題上具有一定的加速性（可以簡單理解為量子算法具有高度的并行計算能力）。例如，在傳統(tǒng)計算機上需要亞指數(shù)計算時間的大整數(shù)分解問題，在量子計算機上多項式時間內(nèi)就可求解。然而，量子算法相對于傳統(tǒng)算法的“指數(shù)”加速性并不是對所有數(shù)學問題都成立。事實上，對于某些問題（如NP完全問題、基于格、基于編碼和基于多變元方程的數(shù)學問題），量子算法相對于傳統(tǒng)算法并沒有明顯的優(yōu)勢。緊跟著Shor算法的出現(xiàn)，國內(nèi)外密碼學家已對基于格、基于編碼和基于多變元方程密碼方案展開了大量的研究，力圖設(shè)計可以對抗量子計算機的經(jīng)典密碼算法，并統(tǒng)稱這些研究為后量子密碼學。以下我們對后量子密碼中的一兩個基本困難問題做一個簡單的介紹。這里攻擊者的目標是求解以下的n元一次方程組，其中系數(shù)a11， … ， aqn，未知數(shù)x1，… ， xn都是GF（2）上隨機選取的（即0或1的隨機比特），e1， …， eq都各自獨立的服從參數(shù)為0＜u＜1/2的Bernoulli分布（即每個ei等于1的概率為u，否則ei等于0）。

該問題要求在已知給定的系數(shù)a11， …， aqn和結(jié)果y1， … ， yq的條件下，求解未知數(shù)x1， … ， xn（如果x1， … ， xn求解出來，e1，… ， eq也立即可以得到）。以上問題就是著名的Learning Parity with Noise （LPN）問題。當q遠大于n，并且u是小于1/2的常數(shù)的情況下，未知數(shù)x1， … ， xn是幾乎可以唯一確定的。該問題被證明在最壞情況下是NP完全的，即使在平均情況下，人們至今沒有找到解決該問題的有效算法，目前漸進意義上最好的BKW算法需要亞指數(shù)的時間復雜度，更重要的是，量子算法解決該問題也不具有任何優(yōu)勢。我國學者在利用LPN設(shè)計后量子對稱密碼算法［2］和針對LPN在具體參數(shù)設(shè)定下的密碼分析［3，4］上取得了較為領(lǐng)先的成果，我們也有一項進行中的工作是基于標準LPN問題的困難性設(shè)計公鑰密碼算法和不經(jīng)意傳輸協(xié)議。Oded Regev進一步將以上的LPN問題推廣到更大的素數(shù)域上，即以上方程組中所有的系數(shù)和未知數(shù)都是GF（p）上的元素，且相關(guān)的加法和乘法都在GF（p）上運算，其中p是一個較大的素數(shù)，e1， …，eq都獨立地服從GF（p）上的離散高斯分布。以上推廣后的問題就是著名的Learning with Errors （LWE）問題。目前已知LWE在一定的參數(shù)設(shè)定下可以歸約到GapSVP，SIVP等格上的困難問題（即求解LWE問題并不比求解格上困難問題容易），因此也是后量子安全的。雖然LWE相對于LPN在效率上有一定降低，但其具有更廣泛的密碼應(yīng)用，除了公鑰加密，LWE還可以用來設(shè)計抗碰撞哈希函數(shù)、全同態(tài)加密等。我國學者在這方面也有一些貢獻，如張江等人基于Ring-LWE設(shè)計的可用于TLS協(xié)議的后量子安全的高效密鑰交換協(xié)議［5］。

綜上，現(xiàn)代密碼學并不等同于基于RSA、離散對數(shù)等少數(shù)幾個數(shù)論困難問題的密碼系統(tǒng)，量子計算機的到來也并不是現(xiàn)代密碼學的末日，安全信息傳輸只是傳統(tǒng)密碼學諸多應(yīng)用中的一個，因此量子密碼不可能完全取代傳統(tǒng)密碼。經(jīng)過近20年的發(fā)展，后量子密碼學的研究已經(jīng)取得了豐碩的成果，同時也為抵抗量子計算機攻擊儲備了大量的密碼技術(shù)，一些標準制定機構(gòu)即將甚至已經(jīng)在開展后量子密碼算法的標準化工作，相信在不久的將來量子安全的（但仍是在傳統(tǒng)計算機上運行）密碼系統(tǒng)即可以部署到我們?nèi)粘Ｊ褂玫南到y(tǒng)和網(wǎng)絡(luò)中，更好地保護我們的信息安全。

參考文獻

［1］ 張煥國，韓文報，來學嘉，林東岱，馬建峰，李建華. “網(wǎng)絡(luò)空間安全綜述” 中國科學，第46卷，第2期：125-164，2016.

［2］ Yu Yu and John Steinberger. “Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN”， in Advances in Cryptology - EUROCRYPT 2016.

［3］ Qian Guo， Thomas Johansson， Carl L?ndah.， “Solving LPN Using Covering Codes”. In Advances in Cryptology - ASIACRYPT 2014.

［4］ Bin Zhang， Lin Jiao， Mingsheng Wang. “Faster Algorithms for Solving LPN”. In Advances in Cryptology -EUROCRYPT 2016.

［5］ Jiang Zhang， Zhenfeng Zhang， Jintai Ding， Michael Snook，?zgür Dagdelen. “Authenticated Key Exchange from Ideal Lattices”， In Advances in Cryptology - EUROCRYPT 2015.