I don't know the answer to your question, but if we were able to develop quantum cryptography (http://en.wikipedia.org/wiki/Quantum_cryptography), then we would no longer need to worry about public key algorithms, since Alice and Bob could agree upon a key without fear of eavesdropping, and then use an uncrackable form of encryption, such as a one time pad.
We already have functioning quantum cryptography. In theory it should be unbreakable, but there are practical problems with it (distance... it doesn't work around the world) and still relies on humans to implement the systems.
There are lattice problems that we don't know how to solve efficiently in the quantum model yet. Under some plausible conjectures, certain learning with error problems would be hard in the quantum model. Quantum complexity is an open and ongoing area of research.
6 comments
[ 3.4 ms ] story [ 24.1 ms ] threadCurrent quantum cryptography systems have already been cracked to some extent: http://spectrum.ieee.org/computing/it/quantum-cryptography-c...
Chris Peikert has some recent results on the topic: http://www.cc.gatech.edu/fac/cpeikert/pubs/svpcrypto.pdf
Oded Regev has also done quite a bit of relevant work.