淺談量子計(jì)算與后量子密碼

文/郁昱 張江

?

淺談量子計(jì)算與后量子密碼

文/郁昱 張江

郁昱

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

張江

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

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

生活中的“密碼”

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

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

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

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

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

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

后量子密碼技術(shù)

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

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

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

參考文獻(xiàn)

［1］ 張煥國，韓文報(bào)，來學(xué)嘉，林東岱，馬建峰，李建華. “網(wǎng)絡(luò)空間安全綜述” 中國科學(xué)，第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.