New Times,
New Thinking.

  1. Culture
8 October 2015updated 01 Jul 2021 1:31pm

Code breaking’s quantum leap – you have been warned

Our most secure encryption systems, such as RSA and elliptic curves, could be broken by quantum computing.

By Michael Brooks

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.

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.

Select and enter your email address Your weekly guide to the best writing on ideas, politics, books and culture every Saturday. The best way to sign up for The Saturday Read is via saturdayread.substack.com The New Statesman's quick and essential guide to the news and politics of the day. The best way to sign up for Morning Call is via morningcall.substack.com
Visit our privacy Policy for more information about our services, how Progressive Media Investments may use, process and share your personal data, including information on your rights in respect of your personal data and how you can unsubscribe from future marketing communications.
THANK YOU

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.

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.

Content from our partners
The UK’s skills shortfall is undermining growth
<strong>What kind of tax reforms would stimulate growth?</strong>

This article appears in the 30 Sep 2015 issue of the New Statesman, The Tory tide