Honey, Quantum Blew Up the Internet

Honey, Quantum Blew Up the Internet

July 2, 2017

It won’t be [insert celebrity here] that breaks the internet, it will be quantum computing. Here’s a quick update on what’s happening and why it’s a worry…

By Joseph Smith

Most people know that computers are a series of off and on switches (massively simplified but basically the case). This system is great for a lot of types of calculations however one type in particular it is not so great at being able to reverse engineer the result of multiplying two prime numbers.

To-date, multiplying prime numbers has been used to secure the entire internet and internal networks secured by these algorithms. At the most basic level, this ­works on exchanging the result of multiplying two large prime numbers.

The Secure Socket Layer (SSL) certificates which is what gives us that little lock button in the top left of our browser lets us know that our communication with the website we are putting our details into is safe, uses this to secure data exchanges. It works by having a public and private key.

The public key is a large prime number which is exposed to everyone. The private key is another large prime number which is not exposed to everyone. Anyone watching the data exchange that wants to decrypt the payload only has half the puzzle. Without the other half (private key) it will take considerable time to reverse engineer the private key. By the time it’s decrypted, the opportunity has long past to exploit it; this is known as the “factoring problem”. This is fundamentally what has secured the entire internet and to date it is the best we have and it works.

However, there is a storm on the horizon and an internet scale monoculture is fertile ground that leaves us all susceptible to a vulnerability that would attack our foundation assumption on the ability to solve the “factoring problem” of prime numbers.  Quantum computing is on the cusp of solving this at speed and at scale.

What is quantum computing and why does it pose a threat?

A normal computer has a memory made up of bits and each bit is represented by either a one or a zero, whereas a quantum computer maintains a sequence of qubits. A single qubit can represent a one, a zero and any quantum superposition. Now, here comes the magic. Where the normal computer can only be in one state at one time a quantum computer can hold multiple states simultaneously.

Enter MIT Applied Mathematics Professor Peter Shor who figured out in 1994 a quantum algorithm to calculate prime factors of large numbers which was significantly superior than conventional computing. So now we have a way, theoretically at least, to calculate large prime numbers. This was not such an issue when quantum computers did not exist, and it still was not a problem when early quantum computers only had a few qubits the application was limited.

As per the Chuang experiment in 2001, which used Shor’s algorithm on a quantum computer based on a single molecule held in superposition and manipulated with nuclear magnetic resonance to factor the number 15. However, Shor’s algorithm’s success depended on a computer with a large number of quantum bits. So, to date the implementations of Shor’s algorithm in various quantum systems have not been done at scale.

A paper published in March 2016 in the journal Science, showed that researchers from MIT and the University of Innsbruck in Austria reported that they have designed and built a quantum computer from five atoms in an ion trap. The Chuang experiment, although successful was not scalable and became unstable when atoms where added. However, the latest design allows for more atoms and lasers to be added which means larger and faster quantum computers are possible. This means quantum computers that can factor much larger numbers representing the first scalable implementation of Shor’s algorithm.

So if the code can be broken that secures everything online we can understand why quantum computing will be a watershed moment for cyber security.

Today quantum computers are in their infancy and are only the domain of extremely well-funded laboratories and are not composed of the equipment that can be purchased from the internet. However, it is probably not that long till it is in the hands of organisations like the NSA and other security agencies around the world.

One thing for sure is that once quantum computing becomes more common place we better have different ways of encrypting and securing communications. Mic drop.


Leave a Reply

Your email address will not be published. Required fields are marked *