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;

I

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].

23.16 QUANTUM CRYPTOGRAPHY

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

right-diagonal,

Page 555

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

23 Special Algorithms for Protocols

CHAPTER

For example, Alice sends Bob:

II/--\-I--/

(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:

x++xxx+x++

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:

/l-\/\-/-l

(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:

\-*-*

*I***

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:

0011

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.