Quantum computing: Is it a Pandora’s Box?

Quantum computing Pandora's Box
Quantum computing: great upgrade or a Pandora's Box?

The quantum computing crisis is coming

…or why we need to research a post-quantum computing cryptographic solution

In 2018, IBM Director of Research Arvind Krishna posited that “if somebody is saying that they want something protected for at least ten years, should seriously consider whether they should start moving to alternative encryption techniques now” (Krishna, 2018). Mr. Krishna is referring to the challenge of factoring large numbers with classical computers.  Quantum computers or computers that leverage quantum phenomena to perform certain tasks faster than current computers can quickly factor large numbers once companies develop and deploy these systems. Anyone using these devices could hijack large swaths of the Internet as they will have the power to break current security measures. Companies, governments, or individuals will build and deploy quantum computers within our lifetimes.  We must accelerate the development of post-quantum cryptographic solutions that work on modern or classical computers, or we will face a plethora of economic and computing disasters.

Quantum computing
LAS VEGAS, NEVADA – JANUARY 9, 2020: IBM Q System One Quantum Computer at the Consumer Electronic Show CES 2020

Unless we develop and implement new cryptographic techniques, quantum computing advancement will compromise our current encryption methods and lead to many societal and economic problems. The solution to this problem is post-quantum cryptography. This area of computer science focuses on implementing new quantum-resistant encryption standards on classical machines. This paper will describe the state of progress in this field and the impediments to implementing these solutions. The barriers are significant.  Let’s do a deep dive and explore why the seemingly obvious suggestion that we should halt research into quantum computing until we find cryptographic solutions will not happen. Given that today, no firm, government, or individual can stop quantum computing research.  That means we must urgently research the testing, optimizing, and deployment of post-quantum cryptographic solutions before quantum computing destroys the Internet.

Current encryption works, why change it?

Quantum computing creates the potential for any organization with a powerful enough quantum computer to crack the widely used cryptographic solutions that underpin the Internet’s safe functioning. These solutions rely on the inability of current computer systems to have enough power to quickly factor enormous numbers.

A common companion to asymmetric encryption for transmitting secure data is “symmetric encryption.” Symmetric encryption is a security measure where both sides of the transmission use a mathematical key generated by one party to encrypt the data. This same key would then be used by the encrypted data recipient, who would perform the algorithm in reverse to obtain the original text.

Since a mathematically large number of possible keys are available, or “keyspace” is available third-party hackers would not determine the key in any reasonable period. Again, intense computational math means that symmetric encryption would be safe and secure in a world based on traditional or classical computing.

Still, symmetric encryption has a weakness: sending the key to the recipient directly through electronic transmission would have risks as a malicious attacker could intercept this transmission and then decode messages.

Are you sure no one can hear what you are saying?

In 1977, cryptographers Ron Rivest, Adi Shamir, and Leonard Adleman found a solution to the key distribution problem: asymmetric encryption. They proposed using two keys, known as the public key and the private key, rather than having one key. The two were mathematically linked so that individuals used the private key to decrypt messages encrypted with the public key. Each party would generate a pair of these keys and transmit their public key to anyone who wanted to communicate. Anyone wishing to send data securely would encrypt it with the recipient’s public key before releasing their message. Even with the public key, a third party intercepting it would not decipher the text. The system is effective yet computationally intensive.

Many applications employ intensive asymmetric encryption to exchange for the less intensive symmetric encryption, which is then used for further transmissions (CyberFirst Advanced Course Companion, 2019). Private keys are created by multiplying two huge prime numbers.  If an attacker could factor the large multiplied number into its constituent primes, they would easily reverse engineer the two keys. Today’s best-known traditional computer systems cannot factorize the number in any time shorter than several hundred years. The security of the Rivest-Shamir-Adleman (RSA) cryptosystem and the Internet hinges on this critical fact. 

The current generation of high-speed computers cannot efficiently factor large numbers because there is no known “polynomial-time” algorithm to factor the number. Polynomial-time algorithms are algorithms whose time taken to complete can be represented as a polynomial function of the input size.

