Y2Q: quantum computing and the end of internet security

What if you woke up one morning to find all locks had disappeared? Not just the one on your front door, or the lock on your bicycle – but the ignition on your car, and even the massive tumbler on the vault in your bank.

All of these very valuable things these locks protect would lie unprotected, able to be stolen or plundered. Of course, you’d immediately try to replace the missing locks with new ones. But all the locks have disappeared; it’s as if they never existed at all. What would you do?

While this may sound like a wild bit of fantasy fiction, we’re on the cusp of such an event.

The digital security horizon

The digital world, secured throughout by its own locks – employing the principles of mathematics, rather than physical tumblers and keys – looks set to experience such a sudden ‘liberation’. A new generation of quantum computers will exploit the weirder-than-you-can-imagine qualities of the quantum realm do things that should be impossible, such as making impossibly hard maths problems instantly soluble.

Instantly, all our digital security vanishes – a sudden moment of digital insecurity we might want to name “Y2Q”.

To understand how we arrived at the edge of this digital precipice, we need to step back a generation, to a time when a still-fledgling World Wide Web had no real need for security.

In its earliest days, everything was sent around the Web went via “cleartext” – characters readable by anyone who wanted to listen into the conversation. While this worked well enough for the tiny, trusted, research-oriented Web of the early 1990s, as commercial organisations – and, more specifically, financial organisations – went online, it became clear that sending banking and account details in the open would rapidly lead to serious breaches of both security and confidentiality.

To keep those Web-based transactions both secure and private, the Web’s architects quickly added an upgrade called Transport Layer Security. TLS uses mathematical encryption in every secure ‘conversation’ (or session) between a Web browser and a Web server. That encryption makes it very difficult – effectively impossible – for anyone else to be able to listen in on the conversation.

Paranoid cryptographers outlive the others.

The mathematical foundations of encryption fill whole libraries at places like the Australian Signals Directorate and the US’s NSA. Sitting at the intersection between number theory and game theory, it’s a body of research that actively encourages a paranoia in its practitioners: cryptographers labour under the assumption that everything they do will be actively attacked by a hostile opponent with far greater resources, working ceaselessly to decode their secrets. Paranoid cryptographers outlive the others.

Hiding in prime sight

Cryptography goes back nearly as far as civilisation itself. Military cyphers were famously employed by Julius Caesar to encrypt communiques to his field commanders. Advances in computer networking in the 1970s led researchers Ron Rivest, Adi Shamir and Leonard Adelman to develop their “RSA” cryptosystem, the beginning of what is today known as “public-key cryptography”, with broad, non-military uses.

The essence of RSA public-key cryptography is fairly simple. Take two prime numbers (in this example, 13 and 31) – numbers divisible only by themselves and by 1. We’ll keep these numbers private – but when we multiply these two private numbers together, we get the number 403. This product of the two prime numbers number we can share as our “public key”. Anyone can use this public key to encrypt messages that can only be read by us.

Why are we the only ones who can read these messages? Because it’s terrifically difficult to work out which two prime numbers have been multiplied together to produce that public key. Not, of course, in this example – it could be solved on paper in just a few minutes. Modern RSA implementations use very large prime numbers – hundreds of digits in length – to create public keys so big they’re effectively impossible to factor into the prime numbers used to create them, making it impossible for anyone else to read a message encrypted using the public key.

Public-key cryptography became the core of TLS – so commonplace we no longer even notice the “lock” symbol in a Web browser’s address bar, indicating we’re actively engaging in a secure communications session. Although computers have grown about a thousand times faster than those early PCs running first-generation Web browsers, that hasn’t much affected the security of their connections. Public keys can grow larger (and therefore harder to crack) faster than computers can speed up, making it an ideal long-term solution for security.

As the Web grew into every corner of our lives, it carried all our most private conversations securely. Yet, as any paranoid cryptographer can tell you, no security is ever perfect – nor does any solution last for ever. Sometimes mathematical flaws can be found and used to exploit weaknesses in encryption. At other times, a new technology comes along and changes everything.

The quantum era

Quantum computing has been around in some form or another for 30 years, with theoretical foundations stretching back into the late 1960s. The basic premise appears simple enough: rather than using a “classical” bit – generally a semiconductor “gate” that’s either open (zero) or closed (one) – to represent information, quantum systems model information as quantum bits (“qbits”), which can be either zero, or one, or in “superposition” – a range probabilities between zero and one. 

This superposition is the superpower of quantum computing: a qbit in superposition holds every possible value.

While superposition isn’t very interesting when you consider a single qbit – it’s going to be zero, or one, innit? – when you start to string qbits together, it becomes very interesting. A quantum computer with four qbits can be in a superposition of any value between zero and 15. 

A process that might take hundreds of thousands of years on the world’s fastest supercomputers could be performed – theoretically – in a few minutes

In 1994, not long after the first single-qbit quantum computers had been created, mathematician Peter Shor published an algorithm showing how a quantum computer with sufficient qbits can use superposition to radically speed the factorisation of numbers. A process that might take hundreds of thousands of years on the world’s fastest supercomputers could be performed – theoretically – in a few minutes on a sufficiently powerful quantum computer exploiting superposition to examine all possible results.

At the dawn of quantum computing, a “big enough” quantum computer seemed a long way away, and RSA public-key cryptography remained safe. Continuing research has only reinforced the difficulty involved in constructing multi-qbit quantum computers; even the most advanced labs haven’t managed to produce an effective quantum computer of even 100 qbits – far less than what’s needed to make a real assault on RSA.

Nonetheless, the gap between the potential power and the reality of quantum computing steadily narrows. Cryptographers have already already looked beyond the factorisation of large numbers that undergirds RSA encryption toward other forms of mathematics believed to be more resistant to quantum attacks. These include employing the geometric principles of elliptic-curve cryptography, used to generate ‘harder’ public keys, more resistant to quantum hacks.

Will these advances be enough? Or will all our digital secrets fall prey to quantum computation? Michael Biercuk, CEO of Sydney based quantum computing startup Q-CTRL, sounds a mixed note of caution and skepticism: “Since the mid 1990s we have gradually learned that the systems required to perform useful factoring must be very large and much more capable than they are today… systems relevant to factoring may remain decades away.” 

It seems likely that Y2Q will occur – even if we can’t be sure of just when. When it comes to digital security, paranoid algorithms outlive the others.