Let's suppose we have developed a stable quantum computer. How would the internet look like? Would it be the end of security?
This is not too far fetched. 2017 is set to be the year that the first general commercial available quantum computer D-Wave 2000Q will hit the market.
No doubt that this is an incredible feat, and an important step for science, but what does it mean for our security? To answer this, first, we need to know what a quantum computer is.
What is a quantum computer? - the basics.
Suppose a traditional computer like the one you're reading this on. It has memory made from bits; ones and zeros. Each bit can represent either a one or zero.
A quantum computer's memory, however, is made from qubits which can represent either a one, a zero, or any quantum super position of those two states. We won't talk more about quantum super position in this article, so while you could just regard it as a being both one and zero at the same time, I encourage you to read more about it here.
A traditional computer with three bits of memory can be in one of 2^3 = 8 different memory states.
000 or 001 or 010 or 011 or 100 or 101 or 110 or 111
In general, a traditional computer can be in one of 2^n memory states where n is the number of bits.
However, due qubits' property of superposition, a quantum computer can with three qubits of memory be in 2^3 = 8 different memory states simultaneously.
Meaning instead of having to go through each memory state one at a time, a quantum computer can go through all memory states at the same time.
000 and 001 and 010 and 011 and 100 and 101 and 110 and 111
Generally, it can be said about quantum computers that given n qubits, it can be in 2^n different memory states simultaneously.
The use of qubits instead of regular bits, however, the system must, at the end of a calculation , be collapsed down to represent one, and only one, of the memory states. The outcome can therefore be at most n classical bits of information.
This also has the effect of making most algorithms probabilistic, so the outcome only has a known probability of being correct.
This is only the briefest of introductions, and I've skimmed over a lot of the details. If you're interested in quantum computing, I recommend to start by reading this paper.
So what does all this mean for the internet?
Due to the properties described above quantum computers will be very efficient at integer factorization. Something that's often deemed unfeasible for traditional computers.
Integer factorization is what underpins the security of public key cryptography. Basically, the system that makes the internet secure.
What makes it possible to log securely into your bank account. What makes it possible to securely send data between you and serves. Between you and anybody else.
Security as we know it will largely be rendered inefficient by quantum computers coupled with Shor's algorithm.
Quantum computers may be the greatest security threat we will face this century.
But will this be the end of security all together, and subsequently the internet?
Not quite.
There are other cryptographic algorithms, and even some public-key algorithms that are not based on integer factorization, and do not appear to be easily broken using quantum computing techniques. Note that as we discover more properties about quantum computing, some of these algorithms may be found to be insecure against quantum computing attacks.
Moreover, lattice-based cryptosystem are not known to be broken by quantum computers. These system have the benefit of being secure against both traditional, and potentially quantum computers.
It's important to remember that quantum computers will do much more good for science than it does compromising for security. For example, quantum computers will be dispensable for physics, chemistry, and climate simulation; In fact, nearly all large scale simulations than would be too complex for traditional computers.
However, we need to consider the security implications of such devices before they are developed and on the market. Because, as history has shown us, we cannot stop progress.
Image credit: Google, D-Wave 2x