Post Quantum Cryptography

Today I’m at the Joint Quantum Institute attending a workshop on quantum computing.  This morning’s session is on “post quantum cryptography.”  Post quantum cryptography is the study of classical (public key) cryptosystems which could replace the plethora of cryptosystems that quantum computers break (RSA, Diffie-Hellman, elliptic curves.)  These new systems include lattice based cryptography, the McEleise crypstosystem, and more (The name is kind of confusing, because post quantum cryptography, to me, sounds like the study of cryptosystems based on possible extensions or modifications of quantum theory, but that’s probably just because I spend too much time listening to foundations of quantum theory folks 🙂 )  Of course as a quantum computing person, my interest mostly is in hearing about problems that I can try to crack using a quantum computer 🙂

RSA and its ilk have a security that is based upon the computational difficulty of problems that now have a long history of study (factoring, discrete logarithm, etc.)  While it is completely possible that there is an efficient classical algorithm for factoring, a lot of our confidence in this not being true is based upon the large amount of effort that has been put into solving this problem.  We could even define a quantity: the integrated number of theorist hours spent on the problem.  This is certainly a very large number.  How large?  Well one probably has to know the size of the National Security Agency’s payroll to calculate it, but even in the public sphere this number is pretty high.  So for the post quantum cryptography world, the new (or old, but now more relevant) cryptosystems that have been proposed, we could also calculate this number.  More interestingly we could try to calculate this number for people working on quantum attacks on these problems.  I think I could actually do this calculation myself, as I know most of these people (or at least the ones in the public sphere), and even something about their working habits 🙂  But this is certainly a very very small number.  So it seems to me that if one really wants to study post quantum cryptography, one needs to invest heavily not just in people classically attacking the problems, but also in quantum theorists attacking the problem in order to insure confidence that this is truly “post quantum.

So…um, it seems that there is a very strong need to establish a very large effort in quantum algorithms, not just because we’d like to know what else quantum computers are good at, but also because we need to make sure “Shor, part II” doesn’t occur and the post quantum cryptography systems that are deployed aren’t themselves vulnerable to quantum attack.  I was at a program review recently where a speaker who funds quantum computing got up and said roughly “I got into quantum computing because it scared me.  What I want to see today is more things that scare me.”  Damn straight, but in practice I worry that the size of the effort directed this way in quantum computing is not nearly large enough.  The U.S. in particular has a severe dearth of quantum computing theorists, or at least such theorists who advance beyond the graduate student / postdoc level.

So post quantum cryptography is great, but it needs to be really “post quantum.”  And that scares me, because I look around and just don’t see the basis for a concerted effort to insure the security of these new cryptosystems against quantum attacks.