Can quantum computers put computer security in jeopardy?
Can quantum computers put computer security in jeopardy?
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:
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.
– tylo
Sep 3 at 18:29
@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.
– fgrieu
Sep 23 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, Schnoor 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.
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
– poncho
Sep 2 at 11:47
@poncho In reference to"research into replacement algorithms"Is it a special project by a specific organization or you meant Generally.
– R1w
Sep 4 at 16:07
@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.
– poncho
Sep 4 at 16:21
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(sqrtN)$ 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.
Comments are not for extended discussion; this conversation has been moved to chat.
– e-sushi
Sep 28 at 23:15
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.
– mephisto
Oct 14 at 16:44
Thanks for contributing an answer to Cryptography Stack Exchange!
But avoid …
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
But avoid …
To learn more, see our tips on writing great answers.
Required, but never shown
Required, but never shown
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
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.
– MSalters
Sep 2 at 22:38