Quantum computing is building on Alan Turing’s legacy
The Bank of England has a new hero: Alan Turing. The gay mathematician, computing pioneer and wartime codebreaker — whose work helped decrypt messages encoded by Germany’s Enigma machine but whose sexuality saw him criminalised and chemically castrated — was unveiled this week as the face of the new £50 note.
The piece of pink polymer is a pleasing addition to any purse: it features Turing’s date of birth written in binary code plus drawings of the Bombe, the device he co-invented for cracking Enigma. It also contains a quote from a 1949 newspaper interview: “This is only a foretaste of what is to come, and only a shadow of what will be.”
Even 20 years ago, it would have taken the most visionary computer scientist to forecast what currently is. The big challenge today is keeping data secret in the face of accelerating computer power. And the most serious threat to that secrecy is the prospect of quantum computers, a concept that can be viewed as a natural successor to Turing’s vision of a “universal machine”. Computer scientists are now scrambling to develop “post-quantum cryptography”, a set of new cyber security protocols that cannot be undone by these futuristic machines.
Quantum computers, a concept that took off in the 1980s, are a world apart from their conventional counterparts. A classical computer uses bits (binary digits) which have only two possible states: 1 or 0. A quantum computer uses quantum bits, or qubits, which can exist in many states simultaneously. By stringing qubits together, makers of quantum computers hope to unleash an exponential explosion in processing power.
Google, IBM, Microsoft and Rigetti are among those vying to assemble a machine that can tackle the problems that the best conventional supercomputers cannot, something that most observers believe has not yet happened.
Quantum computing is perhaps decades away from fulfilling its potential, but its rise poses a security threat nonetheless. The algorithms that encrypt all sorts of data, from online payments to sensitive government documents, are based on notoriously difficult mathematical puzzles that conventional computers are unable to solve. It is this intractability that gives the algorithms their secret-keeping powers.
Consider the widely used RSA encryption algorithm, for example, which is based on factoring huge numbers. While guessing the factors of 15 is easy enough (3x5), factoring 600-digit numbers is sufficiently difficult to make RSA a popular security choice. Factoring, however, is a task that quantum computers are likely to perform with ease.
“If you consider applications that require confidentiality for tens of years, such as government documents, then we require new algorithms that even quantum computers cannot break if they are built in the next 10 to 20 years,” explains Siamak Shahandashti, a cyber security researcher at York university in the UK.
Computer scientists are now mining mathematics to find “hard problems” from which to concoct new algorithms. Number theory, the study of numbers and how they relate to each other, is fertile ground: it has occupied generations of thinkers and captivated some of history’s most famous mathematicians, such as Pythagoras and Euclid.
Any number of problems that defy easy solution, despite millennia of attention, are candidates for algorithms. Lattice-based cryptography is one such prospect. A lattice is a grid of dots and is relatively easy to visualise in two or three dimensions. Pick any point inside that lattice, and it would be fairly simple to work out where the nearest dot to that “origin” would be.
But what if we make the lattice infinite and raise the number of dimensions? This complicates the computation. At hundreds of dimensions — impossible to visualise but apparently theoretically workable — the calculation might soar beyond the reach even of quantum computers.
Lattice schemes are among new cryptographic possibilities being evaluated by the National Institute of Standards and Technology in Maryland, which makes recommendations on cyber security standards. NIST’s Post Quantum Cryptography Standardisation project will shortlist promising encryption methods by the end of this year.
Turing died in 1954 after swallowing cyanide, a probable suicide. It was a wretched end for an underrated thinker who, in life as in death, was on the money. “Sometimes it is the people no one can imagine anything of who do the things no one can imagine,” he once said.
The writer is a science commentator
Gloss