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

文/郁昱 張江

?

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

文/郁昱 張江

郁昱

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

張江

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

最近一些新聞媒體報道了量子信息/量子計算將對傳統密碼技術（也稱為現代密碼或經典密碼）構成嚴峻挑戰甚至將是徹底的顛覆。作為密碼學的研究人員，我們拋磚引玉談談對“量子計算vs密碼技術”這一問題的看法，同時簡單介紹一下近期正在開展的后量子密碼方面的研究工作。

生活中的“密碼”

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

量子密碼技術對傳統密碼技術的“威脅”

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

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

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

圖1　現代加密系統的工作原理圖（由黃晨歌繪制）

后量子密碼技術

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

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

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

參考文獻

［1］ 張煥國，韓文報，來學嘉，林東岱，馬建峰，李建華. “網絡空間安全綜述” 中國科學，第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.