Tuesday, February 5, 2013

Quantum-Resistant Encryption (UPDATED)...

If you posit the existence of a quantum computer (either now, tucked away in a government agency, or in the future when scientists figure out how to do it), then the cryptosystems in general use today can be trivially broken.  In plain English: anybody with a quantum computer can read all of your encrypted messages, including any secure web sessions (HTTPS via SSL).

I just stumbled across a cryptosystem that doesn't have any known attack via quantum computer, and is available today.  It's called NTRU, and it's an asymmetric key system with fairly high performance (especially compared with conventional asymmetric cryptosystems).  It's available in a Java library from the creators, and it's now part of Bouncy Castle.

I just barely understand the math behind conventional cryptosystems.  I haven't (yet) tried to understand this one, but I'm very curious to see how its mathematical properties make it immune to the quantum attacks that would work against conventional cryptosystems.  Perhaps one of my readers understands and can illuminate the topic for us?

Update 2/5:  Reader and friend Doug W. writes to say:
Color me very skeptical. I have no problem with quantum computing as an interesting basic research topic, but many folks, both in the field and in the press, seem to believe that we’re just a few years away from something practical. My suspicion is that it’s more like nuclear fusion power, which has been a constant 10-20 years away from practicality for over sixty years. In fact, I’m far more optimistic about fusion power than quantum computers, which isn’t saying much.

It’s possible – in some very strange theoretical sense – for a quantum computer to factor large numbers used in RSA crypto, assuming you could even convince the quantum device to do big integer math, though that alone seems unlikely to me. However, my gut says that the thermal noise in any system, even near absolute zero, dwarfs the energy difference between that many superimposed quantum states by many orders of magnitude (dozens? hundreds?). Thus, I find it difficult to believe that such a system would be stable long enough to be useful. I could certainly be wrong, but I’m not holding my breath. Right now, quantum computers can factor the number 15, and they’ve been stuck there for a good while -- it’s a long way from 2**4 to 2**1024. Just saying…

And don’t get me started about quantum cryptography. As Paul Kocher (a very well known and respected crypto researcher) said in 2003:
To me, quantum cryptography is useless. It purports to solve a problem that’s already solved. It is an interesting research problem, though. But, you’re not going to see quantum computers showing up to do useful things probably in my lifetime and possibly never. But it is the most interesting problem in computing in the last 30 years. It’s absolutely fascinating. But, of all the things that keep us awake at night, that’s way down there with alien invasions.
I’ve heard lots of talks on quantum crypto at cryptography conferences over the past 15 years, and most of the cryptographers I know just roll their eyes. It is, however, a great research area if you are looking to get research grant money.

Also, fwiw, NTRU has been around quite a while and is at best a niche technology. Lattice cryptography has a bit of a funky reputation (not all due to NTRU), due to lots of claims which have been repeatedly broken. The NTRU folks are nice guys and very bright, but I don’t see it getting wide deployment anytime soon.

[Full disclosure: I have an applied physics degree from Caltech, and I do cryptography for a living]