Are there any cryptosystems that we know that would be secure against an attack by a quantum computer?

Are there problems which are known or suspected to be hard for quantum computers, and can these be utilized to yield cryptographic protocols which are secure against quantum computers?

  • 7
    $\begingroup$ The key search term for that literature is “post-quantum cryptography”. $\endgroup$ Jun 29 '18 at 5:02
  • $\begingroup$ Intuitively, the protocols that utilize problems not in $\mathrm{BQP}$... (I do not know too much about either crypto or complexity theory, though) $\endgroup$
    – xrq
    Jun 30 '18 at 19:24
  • 1
    $\begingroup$ I am no expert, but I think lattice cryptography, like schemes based on the Learning with Errors problem, are conjectured to be secure against quantum attacks. This would follow from worst-case quantum hardness of variants of the shortest vector problem. $\endgroup$ Jul 31 '18 at 13:30
  • $\begingroup$ Note that Cryptography protocols and Cryptosystems are not the same. $\endgroup$
    – kelalaka
    Sep 11 '19 at 7:21

"Quantum Computers" may give you significant speedup in many types of attacks. These speedups may not necessarily be exponential like the current Shor's algorithm usage for breaking RSA. You may find more information here: https://security.stackexchange.com/questions/116596/will-quantum-computers-render-aes-obsolete


There was just a paper published by R3 on a cryptographic method using Merkle trees adapted for blockchain (https://eprint.iacr.org/2018/658.pdf). The field of PQ-Cryptography is right now reliant mainly on hashes and other algorithms that are not dependent on the factoring problem (or modifications of this problem such as the discrete log). Altered Bulletproofs and Ring Signatures are two current post-quantum secure algorithms that show promise (NTRU in particular). I advise you submit this post on (https://crypto.stackexchange.com/) as that is an SE for cryptography.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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