Quantum Encryption

From: John Clark (jonkc@worldnet.att.net)
Date: Mon Apr 03 2000 - 21:38:10 MDT

Zero Powers <zero_powers@hotmail.com> Wrote:

>>Quantum Encryption, which has actually been used in a commercial setting
>>not just in the lab, is as secure as the laws of physics.

> *That* is news to me. Do you know where I can find out more about this
> quantum encryption?

I found an old post that I wrote on this subject and sent to the list on May 3 1996:

With a random One Time Pad you can generate a perfect encryption scheme,
even if your opponent has a computer of infinite power he can never read your
message. Despite this it has severe practical limitations, how do you
distribute the One Time Pad to the person you want to talk with? You can't
receive the pad electronically, if your electronic channel is not secure then
an eavesdropper can tap your line and get a copy of the pad, if your channel
is already secure then you don't need the pad. The only secure method is to
physically hand a disk with the pad on it to the person you want to talk to
and then hand him another one when that one gets used up. That's not practical
in most cases, certainly not for Crypto Anarchy in an economy biased on
anonymous electronic money.

Public Key Cryptography solves the key distribution problem but at a (small)
price, it is breakable in theory but probably not in practice. In a year or
two it will be expensive but possible to break a 512 bit key, a 1024 bit key
would be astronomically more difficult. Many users of PGP have a 2048 bit key,
even with Nanotechnology there is not enough matter in the observable universe
to make a machine that can break a key of that size before the heat death of
the universe, or the Omega point whichever comes first. We can be absolutely
certain that a 2048 key will never be broken.. unless..

Unless P =NP and somebody finds a way to improve existing factoring algorithms
by a lot. An improvement by a measly few hundred trillion percent would by
useless, I said a lot. This doesn't seem very likely, but there is one other

Unless Quantum Computers are possible and somebody actually manages to build
one. (Such a machine would revolutionize the world so much that breaking your
PGP key would probably be the last thing on your mind, but let's ignore that
for now.) Would this mean the end of Crypto Anarchy? No, because we can use
quantum mechanics on our side too, we can use Quantum Cryptography, and unlike
Quantum Computers we know this will work because it's already been done.
This is how:

I send you a bunch of photons, each photon is polarized in one of 4
directions, horizontal, vertical, left-diagonal and right diagonal, - | \ / .
In this example I send you 10 photons polarized as follows
| | / - - \ - | - / .

You have a polarization detector, you can set your detector to measure the
horizontal and vertical photons (+) OR you can set it to measure the
left-diagonal and right diagonal photons (x). The laws of physics do not
allow you to measure one photon both ways, because measuring one destroys
all information about the other.

You set your detector at random, let's say you set it to find rectilinear
photons and let's say you have guessed correctly and it really is a
rectilinear photon. If you can detect the photon after it passes through your
polarized material, you will correctly deduce that it is a horizontal photon.
If you can not detect a photon after it hits your polarizing material you
will correctly deduce that the photon is vertical.

What if you guessed incorrectly when you set your detector, what if you set
it to detect a rectilinear photon but I send you a diagonal polarized photon?
Then the photon will hit your polarizing material at a 45 degree angle so
there is a 50% chance the photon will get through, a 50% chance it will not.
In other words you get a random result.

I send you 10 photons polarized as follows | | / - - \ - | - /
At random you set your polarization detector as follows x + + x x x + x + +
So you might claim the photons were polarized as follows / | - \ / \ - / - |

Now you tell me over an insecure channel how you set your detector for each
photon, Big Brother is free to listen in, it won't help him. I tell you over
the same channel which settings on you polarization detector were correct, in
this example settings number 2,6,7 and 9 were correct * | * * * \ - * - *
We only use those readings and junk the others , and we agree that
horizontal and right diagonal photon means 1, and vertical and left diagonal
means 0. So we have sent the number 0011 and we can be as certain as we want
to be that there has been no eavesdropping.

An eavesdropper can not know what type of photon is being sent and just like
you must guess what direction to set his polarization detector. He will be
wrong 50% of the time and when he is he will change the polarization of the
photon and give himself away. We compare N bits in the string of numbers
sent over an insecure channel, if there are no discrepancies then there is
only one chance in 2^N that somebody is eavesdropping, so we can use the
remaining bits as a one time pad. As I said this has already been done and
messages have been sent about 35 miles in this way. I learned about this
stuff mostly from Bruce Schneir's wonderful book "Applied Cryptography".

       John K Clark jonkc@att.net

This archive was generated by hypermail 2b29 : Thu Jul 27 2000 - 14:09:02 MDT