Any other computational solution, such as exponential or factorial time, would be too inefficient to be practical. Cryptographic suites essentially employ a mathematical key that cannot quickly be reverse-engineered by third parties. Given that there is no quick and simple solution to breaking current cryptographic systems, the Internet structure is very secure.

This fundamental assumption of security – that computers are not fast enough to solve the problem – will not be maintained in an era of quantum computing. Peter Shor of Bell Laboratories discovered an algorithm that efficiently solves the integer factorization problem in polynomial time. This algorithm would only work in quantum computers (Shor, 1997). Shor’s idea gives a quantum computer using the power to take the widely available public key of one party and deduce the corresponding private key. Shor’s algorithm threatens the Internet’s security as we know it today by providing any quantum computer owner ability to read encrypted transmissions and websites. With this security risk, the world of quantum computing and current encryption cannot coexist.

RSA encryption – worked so far…

The protection currently provided by the RSA cryptosystem to billions of usernames, passwords, and banking details shared between users and corporate servers will be lost. Unauthorized third parties will obtain illegitimate access to user accounts. Without alternative encryption forms, online organizations’ only choice will be to restrict online operations severely. While many high-profile examples of millions of accounts hacked on classical systems, quantum computers would offer an order of magnitude more power. As with any other hacking system, quantum computers utilizing Shor’s algorithm will enable numerous nefarious groups to engage in financial fraud and identity theft.

TCP will be vulnerable

TCP vulnerable
OSI Reference Model and TCP/IP Model Layers

There are two significant areas of vulnerability. The first is when the data is transmitted worldwide via the “Transport Layer” (TL). The second is the potential to hijack and impersonate websites by compromising the domain-validated certificates in the “Domain Name System” (DNS).

In the TL, the data to be sent is encrypted and then electronically launched across the network. Security for the TL is known as “Transport Layer Security” (TLS). TLS operates using protocols such as “HyperText Transfer Protocol Secure” (HTTPS), which employs RSA versions. With the advent of a quantum computer capable of running Shor’s algorithm, hackers will easily break these TLS standards. For example, to log onto a secure website, users must enter their username and password onto a local web page. When they submit their login form, these details are encrypted and sent to the server they are accessing. A quantum computing hacker could monitor network traffic and intercept and decrypt any transmitted data. There would be no limit to the types of encrypted data that a quantum computer hacker could read by monitoring ordinary network traffic.

Disaster? Not yet but…

The fear of what quantum computers could do might precipitate a media firestorm where the public could cause as much damage as an actual quantum computer hack. In October 2019, leaked files from a NASA server indicated that Google had achieved ‘quantum supremacy’ with its 53 quantum bit (qubit) quantum computer.

Panic, interest, or news: the world was captivated in October 2019

The screenshot from Google Trends shows this news quickly captivated the knowledgeable public. An event as important as a quantum computer capable of running Shor’s algorithm would make a much more significant impact than Google’s machine because of its Internet-breaking abilities. A media frenzy full of warnings of quantum computers’ dangers would likely panic the Internet public. People would have to move their sensitive information and assets on the Internet. This decline in Internet use would slow the economy and affect the revenues of many internet-based firms that rely on user engagement or eCommerce. All 21st-century business depends on the online medium, and all would be affected.

This drop in revenue and the collapse of consumer trust could have a further catastrophic effect on the financial markets. The significant decrease in transactions could result in a stock market crash and usher in an economic recession. Stock market share prices are affected by the company’s revenue and the unpredictability of future gains or profits. The drop in profits, combined with internet encryption uncertainty, could lead to collapsing financial markets. Examples of similar events include the stock market crash of 1929. The market had been consistently optimistic and had been steadily increasing until investors began to panic en masse about an impending crash. This instability and sudden uncertainty in the markets led to a steep fall in stock market asset value and a deep economic recession.

The end of DNS?

RSA encryption
RSA: the key to Internet Security

