There are many articles about quantum computers describing how powerful they are in computing and that they can solve very complicated equations in a short time. One of the biggest security measures that provide safety for computer security is that sometimes it takes years to break a piece of encrypted data. Will this safety remain after a quantum computing revolution? The question is:

  • Can they do such complicated computing?
  • Is it possible quantum computers put computer security in jeopardy?
  • 2
    $\begingroup$ On the flip side, Quantum Key Distribution reduces the demands put on strong encryption. In particular, the amount of plaintext being encrypted with a single key may sharply drop. For some purposes, One-Time Pads may become feasible. $\endgroup$
    – MSalters
    Commented Sep 2, 2018 at 22:38
  • 2
    $\begingroup$ With regards to terminology, safety and security are different concepts. And if something takes just a few years to break, that is considered completely insecure in the context of cryptography. What is considered secure is often far beyond what is possible within this universe. But humans are really, really bad when it comes to very large or very small numbers. $\endgroup$
    – tylo
    Commented Sep 3, 2018 at 18:29
  • 1
    $\begingroup$ @e-sushi: That question is arguably not a duplicate of the answers cited for closing it, and is the most straightforwardly worded of all 5. Can X attack Y is not the same as what would X need to attack Y, with the later leaving aside feasibility. Computer security and quantum cryptography are mostly disjoint, thus that (later) question (and its answer) are unrelated. Breaking modern computer security does not imply breaking symmetric crypto. Cryptography might well be preventively changed by Quantum Computing even without a quantum cryptopocalypse. $\endgroup$
    – fgrieu
    Commented Sep 23, 2018 at 16:53

2 Answers 2


can they (quantum computers) do such complicated computing (cryptanalysis)?

Not currently. Current quantum computers (including the adiabatic variants specialized in quantum annealing) do not perform anything useful for cryptanalysis. In the future: we don't know.

Is it possible quantum computers put the computer security in jeopardy?

It is reasonable to worry for the long term. There's therefore a lot of activity to be prepared for quantum computers useful for cryptanalysis. The quasi consensus is that 256-bit symmetric crypto (AES-256, SHA-512, SHA3-512 and the like) will remain safe in the foreseeable future. Most currently used asymmetric/public-key crypto (RSA and others based on factorization; DSA, DH, Schnorr signature, ECDSA, EdDSA, ECDH and others based on discrete logarithm) may not, especially for the smallest key sizes currently considered safe. But practical quantum-safe asymmetric cryptography seems feasible, and is in the works. There's preliminary standardization effort at NIST.

This related question asks how to predict when and if quantum cryptopocalypse is coming.

  • 6
    $\begingroup$ R1w: Currently used asymmetric crypto (including the algorithms listed, RSA et al) is likely not secure. There is active research into replacement algorithms that are believed not to be broken by a Quantum Computer $\endgroup$
    – poncho
    Commented Sep 2, 2018 at 11:47
  • 1
    $\begingroup$ @poncho In reference to"research into replacement algorithms"Is it a special project by a specific organization or you meant Generally. $\endgroup$
    – R1w
    Commented Sep 4, 2018 at 16:07
  • 3
    $\begingroup$ @R1w: generally. Current, the NIST PQC project is acting as the generally accepted forum (see csrc.nist.gov/projects/post-quantum-cryptography), there are a number of different submissions to them by various teams. $\endgroup$
    – poncho
    Commented Sep 4, 2018 at 16:21
  • $\begingroup$ I don't think this is still accurate: quantum annealing on D-Wave can solve small problems, with complexity roughly b^2 where b is the number of bits in the number to factorize (ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9797855). $\endgroup$ Commented Aug 11, 2022 at 22:02
  • $\begingroup$ @John Targaryen: see this answer, starting at adiabatic quantum computing records, for why the factorization records in D-Wave quantum computers do not make them Cryptographically Relevant Quantum Computers. $\endgroup$
    – fgrieu
    Commented Aug 12, 2022 at 7:47

If quantum computers are physically feasible, then there are some algorithmic problems that they should be able to solve faster than classical computers. It happens that brute-force search and discrete logarithms are two of those problems. Unfortunately, the security of symmetric cryptosystems depends on brute-force search being hard, and the security of the currently-used asymmetric cryptosystems depends on discrete logarithms being hard.

The situation for brute-force search is not so bad: the quantum algorithm operates in $O(\sqrt{N})$ time, which means if we just double the length of our symmetric keys we're back where we started. Thus, for instance, you may read that AES-128 is weak against quantum computers but AES-256 isn't.

But the situation for discrete logarithms is very bad: the quantum algorithm brings the task down from "subexponential" time to "polynomial" time, and that means we need to replace the asymmetric cipher primitives that depend on discrete logs with new ones that don't. The good news is we already have some candidates.

It is important to understand that quantum computers do not, as far as we know, enable us to solve "NP-complete" problems in polynomial time (formally, complexity theorists have strong reasons to think that BQP does not contain NP; but this has not yet been proven). If they could, that would imply that a quantum computer could invert any one-to-one function in polynomial time, even if it was a one-way function for a classical computer. That in turn would mean quantum computers could break all known message ciphers except for the one-time pad. Perhaps even worse, they could counterfeit all known message authentication schemes.

Incidentally, "quantum key distribution" is not a cryptosystem; it's a key exchange protocol. It allows two parties to agree on a key with a strong guarantee that no eavesdropper could have also received that key. In the absence of one-way functions, you could use QKD to distribute one-time pads, but you would still have all of the practical difficulties associated with one-time pads.

  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – e-sushi
    Commented Sep 28, 2018 at 23:15
  • 2
    $\begingroup$ QKD is no key exchange but rather a key growing scheme as it requires an initial shared secret! Without the existence of a one-way function, this cannot be established online. Hence, you still got the key exchange problem. $\endgroup$
    – mephisto
    Commented Oct 14, 2018 at 16:44

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.