Wednesday, October 11, 2006

Cheap quantum cryptography

Quantum information theory is a fascinating subject. By applying the simple computational rules of quantum mechanics it is often possible to process information much better than with just classical devices. A famous example being Shor's algorithm for the factorisation of integers relevant for breaking many popular public key encryption schemes such as RSA. The speed up is not exponential but "only" by a square root but this can already be substantial. Formal computer scientists amuse themselves by investigating how the many complexity classes change if you have access to some quantum computations, the Complexity Zoo gives a nice overview.

A beatiful introduction into the subject are the lecture notes by John Preskill. A more formal aspect (investigating which quantum machines can be constructed, how does the impossible quantum copier differ from possible devices and that in the language of operator algebras) is treated in the notes by Reinhard Werner.

However, all this, much like string theory, is only theory and does not have real world applications. As far as real experiments go, IBM has been able to factor 15 with a quantum computer in 2001.

Another potentially applicabel area of application is cryptography: It is possible to construct quantum channels that are immune to eavesdropping: If somebody in the middle listens in the information does not reach the intended recipient anymore. This has been demonstrated in a real experiment by Anton Zeilinger: He managed to transmit the keys of a classical encryption scheme via entangled photons (with a bitrate of 400-800bit/s and 3% error).

This still involves a considerable experimental set-up and remember: You only transmit the keys, as the quantum channel is my far too slow to transmit real data (you probably read much faster than 400bit/s). But there are cheap alternatives (not in the theoretical but in the practical sense) which are as well impossible to crack: One-time pads. Assume I have 1GB of data which I want to transmit to you securely. All I need are 1GB of random numbers which I share with you beforehand and then I xor the data with the random numbers transmit the result (which is just noise for anybody in between) and xor the encrypted message to recover the original data.

This is not elegant as we have to share the random numbers beforehand, we have to share as many bits as we want to transmit. But for many practical applications this is easily possible (headquater of some company who want to transmit construction plans to factory, a spy who wants to phone home, you name it): Cheap small harddrives have more room than all the information you would like to transmit secretly in all you life. When you construct the factory you just bring there the harddrive in a sealed box and practially all future communication is secure, the spy carries a sealed usb-stick and has more shared randomness than all the secret pictures he is goint to take and all the reports he has to send. This is not elegant but dead cheap and efficient.

And if you like you can even produce the randomness using quantum physics to make it physically safe: For example you could sample the timing of the ticks of a Geiger counter and have pure quantum randomness.

Here is a small homework: Take t1, t2,...,tN to be the times of N clicks. By themselves, they are not pure random numbers but the time difference follows a Poisson distribution. Assume that the ti are specified with B bits each, so the possible time resolution is dt and the decay constant of the probe is lambda. How many bits of pure randomness can you extract and how do you do it?


Anonymous said...

"A famous example being Shor's algorithm for the factorisation of integers relevant for breaking many popular public key encryption schemes such as RSA. The speed up is not exponential but "only" by a square root but this can already be substantial."

The speed up of Shor's algorithm is exponential, the square root speed up is that of Grover's algorithm.

Quantum cryptography is the generation of one-time pads between emitter and receiver, the superiority of this scheme on classical one-time pads is that in the classical case the key could have been copied without your knowledge.

Robert said...

I stand corrected.

Regarding copying the key: That's why I mentioned to "seal" the hard disk. Even in the quantum version, eventually the RSA keys have to be extracted in classical form and then are prone to copying. For practical purposes I thing it would be possible to take a hard disk from Bremen to New York say knowing that nobody had access to the data on it.

Anonymous said...

From your link to wikipedia:
"Shor's algorithm is a quantum algorithm for factoring a number N in O((log N)^3) time", that is the time needed to factoring a number N grows as the cube of the number of its digits.

So if the speed up of the Shor's algorithm were a square root then this would imply that classical algorithms factorize a number N in a time that grows like O((log N)^6), but in the same article of wikipedia: "no classical algorithm is known that can factor in time O((log N)^k) for any k".

So the speed up of Shor's algorithm is exponential.

On the other hand I think that quantum cryptography is better than your idea of sealed hard discs. With quantum cryptography we have total control of the key from the moment in which it is generated, whereas with sealed hard discs we have to trust many intermediate people.

Finally I am not in agreement with your affirmation about quantum information theory: "...all this, much like string theory, is only theory and does not have real world applications"

Quantum information theory is not a physical theory, it is the application of quantum mechanics to data processing, and quantum mechanics is a physical theory thoroughly tested. If today we cannot construct a quantum computer it is because the technical difficulties are enormous but not because the quantum mechanics is wrong or because it is a theory without experimental support.

Unknown said...

This is really difficult to learn and study. After reading so many blog posts I am still not clear with the complete idea behind it.
e signatures