Scientific American on Quantum Encryption 374
prostoalex writes "Scientific American claims that advances in commercially available quantum encryption might obsolete the existing factorization-based solutions: "The National Security Agency or one of the Federal Reserve banks can now buy a quantum-cryptographic system from two small companies - and more products are on the way. This new method of encryption represents the first major commercial implementation for what has become known as quantum information science, which blends quantum mechanics and information theory. The ultimate technology to emerge from the field may be a quantum computer so powerful that the only way to protect against its prodigious code-breaking capability may be to deploy quantum-cryptographic techniques.""
Re:Quantum Encryption (Score:5, Insightful)
Well, you think wrong. Quantum encryption cannot be 'brute-forced'. Because it's not 'encryption' in the conventional sense but rather 'secure transmission'. The data is not encoded, but rather transmitted in a way which makes eavesdropping impossible. Since you can't intercept any 'coded message', there is nothing for you to brute-force.
And this holds as long as what we know of quantum mechanics holds.
(More specifically, the Bell inequality [ucr.edu]. Which was verified in the famous Aspect experiment.)
So no, nothing in quantum physics is going to invalidate quantum encryption. And I wouldn't get my hopes up for future theories, either, because this 'wierdness' of quantum mechanics so well-verified experimentally that it'd be unlikely that any future theory would change it. (But hopefully explain it)
Ridiculously overblown (Score:1, Insightful)
It's like replacing a steel deadbolt with titanium, meanwhile the door is wooden, the hinges are brass, and there's a large window right next to it.
The only possible uses are extremely high-value applications like banking and the military. Even then I'd spend my money elsewhere.
The breaking RSA stuff is unrelated (quantum computers, not quantum key exchange) and pure speculation. RSA isn't going away for a loooong time.
Re:Don't verb adjectives (Score:5, Insightful)
OK, there's two very different uses of quantum technology when applied to crypto problems:
1. If you had a quantum computer some problems like factorization become easy; therefore things like RSA would be instantly decryptable. The gotcha is that the current "state of the art" for quantum computers are still absolutely tiny and there are HUGE engineering challenges towards building one large enough to factor a real key (I think they're at the point now where they can factor numbers like "12"... so they have a bit of scaling before they can start attacking 300-digit numbers)
Of course there could be a massive breakthrough in quantum computer design tomorrow which would throw the whole crypto world on its head. That makes this area really interesting for crypto people.
Does NSA secretly have a quantum computer that can do that? I'd say its extremely unlikely... I'm sure they have people looking into it but they would have to be AMAZINGLY far ahead of the public research community to have actually built a full-size one.
2. What this article is talking about is "quantum encryption" what's really "quantum" about it is making an untappable fiber line by signalling using the characteristics of single photons. By using Heisenberg's uncertainty principal you can make it impossible for anyone to tap the line (and thus observe the photon states) without also randomizing the bits. It's really hard to get your head around but it actually works.
Note that nowhere here did we use a "quantum computer"... this is all using technology that exists today (obviously, since you can buy it)
So basically even if your adversary has a trillion dollar budget to attack you with they CANNOT tap that fiber line without destroying the communication in the process. It's physically not possible with any technology.
So unless the NSA has a whole undiscovered field of physics that the world doesn't know about they don't have "quantum decyption" As we understand physics today it's literally impossible to build such a device.
Re:TFA is quite ..umm.. cryptic (Score:4, Insightful)
Who said using it on current networks? In real life, custom networks are used, of course.
Sending information faster than light is likely not possible. The FAQ you linked to says that too. Currently, theory says no, and experiment can't tell. Some have chosen to interpret their experiments as supporting FTL transmission of information. But the majority do not agree with that interpretation.
Using photons in computers in any form is so far off that suggesting it as a solution to current day problems like die size vs clock speed is ridiculous.
Re:Ridiculously overblown (Score:4, Insightful)
Quantum encryption is not about exchanging keys, its not even encryption in its normal sense. What it really is, is secure trasmission.
Secure meaning, nobody can read this data during transmission other than the reciever without it being physically impossible to notice.
Re:I don't know if I can make this clear, but I'll (Score:2, Insightful)
At any given moment, a quantum particle is having its wave equation collapsed by an interaction with another particle. The key to understanding this is that even though the wave has collapsed, it is not really collapsed and will continue to transmit and collapse.
It is a HUGE misconception that the cat is equally alive or dead, being as those are two fundamentally mutually exclusive properties. At any given point in time, there is a probability that the cat is either alive or dead. The cat interacts with itself (a single quantum particle would not interact with itself and so it cannot collapse its own wave equation) and with the air molecules, box molecules, etc. Whether or not YOU look at the cat or not is irrelevant. The cat interacts with its environment and other particles simply by the means of being.
Once you stop trying to think that an observer must be a sentient being with intent to measure a particle, you can see that the particle itself is interacting with other particles, each acting as observers of the other.
Re:Uhh... (Score:5, Insightful)
However, it is perfectly reasonable to borrow a large sieve with a water tray - which both work on all the grains simultaneously - and then the job becomes doable in hours.
Re:Baloney. (Score:5, Insightful)
Ultimately cryptographers want some form of quantum repeater--in essence, an elementary form of quantum computer that would overcome distance limitations. A repeater would work through what Albert Einstein famously called "spukhafte Fernwirkungen," spooky action at a distance. Anton Zeilinger and his colleagues at the Institute of Experimental Physics in Vienna, Austria, took an early step toward a repeater when they reported in the August 19, 2004, issue of Nature that their group had strung an optical-fiber cable in a sewer tunnel under the Danube River and stationed an "entangled" photon at each end. The measurement of the state of polarization in one photon (horizontal, vertical, and so on) establishes immediately an identical polarization that can be measured in the other.
And it continues on this page http://www.sciam.com/article.cfm?chanID=sa006&arti cleID=000479CD-F58C-11BE-AD0683414B7F0000&pageNumb er=3&catID=2
Re:TFA is quite ..umm.. cryptic (Score:1, Insightful)
The parent gives the impression that FTL communication is possible while the FAQ and the reply both say that isn't true.
Re:Ridiculously overblown (Score:2, Insightful)
Currently QC
a) is only good for point-to-point links. (Photonic switches would likely break the entanglement)
b) is just exchanging symmetric keys for use on a secondary channel
Now, even if we develop repeaters that decode and re-encode the symmetric key and perform routing, unless you're willing to trust the phone company's repeaters (the Chinese factory where they will likely be built, the code they are running, the administrators managing them, the physical integrity where the repeaters are located, and the ethics of the company directors preventing industrial espionage on competitors), you're still back to square one. If you need to run point to point lines, then you might as well ship a 200GB drive full of symmetric keys or a striped multi-Terabyte one-time pad. It will be a lot cheaper than running new fiber without the distance limitation and by the time this is necessary, 200GB will probably fit on a USBv4 key).
On the other hand, the grandparent is incorrect that breaking RSA via Quantum Computing is unrelated. The only reason why you would bother going to this is because you expect that factoring could be done in O(f(n bits)) - where f(n) is less than exponential - with Quantum Computers. I haven't heard any indication that quantum computers could be used to break symmetric cyphers.
Re:Uhh... (Score:1, Insightful)
So it seems encrypting your message with even a really weak encryption algorithm before encrypting it with a strong one would help a lot. Is that true?
Or, as an extention on that technique, I always wondered why people don't simply chain _all_ the candidates for AES instead of just picking the one algorithm that won. Seems if they did that, then if any algorithm was sound, you'd win.
Re:Uhh... (Score:3, Insightful)
In effect you go back to square one. To simulate N qbits roughly your quantum computer simulator must have the capacity to completely explore 2^N states. It quickly becomes unmanageable, and you revert to the original problem.
Equivalently you can say that if you have the traditional computing power to solve the problems that a given quantum computer would be able to solve easily, then you approximately have the capacity to simulate this quantum computer (give or take an order of magnitude perhaps).
Your approach wouldn't work. Perhaps a given fast computer would, say, be able to simulate 7 qbits. Then 2 such computers would only be able to simulate 8 qbits, not 14 ; a thousand such computers would only be able to simulate 17 qbits, and so on.
BTW, some people say that the reason why we haven't been able to produce a strong AI yet is that some quantum effects happen in the brain. Roger Penrose in particular is a big proponent of this idea.
On the other hand some AI people say that the only reasons why we haven't got strong AI yet is (a) we don't really know how the brain works yet, and (b) we need more computing capacity. More research is needed for (a), and Penrose would agree with this, but eventually we'll have all the computing capacity we need.
However if thought is based on quantum processes then we might require quantum computers to simulate it, who knows. This could mean that strong AI is some years away.
Re:Don't verb adjectives (Score:1, Insightful)
Furthermore, even though Shor's algorithm can factor in roughly linear time, it still has a work factor present. You may have to run the quantum Fourier transform multiple times before you get an acceptable discrete log to finish the equation with, thanks to the joys of trying to extract a single value from a superposition.
And yes, IBM made a 7-qubit NMR-based QC a while ago and tested Shor's algorithm on it, factoring 15 into 3 and 5. NMR QCs are not currently scalable though, which prompted some scientists to prematurely declare quantum computing as a dead end.
Re:Easy explination of Quantum Encryption.... (Score:2, Insightful)
I've said it a million times, and I guess I have to say a million times more: Quantum crypto doesn't protect against an active Monkey-in-the-middle attack! And thus it is not the perfect uncrackable holy grail everybody is so hyped up about.
Nothing to see here, move along...
--Blerik
Re:Don't verb adjectives (Score:2, Insightful)
Re:Don't verb adjectives (Score:2, Insightful)
No, what he's attempting to do is describe entanglement - the presently baffling feature of quantum mechanices. As Heisenberg would tell you, any attempt to measure the state of a photon (an entangled pair of a photon in this case) will in fact alter the state of the photon itself and consequently sound an alarm bell if the data (many photons!) is corrupt at the other end. However, a sub-atomic group in Paris - ENS- have made progress in findinf ways to not measure the magnitude of a photon, but rather measure the phase shift of tiny rubidium rods as they pass through a photon. This still makes a change of course but a change that is even more difficult to detect! It's fascinating stuff and arguably the future of communication and computing, and who knows even replication...
Re:Don't verb adjectives (Score:5, Insightful)
So, you could send a key to the other end, but it wouldn't be the same key that you received, because the key is created during the exchange based on which photons were encoded in the same orientation they were measured. So, any protocol that uses this has to be designed to take advantage of this property to prevent man-in-the-middle attacks. Apparently the crypto boys and girls feel this is enough of an advantage to be done--I haven't inspected any protocols that do this, so I can't explain how it's achieved. But simply sending a long key and XORing the message with it isn't enough--the man in the middle could foil that by just generating a new key and reencrypting.
I'm sure someone has a good discussion of this up on the web. The question is if there's one that's accessible to the non-cryptographer.
Question (Score:3, Insightful)
Re:Ridiculously overblown (Score:3, Insightful)
There is no relation between quantum "encryption" and RSA. Quantum computers are a completely different technology than quantum key distribution. All you need for the latter is fiber optic cable, some photon counters, and polarizing filters. Quantum computers OTOH require quantum circuits, which are no more than lab toys ATM. It could be 50 years before we see sizable quantum computers, if ever.
Even if QCs do arrive, that doesn't mean quantum key distribution will take off as well. As you said, it will be a whole lot cheaper and just as effective to ship a storage device full of symmetric keys to whoever you're communicating with. RSA and quantum encryption are independent technologies; the downfall of one will not necessarily lead to the rise of the other.