The RSA cryptosystem is the Domain Name Service (DNS) certification system’s backbone. The DNS system consists of two parts. The first and most well-known is domain name resolution. Tens of thousands of name resolution or DNS servers manage this system that translates a name to an IP address. The name resolution system is how the Internet resolves a request for Apple.com and directs requests to routers and servers run and managed by Apple.

The second and more exploitable part is the digital certificate system. A digital certificate authenticates the website’s ownership of a given domain name. This authentication allows end-users to confirm that the website they visit is legitimate. A certificate is created by hashing a known text and then encrypting it with a private key. Certificates are also used for ‘signing.’ Since public keys are widely available, the two keys’ mathematical linking allows concerned users to decrypt the text to verify the organization that authorized the certificate.

The certificate system is further used in verifying the IP address corresponding to a given domain name. The signature is from a reputable third party known as a certificate authority, such as GoDaddy or Verisign, who verifies and confirms any applicant’s authenticity applying for a certificate. The certificate authority sends these New certificates to several DNS servers, which then propagate the certificate to other DNS servers (CyberFirst Advanced Course Companion, 2019). Given the Internet’s reliance on the RSA cryptosystem and the potential speed at which a quantum computer could hack these digital certificates, it will easily compromise its security in the era of quantum computers.

These certificates are the basis of Internet integrity. Any criminally inclined third party who could decrypt these certificates would be able to impersonate any website on the Internet. Once a hacker creates a fake certificate, the name resolution system that runs on tens of thousands of computers worldwide would propagate that fake certificate everywhere. Many people would be logging into phony bank accounts, essentially giving away their login credentials.

A quantum computer hacker would be phishing on steroids.

Today we call this “phishing.” In an era where a hacker would have a quantum computer, it would be “phishing on steroids.” Today, when visiting a web page, savvy users can check the URL’s domain name address to see if they are accessing a domain with a verified certificate. In a quantum computer world, users will no longer use this information as their web browsers will recognize the phishing website’s forged certificate as legitimate.

Quantum computing cleanup is worse than the crime

Removing a false certificate – either incorrectly issued or forged – is costly and complex. The only way to rectify inaccurate information would be to update the DNS servers manually. Manually updating the plethora of DNS servers in the world could prove futile. There could be multiple groups attempting to fix and different groups trying to hack the certificate system simultaneously.

Once users lose confidence in the integrity of the Internet and the sites they would be visiting, users would no longer view the Internet as offering any form of security. Fear and uncertainty would undoubtedly result in a decrease in online transactions.

Inc. magazine had stated that up to “60% of small businesses fold within six months” after being cyber attacked (Galvin, 2019). Not only do companies have to repair any damage from a security breach, but they also have the difficult task of restoring trust with their patrons. The cleanup from a catastrophic cyber attack would be very costly and might take years.

Web fraud is not the only possible use of certificate falsification. In 2001, VeriSign discovered that they had falsely issued two certificates to a person claiming to represent Microsoft. Once found, the security engineers moved quickly to invalidate and limit the impersonator’s ability to cause harm. The fraudulent certificate owners would be allowed to sign their computer programs to appear as if Microsoft wrote them. Fraudulent certificates would encourage users to run the code containing malware. The perpetrator of the fraud could issue malware-ridden updates to Windows operating systems which may automatically install onto some computers.

An example of how much damage a self-perpetuating piece of computer malware could cause, consider the WannaCry attack from 2018. This attack took down the UK’s National Health Service, causing approximately nineteen thousand canceled appointments and ninety-two million pounds in damages (The Telegraph, 2018). WannaCry took advantage of a weakness in the operating system to transfer itself across networks. Pushing a trojan update using certificates falsified with quantum computers to a large number of unsuspecting doctors and consumers could similarly cause large amounts of damage. Without a solid certificate system, security managers would be hard-pressed to stop a malware attack when there would be no suitable method to sort a good player from a bad player.

