Quantum Decryption: Have We Lost the Encryption Battle?

While quantum computers capable of decoding encrypted messages are yet to exist, it may turn out that we have already lost to these future machines as hackers and state actors scrape encrypted internet traffic. What challenges do quantum computers present to encryption, why may it already be too late, and what can be done to mitigate against this?

What challenges do quantum computers present to encryption?

The Quantum Threat to Current Encryption Systems

Despite the numerous advances that have been made in the field of quantum computing, no machine has yet been made that can be used for practical quantum computing applications. The reason for this comes down to several factors, including the extreme complexity of quantum computers, finding materials that can help scale up quantum designs, and the infancy of the field. 

However, should researchers accomplish the task of building a functional quantum computer, then encryption systems commonly used in computer systems would be highly vulnerable to attack. Unlike traditional encryption-breaking algorithms, which execute linear code, quantum computers utilise probability and statistical analysis to generate answers. 

The implications of quantum computing on internet security extend beyond theoretical concerns. As highlighted in Scientific American, the advent of quantum computing could herald a new era where traditional encryption methods become obsolete overnight. This 'Q-day' scenario, where a quantum computer can break RSA encryption, poses a significant threat to global data security. The race for quantum supremacy, particularly between major powers like the US and China, adds a geopolitical dimension to this technological development. The first nation to develop a robust quantum computer could gain unprecedented access to encrypted data worldwide, raising concerns about international cybersecurity and espionage.

The Vulnerability of Asymmetric Encryption

Further emphasizing the gravity of this situation, Michele Mosca, a mathematician at the University of Waterloo and CEO of the cybersecurity company evolutionQ, warns, 'If that encryption is ever broken, it would be a systemic catastrophe.' His words highlight the critical need for proactive measures in developing quantum-resistant encryption methods. 

Simply put, in classical computing systems, decryption and such encryption algorithms are a 2n problem, while in quantum computers (using Shor’s algorithm), it becomes a log N problem. Thus, large keys with 256 bits would take more than the age of the universe to break via classical computing but can be done in a matter of months (if not weeks/days) with a relatively small quantum computer. 

Considering that most of human society is now dependent on the internet for all daily tasks, ranging from banking to shopping, anyone with access to a sufficiently powerful quantum computer could very easily sniff internet traffic and then break existing encryption methods. Not only would this be incredibly damaging to any and all economies, but it also has the power to cripple governments, the lives of citizens, and even society itself. 

While encryption methods currently used are certainly vulnerable to quantum computers, reports on quantum computing and encryption often fail to mention a very important fact: not all encryption methods are vulnerable. To be specific, only those that operate on asymmetric keys utilising key exchange are highly vulnerable, while those that are based purely on random numbers are much more resilient.

The reason for this comes down to how asymmetric keys are generated. In most cases, asymmetric keys utilise a private and public key pair, with the public key being shared with the world and the private key being kept a secret.

To make it virtually impossible for classical computers to break this private key, asymmetric key algorithms use the product of two large prime numbers, which are extremely difficult to factorise. However, two parties involved in the key exchange itself can both arrive at the same key despite not having the other’s private key, thanks to some clever maths (see RSA key exchange for more details).

However, quantum computers are extremely good at factorising large numbers very fast, meaning that it takes a fraction of the time for a quantum computer to determine the two prime factors of such keys. Thus, asymmetric keys that are generated via factorisation are extremely vulnerable to quantum computers. Because quantum computers are not designed for brute force attacks, symmetric keys that are generated via pure random number generation with a sufficiently high bit size (256 bits, for example) are considered quantum safe.

The shift in computational power that quantum computers represent is not limited to encryption but extends to various fields, from material science to complex logistics. However, the immediate concern is the safeguarding of digital information. As highlighted in Science News, the urgency to develop quantum-resistant encryption is paramount. The current internet infrastructure, heavily reliant on vulnerable encryption methods, could be at risk in the face of advanced quantum decryption techniques. This necessitates a proactive approach in cryptography, ensuring the security of data against the impending quantum computing era.

Historical and Contemporary Examples of Encryption Vulnerabilities

The history of encryption reveals a continuous battle between code makers and code breakers, a dynamic that quantum computing is poised to revolutionize. A poignant historical example is the Allied forces' decryption of the Enigma machine during World War II. This breakthrough, which involved early forms of computational analysis, was pivotal in turning the tide of the war. It underscores the catastrophic consequences that can ensue when cryptographic systems are broken. Today, as we stand on the brink of the quantum computing era, this historical lesson resonates with renewed urgency.

