|
"Normal"
Encryption
The most common encryption
we use today is an asymmetric cipher known as RSA (Rivest, Shamir,
Adleman). It is asymmetric because it relies on a special one-way
function that makes it easy to encrypt something but difficult to
decode it. The heart of the RSA system depends on the properties
of prime factors (numbers that can only be divided by themselves
and 1, such as 5, 7, 13, and 17) for security. It is very easy to
multiply two primes together, yet difficult to factor them. (see
the example in What Good
is a Qubit?)
The security of the RSA
encryption system relies on the fact that it is difficult to factor
numbers, especially large numbers with prime factors.
According to William Crowell, Deputy
Director of the NSA, "If all the personal computers in
the world—approximately 260 million computers—were to be put to work
on a single PGP encrypted message, it would take on average
an estimated 12 million times the age of the universe to break a
single message." (Singh 317)
(PGP—Pretty Good Privacy—uses the RSA encryption system, but the
difference is that it is a compromise between total
security and usability. PGP, however, was designed for the general public and
is a user-friendly version that can run on ordinary computers.
(Singh 317, 298))
Back
to the top.
What's Wrong
With It?
The fact that today's
encryption relies on a lack of number crunching power means that
foundations of RSA aren’t solid. It has never been proven that there
are no easier ways to factor numbers. So if a method is discovered,
RSA is obsolete. (Of course, for you paranoid nuts, there is no
guarantee that the government hasn’t already discovered a
method…)
But because the encryption
used today can theoretically be broken, given enough time and computational
power, it is vulnerable. If and when a useable quantum computer
is built, the strongest encryption we use today will become obsolete.
Exploiting a theory of quantum mechanics which says that a particle
exists in all possible different states until observed, a quantum
computer could execute many different calculations simultaneously—calculations
a traditional computer would have to execute one at a time. (see
Quantum Computers)
This use of quantum mechanics
gives a quantum computer unimaginable power, and it will be able
to break any types of encryption which solely rely on our lack of
number-crunching computational power. If we are to use quantum computers
in the future, other methods of encryption must be developed. (Singh 331)
Back
to the top.
Polarization
To understand quantum
cryptography, you must understand polarization.
Light can be described
as an electric field vibrating perpendicularly to a magnetic field.
In normal light, the electric field can be oriented in any direction
you can think of. In polarized light, all the photons’ electric
fields are oriented the same direction. Check out the Animated
Lightwave Illustration to see an example of a polarized light
wave in action.
The filter (blue here) doesn't let the horizontally polarized
photons (red) through, but does let the vertically polarized
photons through (yellow). |
A Polaroid filter can
be used to polarize light. It works by letting only photons polarized
in a certain direction through, while absorbing all the photons
polarized perpendicularly to the filter.
For instance, a vertical
Polaroid filter would let all photons with a vertical polarization
pass through it, but would block all photons with a horizontal polarization.
But what happens to the
photons with diagonal polarizations? Half would be let through the
vertical Polaroid filter and would be changed into vertically polarized
photons. The other half would be blocked by the filter. Therefore,
all the photons that come out of the vertical Polaroid filter are
vertically polarized.
(To simply issues, we
will assume that there are just 4 directions-  standing for vertically
polarized photons,
 for horizontal polarization,  and 
for diagonally polarized photons)
| Photon |
Description |
|
Horizontally polarized photon |
|
Vertically polarized photon |
|
Diagonally polarized photon |
|
Diagonally polarized photon |
Back
to the top.
What
Polarization has to do with Quantum Cryptography
How does this relate
to quantum cryptography?
Say
Alice wants to send Bob an encrypted message.
They will use the "one-time pad," a method of encrption
which uses a secret, random key to encrypt messages. The
one-time pad is unbreakable, even theoretically, but it was not practical
becuase of the difficulty of transferring a secure key.
This is the paradoxical problem: how does Alice send Bob a secret key
before they have set up a system of encryption?
Quantum
mechanics solves the problem of getting a perfectly secure key from one
person to another.
In the 1980’s, computer
scientist Giles Brassard and researcher Charles Bennett devised a
system that would use photons of different polarizations
to transmit a secret binary key which would consist of
a random series of bits. (A binary message is made up of a
series of 1’s and 0’s called bits, the format in which computers
ultimately store data.) (Singh 339)
Their system was set up in the following way. Say Alice wants to
send Bob a secret, random series of bits (1's and 0's) which
will eventually become their encryption key. Each 1 or 0 can be
represented by a photon of a certain polarization. There are two
schemes Alice can choose from to represent these 1’s and 0’s.
The first scheme is called
rectilinear, or +-scheme. In this scheme, a vertically polarized
photon, or ,
stands for 1, and the horizontally polarized photon,
,
stands for 0. The second scheme is called the diagonal, or
x-scheme. In this scheme, one diagonally polarized photon, ,
stands for 0, while the other diagonally polarized photon, ,
stands for 1.
If Alice wants to send
a binary message 00101101, she could transmit it in the following
way, switching between the two schemes randomly.
| Message: |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
| Scheme: |
X |
+ |
+ |
X |
+ |
X |
+ |
+ |
| Transmission:
|
|
|
|
|
|
|
|
|
Note that the first two
digits that she is sending are zeros. The first one, using the x-scheme,
is transmitted as a . The second one, using the +-scheme, is
transmitted as
.
Now remember that when
a photon polarized diagonally () hits a vertical filter, it
has 50% chance of going through. If it does, it will come out polarized
vertically. But there is no way to know whether it was originally
vertically or diagonally polarized.
Conversely, a photon
of unknown polarization that doesn’t go through a vertical filter
isn’t necessarily a horizontally polarized photon. It could be a
diagonally polarized photon.
Say Eve wants to intercept
and decode the message. The only way Eve can find out anything about
the polarizations of the photons is by measuring them. She uses
a Polaroid filter to do this. However, she doesn’t know what scheme
Alice will be using for each photon, and there is no way for Eve
to know whether she is using a filter from the right scheme. Say
Eve tries to decode the first photon of Alice’s transmission.
Eve picks a vertical
filter from the +-scheme, but Alice has sent a photon using the
x-scheme. When Eve tries to measure the with her vertical filter,
the photon has a fifty percent chance of going through. Whether
or not the photon does goes through Eve’s filter, she will not know
whether the scheme she picked was correct.
If it the does go
through the vertical filter, it will appear to be a photon,
which she interprets as a 1, while in reality Alice has sent a 0.
Eve cannot know whether she picked the right scheme, and thus whether
her assumption is correct. If she uses a filter from the wrong scheme,
her answer is meaningless. Even if she does pick the right scheme
by chance, she has no way of knowing whether she did indeed pick
the correct scheme and thus whether her answer is meaningful or
not.
The problem is, Bob is
in exactly the same position as Eve. Although he is the intended
receiver of the code, he doesn’t know what schemes Alice has used
for each photon either. So he choses a filter from either scheme
at random, and measures the photons.
But wait! He doesn’t
know whether he’s got the right scheme or not!
Absolutely. But the beautiful
part is that by chance, he will have chosen the correct scheme at
least part of the time. Alice calls Bob up on an ordinary telephone
line and tells him which schemes she's used
for each photon. But she doesn’t say what the actual
polarization of the photon she sent was.
Now Bob tells Alice which photons he's measured with
the correct scheme. So they throw out the photons for which
Bob picked the wrong scheme, and only keep the ones he got right.
Remember, each different polarization stands for either a 0 or a
1, so they both have secret identical strings of 1’s and 0’s. So
they have succeeded transferring a secret, perfectly secure key
which they can use to encrypt messages.
But what about Eve?
If Eve had only eavesdropped
on the telephone conversation, she wouldn’t know a single useful
thing because neither Alice nor Bob mentions the actual polarization
of the photons, and thus whether the numbers were 0’s or 1’s. They
only say what schemes they used and not what the actual polarizations
of the photons were.
But Eve did give
a try at intercepting the photons that Alice sent to Bob. Say she
finds out that she did pick the right scheme, and thus knows whether
the photon represented a 0 or 1. But if Bob didn’t pick the right scheme,
Alice and Bob throw that photon out. So in this case Eve’s knowledge is useless.
If she
picked the wrong scheme, then her answer is useless
because—remember—there is no way that she can deduce the original polarization
of the photon from her measurement.
But it is probable
that, by chance, both Bob and Eve would've picked the same, correct scheme for a few of the photons. So
won’t Eve have part of the code that Alice and Bob are using?
Yes, but it won’t matter
if she has only part of the key; she doesn’t have the whole key.
But even then, that doesn’t matter anyway, because Alice and Bob
will be able to detect whether Eve has been eavesdropping, and will
throw out the key.
In the process of
picking the filters, Eve will inevitably pick the wrong scheme or a
filter of a different orientation as the polarization of the photon.
That sounds really complicated, but basically it means that she
will change the message. There are many ways in which Eve can alter
the message.
Way #1 to mess up: She
can pick the wrong scheme to measure the photon. Remember, if she
picks a scheme different than the scheme Alice uses, regardless
of which filter she picks, there is a fifty percent chance that
the photon will be absorbed and a fifty percent chance that it will
come through, but with a different polarization. So Eve has changed
the message.
Way #2 to mess up: Eve
picks the right scheme, but a filter of a different orientation
than the polarization of the photon. Basically, the filter will
absorb/block the photon and it will never reach Bob. In any case,
Eve has tampered with the message.
There are many variations
on the ways Eve can change the message, but basically, she has four
filters to chose from, and if she doesn’t pick the right
one, the photon will be blocked or its polarization will be changed.
It’s relatively easy
for Alice and Bob to see if Eve has been eavesdropping. Eve will
inevitably, by intercepting and measuring the photons, have changed
the message. Alice and Bob can simply pick a few of the photons,
call each other up, and check whether their numbers were identical.
Then they just throw out those numbers because they have been spoken
over an unsecured line. There is no need for them to check all their
numbers. If they check just 75, the chances are less than one in
a billion that Eve could have eavesdropped without affecting any
of the 75.
If Alice and Bob find
out they’ve been eavesdropped on, they must throw out the key because
it will have errors. Even if they didn't discard the key, the probability of Eve
having whole key is infinitesimally small.
So Alice and Bob try again until they
finally get a secure and correct key.
Back
to the top.
So Bob and Alice have gone to all this trouble to create and transmit a perfectly random, perfectly secure key. What am they supposed to do with it?
They are going to use it in a one-time pad cipher, a method of encryption developed at the end of World War I. The flawed, but much more useable Enigma encryption of World War II was derived from the one-time pad cipher.
The one-time pad cipher was based on the Vignere cipher, whose security rested on the fact it used a different alphabet to encode each letter. The key was used to decide which alphabet should be used to encode what letter. The one-time pad cipher functions identically to the Vignere cipher, but the difference is in the key.
In the one-time pad cipher, the key must be as long as the message itself, totally random, and used only once. Because of this randomness, there are no patterns for a cryptanalyst to find, and thus crack, the key. This method of encryption has been mathematically proven to be totally secure. It was not often used in the past because of the difficulty in making a large number of completely random keys, giving a copy to every sender and receiver, and making sure the enemy didn't get a hold of the book of keys, which would compromise the whole system.
So all of Bob and Alice's effort was directed towards solving these problems. Quantum cryptography automatically creates a random key in the process of securely transmitting it to both sender and reciever, in such a way that eavesdropping is impossible.
Now Bob and Alice can happily send messages back and forth on any line, secure in the knowledge that no one can eavesdrop.
Back
to the top.
But
is this really practical?
The main problem is sending
the photons without having them affected by the environment. As
of 1995, researchers have used this system of quantum cryptography
to send a key 23 kilometers (14.3 miles) through an optic-fiber.
More recent experiments have succeeded in sending a key through
the air for up to one kilometer (1.6 miles). The current state of
technology is enough to secure the communications within a small
city.
As Simon Singh says,
"It is currently possible to build a quantum cryptography link
between the White House and the Pentagon. Perhaps there already
is one." (Singh 349)
Back
to the top.
1. Singh, S.
2. Barenco, A., et al
3. Deutsch, D. and Ekert, A.
|
