對稱密碼的量子分析法綜述*

董曉陽

1.清華大學(xué) 網(wǎng)絡(luò)科學(xué)與網(wǎng)絡(luò)空間研究院, 北京 100084

2.密碼科學(xué)技術(shù)國家重點實驗室, 北京 100878

3.山東區(qū)塊鏈研究院, 濟南 250102

4.中關(guān)村實驗室, 北京 100194

1 引言

1994 年, Shor 的開創(chuàng)性工作[1]表明, 規(guī)模足夠大的量子計算機能夠在多項式時間內(nèi)對大整數(shù)進行因子分解和求解離散對數(shù)問題, 這將會破壞當(dāng)今廣泛使用的許多公鑰方案, 如RSA 和ECC 等.為了迎接未來的挑戰(zhàn), 公鑰密碼學(xué)界和標準化組織投入了大量精力進行后量子公鑰密碼方案的研究.特別地, 美國國家標準與技術(shù)研究院(National Institute of Standards and Technology, NIST) 在2016 年啟動了后量子標準征集競賽(Post-Quantum Cryptography Standardization), 旨在征求、評估和標準化一個或多個抗量子公鑰密碼算法[2].相比之下, 關(guān)于量子計算如何改變對稱密碼的安全格局的研究似乎不太活躍.1996年, Grover 算法[3]的提出使得窮舉搜索攻擊在量子計算環(huán)境下能夠獲得二次加速(quadratic speedup),即在N個元素中找到某一特定元素, 經(jīng)典計算環(huán)境下所需的時間復(fù)雜度平均為O(N/2), 而在量子計算環(huán)境下, Grover 算法能夠在O(√N) 的時間復(fù)雜度下找到該元素.在十余年的時間里(1996–2010 年前后),密碼研究者普遍認為, Grover 算法是對稱密碼的唯一量子計算攻擊威脅, 因此密碼研究者認為加倍密鑰長度即可解決該問題[4].2010 年和2012 年, 隨著Kuwakado 和Morii 的初步工作, 這種觀點開始發(fā)生變化.他們證明了經(jīng)典計算環(huán)境下可證明安全的Even-Mansour 密碼和三輪Feistel 網(wǎng)絡(luò)可以在量子計算機的幫助下在多項式時間內(nèi)被破解[5,6].在2016 年美密會上, 法國密碼研究者Kaplan 等人[7]利用量子計算模型進一步在多項式時間……