Quantum Cryptography

John K Clark (johnkc@well.com)
Sat, 28 Dec 1996 22:35:34 -0800 (PST)


On Tue, 24 Dec 1996 James Rogers <jamesr@best.com> Wrote:

>What about encryption algorithms specifically designed to be
>operated on quantum computers? The same properties that
>make quantum computers so adept at cracking codes could also
>be used to make encryption that much stronger.

Yes, even if everyone had a Quantum Computer in their pocket we could still
communicate privately because there is a way to make Cryptography as secure as
the laws of Physics, and the really amazing thing is that it's practical too.
Recently 2 banks exchanged financial information with Quantum Cryptography
through a cable under Lake Geneva. The idea is to use Quantum Cryptography to
send a One Time Pad of numbers to the person you want to talk to, the message
can be detected but NOT without you knowing it was detected. With a random
One Time Pad you can generate a perfect encryption scheme, even if to
everybody's surprise it turns out that P=NP, even if your opponent has a
quantum computer, even if your opponent has a computer of infinite power,
he can never read your message. Despite its perfect security it has severe
practical limitations, how do you distribute the One Time Pad to the person
you want to talk with? You can't send 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, what is practical is to
use Quantum Cryptography, and unlike Quantum Computers we know for sure 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 johnkc@well.com

Version: 2.6.i