Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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 (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.
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.
