新聞中心

後量子密碼學概述與未來展望


壹  前言

因應量子計算對現行主流密碼學方法造成的衝擊和安全威脅,在傳統電腦(Classical Computer)建立和執行具備抵抗量子計算攻擊的後量子密碼學(Post-Quantum Cryptography, PQC)方法是目前資訊安全的領域重要議題之一。

貳  後量子密碼學概述

一、 密碼學方法分類

密碼學方法主要可以分為對稱式密碼學方法和非對稱式密碼學(或稱為公開金鑰密碼學)方法兩大類。

現行主流的對稱式密碼學方法主要有高級加密標準(Advanced Encryption Standard, AES)密碼學方法,並且高級加密標準密碼學仍具備抗量子計算攻擊的能力,所以未來仍可以繼續使用高級加密標準密碼學方法。雖然對稱式密碼學方法還包含有資料加密標準(Data Encryption Standard, DES)密碼學方法和RC4 (Rivest Cipher 4)密碼學方法等,但這些方法已被證實不安全,所以不建議採用。

現行主流的非對稱式密碼學方法主要有RSA (Rivest-Shamir-Adleman)密碼學方法和橢圓曲線密碼學(Elliptic Curve Cryptography, ECC)方法,但這些方法已經被證明無法抗抵量子計算攻擊(將於下一節中描述說明),所以採用其他非對稱式密碼學方法來抵抗量子計算已成為刻不容緩的目標。因此,盤點現有的非對稱式密碼學方法除了RSA密碼學方法和橢圓曲線密碼學方法之外,還有基於格(Lattice)的密碼學方法、基於雜湊(Hash)的密碼學方法、基於編碼(Code)的密碼學方法、以及基於多變量(Multivariate)的密碼學方法等。

二、 量子計算對密碼學的衝擊

隨著量子電腦(Quantum Computer)技術的成熟,許多的量子演算法也逐漸蓬勃發展,這些演算法運用量子邏輯閘和量子疊加態、量子糾纏態等量子特性可以提升運算效率,解決傳統電腦的非決定性多項式時間(Nondeterministic Polynomial Time, NP)問題。其中,知名的量子演算法包含有秀爾(Shor)量子演算法可以快速解決質因數分解問題和離散對數問題[1]。另外,格羅弗(Grover)量子搜尋演算法可以大量減少搜尋次數[2],提升破解出金鑰的效率。

然而,RSA密碼學方法的安全性主要建構在質因數分解問題的基礎上,而橢圓曲線密碼學方法的安全性主要建構在離散對數問題的基礎上,所以在傳統電腦上嘗試破解這些密碼學方法是非決定性多項式時間問題;但是在量子電腦搭配秀爾量子演算法嘗試破解這些密碼學方法將會是多項式時間問題,可以快速破解質因數分解問題和離散對數問題[1]。有鑑於此,現行主流的非對稱式密碼學方法(RSA密碼學方法和橢圓曲線密碼學方法)不具備抗量子計算攻擊的能力。

另外,雖然格羅弗量子搜尋演算法[2]可以通過加速搜尋效率的方式來提升破解對稱式密碼學方法的效率,但仍無法把破解密碼學方法的問題從非決定性多項式時間問題化簡為多項式時間問題。因此,現行主流的對稱式密碼學方法(高級加密標準密碼學方法)可以通過加長金鑰長度的方式來提升抵抗量子計算攻擊。

有鑑於此,近年來主要致力於發展基於其他非決定性多項式時間問題的非對稱式密碼學方法,包含有基於格的密碼學方法、基於雜湊的密碼學方法、基於編碼的密碼學方法、以及基於多變量的密碼學方法等,建構具備抵抗量子計算攻擊能力的密碼學方法,稱之為「後量子密碼學」。

三、 後量子密碼學標準化進展

為建立國際通用且足夠安全的標準後量子密碼學方法,美國國家標準暨技術研究院(National Institute of Standards and Technology, NIST)在2016年開始公開評選後量子密碼學方法[3]。世界各地的密碼學專家向提出美國國家標準暨技術研究院各自的後量子密碼學方法,在多個指標(包含安全等級、金鑰長度、運算時間長度、簽章長度等)的競爭和權衡下選出最合適的密碼學方法成為標準後量子密碼學方法。

在2022年7月,美國國家標準暨技術研究院發佈了第三輪後量子密碼學方法標準化進展報告,並且評選出多個後量子密碼學方法成為標準,如表1所示。在報告中指出基於格的密碼學方法具備較短的運算時間、較短的簽章長度等優勢,所以在金鑰封裝機制(Key-Encapsulation Mechanism, KEM)和數位簽章演算法(Digital Signature Algorithm, DSA)都挑選出基於格的密碼學方法作為標準後量子密碼學方法。其中,金鑰封裝機制的標準後量子密碼學方法包含有CRYSTALS–Kyber,數位簽章演算法的標準後量子密碼學方法包含有CRYSTALS–Dilithium和Falcon等。除此之外,由於基於雜湊的密碼學方法具有較短的金鑰長度,所以SPHINCS+也入選為數位簽章演算法的標準後量子密碼學方法之一[3]。未來在部署系統和服務時,可以根據運算時間、簽章長度、金鑰長度等考量來選擇適合的標準後量子密碼學方法。

後量子密碼學方法分類 金鑰封裝機制 數位簽章演算法
基於格的密碼學方法 CRYSTALS–Kyber (第3輪) CRYSTALS–Dilithium (第3輪)Falcon (第3輪)
基於雜湊的密碼學方法 SPHINCS+ (第3輪)
基於編碼的密碼學方法 BIKE (第4輪候選)Classic McEliece (第4輪候選)HQC (第4輪候選)
基於多變量的密碼學方法
超奇異同源(Supersingular Isogeny)的密碼學方法 SIKE (第4輪候選)
表1 第三輪後量子密碼學方法標準化進展評選結果[3]

另外,由於目前金鑰封裝機制只評選出基於格的密碼學方法作為標準後量子密碼學方法,為避免未來基於格的密碼學方法被破解,所以需評選另一套其他的密碼學方法來作為備案。其中,基於編碼的密碼學方法的BIKE、Classic McEliece、HQC等密碼學方法分別被列入第4輪候選。

參  結論

為建構抵抗量子計算攻擊的能力,本院朝向後量子密碼學公開金鑰基礎建設(Public Key Infrastructure, PKI)技術及應用演進與規劃,致力研發標準後量子密碼學關鍵技術,逐步實現符合國際標準與互通性目標。

肆  參考文獻

[1] P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," in SIAM Journal on Computing, vol. 26, no. 5, pp. 1484-1509, 1997. DOI: 10.1137/S0097539795293172
[2] G. M. Vinod and A. Shaji, "Finding Solutions to the Integer Case Constraint Satisfiability Problem Using Grover’s Algorithm," in IEEE Transactions on Quantum Engineering, vol. 2, pp. 1-13, 2021. DOI: 10.1109/TQE.2021.3120449.
[3] G. Alagic et al., "Status Report on the Third Round of the NIST Post-quantum Cryptography Standardization Process," NIST Special Publication, NISTIR 8413, 2022. DOI: 10.6028/NIST.IR.8413.