Will there be a need to change the definitions of security if we have quantum computers? What cryptographic constructions will break? Do you know a survey or an article that explains what will be needed to change?

  • 1
    $\begingroup$ You might find this article, available through the ACM, interesting; it seems to address your question, or at least aspects thereof: dl.acm.org/… If you don't have access, it may be available for download online. Otherwise, I can read it and try to briefly summarize the main points. $\endgroup$
    – Patrick87
    Apr 30 '12 at 17:21
  • 1
    $\begingroup$ @Patrick87: It's behind a paywall, for me. A summary would be appreciated. :) $\endgroup$ Apr 30 '12 at 19:28

Summary of this paper providing a (partial) answer.

There are two kinds of traditional public-key cryptographic methods: those based on integer factorization, and those based on the discrete logarithm, including elliptic-curve-based methods. These models are believed to be hard in the classical models, but have been shown that neither is hard in the quantum model.

Although Grover developed a quantum algorithm providing quadratic speedup for searching, Bennet, Bernstein, Brassard and Vazirani showed that the quantum model couldn't allow exponential speedup for search problems. This suggests symmetric encryption algorithms, one-way functions and cryptographic hashes should resist quantum-based attacks. The focus, then, should be on developing secure public-key methods.

Lamport signatures may provide a one-time signature mechanism secure against quantum attacks. Lattice problems may form the basis for public-key methods which are resistant to quantum attacks; in particular, the NP-Hard shortest-vector and closest-vector problems are attractive. For both the classical and quantum models, these problems are believed to be hard for lattices of high dimension. The NTRU family of cryptographic algorithms, based on lattice problems, may provide a practical means of achieving public-key cryptography resistant to quantum attacks. Another problem which might serve as a basis for secure public key methods is the syndrome decoding problem. The McEliece encryption system is based on this problem, and variants may provide a way forward.


I'm by no means an expert (or even close to that) on the topic, but from what I know:

Classical cryptography depends on the intractability of factoring (or the discrete log problem). However, factoring is not believed to be NP-complete, and it is indeed solvable in polynomial time by quantum computers. So any cryptography that depends on those operations would break (which is every kind of cryptography used out there that I know of).

Quantum cryptography depends on quantum mechanics, and it's theoretically impossible to break it. It's not a matter of time at all -- it's simply based on randomness, and the fact that a state collapses upon being measured, so without the appropriate information, your best choice is to simply 'guess' the message... which is useless.


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.