Slashdot Mirror
Scientific American on Quantum Encryption
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.""
The printer-friendly version puts it all on one nice and image free page.
Article here
Because you could implement Shor's factorization algorithm.
Quantum computing provides an algorithm (Shor's), utilizing quantum mechanical manipulations, which factors numbers exponentially faster. Thus, factoring and checking factors takes the same amount of time.
This leads to the undesirable conclusion that encryption and decryption (by an intercepting 3rd party) of a signal take the same amount of time (up to a polynomial equivalence). In other words, the encryption is breakable, since the interceptor need only invest roughly the same amount of computational effort as the sender in order to crack the message.
That is why the creation of a quantum computer would "obsolete" present encryption. The point of quantum encryption is that it is not vulnerable to such attacks.
Quantum encryption is a misnomer, it should be called (and is, in some circles) quantum key distribution. It's all about how the key is transmitted, not how the data is secured. The encryption method is independant of how the key is distributed. Contrary to popular belief, it typically cannot be a one-time pad, since the bandwidth on the "key" channel is very limited due to the exact nature of the transmission. It can be, though, a constantly shifting AES key, or other type of data, making the datastream as a whole effectively unbreakable.
The problem lies in that you have to have a single, unbroken fiber optic connection between the two points, and this fiber optic connection is very limited in the amount of loss that it can withstand. That means you're geographically limited on how far the circuit might be able to travel. You're looking at a few hundred kilometers, at the absolute maximum.
Considering the amount of money you'd spend on putting the circuit in place versus the amount of money you'd lose if the data was compromised, it's very unlikely that anyone, anywhere will have a practical use for QKD/QE. Government and defense, maybe, but then only in very limited applications.
There is a chance that, should quantum computing become a reality and modern encryption algorithms can suddenly be cracked very, very easily that this method may see some use, and by no means is development a waste of time and effort. But, QC is still very much in the early stages, if a working system is ever developed at all.
Thta being said, PKI and courier delivery of key material will continue to be the order of the day for quite some time.
give it a shot.
Particles that are treated best by quantum theory (such as photons, here) exhibit quantum states. Just think of them as metainformation about the particle, which is accurate to a first approximation and appropriate for this explanation. In this case, the light is polarized, which dictates some of its quantum metainformation.
The Heisenberg principle, which you've probably heard about, says that you cannot know the position and momentum of a particle exactly, simultaneously. You can know one or the other exactly, you can know both with noninfinitesimal error, but you can't know both. For big, heavy things, like macroscopic objects, the uncertainty is so small as to be irrelevant.
The quantum weirdness which results is as follows: an unobserved object simultaneously exists in a linear combination of multiple quantum states. That is, it exists as
(x*A+y*B+z*C)/(x+y+z)
Where A,B,C are quantum states and x,y,z are relative probabilities. If they add to 1, the x+y+z term falls out.
This is where schrodinger's cat. If you wait exactly long enough that the probability of the cat dying is 50%, the cat is exactly equal parts dead and alive. It's accurate, but I think it's confusing because it confuses the fact that quantum states really only apply to very small things, except in isolated cases like this.
Where the unbreakability of quantum encryption comes in is the observer. If you open the box, the cat is no longer both, it's just dead or alive. If you look at the photon, it's A,B, or C. You have destroyed the metainformation contained in the photon, because up until when you observed it, it was x parts A, y parts B, and z parts C.
This is unavoidable and fundamental to quantum mechanics.
For quantum encryption/communication not to work this way, we have to be wrong about quantum mechanics, and the fact that it's just so WEIRD is part of the reason I suspect it will work. It's so counterintuitive people have verified this many times.
"A language that doesn't affect the way you think about programming, is not worth knowing" - Alan Perlis
Alice sends Bob a stream of photons. Each photon that is sent, Alice encodes a state of '1' or '0' on each photon.
Unfortunately, Due to Quantum Mechanics, Bob only has a 50% chance of actually reading the state of the photon. 50% of the time he gets '0' or '1', and 50% of the time he gets 'Unknown', and the photon is destroyed..
This is ok, because after receiving 1 million bits, Bob phones up Alice on an unsecured line and says I managed to read photon numbers 5,6,9,12,13,16....(+ approx 500,000 more), so I will use the state of these photons as a one time pad. Alice looks up the states she sent these photons, and now both parties have a one time pad to encrypt data.
Now, lets say there was an intruder attempting to intercept the key exchange. The intruder is also constrained QM, and can only read 50% of the photons, with the other 50% Destroyed. Because, the 50% of photons the intruder would receive, would be different to the 50% bob had read, it is impossible for the hacker to use the information sent using by bob to Alice, via the unsecured phone call, to build an equivalent one time pad.
Also, as the intruder is only able to forward a exact copy of just 50% of the photons to Bob, with the other 50%, now destroyed. He could replace this 50% of photons with his own set of random state photons, but this will be detected by Bob and Alice, as the one time pads would be different on this 50%, and the transmitted data using the pads would be corrupted.
If you have a quantum byte, i.e. 8 quantum bits, you can load it with 256 different integers simultaneously. You can do a single computation on the byte, and this computation is done simultaneously on all the 256 integers. This can easily be emulated, with 256 computers, as you suggest.
But, if you have a quantum computer with 256 quantum bits, you can do computations simultaneously on 2**256 integers. That's not easy to emulate with classical computers because we don't have enough of them.
The main problem with constructing algorithms for quantum computers is to read the result. When you read the 256-bits you only get a single number among the 2**256 which are stored there. Each of 2**256 integers has a probability associated with it, what you read is governed by this probability. Once you read, the state of the computer collapses to what you read, all the other information is lost.
Shor's algorithm solves this by ensuring that the result is periodic, the period being the solution to the problem. It then performs a Fourier transform on the state. Then reads it and gets the period with high probability.
Quantum entanglment cannot be used to send information faster than light, as explained here