When Did Quantum Computing Start to Look Like a Real Threat to Cryptography?
A quantum revolution is in the air, powered by formidable computing power and counterintuitive subatomic properties. While many are looking forward to the quantum magic that can dramatically accelerate computations, we may also be launching ourselves into a future where many of our digital information such as online transaction records, emails, website logins are susceptible to quantum attack.
Cryptologists today are worrying that classical public key encryption system will soon be rendered obsolete by quantum computers. However, this is not because quantum computing is so new and ”disruptive“ that it caught cryptographers off guard. Not at all. On the contrary, I would argue that cryptographers and the government’s delay in taking proactive action against quantum attack reveals an unwarranted belief that a quantum computer cannot be built in any near future, even though there were sufficient evidence and historical precedent proving that the public key system and other encryption schemes alike would be directly devastated by brute force machines.
Super Short History of Encryption Standards and Quantum Computing
Even back in the 70s, Cryptologists were well aware of the threat posed by increasing computing power to cryptologic algorithms. In 1976 when the National Institute of Standard and Technology (NIST) released for the first time a national digital encryption standard (DES), two Stanford University professors, Martin Hellman and Whitfield Diffie, warned that the new encryption scheme could be compromised by building a machine to exhaustively search for any user’s key. As a response, NIST hosted two workshops to evaluate any technology in the foreseeable future that might reduce the effectiveness of this encryption system. The conclusion drawn from the workshops was that although Hellman and Diffie’s machine was theoretically feasible, it was too expensive and difficult to build that it probably won’t be ready by 1981 at the earliest, and even then it would come with a price tag of 20 million dollars that doing so would not be cost effective.[1]
In a sense, this estimation was not completely inaccurate. DES did last for over 20 years before NIST launched a new round of search for a more secure encryption algorithm. However, the motivation behind this new search was precisely as Hallman and Diffie predicted: a machine, dabbed the DES cracker, emerged in 1998 to try all possible key values to determine which key was used to encrypt a message, and it could complete this task within a few hours at a cost of less than $250,000.
Meanwhile in the realm of quantum computing, things were happening more quietly, although without a lack of substantial progress. Since Richard Feynman first proposed the idea of a quantum computers in 1982, theories of quantum logic gates, quantum information theory, and quantum computer designs were piling up.[2] However, all of these works only proved that quantum computing could work in theory (shoutout to UChicago). The turning point came in 1994 when Peter Shor astonished the computer science and cryptography communities with his quantum algorithm that can easily solve the prime factorization problem, the backbone of many digital encryption schemes such as RSA. Shor’s Algorithm proved for the first time the usefulness of quantum computers in cryptanalysis.[3]
As Long As There Is No Real Quantum Computer, There is No Real Threat?
It may seem immediately obvious that the continuous interest in quantum computing together with a workable cryptanalysis quantum algorithm means that current encryption systems would soon be vulnerable, if not obsolete, in face of quantum computers. Especially in the light of the successful deployment of DES cracker in 1998, it was not difficult to take a step further and recognize quantum computers as the next DES cracker of the existing encryption standard.
However cryptographers seemed to take little heed of quantum computing in the 90s when Shor came up with his famous algorithm. Even though in 1997 NIST started searching for a new encryption standard, it was not because of Shor’s algorithm but the DES cracker. The idea of quantum resistant cryptography was not proposed until 2004.[4] And it was not until 2016 NIST announced that the current encryption standard could not withstand quantum attack and therefore initiated a third round of search for quantum resistant cryptographic algorithms.
The main reason for the lag between the advent of Shor’s Algorithm and a push for post quantum cryptography is that there was a serious doubt whether building a quantum computer was feasible. Many scholars suspected that quantum computing would not be a scalable technology considering the extreme fragility of the quantum state.[5] Even though Shor’s algorithm sparked immense interest in building a quantum computer and serious effort was invested in this endeavor, the fact that a quantum state is very sensitive to noise and prone to errors made it seem like an actual quantum computer was not attainable even in lab environment, not to mention in everyday life.
Yes There Is No Quantum Computer… Yet
However, as legitimate as the doubt surrounding the feasibility of a quantum computer may sound, already in the late 90s, theoretical breakthrough was made in error correction codes and threshold theorems that relaxed the strict error-free environment that a quantum computer might require and made building the machine a more realistic task.[6] In other words, by the time that we entered the new millennium, the crucial theoretical puzzles of how a quantum computer could be built had already been laid bare. The question that followed is whether these various theories could be engineered into an actual computer sitting in a lab or even on our desktop.[7] To that, cryptographer Gilles Brassard made an illuminating analogy in 1994:
“That no quantum computer has yet been built should not be considered more fundamental an issue than was the fact that no classical computers existed when Turing set forth his model of computation.”[8]
Just like Turing and his computing machine, a machine with quantum behavior had a great potential of being realized when its theoretical foundation was already established. Meanwhile, Shor’s algorithm and the precedent of DES being broken by a brute force machine should alert cryptographers that the fate of the short-lived DES might happen again to other encryption schemes in the near future. However, building a quantum resistant cryptography infrastructure was merely optional, if at all considered by the government in the 90s, while less than 20 years later it became a necessity.
In its call for post quantum cryptographic algorithms, NIST warned that the rate of building a functional quantum computer might outpace the implementation of a quantum safe encryption scheme. In other words, by the time that we finally upgrade all of our encryption system to be quantum safe, it may be too late.
Today, whether or not a functional quantum computer can be built is less of a question than to what scale it can be built to. Due to readymade quantum algorithm like Shor’s, the cryptographic infrastructure will be the first target of attack once quantum computers are delayed. Maybe it is time to double our key size and discard the shift away from the public key system.
[1] Kolata, Gina Bari. “Computer encryption and the National Security Agency connection.” (1977): 438–440.
[2] Steane, Andrew. “Quantum computing.” Reports on Progress in Physics 61, no. 2 (1998): 117. 8–10.
[3] Ibid.
[4] This the result of a google scholar search for articles containing the phrase “quantum resistant cryptography”.
[5] Chen, Lily, Lily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta, Ray Perlner, and Daniel Smith-Tone. Report on post-quantum cryptography. US Department of Commerce, National Institute of Standards and Technology, 2016.
[6] Ibid.
[7] Rieffel, Eleanor, and Wolfgang Polak. “An introduction to quantum computing for non-physicists.” ACM Computing Surveys (CSUR) 32, no. 3 (2000): 300–335.
[8] Brassard, Gilles. “Quantum computing: the end of classical cryptography?.” ACM Sigact News 25, no. 4 (1994): 15–21.
