量子計算對當代密碼系統之威脅及對策

Treats of Quantum Computing Occurring with Modern Cryptosystems and Possible Strategies to Conquer

劉江龍(Chiang-Lung Liu)

《前瞻科技與管理》 9卷1&2期 (2019/11) Pp. 4-21

https://doi.org/10.6193/JATM.201911_9(1_2).0002

摘要

由於近幾年來量子電腦技術快速的發展，以往基於量子特性所提出的破密演算法有可能在不久的將來得以實現，屆時不管是傳統的對稱式密碼技術或非對稱式密碼技術的安全均會受到威脅，其中尤以基於離散對數計算及質因數分解難題的金鑰分配協定或密碼系統所受的安全威脅最為嚴重。本文之目的即在說明Grover演算法及Shor演算法對當代密碼技術安全所造成的威脅，並提供對稱式密碼系統面對Grover演算法威脅的補強策略；此外，本文同時說明目前世界各國取代傳統金鑰分發技術所採取的量子密鑰分發（Quantum Key Distribution, QKD）技術及後量子密碼學（Post-Quantum Cryptography, PQC）的發展現況；最後針對國內未來在量子計算的威脅下提出相關建議，以供國內網路安全相關單位未來制定相關因應策略之參考。

關鍵字

Grover演算法 ； Shor演算法 ； 量子計算 ； 量子密鑰分發 ； 後量子密碼學

並列摘要

With rapid development of quantum computing technology in recent years, the cryptanalytic algorithms based on quantum characteristics can be realized in the near future. Therefore, the security of the traditional symmetric or asymmetric cryptography may not be guaranteed as in the past, especially the key-distribution protocols and cryptosystems which are either based on the hard problems of calculating discrete logarithm or factoring. The purpose of this article is to explain how the Grover and Shor algorithms threat the security of the modern cryptography. Meanwhile, the strategy to enhance the security of the symmetric cryptography under the threat of Grover algorithm is also provided. Moreover, the development of the quantum key distribution (QKD) and the post-quantum cryptography (PQC), which will be used to replace the traditional key distribution techniques in the future, is also described. Related suggestions to deal with the threats of the quantum computing are also provided in this article for the references of the network security-related departments to establish the corresponding strategies.

並列關鍵字

Grover algorithm ； Shor algorithm ； quantum computing ； quantum key distribution ； post-quantum cryptography

參考文獻

Ajtai M., and Dwork C., 1997, “A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence,” in Proceedings of the Twenty-Ninth STOC, El Paso, TX: Association for Computing Machinery, 284-293. doi:10.1145/258533.258604

Biham E., and Shamir A., 1993, Differential Cryptanalysis of the Data Encryption Standard, New York, NY: Springer-Verlag. doi:10.1007/978-1-4613-9314-6

Diffie W., and Hellman M. E., 1976, “New Directions in Cryptography,” IEEE Transactions on Information Theory, 22(6), 644-654. doi:10.1109/TIT.1976.1055638

ElGamal T., 1985, “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” IEEE Transactions on Information Theory, 31(4), 469-472. doi:10.1109/TIT.1985.1057074

Elliott C., Colvin A., Pearson D., Pikalo O., Schlafer J., and Yeh H., 2005, “Current Status of the DARPA Quantum Network,” in Proceedings of the Defense and Security, Orlando, FL: Society of Photo-Optical Instrumentation Engineers, 138-149. doi:10.1117/12.606489