For decades, a thought has been keeping security experts awake at night: what if someone has worked out an easy way to find the factors of large numbers? If they have, they could be quietly siphoning off funds from any investment bank. They could be reading the most secret files of every intelligence agency in the world and be listening in while heads of state discuss military plans and strategies.
The world’s security infrastructure relies on the extreme difficulty of finding the numbers that multiply together to make another large number. When the given number is small – 15, say – it’s easy: 5 and 3. Our most secure encryption systems, such as RSA and elliptic curves, use far bigger numbers and their factors would be discoverable only through trial and error and a long stint on the world’s fastest supercomputer networks.
Although we do not know of any mathematical process that can do the job quickly and efficiently, there may be one – hence the sleepless nights. Much more pressing is the prospect of a quantum computer: a machine that uses rules derived from the quantum world of atoms, electrons and photons of light to perform its calculations. For 20 years, we have known that a quantum computer would find the factors of large numbers as quickly as you or I can find the factors of 15. This month in Seoul, South Korea, experts are gathering to discuss what should happen if and when such a machine is built.
The quantum computer is powerful because quantum particles have the absurd ability to do multiple things at once – an atom can spin clockwise and anticlockwise simultaneously, for example. If you encoded a binary 0 as a clockwise spin and a binary 1 as anticlockwise, the atom can, in a phenomenon known as superposition, be both binary digits, or bits, at the same time.
Related
The next trick is to combine that property with quantum entanglement, in which atoms share their properties between them. Now each one can affect the other without any physical signal passing between them. Three atoms in superposition and entangled have the ability to encode simultaneously all of the numbers from 0 to 7 and process those numbers in all possible computations within a single operation. With a register of 250 atoms, one could concurrently encode and process more numbers than there are atoms in the known universe. In that scenario, finding factors of large numbers becomes child’s play.
One of the organisers of the Seoul meeting, Michele Mosca of the Institute for Quantum Computing in Canada, thinks that a code-cracking quantum computer is likely to appear in the next couple of decades: his odds are 1/2 by 2031. How long will it take us to “quantum-proof” our security systems? Possibly a lot longer than that.
Content from our partners
In August, the US National Security Agency announced that it has started advising large institutions to transition to “quantum-resistant algorithms”, explaining that the “ultimate goal is to provide cost-effective security against a potential quantum computer”. An EU-funded research project called PQCrypto has also released a list of recommended quantum-safe solutions, urging their immediate uptake.
It’s not paranoia. PQCrypto points out that many secrets need to be kept for decades and: “Information encrypted today using RSA or elliptic curves and stored until quantum computers are available will then be as easy to decipher as Enigma-encrypted messages are today.”
You have been warned.
This article appears in the 30 Sep 2015 issue of the New Statesman, The Tory tide