. 2
( 2)

int x0 (int p, int q, int n, int t, int xt)

int a, b, u, v, w, z;

/* we already know that gcd(p, q) == 1 */
CvoidIextendedLeuclidianCp, q, &a, &b);
u = modexp ((p+1)/4, t, p-l);
v = modexp ((q+1)/4, t, q-l);
w = modexp (xt%p, u, p);
z = modexp (xt%q, v, q);
return (b*q*w + a*p*z) % n;

Once you have x0, decryption is easy. Just set up the BBS generator and XOR the out-
put with the ciphertext.
You can make this scheme go even faster by using all the known secure bits of xi,
not just the least significant bit. With this improvement, Blum-Goldwasser proba-
bilistic encryption is faster than RSA while leaking no partial information about the
plaintext. You can also prove that the difficulty of breaking this scheme is the same
as the difficulty of factoring n.
On the other hand, this scheme is totally insecure against a chosen-ciphertext
attack. From the least significant bits of the right quadratic residues, it is possible to
calculate the square root of any quadratic residue. If you can do this, then you can
factor. For details, consult [1570,1571,35,36].

Quantum cryptography taps the natural uncertainty of the quantum world. With it,
you can create a communications channel where it is impossible to eavesdrop with-
out disturbing the transmission. The laws of physics secure this quantum channel:
even if the eavesdropper can do whatever he wants, even if the eavesdropper has
Page 554
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

unlimited computing power, even if P = NP. Charles Bennett, Gilles Brassard,
Claude Crepeau, and others have expanded on this idea, describing quantum key
distribution, quantum coin flipping, quantum bit commitment, quantum oblivious
transfer, and quantum secure multiparty computation. Their work is described in
[128,129,123, 124,125,133,126,394,134,392,243,517,132,130,244,393,396]. The best
overview of quantum cryptography can be found in [ 1311; [ 16511 is another good
nontechnical overview. A complete bibliography of quantum cryptography is [237].
This would still be on the lunatic fringe of cryptography, but Bennett and Brassard
actually went and built a working model of the thing [127,121,122]. Now we have
experimental quantum cryptography.
So sit back, get yourself something to drink, and relax. I™m going to explain what
this is all about.
According to quantum mechanics, particles don™t actually exist in any single
place. They exist in several places at once, with probabilities of being in different
places if someone looks. However, it isn™t until a scientist comes along and mea-
sures the particle that it “collapses” into a single location. But you can™t measure
every aspect (for example, position and velocity) of a particle at the same time. If
you measure one of those two quantities, the very act of measuring it destroys any
possibility of measuring the other quantity. The quantum world has a fundamental
uncertainty and there™s no way to avoid it.
That uncertainty can be used to generate a secret key. As they travel, photons
vibrate in some direction; up and down, left to right, or more likely at some angle.
Normal sunlight is unpolarized; the photons vibrate every which way. When a large
group of photons vibrate in the same direction they are polarized. Polarization filters
allow only photons that are polarized in a certain direction through; the rest are
blocked. For example, a horizontal polarization filter only allows horizontally polar-
ized photons through. Turn that filter 90 degrees, and only vertically polarized pho-
tons can come through.
Let™s say you have a pulse of horizontally polarized photons. If they try to pass
through a horizontally polarized filter, they all get through. Slowly turn that filter
90 degrees; the number of photons getting through gets smaller and smaller, until
none get through. This is counterintuitive. You™d think that turning the filter just a
little will block all the photons, since the photons are horizontally polarized. But in
quantum mechanics, each particle has a probability of suddenly switching its polar-
ization to match the filter. If the angle is a little bit off, it has a high probability. If
the angle is 90 degrees off, it has zero probability. And if the angle is 45 degrees off,
it has a 50 percent probability of passing through the filter.
Polarization can be measured in any basis: two directions at right angles. An exam-
ple basis is rectilinear: horizontal and vertical. Another is diagonal: left-diagonal and
right-diagonal. If a photon pulse is polarized in a given basis and you measure it in the
same basis, you learn the polarization. If you measure it in the wrong basis, you get
a random result. We™re going to use this property to generate a secret key:

(1) Alice sends Bob a string of photon pulses. Each of the pulses is randomly
polarized in one of four directions: horizontal, vertical, left-diagonal, and
Page 555
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
23 Special Algorithms for Protocols

For example, Alice sends Bob:
(2) Bob has a polarization detector. He can set his detector to measure recti-
linear polarization or he can set his detector to measure diagonal polariza-
tion. He can™t do both; quantum mechanics won™t let him. Measuring one
destroys any possibility of measuring the other. So, he sets his detectors at
random, for example:
Now, when Bob sets his detector correctly, he will record the correct polar-
ization. If he sets his detector to measure rectilinear polarization and the
pulse is polarized rectilinearly, he will learn which way Alice polarized
the photon. If he sets his detector to measure diagonal polarization and the
pulse is polarized rectilinearly, he will get a random measurement. He
won™t know the difference. In this example, he might get the result:
(3) Bob tells Alice, over an insecure channel, what settings he used.
(4) Alice tells Bob which settings were correct. In our example, the detector
was correctly set for pulses 2, 6, 7, and 9.
(5) Alice and Bob keep only those polarizations that were correctly measured.
In our example, they keep:
Using a prearranged code, Alice and Bob each translate those polarization
measurements into bits. For example, horizontal and left-diagonal might
equal one, and vertical and right-diagonal might equal zero. In our exam-
ple, they both have:

So, Alice and Bob have generated four bits. They can generate as many as they like
using this system. On the average, Bob will guess the correct setting 50 percent of
the time, so Alice has to send 2n photon pulses to generate n bits. They can use
these bits as a secret key for a symmetric algorithm or they can guarantee perfect
secrecy and generate enough bits for a one-time pad.
The really cool thing is that Eve cannot eavesdrop. Just like Bob, she has to guess
which type of polarization to measure; and like Bob, half of her guesses will be
wrong. Since wrong guesses change the polarization of the photons, she can™t help
introducing errors in the pulses as she eavesdrops. If she does, Alice and Bob will end
up with different bit strings. So, Alice and Bob finish the protocol like this:

(6) Alice and Bob compare a few bits in their strings. If there are discrepancies,
they know they are being bugged. If there are none, they discard the bits
they used for comparison and use the rest.
Page 556
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

Enhancements to this protocol allow Alice and Bob to use their bits even in the
presence of Eve [ 133,134,192]. They could compare only the parity of subsets of the
bits. Then, if no discrepancies are found, they only have to discard one bit of the sub-
set. This detects eavesdropping with only a 50 percent probability, but if they do
this with n different subsets Eve™s probability of eavesdropping without detection is
only 1 in 2”.
There™s no such thing as passive eavesdropping in the quantum world. If Eve tries
to recover all the bits, she will necessarily disrupt the communications.
Bennett and Brassard built a working model of quantum key distribution and have
exchanged secure bits on a laser table. The latest I heard, some folks at British Tele-
corn were sending bits over a lo-kilometer fiber-optic link [276,1245,1533]. They
figure 50 kilometers is feasible. The mind boggles.


. 2
( 2)