The final concern would be long-term trust issues. A generation that suffered through a period of internet paranoia would be less likely to return to online retail due to a significant negative experience. Internet commerce would take time to reach the levels of a pre-quantum computer-fuelled attack. Companies’ failure to realize a profit due to the lack of consumer confidence in the security of Internet commerce could cause a delayed economic recovery. Consider the dot-com crash: economists concluded it took the market fifteen years after the market crash to reach its pre-crash highs (Hayes, 2019). In the reality of quantum computers with post-quantum cryptography, a prolonged period of economic depression would be observed as consumers slowly and reluctantly returned to online shopping.

The end of the internet or is there hope?

Quantum computing - clean-up worse than crime
The possible solutions are there: but can a solution be found that is not worse than the problem?

All is not over for the Internet. Alternative methods, dubbed ‘post-quantum cryptography,’ are in development as RSA replacements. Cryptographic researchers have not developed potential solutions yet. The problems discussed above require significant investment to address all issues. Much of modern encryption currently relies on integer factorization without a known polynomial-time solution.

There are security methods based on other mathematical problems not known to have polynomial-time solutions on classical or quantum computers. One such method is lattices. A lattice is “a set of points in n-dimensional space with a periodic structure” (Micciancio and Regev, 2008). Lattices are defined by several basis vectors n, such that n is the lattice’s order. A two-dimensional lattice will have two basis vectors; a three-dimensional lattice will have three, and so on.

Lattice-based cryptography is based on several mathematical problems for which no polynomial-time solution is known, such as the closest vector problem (CVP). Consider we have a two-dimensional lattice L, and we have a vector V, such that V may or may not be in L. The closest vector is the vector in L that is closest to V. While not possible given a random lattice, some lattice bases can more efficiently provide a solution to the problem based on their orthogonality.

The devil is in the detail

Lattice-based cryptography can be used in applications including but not limited to hash functions and public-key cryptosystems. To generate this cryptosystem, one first generates a high-dimensional lattice with mostly orthogonal vectors to be a private key. Next, one generates an equivalent lattice with a different basis such that where the vectors are as close to being parallel as possible to be the public key. Encryption of data is done with a small noise vector, and decryption relies on the private key being the most efficient method for solving the CVP for the given lattice.

Reverse computation from the public key to the private key is difficult if not impossible as a result of the CVP. The decryption of the message with the public key would require immense amounts of processing power, as the vector space of it is chosen specifically so that it is the ‘worst possible basis’ for the task.

While the theoretical version of this system is secure, it does not perform well in practice. To achieve the level of efficiency needed, practical applications often will abstract parts of the security, resulting in a faster system that is not provably secure. Thus, mathematically quantum-proof solutions to the internet security issues raised by the quantum prime-factorization algorithm do exist and need implementation on current systems.

Speed is life?

Speed is life
Milliseconds really do matter.

Putting algorithms such as lattice-based cryptography into practice creates challenges for the computers in use today. A slower security protocol may have delays of up to one second. While this theoretical delay in a secure data exchange using new protocols might not seem significant, a web server hosting a large audience such as Google would have to manage tens of thousands of HTTPS requests per second for searches alone (Internetlivestats.com, n.d.).

When a user requests data from a server, the server must use some of its memory space to maintain a connection to the user. The computer releases this memory space after completing the transmission. If the protocols ran for additional time, the server might not be able to terminate connections faster than it receives. In this slowed-down scenario, the server’s memory usage would become very large, and eventually, the server could run out of room. It would either have to ignore incoming connections or crash. Online businesses could not afford for either option to occur as it would reduce user engagement with the site, affecting earnings in the long term.

Fortunately, some post-quantum solutions operate at relatively fast speeds. A team at Google has been working on “NewHope”. NewHope is a lattice-based method that allows for exchanging the keys used in symmetric encryption.

The Google team performed a laboratory test using a modified version of the NewHope algorithm on a processor with a clock speed of 1.5 GHz. The key exchange transmissions completed in a remarkably fast 0.33 ms (Streit and De Santis, 2018). That figure alone would be enough to justify integration into the everyday computer. NewHope is promising, but there are still issues that researchers must solve before recommending implementation. The Google engineers tested NewHope under ideal circumstances with no other processes running on the same computer. While this allows for acceptable approximations of the time the key exchange would take to complete on classical machines if implemented immediately, this experiment does not accurately represent the delays one would encounter on current systems. Speed is life on the Internet, and a lattice-based system is not yet ready to deploy.

