Security in the Quantum World — Part 2, Offense

Last week I described how quantum effects can be used to secure your data, distributing keys for a Vernam cipher or one-time pad. The quantum system isn’t doing the cryptography,
it’s providing a trusted channel to distribute keys.

Could quantum systems be used to break security? The precursors of such systems are now on the market.

The Vernam or one-time pad system is the only perfectly secure system. All other cryptography is limited to being “strong enough”, where you believe that it would probably take your adversary long enough to break it that you would no longer care about the exposed secret. For example, if it would probably take three years to discover the key protecting next year’s car design.

“Strong enough” translates to math problems that are “hard enough”. The security of RSA, which protects so much, is based on the difficulty of factoring very large numbers (hundreds of digits!) into their prime factors.

Some mathematicians believe that a computer based on quantum effects might be able to very quickly solve the factoring problem. A paper in Nature in July 2013, “Oversimplifying Quantum Factoring”, discussed using Shor’s algorithm on a quantum computer for an exponential speed-up in factoring.

If such a device were available, that would break pretty much all security on the Internet today. I mentioned before that digital certificates based on Elliptic Curve Cryptography are now offered, providing an alternative form of security, but RSA is still the overwhelmingly popular choice.

“If such a device were available”? Vancouver-based D-Wave sells quantum computing systems today. Wired had a good introduction to the company and its products in 2012. D-Wave published a paper in Nature in 2011 showing that their system performed quantum annealing, an optimization technique vastly accelerated by quantum computing.

The computer science community continued to argue, was this really quantum annealing or its conventional (and much slower) forerunner simulated annealing? But on a practical level, Lockheed Martin bought a D-Wave system which they hoped to use to speed up the largely intractable problem of testing program accuracy and completeness. More recently, Google and NASA opened a lab at the NASA Ames Research Center, the Quantum Artificial Intelligence Center, powered by a D-Wave system. Google plans to apply it to machine translation. Wired wrote about the Google-NASA D-Wave in May and June of 2013.

D-Wave’s system is designed to solve combinatorial optimization problems like the classic “Traveling Salesman Problem”. Variations of these problems are of interest to airlines and investment firms, among others.

Factoring is a completely different problem, and it does not seem that a D-Wave (or other combinatorial optimization system) would be well-suited for factoring products of large primes. However, think about the evolution of tools useful for large factoring projects — we used to say that some specific type of quantum computer might solve it, but don’t worry because there are no quantum computers and no signs of any appearing soon. Now we have quantum computers — not the specific type suited for factoring, but we are getting close.

Keep an eye on ECC or Elliptic Curve Cryptography, it might suddenly become extremely important! We discuss this and other current trends in Learning Tree’s Cloud Security Essentials course.

Bob Cromwell

Type to search

Do you mean "" ?

Sorry, no results were found for your query.

Please check your spelling and try your search again.