1.2 量子計算機的潛在威脅

當今信息安全領域廣泛使用的公鑰密碼體制主要都是基于經典計算機“難以求解”的數學問題所設計構造的。例如，RSA基于大整數分解問題，Diffie-Hellman和ElGamal基于離散對數問題，ECC基于橢圓曲線離散對數問題。具體來說，在經典計算范式（Classic Computing Paradigm）下，RSA、Diffie-Hellman和ECC等密碼算法所依賴的底層數學問題是足夠困難而無法在指數時間O（n2n）內求解的[14]，其中n代表被分解的整數或離散對數的參數。一旦上述數學問題可以在一個合理的時間復雜度（如多項式時間）下求解，則該解決方案就可以用來破解相關的密碼算法并還原出密鑰和原始加密信息。

1994年，貝爾實驗室的數學家Peter Shor首次論述了通過使用能執行量子算法的量子計算機，可以在多項式時間O（n2）內求解大整數分解問題[15]。在對Shor提出的量子算法進行改進后，同樣可以有效求解（橢圓曲線）離散對數問題。Shor的研究發現迅速掀起了世界范圍內量子計算機和量子算法的研究浪潮：一方面，諸如Grover搜索算法、基于量子傅里葉變換和基于量子遍歷的量子算法層出不窮，顯著縮短了傳統公鑰密碼體制所依賴數學問題的求解時間[16]；另一方面，大量的研究工作朝著設計出實際可行的、可執行量子算法的、擁有強大算力的量子計算機這一目標而不斷向前推進。據專業人士估計，破解2048位強度的RSA密鑰可能需要當今最快的超級計算機耗費80年以上，而運行Shor算法的量子計算機只需要不到8h就可以完成。2008年，中國科學技術大學潘建偉教授領導的研究團隊率先在光量子計算機上實現了量子分解算法。2015年，全球第一家量子計算公司D-Wave宣布開發出了一種1000量子比特（Qubit）的新型處理器。2017年，IBM公司宣布推出全球首個商用的量子計算服務。量子計算機和量子算法的快速發展，對現有公鑰密碼體制造成了巨大沖擊。在量子計算機面前，傳統公鑰密碼體制通過增加密鑰長度和改變參數來抵御安全攻擊的方式不再有效。2019年10月23日，Natrue上刊登了Google公司關于實現“量子霸權”（Quantum Supremacy）的論文[17]，介紹了Google公司量子硬件首席科學家John Martinis所在團隊設計的具有53量子比特的Sycamore處理器（即“懸鈴木”），可在200s內完成IBM超級計算機Summit需要花費1萬年才能完成的計算任務。2020年12月4日，中國科學技術大學宣布潘建偉院士所在團隊成功構建了76個光子量子比特（Photonic Qubit）的量子計算原型機“九章”，只需200s即可求解5000萬個樣本的高斯玻色取樣，而超級計算機“富岳”完成相同計算需要6億年?！熬耪隆边@一研究成果在Science上同步發表[18]，牢固確立了我國在國際量子計算研究領域中的第一方陣地位。在經典計算機中，使用了由電平（電壓）表征的比特（bit）來對信息進行存儲，且比特值只能為0或1中的一個。而在量子計算機中，量子計算所使用的量子比特則不再是一個簡單的0或1了。1量子比特是1個展開的二維空間，其遵循量子力學的規律，可同時為0和1。這是一種被稱為“疊加態”（Superposition）的屬性。同理，如果擁有2量子比特，就可以同時具備4（22）個計算狀態；如果擁有333量子比特，將會具備2333，即1.7×10100個計算狀態，這比宇宙中原子數目的總和還要多。在這種特性下，量子比特的計算狀態會隨著量子比特的數量增加而呈“指數級”增長，使量子計算機在探索一個問題時，可能擁有眾多解決方案，以實現高速并行求解。

雖然目前量子計算機還遠未達到商用階段，但埃森哲公司（Accenture）的技術分析報告[19]指出：根據學術界的共識，在2028年之前，量子計算機將具備足夠大的規模來實施Shor算法并能攻破當前所使用的傳統公鑰密碼體制。隨著研究人員在增加量子比特壽命方面不斷取得重大研究進展[20]，上述情形可能在2026年就會發生?？梢钥吹?，Google公司在2019年所設計的“懸鈴木”實際上只能在-273.12℃這一超低溫環境下正常運行。我國于2020年提出的“九章”卻可以整體運行在正常的室溫環境下。這也反映了量子計算機技術一直都在突飛猛進。盡管在理論上真正實現了一個通用容錯的量子計算機需要100萬量子比特，且每量子比特的操控精度要求為99.8%以上，但我國相關研究團隊和Google公司均制訂了相似的研究計劃：預計在未來5年實現1000量子比特的原型機。這樣就能比經典計算機更快求解一些實際的密碼學應用，并且在未來10年完成100萬量子比特這一極具挑戰性的研究目標，初步實現商用量子計算機。

在實際可用的量子計算機面前，傳統公鑰密碼體制所基于的數學難題將可在多項式時間內被輕易求解，進而依賴傳統公鑰密碼體制而構建的信息安全系統及各種應用將面臨嚴峻的安全攻擊，甚至是被完全破解的潛在威脅。企業和組織必須確保在未來量子計算機的攻擊下，使用傳統加密方案加密的敏感數據仍然能保持多年內不可被解密。量子計算機的迅猛發展在給信息安全領域帶來威脅的同時，也點燃了研究能抵御量子計算攻擊的密碼算法的火花。對于對稱密碼體制，以最常使用的AES-128加密算法為例，破解AES-128最有效的方法是使用暴力破解來搜索并找到正確的密鑰。由于量子計算機在執行Grover搜索算法后可明顯加速對AES-128的暴力破解，因此研究者認為應當加倍AES-128所使用的密鑰長度來實現量子計算機下128位的安全級別，即使用AES-256來替代常用的AES-128即可。對于傳統公鑰密碼體制，由于量子計算機在執行Shor算法后可在多項式時間內對其完成求解，增加密鑰長度并不能抵御量子計算攻擊，因此研究者開始研究由不受量子計算攻擊影響的數學問題來構建新型公鑰密碼算法，以在未來全面取代傳統公鑰密碼體制[21]。