Mixing
Can quantum computers put computer security on jeopardy?
Clash Royale CLAN TAG#URR8PPP
up vote
10
down vote
favorite
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?
encryption distributed-decryption quantum-cryptanalysis
asked Sep 2 at 7:52
R1w
29915
add a comment |Â
up vote
10
down vote
favorite
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?
encryption distributed-decryption quantum-cryptanalysis
asked Sep 2 at 7:52
R1w
29915
1
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
1
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
add a comment |Â
up vote
10
down vote
favorite
up vote
10
down vote
favorite
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?
encryption distributed-decryption quantum-cryptanalysis
asked Sep 2 at 7:52
R1w
29915
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?
encryption distributed-decryption quantum-cryptanalysis
asked Sep 2 at 7:52
R1w
29915
edited Sep 6 at 18:00
asked Sep 2 at 7:52
R1w
29915
asked Sep 2 at 7:52
R1w
29915
asked Sep 2 at 7:52
R1w
29915
29915
1
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
1
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
add a comment |Â
1
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
1
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
1
1
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
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
1
1
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
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
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
14
down vote
accepted
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.
answered Sep 2 at 11:08
fgrieu
72.4k6149309
4
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
2
@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
add a comment |Â
up vote
6
down vote
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.
answered Sep 2 at 18:47
zwol
485210
3
“it would mean that they could break any cryptosystem†– except quantum teleportation. (And one-time pad.)
– leftaroundabout
Sep 3 at 0:24
1
Not sure about that "any cryptosystem" bit. There might be cryptography outside of NP that we don't really know about. Also, quantum might give some measures of security - like making it impossible to listen in unnoticed even if you do break privacy. Quantum entanglement could make it impossible to listen in without scrambling the data, which would be a huge flashing red light on the data-breach warning panel. That said, it's a bit further off than quantum computing will be. Call me naive, but I think that while quantum will weaken current solutions, it will also provide new ones.
– Jacco van Dorp
Sep 3 at 7:42
1
@JaccovanDorp There's a precise mathematical sense in which what I said is true: if $P = NP$, then one-way functions do not exist. All known cryptosystems, other than the one-time pad, depend on functions that are believed to be one-way.
– zwol
Sep 3 at 14:05
1
I will fully admit I was nitpicking the difference between "all cryptosystems" and "all known cryptosystems". Even if quantum computers will break everything we currently have, it may also provide new cryptosystems that are as hard to break with quantum systems as the current crypto is without.
– Jacco van Dorp
Sep 4 at 8:22
1
@JaccovanDorp If $NP notsubseteq BQP$, you're definitely right. In the unlikely case that $NP subseteq BQP$, you may still be right but finding them is going to be much harder. (All of the current generation of "post-quantum" asymmetric ciphers would fall to a polynomial-time 3SAT solver, AFAICT.)
– zwol
Sep 4 at 12:50
 |Â
show 1 more comment
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
14
down vote
accepted
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.
answered Sep 2 at 11:08
fgrieu
72.4k6149309
4
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
2
@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
add a comment |Â
up vote
14
down vote
accepted
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.
answered Sep 2 at 11:08
fgrieu
72.4k6149309
4
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
2
@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
add a comment |Â
up vote
14
down vote
accepted
up vote
14
down vote
accepted
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.
answered Sep 2 at 11:08
fgrieu
72.4k6149309
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.
answered Sep 2 at 11:08
fgrieu
72.4k6149309
edited Sep 3 at 5:55
answered Sep 2 at 11:08
fgrieu
72.4k6149309
answered Sep 2 at 11:08
fgrieu
72.4k6149309
answered Sep 2 at 11:08
fgrieu
72.4k6149309
72.4k6149309
4
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
2
@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
add a comment |Â
4
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
2
@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
4
4
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
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
@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
2
2
@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
@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
add a comment |Â
up vote
6
down vote
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.
answered Sep 2 at 18:47
zwol
485210
3
“it would mean that they could break any cryptosystem†– except quantum teleportation. (And one-time pad.)
– leftaroundabout
Sep 3 at 0:24
1
Not sure about that "any cryptosystem" bit. There might be cryptography outside of NP that we don't really know about. Also, quantum might give some measures of security - like making it impossible to listen in unnoticed even if you do break privacy. Quantum entanglement could make it impossible to listen in without scrambling the data, which would be a huge flashing red light on the data-breach warning panel. That said, it's a bit further off than quantum computing will be. Call me naive, but I think that while quantum will weaken current solutions, it will also provide new ones.
– Jacco van Dorp
Sep 3 at 7:42
1
@JaccovanDorp There's a precise mathematical sense in which what I said is true: if $P = NP$, then one-way functions do not exist. All known cryptosystems, other than the one-time pad, depend on functions that are believed to be one-way.
– zwol
Sep 3 at 14:05
1
I will fully admit I was nitpicking the difference between "all cryptosystems" and "all known cryptosystems". Even if quantum computers will break everything we currently have, it may also provide new cryptosystems that are as hard to break with quantum systems as the current crypto is without.
– Jacco van Dorp
Sep 4 at 8:22
1
@JaccovanDorp If $NP notsubseteq BQP$, you're definitely right. In the unlikely case that $NP subseteq BQP$, you may still be right but finding them is going to be much harder. (All of the current generation of "post-quantum" asymmetric ciphers would fall to a polynomial-time 3SAT solver, AFAICT.)
– zwol
Sep 4 at 12:50
 |Â
