Subscribe / Unsubscribe Enewsletters | Login | Register

Pencil Banner

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

George Nott | July 18, 2016
Quantum computers could one day decrypt everything.

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 academicsusing "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.

 

1  2  Next Page 

Sign up for MIS Asia eNewsletters.