Shor’s Quantum Algorithm
Introduction
Among the numerous applications of the quantum computing model, the most relevant in the cryptographic field is represented by the work of the American computer scientist Peter W. Shor.
Assuming the existence of a suitable quantum computer, with the article published in 1995 “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” Shor exposed to the scientific community a quantum algorithm capable of breaking the RSA scheme and the Diffie-Hellman protocol, the foundation of public key cryptography in use today and of most secure communication systems.
In fact, consider that all of today’s public key cryptography standards (eg NIST SP 800-56 A / B, FIPS 186) would be vulnerable to the use of this algorithm. In the following, we will specialize our discussion on the RSA scheme, which bases its security on the assumption that the mathematical problem of factorizing suitably chosen integers is computationally intractable by today’s computers.
In fact, it is estimated that, even by exploiting the most advanced classical computing technologies, trillions of years are required to complete the factorization that would break the 2048-bit RSA scheme. On the other hand, if a quantum computer with certain characteristics in terms of memory and computing power were created, the implementation of the algorithm theorized by Shor would allow the same factorization to be completed in a few hours.
The Shor result is an example of exponential speed-up of the quantum computation model compared to the classical case. The theoretical analysis of the best state-of-the-art classical algorithm[1] to factor a number of n bits estimates a computational cost of O\Big(e^{c\sqrt[3]{n\log^2{n}}}\Big) operations[2] in asymptotic terms, while Shor’s quantum algorithm has complexity O(n^2\log{n}\log{\log{n}}). Specifically, the classical algorithm is said to have a subexponential complexity in the parameter n while the quantum one is polynomial complexity in n.
Similar considerations also apply to the Diffie-Hellman protocol in relation to the mathematical problem of the discrete logarithm.
To fully understand the discussion, it is advisable to resume the concepts presented in the introductory article to the qubit, while to deepen the topic we recommend a seminar held at the De Cifris association in collaboration with Telsy and the Polytechnic of Turin.
Click the link to read the full article.
[1] General Number Field Sieve (GNFS)
For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.
The authors
Edoardo Signorini, graduated in Mathematics with a curriculum in cryptography at the University of Trento, in 2020 carried out the Master’s thesis in the field of Post-Quantum Cryptography (PQC) at Telsy. He currently holds the role of cryptographer within the Telsy research group and carries out an industrial research doctorate in Pure and Applied Mathematics at the Politecnico di Torino. His activity focuses on PQC research and on the analysis and development of cryptographic protocols.
Francesco Stocco, a master’s degree in Mathematics at the University of Padua and the Université de Bordeaux attending the course of study “Algebra Geometry And Number Theory” (ALGANT), joined the Telsy research group in Cryptography at end of 2020 focusing in particular on issues related to quantum technologies.