show 1 more comment
up vote
6
down vote
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.
answered Sep 2 at 18:47
zwol
485210
3
“it would mean that they could break any cryptosystem†– except quantum teleportation. (And one-time pad.)
– leftaroundabout
Sep 3 at 0:24
1
Not sure about that "any cryptosystem" bit. There might be cryptography outside of NP that we don't really know about. Also, quantum might give some measures of security - like making it impossible to listen in unnoticed even if you do break privacy. Quantum entanglement could make it impossible to listen in without scrambling the data, which would be a huge flashing red light on the data-breach warning panel. That said, it's a bit further off than quantum computing will be. Call me naive, but I think that while quantum will weaken current solutions, it will also provide new ones.
– Jacco van Dorp
Sep 3 at 7:42
1
@JaccovanDorp There's a precise mathematical sense in which what I said is true: if $P = NP$, then one-way functions do not exist. All known cryptosystems, other than the one-time pad, depend on functions that are believed to be one-way.
– zwol
Sep 3 at 14:05
1
I will fully admit I was nitpicking the difference between "all cryptosystems" and "all known cryptosystems". Even if quantum computers will break everything we currently have, it may also provide new cryptosystems that are as hard to break with quantum systems as the current crypto is without.
– Jacco van Dorp
Sep 4 at 8:22
1
@JaccovanDorp If $NP notsubseteq BQP$, you're definitely right. In the unlikely case that $NP subseteq BQP$, you may still be right but finding them is going to be much harder. (All of the current generation of "post-quantum" asymmetric ciphers would fall to a polynomial-time 3SAT solver, AFAICT.)
– zwol
Sep 4 at 12:50
 |Â
show 1 more comment
up vote
6
down vote
up vote
6
down vote
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.
answered Sep 2 at 18:47
zwol
485210
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.
answered Sep 2 at 18:47
zwol
485210
edited Sep 4 at 12:56
answered Sep 2 at 18:47
zwol
485210
answered Sep 2 at 18:47
zwol
485210
answered Sep 2 at 18:47
zwol
485210
485210
3
“it would mean that they could break any cryptosystem†– except quantum teleportation. (And one-time pad.)
– leftaroundabout
Sep 3 at 0:24
1
Not sure about that "any cryptosystem" bit. There might be cryptography outside of NP that we don't really know about. Also, quantum might give some measures of security - like making it impossible to listen in unnoticed even if you do break privacy. Quantum entanglement could make it impossible to listen in without scrambling the data, which would be a huge flashing red light on the data-breach warning panel. That said, it's a bit further off than quantum computing will be. Call me naive, but I think that while quantum will weaken current solutions, it will also provide new ones.
– Jacco van Dorp
Sep 3 at 7:42
1
@JaccovanDorp There's a precise mathematical sense in which what I said is true: if $P = NP$, then one-way functions do not exist. All known cryptosystems, other than the one-time pad, depend on functions that are believed to be one-way.
– zwol
Sep 3 at 14:05
1
I will fully admit I was nitpicking the difference between "all cryptosystems" and "all known cryptosystems". Even if quantum computers will break everything we currently have, it may also provide new cryptosystems that are as hard to break with quantum systems as the current crypto is without.
– Jacco van Dorp
Sep 4 at 8:22
1
@JaccovanDorp If $NP notsubseteq BQP$, you're definitely right. In the unlikely case that $NP subseteq BQP$, you may still be right but finding them is going to be much harder. (All of the current generation of "post-quantum" asymmetric ciphers would fall to a polynomial-time 3SAT solver, AFAICT.)
– zwol
Sep 4 at 12:50
 |Â
