I've been told that physicists and computer scientists are working on computers that could use quantum physics to increase significantly computation capabilities and break any cipher so cryptography becomes meaningless.
Is it true?
$\begingroup$
$\endgroup$
8
-
9$\begingroup$ Related reading: How will Cryptography be changed by Quantum Computing? (and probably a fair bit in Cryptography's post-quantum-cryptography tag and Information Security's quantum-computing tag). $\endgroup$– userJul 16, 2015 at 10:19
-
8$\begingroup$ I'm voting to close this question as off-topic because the question is asking about verifying the claim of the use of a quantum computer and not at all about physics. Perhaps Cryptography or Skeptics might be better suited for this question. $\endgroup$– Kyle KanosJul 16, 2015 at 15:15
-
9$\begingroup$ I actually don't think this is on topic for us. It's really a question about cryptography - the only connection to physics is knowing that a quantum computer can effectively solve certain problems in less-than-exponential time. $\endgroup$– David ZJul 16, 2015 at 15:16
-
$\begingroup$ I don't think it's even that big of a deal. I answered a similar question a while ago, How will Cryptography be changed by Quantum Computing?, and the tdlr of it was we know how to deal with computers getting faster: bigger key-spaces. $\endgroup$– Nathan CooperJul 16, 2015 at 16:03
-
1$\begingroup$ @NathanCooper If I can build a machine whose ability to factor grows faster than your machine's ability to encrypt/decrypt, then bigger key spaces don't help. Or am I missing something? $\endgroup$– DanielSankJul 16, 2015 at 17:42
|
Show 3 more comments
7 Answers
$\begingroup$
$\endgroup$
0
No, it is not.
Quantum computers can factor large numbers efficiently, which would allow to break many of the commonly used public key cryptosystems such as RSA, which are based on the hardness of factoring.
However, there are other cryptosystems such as lattice-based cryptography which are not based on the hardness of factoring, and which (to our current knowledge) would not be vulnerable to attack by a quantum computer.
answered Jul 16, 2015 at 8:55
$\begingroup$
$\endgroup$
4
Quantum computing holds lots of promise, but it is not infinitely powerful.
The (exaggerated) claims you've heard are probably based on the most famous quantum computing algorithm, Shor's algorithm. This is a method for using a quantum computer to factor integers into prime numbers. As it turns out, many encryption schemes rely on the fact that factoring large numbers is very hard. Messages can be encrypted fairly easily in such a way that only someone who knows the prime factorization of a particular number can decrypt them with any reasonable amount of effort. If you could quickly factor large numbers, you would break many present-day encryption schemes.
However, there are other techniques that are not immediately threatened by quantum computers. If nothing else, you can always use a one-time pad as long as the message itself. This is mathematically unbreakable, since any message can be "decrypted" from the encrypted one with the appropriate guess at the key, so there is no way for an eavesdropper to know the real message.
Quantum computation may also open the doors to next-generation ways of securely transmitting information. For example, most encryption today is just that -- scrambling the message so that only the intended recipient can make sense of it. But there may be good quantum ways to physically ensure eavesdroppers cannot access the transmission in the first place.
-
$\begingroup$ so would quantum computers help eavesdroppers get the edge over encrypters or the other way around? sounds like decryption gets easier in some cases, but good encryption gets easier too. $\endgroup$ Jul 16, 2015 at 9:41
-
3$\begingroup$ For one-time pads, encryption gets both more expensive and less secure, since the pad has to be physically sent to the encryptor, who than has to ensure that it does not get read by The Bad Guys. For very large traffic streams, the pads get big, too, so there's a cost there. As long as the key remains secure, though, eavesdroppers are helpless, and quantum computers are useless. $\endgroup$ Jul 16, 2015 at 15:15
-
1$\begingroup$ But in many cases eavesdropping is not the problem. E.g. say I have a file on my hard disk which I don't want anyone to read, even if they steal the machine. $\endgroup$– jamesqfJul 16, 2015 at 21:58
-
2$\begingroup$ @innisfree Quantum mechanics helps encrypters more than eavesdroppers, since Quantum Key Distribution makes one-time pads viable over an insecure channel. Current systems are designed in such a way that any eavesdropper would cause a wavefunction collapse, destroying the OTP in the process. Also note that Shor's algorithm is largely a theoretical vulnerability (at time of writing, the biggest number that has been factored is 56153), whereas these QKD systems are in use today. $\endgroup$ Jul 17, 2015 at 15:24
$\begingroup$
$\endgroup$
1
There is actually an entire complexity class devoted to the answer, which is "no, it cannot break any code." The class is known as BQP, or "bounded error quantum polynomial time." It is the class of decision problems which can be solved by a quantum computer in polynomial time, with no more than a 1/3 error margin (this error term is accounted for in a classical computation step which occurs after most quantum algorithms to verify that results are correct).
BQP is believed to have the following relations with other complexities:
- Contains P (Polynomial Time)
- Intersects, but probably does not fully contain NP (Nondeterministic Polynomial time)
- Probably does not contain NP-complete (as a corollary)
- Subset of PSPACE (Problems that are solvable with polynomial space requirements)
(The major unknown in that list is that it is not yet known if P=NP. The list assumes P!=NP, but if P=NP, clearly NP and NP-complete would also be part of BQP. We also don't know if NP=BQP or not. so much left to discover!)
RSA is crackable using quantum computers because the task of factoring large composite numbers is in BQP, as demonstrated by Shor's algorithm. Shor's algorithm is NP (but not NP-complete). There are other NP algorithms which are believed to be outside of BQP which can be used for encryption (The accepted answer links to lattice based cryptography, which is one such class of algorithms).
answered Jul 16, 2015 at 12:43
-
$\begingroup$ "The only unknown in that list is that it is not yet known if P=NP." -- The exact relation of NP and BQP is also unknown. $\endgroup$ Jul 16, 2015 at 14:20
$\begingroup$
$\endgroup$
2
The answers so far have focused on public-key encryption, in which someone publishes a public key which can be used to encrypt messages to them, and which is not secret. Quantum computers are known to be efficient at breaking several of the problems most commonly used as the basis of public-key cryptography. It does not affect all public-key cryptography, just the most popular schemes; it does affect the most popular schemes.
However, there is more to encryption than public-key. Symmetric encryption schemes, where the two parties share a secret key, is believed to be subject to no more than a quadratic speedup with quantum computers (quantum computers can achieve a quadratic speedup for general search problems, but no more). This corresponds to effectively halving the key length. Unlike the common public-key systems, effectively halving the key length is extremely easy to respond to: you can just double your key lengths and carry on. Symmetric encryption is extremely common; even where public-key encryption is used, it's most often just used to exchange a key for symmetric encryption.
The most common symmetric system, AES, has a 256-bit key variant that provides 128 bits of security against quantum computers. Other schemes in development support 512-bit keys, which would provide 256 bits of effective security. Both 128 and 256 bits are believed to be secure for the forseeable future.
Likewise, cryptographic hash functions are believed to hold up very well against quantum computers. There's the same Grover's algorithm-based attack, but like with encryption functions it is easy to counter.
So, any claims that cryptography become meaningless are totally off-base, because the only thing that is seriously affected are public-key systems. Public-key systems are important, but cryptography is a much broader field.
-
2$\begingroup$ And this answer is precisely why I feel this question is off-topic here: there's not a drop of physics here (something we expect is in every answer). $\endgroup$ Jul 16, 2015 at 15:51
-
$\begingroup$ @KyleKanos: There is a drop of physics here, in Grover‘s algorithm, which had enough physics in 1997 to be published in Phys. Rev. Lett. ($$) (arXiv version) . I admit, it’s just a drop of physics, but knowing whether it’s physics or computer science is a common (and frustrating) problem with quantum information. $\endgroup$ Dec 2, 2016 at 16:28
$\begingroup$
$\endgroup$
No. There can exist no X computer that can break any cipher because the one time pad is a cipher and one time pad cannot be broken by algorithm (trivial proof in information theory).
$\begingroup$
$\endgroup$
1
I would like to add that quantum computers can not break any existing code because their logical gates can perform the very same operations as classical logical gates can. They add new possibilities while keeping those formerly possible in classical computers.
Since programms, at the core, work on logical gates, it is reasonable to assume that any existing code for classical computers can work on a quantum computer.
See also quantum gate on wikipedia.
-
2$\begingroup$ This makes no sense. How does saying that a quantum computer can do everything a classical computer can, rule out the possibility that quantum computers could crack codes? Especially given that classical computers can crack codes, just not necessarily in a feasible amount of time. Your argument is like saying, "Forklifts can't lift 20kg because they can lift anything a human being can." It's wrong twice: humans can lift 20kg and, even if they couldn't, the forklift can do more. $\endgroup$ Jul 16, 2015 at 20:06
$\begingroup$
$\endgroup$
7
Ok - theoretically a quantum-computer could work like this:
You can start a normal computation and calculate it in parallel for all possible input keys. Which means decrypting an encrypted text with the right key takes just as long as decrypting it with every possible key (with a fixed length). This would mean that all traditional encryption methods like AES etc. could be cracked as fast as they could be decrypted by the holder of the legal key.
The tricky part (where the one time pad excels) is how to know if the resulting message you got from decrypting is actually the right text. For example I send the Message OK to you encrypted with AES 256bit. Now there are 2^256 possible keys to decrypt this message with and all of them will result in some result. Many maybe in something like #§ or other cryptic byte symbols, but some keys might lead to two letters "WB" and some combination might even lead to "NO".
So the difficult part is then to find out, which is the correct message! Because the (theoretical) quantum computer will in the end only output a few results with high propability - so you have to code a check, which will discern if the output is acutally a valid text. If the text is a lot bigger than the key and something like plain english, or better a standard-format which can be checked for integrity this could be possible. But if there are several possible outcomes which look valid, a human will have to sort them through so in the case of a onetime-pad cracking the code is just as good as simply guessing out of the blue. Other encryption-schemes might have to be adapted to produce valid-looking messages for false keys, but this seems possible...
--
This would only work if an actual quantum computer could work like this. As far as I know we have no hard evidence for a qc actually working like this. So maybe it simply can't be done and we don't even have a problem ;-)
-
9$\begingroup$ This isn't how quantum computers work. The belief that they can is so common that Dr. Aaronson has an entire section of his blog devoted to this misconception: Speaking Truth to Parallelism. They do give speedups for some problems, but not nearly as many as that would suggest. (Basically, we don't think that BQP = PSPACE.) $\endgroup$– CharlesJul 16, 2015 at 13:21
-
$\begingroup$ There are a lot of articles in that category, while it is true that memresistors or similar technologies suffer from several problems (like encoding the output) a quantum computer could fundamentally resolve a complex problem with a high probability. And if you can tweak the probability high enough, so you are 99.99% accurate with a few runs that is practically good enough and could solve the mentioned problems, if someone could construct such a QC $\endgroup$– FalcoJul 16, 2015 at 13:39
-
4$\begingroup$ The fundamental issue is that quantum computers don't let you compute all possible inputs in parallel: quantum computing isn't nondetermanism. $\endgroup$– CharlesJul 16, 2015 at 14:11
-
1$\begingroup$ What you're describing is a nondeterministic computer (the "N" in "NP"). While we don't know for sure that quantum computers aren't equivalent to nondeterministic ones (we don't even know that $P\ne NP$), we're pretty much certain that they are not. $\endgroup$– cpastJul 16, 2015 at 15:49
-
2$\begingroup$ -1 This answer is stating that BQP = NP, which is widely believed to be false. Using Grover's Algorthm, quantum computers can speed up brute-force searches by a square-root factor, which means you could brute-force a 256-bit AES key in only 2^128 operations. But that is still exponential complexity. $\endgroup$ Jul 16, 2015 at 15:52