Quantum Computers and Algorithms: A Threat to Classical Cryptographic Systems
Article Sidebar
Main Article Content
Abstract
Contemporary cryptographic algorithms are resistant to the strongest threats to cybersecurity and high profile cyber-attacks. In recent times, information security scientists and researchers had developed various cryptographic schemes that defeated attacks using the most sophisticated (in terms of processor speed) classical computer. However, this resistance will soon erode with the arrival of quantum computers. In this paper, we profiled quantum computers and quantum algorithms based on their widely believed threat against currently secure cryptographic primitives. We found that Grover’s and Shor’s quantum-based algorithms actually pose a threat to the continued security of symmetric cryptosystems (e.g. 128-bit AES) and asymmetric (public key) cryptosystems (e.g. RSA, Elgamal, elliptic curve Diffie Hellman (ECDH), etc.) respectively. We discovered that the source of the algorithms’ cryptanalytic power against the current systems, stems from the fact that they (Grover and Shor) both equipped their respective algorithms with a quantum circuit component that can execute the oracle in parallel by applying a single circuit to all possible states of an n-qubit input. With this exponential level of processing characteristic of quantum computers and quantum-based algorithms, it is easy for the current cryptosystems to be broken since the algorithms can existentially solve the underlying mathematical problems such as integer factorization, discrete logarithm problem and elliptic curve problem, which formed the basis of the security of the affected cryptosystems. Based on this realization and as part of our readiness for a post quantum era, we explored other mathematical structures (lattices, hashes, codes, isogenies, high entropy-based symmetric key resistance, and multivariate quadratic problems) whose hardness could surpass the cryptanalytic nightmare posed by quantum computers and quantum-based algorithms. Our contribution is that, based on the findings of this research work, we can confidently assert that all hope is not lost for organizations heavily relying on protocols and applications like HTTPS, TLS, PGP, Bitcoin, etc., which derived their security from the endangered cryptosystems.
Downloads
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
How to Cite
References
T. ElGamal, "A public key cryptosystem and a signature scheme based on discrete logarithms," in Workshop on the Theory and Application of Cryptographic Techniques, Springer Berlin Heidelberg, 1984.
N. Koblitz, “Elliptic curve cryptosystems”, Mathematics of Computation, 48 (1987), 203-209.
V. Miller, “Uses of elliptic curves in cryptography”, Advances in Cryptology– Crypto '85, Lecture Notes in Computer Science, 218, Springer-Verlag, 1986, pg. 417-426
D. Johnson, A. Menezes, S. A. Vanstone, "The elliptic curve digital signature algorithm (ECDSA)", International Journal of Information Security 1(1):36-63, 2001, Springer.
S. Vanstone, “Responses to NIST's Proposal”, Communications of the ACM, 35, July 1992, 50-52 (communicated by John Anderson).
A. P. Menezes, Van, Oorschot, and S. Vanstone, CRC Press, 1996. Handbook of Applied Cryptography.
A. Sun, et al., “The QR-code reorganization in illegible snapshots taken by mobile phones," in Proc. Int. Conf. on Computational Sci. and its Applicant, 2007, pp.532-538.
A. K. Lenstra, Integer Factoring. In: van Tilborg, H.C.A., Jajodia, S. (eds) Encyclopedia of Cryptography and Security. Springer, Boston, MA. 2011, pp 611–618.
V. I. Nechaev, Complexity of a determinate algorithm for the discrete logarithm. Math Notes 55(2):155–172. Translated from Matematicheskie Zametki 55(2): 91–101, (1994). This result dates from 1968.
V. Shoup, Lower bounds for discrete logarithms and related problems. In: Proceedings of EUROCRYPT ’97. Lecture notes in computer science, 1997. vol 1233, pp 256–266.
Kleinjung et al. "Factorization of a 768-bit RSA modulus" (PDF). International Association for Cryptologic Research (2010-02-18). Retrieved 2010-08-09.
O. Goldreich, Avi Wigderson, "IV.20 Computational Complexity", in Gowers, Timothy; Barrow-Green, June; Leader, Imre (eds.), The Princeton Companion to Mathematics, Princeton, New Jersey: Princeton University Press, 2008, pp. 575–604, ISBN 978-0-691-11880-2, MR 2467561. See in particular p. 583.
McCurley, K. S. The Discrete Logarithm Problem. Proceedings of Symposia in Applied Mathematics, vol. 42, 1990.
M. A Nielsen, Chuang, Isaac L. X. Quantum Computation and Quantum Information. Cambridge University Press, 2010. p. 13. ISBN 978-1-107-00217-3.
P. Shor, (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer∗". SIAM Journal on Computing. 26 (5), 1995 pg. 1484–1509,.
C. P Williams, Explorations in Quantum Computing. Springer (2011). pp. 9–13. ISBN 978-1-84628-887-6.
C. Hughes, J. Isaacson, A. Perry, R. F. Sun, J. Turner, Entanglement. In: Quantum Computing for the Quantum Curious, 2021. Springer, Cham.
P. K. Pradhan, Sayan Rakshit and Sujoy Datta. “Lattice Based Cryptography: Its Applications, Areas of Interest & Future Scope.” 2019 3rd International Conference on Computing Methodologies and Communication (ICCMC) (2019): 988-993.
Nguyen, P. Q., & Stern, J. The two faces of lattices in cryptology. In International Cryptography and Lattices Conference (pp. 146-180). Springer, Berlin, Heidelberg, (2001).
R. Mélissa, Extended Security of Lattice-Based Cryptography. Cryptography and Security [cs.CR]. Équipe CASCADE, Département d'Informatique de l'ENS de Paris; Université PSL, 2020.
S. Edem, G. Vivek, G. R. Sandhya, Role of Hash Function in Cryptography. Conference: National Conference on Computer Security, Image Processing, Graphics, Mobility and Analytics. 2016. DOI: 10.22161/ijaers/si.3.
R. A. McEliece, Public-key cryptosystem based on algebraic coding theory, DSN Progress Report, 1978, 114–116.
H. Niederreiter, Knapsack-type cryptosystems and algebraic coding theory, Problems Control Inform. Theory/Problemy Upravlen. Teor. Inform., 15, 1986, 159–166.
F. Song, A Note on Quantum Security for Post-Quantum Cryptography. In: Mosca, M.(eds) Post-Quantum Cryptography. PQCrypto.Lecture Notes in Computer Science, 2014, vol. 8772. Springer, Cham.
P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring.” Proceedings 35th Annual Symposium on Foundations of Computer Science 1994: 124-134.
L. K. Grover, "A fast quantum mechanical algorithm for database search". Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. STOC '96. Philadelphia, Pennsylvania, USA: Association for Computing Machinery, 1996, 212–219.
C. Figgatt, D. Maslov, K. A. Landsman, , N. M. Linke S. Debnath, & C. Monroe, "Complete 3-Qubit Grover search on a programmable quantum computer", Nature Communications, 2017. Vol 8. ,