show 1 more comment
3
“it would mean that they could break any cryptosystem†– except quantum teleportation. (And one-time pad.)
– leftaroundabout
Sep 3 at 0:24
1
Not sure about that "any cryptosystem" bit. There might be cryptography outside of NP that we don't really know about. Also, quantum might give some measures of security - like making it impossible to listen in unnoticed even if you do break privacy. Quantum entanglement could make it impossible to listen in without scrambling the data, which would be a huge flashing red light on the data-breach warning panel. That said, it's a bit further off than quantum computing will be. Call me naive, but I think that while quantum will weaken current solutions, it will also provide new ones.
– Jacco van Dorp
Sep 3 at 7:42
1
@JaccovanDorp There's a precise mathematical sense in which what I said is true: if $P = NP$, then one-way functions do not exist. All known cryptosystems, other than the one-time pad, depend on functions that are believed to be one-way.
– zwol
Sep 3 at 14:05
1
I will fully admit I was nitpicking the difference between "all cryptosystems" and "all known cryptosystems". Even if quantum computers will break everything we currently have, it may also provide new cryptosystems that are as hard to break with quantum systems as the current crypto is without.
– Jacco van Dorp
Sep 4 at 8:22
1
@JaccovanDorp If $NP notsubseteq BQP$, you're definitely right. In the unlikely case that $NP subseteq BQP$, you may still be right but finding them is going to be much harder. (All of the current generation of "post-quantum" asymmetric ciphers would fall to a polynomial-time 3SAT solver, AFAICT.)
– zwol
Sep 4 at 12:50
3
3
“it would mean that they could break any cryptosystem†– except quantum teleportation. (And one-time pad.)
– leftaroundabout
Sep 3 at 0:24
“it would mean that they could break any cryptosystem†– except quantum teleportation. (And one-time pad.)
– leftaroundabout
Sep 3 at 0:24
1
1
Not sure about that "any cryptosystem" bit. There might be cryptography outside of NP that we don't really know about. Also, quantum might give some measures of security - like making it impossible to listen in unnoticed even if you do break privacy. Quantum entanglement could make it impossible to listen in without scrambling the data, which would be a huge flashing red light on the data-breach warning panel. That said, it's a bit further off than quantum computing will be. Call me naive, but I think that while quantum will weaken current solutions, it will also provide new ones.
– Jacco van Dorp
Sep 3 at 7:42
Not sure about that "any cryptosystem" bit. There might be cryptography outside of NP that we don't really know about. Also, quantum might give some measures of security - like making it impossible to listen in unnoticed even if you do break privacy. Quantum entanglement could make it impossible to listen in without scrambling the data, which would be a huge flashing red light on the data-breach warning panel. That said, it's a bit further off than quantum computing will be. Call me naive, but I think that while quantum will weaken current solutions, it will also provide new ones.
– Jacco van Dorp
Sep 3 at 7:42
1
1
@JaccovanDorp There's a precise mathematical sense in which what I said is true: if $P = NP$, then one-way functions do not exist. All known cryptosystems, other than the one-time pad, depend on functions that are believed to be one-way.
– zwol
Sep 3 at 14:05
@JaccovanDorp There's a precise mathematical sense in which what I said is true: if $P = NP$, then one-way functions do not exist. All known cryptosystems, other than the one-time pad, depend on functions that are believed to be one-way.
– zwol
Sep 3 at 14:05
1
1
I will fully admit I was nitpicking the difference between "all cryptosystems" and "all known cryptosystems". Even if quantum computers will break everything we currently have, it may also provide new cryptosystems that are as hard to break with quantum systems as the current crypto is without.
– Jacco van Dorp
Sep 4 at 8:22
I will fully admit I was nitpicking the difference between "all cryptosystems" and "all known cryptosystems". Even if quantum computers will break everything we currently have, it may also provide new cryptosystems that are as hard to break with quantum systems as the current crypto is without.
– Jacco van Dorp
Sep 4 at 8:22
1
1
@JaccovanDorp If $NP notsubseteq BQP$, you're definitely right. In the unlikely case that $NP subseteq BQP$, you may still be right but finding them is going to be much harder. (All of the current generation of "post-quantum" asymmetric ciphers would fall to a polynomial-time 3SAT solver, AFAICT.)
– zwol
Sep 4 at 12:50
@JaccovanDorp If $NP notsubseteq BQP$, you're definitely right. In the unlikely case that $NP subseteq BQP$, you may still be right but finding them is going to be much harder. (All of the current generation of "post-quantum" asymmetric ciphers would fall to a polynomial-time 3SAT solver, AFAICT.)
– zwol
Sep 4 at 12:50
 |Â
show 1 more comment
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f61975%2fcan-quantum-computers-put-computer-security-on-jeopardy%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
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
1
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