It's well-known that Shor's algorithm can solve integer factorization, discrete logarithm and discrete log over elliptic curves in cubic time. This implies that cryptosystems like RSA, ElGamal, and Elliptic Curve Diffie-Hellman (ECDH) are vulnerable to quantum computers.

Are there any existing public-key cryptosystem that are NOT known to have a polynomial-time quantum attack?

This question was inspired by this blog post.


2 Answers 2



If you mean "syntactically public key" instead of "implies the existence of secure key agreement",
then there is also hash-based signatures.


Since the time you asked your question some new algorithms have shown great promise. The first set of algorithms are based on the Learning with Errors Problem in over polynomial rings. See http://www.cc.gatech.edu/~cpeikert/pubs/suite.pdf

There is also an elliptic curve scheme based around supersingular elliptic curve isogenies. There's a Wikipedia article on that. http://en.wikipedia.org/wiki/Supersingular_Isogeny_Key_Exchange


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.