2
often done by trusted couriers. Recall tha t in one-time
pad, a key must be as long as a message. Sending long
keys by trusted co uriers is clearly rather inconvenient.
All conventional (classical) key distribution schemes
are fundamentally insecure because there is nothing to
prevent an eavesdropper from making a copy of the key
during the key distribution process . Indeed, trusted
couriers could be bribed or compromised. So, the users
can never be sure about the security of a key.
How may one so lve the key distribution problem?
Around 1970s, mathematicians invented public key cryp-
tography. In public key cryptography, there are two dif-
ferent sets of keys, the encryption key and the decryption
key. The encryption key can be broadcas t in public (e.g.,
published in a phone book) wherea s the decryption key
has to be kept secret. Public key cry pto graphy allows
two parties who have never met before to communicate
securely.
Unfortunately, the sec urity of public key encryption
schemes is often based on unproven computational as-
sumptions. For instance , the security of standard RSA
encryption scheme is based on the pre sumed hardness of
factoring a large composite number. Such an assump-
tion may be broken by unanticipated advances in algo-
rithms and hardware. For instance, in 1994 Peter Shor,
then at AT&T, found an efficient quantum algorithm for
factoring. [2] Therefor e , ”if a qua ntum computer is ever
built, much of conventional cryptog raphy will fall apart!”
(Gilles Brassard).
You may think, ”s ince we do not have a quantum com-
puter yet, perhaps, we should not worry ab out this prob-
lem until a quantum computer ha s been built.” Not so.
For ins tance, Canada has kept census information secret
for 92 years on average. An eavesdropper may save mes-
sages sent by you in 2007 and try to decrypt them in
2099. And, who knows whether we will have a quantum
computer by 2099 ?
II. QUANTUM KEY DISTRIBUTION
It is for tunate that quantum mechanics can also come
to the rescue. Unlike conventional cryptography, the
Holy Gr ail of quantum cryptography (code-making ) is
unconditional security, that is to say, security that is
based on the fundamental law of quantum mechanics,
namely that information gain generally implies distur-
bance on quantum states.
How does quantum key distribution work? Intuitively,
if an eavesdropper attempts to learn information abo ut
some signals sent through a quantum channel, she will
have to perform some sort of measurement on the sig nals.
Now, a measurement will generally disturb the state of
those signals. Alice and Bob can catch an eavesdropper
by sea rching for traces of this disturbance. The absence
of disturbance assures Alice and Bob tha t Eve almost
surely does not have any information about the tra ns-
mitted quantum signals.
III. BB84 PROTOCOL: T HE IDEAL CASE
The best-known quantum key distribution (QKD) pro-
tocol (BB84) was published by Bennett and Bras sard in
1984 [3], while its idea goes back to Wiesner. [4] The
basic tool are a q uantum channel connecting Alice and
Bob and a public classical channel, where Eve is a llowed
to listen passively, but not allowed to change the trans-
mitted message. For the quantum channel, we use four
signal states. For simplicity, let us for now regard the
signals as realized by single photons in the pola rization
degree of freedom. Consider two sets of orthogonal sig-
nals, o ne formed by a horizontal and a vertical polarized
photon, and the other formed by a 45-deg ree and 135-
degree polarized photon. These four polarized states are
non-orthog onal. The overlap probability between signals
from two different sets is one half. Bob has two mea-
surement devices at his hand, one in the rectilinear (i.e.,
vertical/horizontal) bas is and one in the diagonal (i.e.,
45-degree/135-degree ) basis. Notice that Bob’s two mea-
surements do not commute.
The procedure of BB84 is as follows. See Figure 1.
Alice: Signals
Bob: Bases
1
0
Sifting
1
1
1:
0:
1
0
1
1
Sifting
Outcomes
FIG. 1: S chematics of the BB84 protocol. [3]
1. Pha se I (Quantum Communication Phase)
(a) Alice sends a sequence of sig nals, each randomly
chosen from one of the above four polar iz ations.
(b) For each signal, Bob randomly chooses one of the
two measurement devices to perform a measurement.
(c) Bob confirms that he has received and measur e d
all signals.
2. Pha se II (Public Discussion Phase)
(a) Alice and Bob announce their polarization bases
for each signal. They discard all events where they use
different bases for a signal.
(b) Alice rando mly chooses a fractio n, p, of all re-
maining events as test events. For those test events, she
transmits the positions and the corresponding polariza-
tion data to Bob. Bob compar e s his polarization data
with those of Alice and tells Alice whether their po lar-
ization data for the test events agree.
(c) In case of agreement, Alice and Bob convert the po-
larization data of the remaining set of events into binary
form, e.g., they call all horizontal and 45-degree signals