Upgrades people, upgrades

Upgrades: one quantum computer with enough power could, in one fell swoop, outdate all the computers in the world.

The future transition to new cryptographic methods isn’t going to be simple, as many users will still run on older systems that will not meet the latest modern standards. Consider the UK’s National Health Service (NHS). In 2018, they were still using a 2001 Microsoft operating system Windows XP. The NHS is an example of a more significant issue regarding the price barriers of upgrading older technology in large corporations. High-performing computers can cost upwards of thousands of dollars for a single unit. Upgrading every computer in a large company is unaffordable.

Beyond simply upgrading hardware, many companies often rely on legacy programs written in programming languages not used in modern machines. Upgrading would be both a software and hardware issue. Depending on the complexity of any legacy programs, upgrading may cost a significant amount of time, a considerable sum of money and create a world of frustrated employees, managers, and customers. Given all these costs, companies tend to avoid upgrading any technology for as long as possible.

Upgrading one company’s technology is difficult; upgrading the entire internet’s technology would be an arduous task. Changing network security protocols can be similarly tricky as it requires most Internet users to agree to employ the new standard. The only way to successfully upgrade the Internet is a slow and gradual rollout with all the necessary next-generation security algorithms embedded within it. If it takes ten years to upgrade the Internet, then today’s technology has to work for ten years. Suppose quantum computers become available within this ten-year timeframe, and the systems that we are deploying today cannot manage the new protocols. In that case, we are deploying equipment with a future security risk.

Test, test, and then test again

A tall order: post-quantum computing cryptographic solution that is hacker proof.

Whatever security algorithm we wish to implement for the quantum computing world, we must thoroughly test it. Hasty implementation of an algorithm for widespread use could lead to an exploit that would affect all systems using the new encryption. For example, researchers released RSA in 1978. Cryptographers found no significant attacks against it until seventeen years later. Paul Kocher, in 1995, discovered that timing attacks were possible against it. In the early stages of the Internet, users could mitigate any damage by rapid system updates. With hundreds of millions of computer systems, this is impractical. If hackers discovered a significant exploit on a level higher than a timing attack, the Internet would be compromised suddenly and immediately, leading to terrifying consequences.

Any algorithm we implement must meet two requirements. The first is that the solution must be mathematically NP-complete. This type of problem has no known polynomial-time solution. Any cryptosystem based on these mathematical problems would have no efficient solution to reverse engineer a decryption method and thus would be, in this regard, theoretically secure.

The second requirement is that any cryptosystem must be robustly tested for several years by many professionals until a significant period of no exploits occurs. Let’s look at the NewHope algorithm. It meets the first test as it is based on NP-complete problems. Some versions of NewHope exist that do not have mathematically provable security yet have faster performance. Researchers’ challenge is that choosing speed over security or security over speed is a catch twenty-two.

The National Institute for Standards and Technology (NIST) in the United States runs a post-quantum cryptography standardization competition to find a replacement for the RSA cryptosystem. NIST scientists automatically dismiss any competitors that vulnerability to non-mathematical attacks (Alagic et al., 2019). As companies deploy more and more computer systems throughout the world, the more complicated cryptographers will find a solution to the quantum computing encryption problem.

Delay, delay and delay…?

In quantum computing, a qubit or quantum bit is the basic quantum information unit. Classic computing uses the 0/1 two-state relationship as its basis. A qubit is the equivalent unit of information in quantum mechanical systems. While it can take the states of 0 or 1 like classical bits, the qubit can take any combination of the two at the same time.

Noting all the risks and issues discussed above, why not delay creating stable qubits to give security researchers more time to develop solutions to the problems raised by Shor’s algorithm? In theory, there is sound logic for doing this.