In the contemporary context, the race to develop quantum-resistant encryption methods is gaining momentum. Companies like Microsoft are at the forefront of this endeavour, working on 'Post-quantum Cryptography.' This initiative aims to create encryption methods that remain secure against the formidable capabilities of quantum computers. Such efforts highlight the proactive steps being taken by the tech industry to safeguard digital information in a future where quantum computing could render traditional encryption obsolete. 

Are we too late to protect against quantum computers?

Even though quantum computers are still yet to be made practical, it is possible that we have already lost against them, or at least, machines that will eventually be manufactured. But how could this be possible?

Well, it turns out that a quantum computer doesn’t need to exist now to decode data exchanges between servers, as data gathered at any point in time can be fed into such a computer. The same is true for any type of data processor, whether it is a computer loading a file from 20 years ago, an encryption device breaking old messages from the Second World War, or an algorithm analysis of a lost language of the past. 

Any and all data streams across the internet that are utilising asymmetric key algorithms, if recorded, could easily be fed into future quantum machines for decoding. While a significant proportion of traffic today would be too old to be of any use, it could easily allow for recovering passwords, user credentials, banking history, and account access.

Peter Schwabe, a computer scientist at the Max Planck Institute for Security and Privacy, provides historical context, noting the limitations of symmetric-key cryptography in our globally connected world. Angela Robinson of NIST (National Institute of Standards and Technology) in Gaithersburg, Md., further adds to the urgency, pointing out the vulnerability of our digital world to quantum-vulnerable algorithms. 

Making matters worse, not all data, such as national insurance numbers, social security numbers, account details, and addresses, changes with time. Thus, any encrypted message sent today remains vulnerable to future attacks if that traffic has been stored. 

As such, there is a genuine fear that state actors and malicious parties are already scraping the internet for such traffic. Considering that quantum computers may be ready by 2030, it is possible that current internet traffic (and thereby any connected system) could be vulnerable to attack in a matter of years.

What can be done to protect against such future attacks?

Fortunately, there are options that engineers can take now to help defend their systems, including products that are connected to the internet. 

By far, the best decision to take is to immediately increase the size of symmetric keys, with 256 bits being the absolute minimum. This also means that designs should try to move away from asymmetric keys, if possible, and move towards symmetric keys that cannot be easily broken by quantum systems. 

Another move that engineers can make includes the shift towards reprogrammable systems that support updates to security encryption methods used. For example, algorithms that may be listed as being quantum-safe may be found to be vulnerable, so it will be essential that updates allow for these algorithms to be replaced.

Finally, it may also be ideal for engineers to consider a more modular design approach, with hardware security modules being entirely replaceable. While this may be costly compared to a software approach, it not only provides users with the ability to upgrade hardware without needing to replace the entire system but can also allow engineers to incorporate new features without affecting the performance of the larger design. 

Overall, it is clear that we may already be under threat from quantum computers despite the fact that they do not exist yet (specifically, those that have the ability to decrypt modern encryption methods). Thankfully, not all is lost, as quantum computers are not infallible, meaning that we can take action today to protect current and future solitons.

Conclusion: Staying Ahead in the Quantum Encryption Race

The emergence of quantum computing presents a formidable challenge to current encryption methods. This article has explored the vulnerabilities that quantum technology could exploit and emphasized the need for advanced cryptographic measures.

Quantum computers, with their advanced problem-solving capabilities, could make traditional encryption obsolete, exposing sensitive data on a global scale. However, this challenge is not insurmountable. The development of quantum-resistant encryption methods is already underway. Key strategies include increasing symmetric key sizes, adopting quantum-safe algorithms, and implementing reprogrammable and modular systems.

The race towards quantum supremacy is more than a technological milestone; it's a catalyst for stronger cybersecurity. As the quantum era approaches, our focus must be on adapting and evolving our encryption strategies to stay ahead of potential threats.

In summary, while quantum computing poses significant risks to encryption, it also drives innovation in cryptographic practices. Staying informed, agile, and proactive is essential to protect our digital infrastructure against the quantum revolution. The goal is to anticipate and prepare, ensuring the security of our digital future in the face of quantum advancements.