Can we find a quantum-resistant algorithm before it’s too late?

The Centre for Quantum Computation and Communication Technology at UNSW, Sydney

The warning from QuintessenceLabs’ CTO John Leisoboer is stark. “When sufficiently powerful quantum computers become generally available,” he says, “it’s guaranteed to break all existing cryptographic systems that we know of.”

In other words, he adds, “Everything that we’re doing today will be broken.”

It’s a sentiment echoed by Google’s Chrome security software engineer Matt Braithwaite who wrote in a blog post earlier this month that “a hypothetical, future quantum computer would be able to retrospectively decrypt any internet communication that was recorded today”.

With the race to build a true quantum computer well underway, governments, financial institutions and tech giants are scrambling to mount a defence against the major security threat the burgeoning technology presents. And it’s proving even trickier than they knew it would be.

Tough maths

The foundation of modern cryptographic systems is, essentially, really tough maths.

Most cryptographic methods in use today – the kind used to secure emails, money transfers, online banking systems, Secure Sockets Layer and Transport Layer Security (the security protocol behind HTTPS) – are hard to unpick because they're based on the problem of integer factorisation: The inherent difficulty of identifying what the prime factors of a large number are.

These types of calculation, the ones that underpin public-key algorithms, prove exceptionally hard for classical computers to crack. In 2009, for example, a 768-bit (232 digit) number was eventually factored by a multi-national team of academics using “many hundreds of machines”. It took them more than two years. Using a single computer, they said, it would have taken more than 1500.

It’s a similar story for elliptic curve cryptography, also used for public key encryption, which is based on the difficulty of finding the discrete logarithm of a random elliptic curve.

“For a classical computer it’s actually a very difficult problem,” explains Professor Michelle Simmons, head of the Centre for Quantum Computation and Communication Technology at UNSW in Sydney. “If you had a quantum computer it could solve it in minutes”.

“If you can use quantum states you can do massively parallel computing that you just can't do with the classical industry.”

While a ‘classical computer’ can process one calculation at a time, in sequence, a quantum computer can work out millions of sums simultaneously.

"The fear is definitely warranted," says Nick Savvides, manager of Symantec's Cyber Security Strategy in Asia Pacific and Japan. “This is an active area of research and offers unrivalled capabilities in terms of computing power and the ability to attack existing technologies.”

Sure threat

In 1994, MIT Professor Peter Shor wrote a quantum algorithm that would be able to factor numbers at relative speed on a quantum computer, which at that time existed only in theory.

Nobody was too worried. A quantum computer capable of running Shor’s algorithm seemed so distant. In 2001, there was a breakthrough, of sorts. IBM researchers working on an early model of a quantum computer used Shor’s method to calculate the factors of 15. Eleven years later a bigger number was factored: 21.

Up against the recommended RSA key length of 3072-bit or longer, the quantum effort so far seems feeble. But the advent of a far more powerful machine is getting closer by the day. The likes of Google, NASA, Lockheed Martin, Commonwealth Bank and Telstra are backing bids in a global race to build one first.

“Although we don’t know exactly when they’re going to come,” says QuintessenceLabs’ Leiseboer, “we do know, when they do come, that everything that’s processed today will be made vulnerable at that point in time. Any information that has longevity now is already an issue.”

Even tougher maths

To avoid such an event – which has been dubbed “wiki-leaks on steroids” and the “cryptopocalypse” – there is a scramble to come up with a new suite of algorithms that are “quantum-resistant”.

Some, the “lattice-based cryptographic primitives” proposed by researchers at Microsoft, though promising have not yet been formally proved safe.

The US National Security Agency, meanwhile, is pushing the National Institute of Standards and Technology and the wider community to develop a “widely accepted, standardised set” of resistant algorithms, but at best these will be available sometime “in the next decade”.

ETSI, the European Telecommunications Standards Institute, set up the Quantum Safe Cryptography working group last year. “We want to be ready” said its chairman Mark Pecan. Quantum computers, he added, were a “significant threat to our global information infrastructure”.

Google, meanwhile, are testing a “post-quantum algorithm” called New Hope, testing it with some users via Chrome Canary.

But quantum-resistant algorithms are currently just that - a hope. Google admits that its “might turn out to be breakable even with today's computers”. And even when a potential solution is found – standardisation takes significant time and testing. Failed attempts litter the course.

In 2013, the UK’s Government Communications Headquarters (GCHQ) abandoned years of work into what they hoped would be a quantum resistant, cyclic-lattice based primitive – code named Soliloquy – after managing to crack it with a ‘reasonably efficient quantum attack’.

In a paper titled ‘A Cautionary Tale’ GCHQ’s experts warned that “much care and patience" is required to apply a thorough security assessment.

Their conclusion was frank: “designing quantum-resistant cryptography is a difficult task”.