Two reasons make stopping development not possible. The first is that having quantum computers would promote enormous scientific advancement and allow the fast management of vast amounts of data. Quantum computers could give scientists the computing power to model complex problems such as quantum phenomena and cancer growth. Second, the financial incentive to build faster and better computers, stopping companies, governments, or individuals from building quantum computers, would not be possible.

Using a quantum computer, a researcher could sort through millions of observations to help develop many medical issues. Beyond medical issues, one could use a quantum computer to design and build even better quantum computers.

Quantum computers allow for rapid calculations that classical computers cannot perform with the same efficiency. Researchers can develop cancer development models and gain a greater understanding of its effects and causes. In practice, medical scientists use high-speed computers to optimize radiation beams in radiotherapy to kill cancer cells efficiently. While there are methods to do so on classical machines, quantum computers could do this work many times faster. (Nazareth and Spaans, 2015). If we choose to delay qubit creation, we could be damaging future scientific advancements and innovation.

A new arms race

a new arms race
Tanks, planes, and bombs: all will be dwarfed by the rise of quantum computing.

There are political consequences of delaying qubit research. Should we choose to regulate quantum research, we may find that other nations do not share our internet security values.
Remember Maslow’s Hierarchy of Needs from that psychology course?

Maslow explained human behavior in terms of levels of need. Maslow’s five levels of needs are:
* physiological needs, such as air, food, and water;
* safety needs, such as employment and property;
* love and belonging needs, including friendship and family;
* esteem, which is to do with respect and status;
*and finally, self-actualization, which is the desire to be the best that one can be.

According to Maslow, when a man reaches the first four, motivation for additional action decreases. However, as one matches the fifth level’s needs, stimulation increases. A more significant increase in research will move the country as a whole more into the fifth need of self-actualization, thus motivating it to research more.  

Quantum computing research is mandatory if a nation wants to maintain control of its Internet, including attacks from foreign countries. One could easily use quantum technology for espionage, population management, political control, etc. No nation or party would try to distance itself from technology. From the lens of a psychological argument, we see that while logically for humanity there could be an imperative to halt qubit research, in practice temporarily, it is an arms race that countries and companies will not be able to resist.

Averting the disaster

Given the current status of post-quantum cryptography and the effects that Shor’s algorithm would cause, there is no reasonable way to stop qubit research. We have no choice but to focus on post-quantum cryptosystems. Their untested nature and usability only hold back the efficiency of algorithms such as NewHope on older machines.

Aside from the NIST and several concerned corporations, consumers have yet to begin preparing for a significant security upgrade (Chen et al., 2016). While it takes time to implement post-quantum solutions, this report and those that follow it indicate that this is not the issue, and instead of that, it is the lack of testing and robustness of the proposals.

We can avert the coming quantum computing disaster by investing more in research, testing, and evaluating new methods. The NIST report also discusses technological inertia and the difficulty of implementing new strategies in an age of massively varying systems. At the slow pace of cryptographic development and testing that we are doing today, we will not likely finish before the advent of powerful quantum computers. We need to devote more time to developing and implementing new encryption algorithms in older machines.

Quantum computing – The only way out

Quamtum computing - light at the end of the tunnel
There is a solution somewhere to avoid the quantum computing Pandora’s Box of problems. Will we find that solution in time?

Given there is no imperative to terminate qubit research, we need to accelerate preparation for the threat posed by Shor’s algorithm. Therefore, we should increase funding for testing and implementing post-quantum cryptographic algorithms. There exist plausible replacements for RSA, such as Google’s NewHope algorithm, which operates with remarkable efficiency and notable baseline security.

Ramifications for not developing and implementing these solutions soon are devastating, ranging from a drop in stock prices and an increase in cyber attacks to total economic collapse and cyber warfare. Time is of the essence for implementation, as technological inertia will inevitably slow us down. With all this considered, Krishna’s words undoubtedly spell a warning that will either be prophetic of the dangers to come or provide the impetus to prepare for cryptographic security in the post-quantum world. If we want to avoid the Pandora’s box of quantum computing, we must quickly find a post-quantum computing cryptographic solution today.


What do you think?

This site uses Akismet to reduce spam. Learn how your comment data is processed.