QUADRATIC RESIDUE

INTRODUCTION: The Quadratic Sieve (QS) and

Let n be an odd, positive integer and let x be an

its variants are the ď¬rst of the modern integer

integer that is relatively prime to n (see modular

factoring algorithms to be able to routinely factor

arithmetic). The integer x is a quadratic residue

abitrary integers in the 60+ digit range on just

modulo n if the equation

a single PC. They are the successor to the ear-

x âĄ y2 (mod) n lier Continued Fraction Method of Morrison and

Brillhart [4] (see integer factoring) and the pre-

has an integer solution y. In other words, the in- decessor to the Number Field Sieve [2]. All three

teger x is a square modulo n. The integer x is a of these algorithms share features in common.

quadratic non-residue otherwise. They are based upon the observation that if A2 âĄ

If n is an odd prime number, then exactly half of B2 mod N and A âĄ Â±B mod N (see modular arith-

all integers x relatively prime to n are quadratic metic), then GC D (A + B, N) and GC D (A â’ B, N)

residues. If n is the product of two distinct odd are proper factors of N. The Quadratic Sieve will

primes p and q, then the fraction is one-quarter. factor an arbitrary integer N, in heuristic time

See also Jacobi symbol, Legendre symbol, and LN[1/2, 1] = exp((1 + o(1)) (log N)1/2 (log log N)1/2 )

Quadratic Residuosity Problem. (see L-notation). The entries integer factoring and

Number Field Sieve discuss the history of these

Burt Kaliski

algorithms and we do not repeat that discussion

here. For those interested in implementing QS,

reference [7] gives all of the necessary details. The

version of QS that is detailed here is known as

QUADRATIC RESIDUOSITY the Multiple Polynomial Quadratic Sieve (MPQS).

PROBLEM Other variants are known.

KEY IDEAS: The Quadratic Sieve, like other

Let n be the product of two distinct odd prime num-

sieving algorithms (and the Elliptic Curve

bers p, q, and let x be an integer such that the

Method for factoring), is based on the idea of

Jacobi symbol (x/n) = +1. The Quadratic Residu-

smooth numbers (see also smoothness). A number

osity Problem (QRP) is to determine, given x and

x is said to be yâ”smooth if all of its prime factors

n, whether x is a quadratic residue modulo n (see

are less than y. QS generates many relations of

modular arithmetic). (All quadratic residues have

the form

Jacobi symbol +1, but not necessarily the reverse.)

This problem is easy to solve given the factors p S 2 = r mod N,

and q, but is believed to be difď¬cult given only x

where the pair (S, r ) is generated from a quadratic

and n. However, it is not known whether the prob-

polynomial in such a way that r is small com-

lem is equivalent to factoring the modulus n.

pared to N. The algorithm then attempts to factor

The QRP is the basis for several cryptosys-

r using a ď¬xed set of primes called a factor base.

tems, including the Goldwasserâ“Micali encryption

The largest prime in the factor base is then the

scheme and Cocksâ™ identity-based encryption

smoothness bound. Most such values will not fac-

scheme [1] (see identity-based cryptosystems).

tor. However, a sieve can be used to attempt to

Burt Kaliski factor many such rs simultaneously. It is the speed

of sieving on modern computers that makes QS

and NFS very effective methods. The sieve works

Reference

by observing that if a prime p divides the value of

a polynomial Q (x), then it divides Q (x + kp) for

[1] Cocks, Clifford (2001). âAn identity based encryp-

all k.

tion scheme based on quadratic residues.â Cryp-

Once a sufď¬cient number of smooth relations

tography and Coding, Lecture Notes in Computer

have been found, a subset is then extracted such

Science, vol. 2260, ed. B. Honary. Springer, Berlin,

that the product of the rs in the subset is a perfect

360â“363.

493

494 Quadratic sieve

square. From that, A2 âĄ B2 mod N is easily com- chosen this way to minimize the maximum value

of Q(x) over the interval [â’M, M]. The computa-

puted.

tion of B, C and S depends on A and is detailed

The subset is found by solving a system of equa-

in [7].

tions mod 2. This is referred to as the linear alge-

bra phase of the algorithm.

OPTIMIZATION PARAMETER SELECTION:

AND

GENERATION RELATIONS: The algorithm

OF It is often useful, rather than to factor just N

starts by computing a factor base FB = { pi |( N ) = 1, to factor kN for some small value of k. This can

pi

p prime, i = 1, . . . , F} for some appropriate value have the effect of allowing more small quadratic

of F and p0 = â’1 for the sign. ( N ) is the Legendre residues in the factor base. In this case, replace N

pi

symbol and indicates that pi must be a quadratic with kN in all of the computations outlined above.

residue of N. It may also be necessary in order for the algorithm

The following is then repeated until enough to work. Since N = B2 â’ 4AC and the right-hand

smooth relations have been collected:

r side is 0 or 1 mod 4, if N âĄ 3 mod 4, then we must

Construct a quadratic polynomial Q(x) = multiply N by k so that k N âĄ 1 mod 4. However,

Ax 2 + Bx + C and solve Q(x) âĄ 0 mod pi for all this requirement may be avoided by taking 2B,

i. There will be two roots r1i and r2i for each rather than just B as the middle coefď¬cient for Q.

prime.

r The Knuthâ“Schroeppel function may be used to

Initialize a sieve array to zero over the interval evaluate the effectiveness of different values of k.

[â’M, M] for an appropriate value of M.

r See [7] for details.

For all pi â FB add the value log( pi ) to Rather than demand that r be fully factored over

the locations r1 , r1 Â± pi , r1 Â± 2 pi , . . . and r2 , r2 Â± the factor base, it is very useful to allow a small

pi , r2 Â± 2 pi , . . .

r â number of somewhat larger primes to appear in

The value of Q(x) will be approximately M N the factorization of r. This is known as the large

over [â’M, M] so compare each sieve location prime variation. Let

with T = log(M) + log(N)/2. Fully factored val-

F

ues will have their corresponding sieve value

piÎ±i P1 P2 . . . ,

r=

close to T. For these, construct the exact fac-

i=0

torization by division. It is also possible (and

where the Pi are allowed to be somewhat larger

usually quicker) to ď¬nd the factorization by re-

primes than those in the factor base. The Birth-

sieving. See the section on optimization for how

day Paradox now becomes useful here. The set of

to do this. We then have

fully factored rs will now be quite large and we

F

piÎ±i

S âĄ Q(x) âĄ

2

mod N. can expect many of the large primes Pi to appear

more than once. When it does, we may multiply

i=0

the corresponding relations together and obtain

The value of S is easily computed from the value

Pi2 on the right-hand side of each relation. For N

of x because of the special way the coefď¬cients

up to about 85 digits, using one large prime is quite

of Q are computed. Let

â’ = {Î± , Î± , . . . , Î± } mod 2.

â’ effective. For N greater than about 85 digits, two

v 1 2 F

primes are effective. Limited experience suggests

Collect a total of at least F + 1 factored relations. that for N above 120 digits, three primes may be

One then ď¬nds a set whose product is a square by effective. Once the factor base primes are removed,

ď¬nding a linear dependency over GF(2) from the P1 and P2 may then be split via Pollardâ™s rho (see

matrix formed by letting each â’ be a row in the

â’v integer factoring) or SQUFOF algorithms (see [6]

matrix. for a deď¬nition of SQUFOF). Both are effective.

The smallest primes pi take the longest time to

COMPUTATION POLYNOMIAL COEFFI- sieve and their logarithms contribute the least to

OF

CIENTS: The coefď¬cients for each polynomial are the accumulated sum at each sieve location. It is

derived from a prime number D = 3 mod 4 with worthwhile to replace the smallest primes (up to

( N ) = 1. Each prime D yields a different polyno-

D

about 30) with small powers of those primes. This

mial. This makes parallel implementation of this has the effect of greatly speeding sieve time while

algorithm easy. Simply give different sets of Ds to losing only a tiny fraction of factored relations.

different machines and let each one run indepen- This is known as the small prime variation.

dently. It is also worthwhile to partition the sieve inter-

To compute the coefď¬cients, we start by letting val [â’M, M] into pieces that will ď¬t in cache while

â

A = D2 with D â (N/2)1/4 / M. The value of D is sieving. This too can greatly improve the speed

Quantum cryptography 495

of sieving, and it cuts down on memory require- Stephen Wiesner wrote âConjugate Coding,â which

ments. unfortunately took more than 10 years to see the

The cost of changing polynomials is dominated light of print [50]. In the mean time, Charles H.

by the cost of computing (2A)â’1 mod pi for each pi . Bennett (who knew of Wiesnerâ™s idea) and Gilles

A method for greatly reducing this cost is known Brassard picked up the subject and brought it to

as the self-initializing Quadratic Sieve (SIQS). De- fruition in a series of papers that culminated with

tails may be found in [5]. the demonstration of an experimental prototype

A fair bit of time is taken by the reconstruction that established the technological feasibility of

of the actual factorization of r. The sieving pro- the concept [5]. Quantum cryptographic systems

cess merely identiď¬es which r are smooth. It does take advantage of Heisenbergâ™s uncertainty rela-

not produce the factorization. This is readily ac- tions, according to which measuring a quantum

complished by trial division of r by the factor base system, in general, disturbs it and yields incom-

primes. However, as N, and hence the size of F in- plete information about its state before the mea-

creases, trial division starts taking a larger and surement. Eavesdropping on a quantum commu-

larger percentage of the run time. This may be al- nication channel therefore causes an unavoidable

leviated by ď¬nding the factorizations by resieving. disturbance, alerting the legitimate users. This

Now, however, instead of accumulating log pi , one yields a cryptographic system for the distribution

simply stores the pi that hit the identiď¬ed smooth of a secret random key between two parties ini-

locations. It is now a simple matter to produce the tially sharing no secret information (however they

actual factorization. must be able to authenticate messages) that is se-

Suggested values for the parameters M and F as cure against an eavesdropper having at her dis-

well as additional coding and computational con- posal unlimited computing power. Once this se-

siderations may be found in [7]. cret key is established, it can be used together

with classical cryptographic techniques such as

Robert D. Silverman the Vernam cipher (one-time pad) to allow the par-

ties to communicate meaningful information in

References absolute secrecy.

Quantum cryptography is best known for key

distribution [7]. A short summary of this so-

[1] Caron, T. and R.D. Silverman (1988). âParallel im-

called BB84 protocol is provided in the Section

plementation of the quadratic sieve.â Journal of

Supercomputing, 1, 273â“290. âQnantum Key Distribution.â A remarkable surge

[2] Lenstra, A. and H.W. Lenstra, Jr. (eds.) (1992). The of interest in the international scientiď¬c and

Development of the Number Field Sieve, Lecture industrial communities has propelled quantum

Notes in Mathematics, vol. 1554. Springer-Verlag, cryptography into mainstream computer science

Berlin.

and physics. Furthermore, quantum cryptogra-

[3] Lenstra, A. and M. Manasse (1994). âFactoring with

phy is becoming increasingly practical at a fast

two large primes.â Math. Comp., 63, 785â“798.

pace. The ď¬rst quantum key distribution proto-

[4] Morrison, M. and J. Brillhart (1975). âA method of

type, built in 1989, worked over a distance of 32 cm

factoring and the factorization of F7 .â Math. Comp.,

[5], [11]. Since then, many additional experimen-

29, 183â“205.

tal demonstrations have been set up, covering dis-

[5] Pomerance, C., J.W. Smith, and R. Tuler (1988).

tances of tens of kilometers. Consult [46] or [42]

âA pipeline architecture for factoring large integers

with the quadratic sieve.â SIAM J. Comp., 17 (2), for popular accounts of the state of the art in ex-

387â“403. perimental quantum cryptography.

[6] Riesel, H. (1987). Prime Numbers and Computer

Methods for Factorization. Volume 57 of Progress in

The Various Uses of Quantum Physics

Â¨

Mathematics. Birkhauser.

for Cryptography

[7] Silverman, R.D. (1987). âThe multiple polynomial

quadratic sieve.â Math. Comp., 48, 329â“339.

In addition to key distribution, quantum tech-

niques may also assist in the achievement of more

subtle cryptographic goals, important in the post-

cold war world, such as protecting private informa-

QUANTUM tion while it is being used to reach public decisions.

CRYPTOGRAPHY Such techniques, pioneered by CrÂ´ peau [10], [15],

e

allow two people to compute an agreed-upon func-

QUANTUM CRYPTOGRAPHY [A]: Quantum tion f (x, y) on private inputs x and y when one

Cryptography was born in the early 1970s when person knows x, the other knows y, and neither is

496 Quantum cryptography

willing to disclose anything about his private input may send to Bob a random bit-stream that she

to the other, except for what follows logically from knows exactly and of which Bob will randomly se-

oneâ™s private input and the functionâ™s output. The lect a constant fraction. These four possible states

may be the 0â—¦ , 45â—¦ , 90â—¦ , and 135â—¦ polarizations of a

classic example of such discreet decision making

is the âdating problem,â in which two people seek photon. According to quantum mechanics, orthog-

onally polarized photons ((0â—¦ , 90â—¦ ) or (45â—¦ , 135â—¦ ))

a way of making a date if and only if each likes

the other, without disclosing any further informa- are perfectly distinguishable whereas nonorthog-

onal photons ((0â—¦ , 45â—¦ ), (45â—¦ , 90â—¦ ), etc.) are not.

tion. For example, if Alice likes Bob but Bob does

not like Alice, the date should be called off without When Alice sends Bob a random state from these

Bob ď¬nding out that Alice likes him. On the other four, he may choose to measure whether it is

(0â—¦ , 90â—¦ ) or (45â—¦ , 135â—¦ ). If he makes the correct mea-

hand, it is logically unavoidable for Alice to learn

that Bob does not like her, because if he did the surement then he detects perfectly the original

date would be on. state. If he makes the wrong measurement then

Indeed, two applications of quantum physics to he detects a random state among the two he was

cryptography were discovered well before quan- trying to distinguish. When Alice later tells him

tum key distribution: quantum bank notes that which was the correct measurement, he keeps the

are impossible to counterfeit and quantum mul- correctly measured states and discards the others.

tiplexing that allows one party to send two mes- Thus, in a perfect world, Bob would receive 50% of

sages to another party in a way that the receiver Aliceâ™s photons in their exact original state and

can obtain either message at his choice, but read- discard the other 50% of the photons. If we assign

binary value 0 to 0â—¦ and 45â—¦ and value 1 to 90â—¦ and

ing one destroys the other irreversibly [50]. (The

135â—¦ , then their agreed bit-stream is obtained by

notion of multiplexing was reinvented 10 years

later by Michael Rabin in the context of classical the correctly measured 50% of the photons.

cryptography under the name of oblivious transfer However, the world is not perfect. Therefore, a

[43], [28].) Unfortunately, even its author, Stephen fraction of the correctly measured photons will

Wiesner, knew from the start that the quantum be detected incorrectly. Also, if an eavesdropper

multiplexing protocol could be defeated with arbi- (Eve) tries to measure Aliceâ™s photons before they

trary measurements performed by the receiver of reach Bob, errors will be induced by the fact that

the strings. Thus, a more elaborate quantum obliv- she is measuring information about the photonsâ™

ious transfer protocol was designed subsequently polarizations. Moreover, these two situations are

[10] under the assumption of the existence of a bit indistinguishable from each other: natural noise

commitment scheme [19], a result unlikely to be or induced noise looks the same. (Indeed, part

possible classically as argued by Impagliazzo and of the ânaturalâ noise is produced by ânatureâ

Rudich [34]. Another quantum cryptographic task eavesdropping on Alice and Bob!) The beauty of

that has been studied extensively is indeed bit quantum cryptography is that an estimate on the

commitment [15]. Unfortunately it turned out that noise level leads to an estimate of the informa-

early claims of security of certain quantum proto- tion obtained by Eve. Consequently, a three-phase

cols for this task were after all insecure as showed classical protocol allows Alice and Bob to extract

by Mayers [39] and independently by Lo and Chau an agreed upon, smaller secret cryptographic key

[37]. This no-go theorem was later extended to from their noisy, partly eavesdropped bit-stream.

any Quantum Bit Commitment scheme consistent These three phases are called âerror estimation,â

with quantum physics [40], [38]. âinformation reconciliation,â and âprivacy ampliď¬-

On a closely related topic, various Quantum cation.â

Coin Tossing protocols have been also introduced

â

[7] as well as a lower bound of 1/ 2 on the bias

of such a protocol in a very general quantum me- Error Estimation. Error estimation is performed

chanical framework [1]. by having one of Alice or Bob pick at random

a certain number t of bits previously transmit-

Quantum Key Distribution ted according to the correct measurement and

announce them to the other party. The latter

The purpose of quantum key distribution is to en- compares these bits with his/her own copy and an-

able two honest parties, Alice and Bob, to agree on nounces the number of errors e. For large enough

a random cryptographic key in a situation where samples, the ratio e/t should be a reasonable esti-

eavesdropping is possible. By transmitting one of mate of the fraction of errors left in the undisclosed

four possible nonorthogonal quantum states, Alice bits.

Quantum cryptography 497

Information Reconciliation. Although interactive tected by quantum mechanics even in storage,

error correction such as [16] was ď¬rst encouraged rather than merely in transit. More interestingly,

in [5], CrÂ´ peau pointed out that traditional error-

e Ekertâ™s scheme can beneď¬t from powerful quan-

correcting codes may be used here as well [10]. In tum techniques that were discovered only years

both cases, this process will disclose some extra in- later, such as entanglement distillation [12], [23].

formation about the remaining (corrected) bits to Prototypes of entanglement-based quantum cryp-

any potential eavesdropper. This extra informa- tography, working over kilometers of ď¬ber, came

tion must be taken into account in the last privacy soon after the theoretical invention [26] as well as

ampliď¬cation phase. much more recently [27].

The past decade has seen an explosion in experi-

mental demonstrations of quantum cryptography,

Privacy Ampliď¬cation. Assume an eavesdropper is

with distances ever increasing, sometimes at the

left with only bits of RÂ´ nyi (collision) entropy

e

expense of giving up the Holy Grail of uncondi-

about the bit-stream W of size n resulting from

tional security. We can mention only a few exam-

the information reconciliation phase. If Alice and

ples here. A plug-and-play device built in Switzer-

Bob can estimate from error estimation and er-

land was tested successfully using 67 km of optical

ror correction, they may produce a new smaller

ď¬ber laid out between Geneva and Lausanne [47].

bit-stream K of size nearly from W. Let H be a

More recent experiments achieve even further dis-

uniformly selected hash function from a Strongly

tances such as 150 km of optical ď¬ber [35]. The

Universal Set [49] mapping n bits to â’ s bits.

notion of quantum repeaters has been discussed

Then we obtain a tight bound on the uncertainty

in order to achieve even greater distances [18].

H(H(W) | H, E) â¤ 2â’s (see information theory for

Free-space prototypes have shown the possibility

deď¬nitions) where E is the eavesdropping informa-

of line-of-sight quantum cryptography over dis-

tion (including error correction). This means that

tances of tens of kilometers [33], [36], making it

if one of Alice or Bob picks a random hash func-

legitimate to dream of a quantum-cryptographic

tion h and announces it publicly to the other, they

satellite-based global network [44]. A thorough

are able to use it to replace their longer string W

survey of quantum cryptography, with an empha-

by K = h(W) that is almost perfectly secret to the

sis on technological issues, can be found in [29]. A

eavesdropper [9] with nearly probability 1.

living roadmap of the work ahead can be obtained

in [6].

Finally, we point out that quantum key distribu-

Eavesdropping. The key distribution protocol de-

tion is now available as a commercial product. In-

scribed above has been proven secure regardless of

formation about quantum-cryptographic products

the eavesdropperâ™s strategy and computing power.

can be found at the Web sites of the Swiss com-

The ď¬rst proof of this theorem is due to Mayers

pany id Quantique (www.idquantique.com) and

[41]. However, the very technical nature of that

the American corporation MagiQ Technologies

proof encouraged many alternate proofs to be de-

(magiqtech.com).

veloped such as those of Biham, et al. [14], Shor

and Preskill [45], Gottesman and Lo [31], etc. A

Cryptography on Quantum Data

more powerful security proof in the universal com-

posability framework was recently demonstrated

by Ben-Or, et al. [13]. The last component of quantum cryptography is

the cryptography on quantum data where cryp-

Alternative Quantum Key Distribution tographic tools are developed for information

Protocols and Implementations imbedded in quantum systems. A ď¬rst example

is known as the one-time quantum pad where the

The original quantum key distribution protocol sender Alice and receiver Bob share a priori a pair

uses four different polarization states of single of maximally entangled particles and use them to

photons as carrier of quantum information [7], but teleport [8] an arbitrary qubit (quantum bit), for

other approaches have been put forward. Early example, from Alice to Bob. The only public trans-

variations were to use only two nonorthogonal mission of this scheme is a pair of classical random

states rather than four [4], and to use phase mod- bits from the sender to receiver, allowing him to

ulation rather than polarization [26], [48]. A more reconstruct the original state she wanted to com-

fundamental variation, due to Ekert [25], was to municate.

make use of Einsteinâ“Podolskyâ“Rosen entangled A second example is the Quantum Vernam

pairs [24], which allows the key to remain pro- Cipher [2] where a classical key of four possible

498 Quantum cryptography

values is used by Alice who applies one of four Proceedings of the 41st IEEE Symposium on Foun-

dations of Computer Science, 547â“553.

unitary (Pauli) operators to an arbitrary system

[3] Barnum, H., C. CrÂ´ peau, D. Gottesman, A. Smith,

e

of a single qubit that may then be transmitted

and A. Tapp (2002). âAuthentication of quantum

to Bob. Bob decrypts the state by applying the

messages.â In FOCSâ™02: Proceedings of the 43rd

inverse unitary operator. The quantum descrip-

IEEE Symposium on Foundations of Computer Sci-

tion of the state transmitted is the same regard-

ence, 449â“458.

less of the original state to be transferred as [4] Bennett, C.H. (1992). âQuantum cryptography us-

long as the key is uniformly distributed and a ing any two nonorthogonal states.â Phys. Rev. Lett.,

secret to an eavesdropper. An interesting differ- 68, 3121â“3124.

ence between the quantum and classical scenar- [5] Bennett, C.H., F. Bessette, G. Brassard, L. Sal-

ios is that two key bits are required to encrypt vail, and J. Smolin (1992). âExperimental quantum

a general qubit in the quantum setting [2], but cryptography.â J. Cryptol., 5 (1), 3â“28.

[6] Bennett, C.H., D. Bethune, G. Brassard, N.

this may be reduced to nearly one key bit to en-

Donnangelo, A.K. Ekert, C. Elliott, J. Franson, C.

crypt a qubit almost perfectly if we tolerate arbi-

Fuchs, M. Goodman, R. Hughes (Chair), P. Kwiat,

trarily small errors, as long as it is not entangled

A. Migdall, S.-W. Nam, J. Nordholt, J. Preskill, and

with Eve [32]. It was also demonstrated recently

J. Rarity (2004). âA quantum information science

how the secret key used for Quantum Vernam Ci-

and technology roadmap, Part 2: Quantum cryp-

pher may be re-used [22] when the plaintexts are tography, Version 1.0.â Advanced Research and

classical. Development Activity (ARDA), July 2004. Available

Quantum error-correcting codes have led to at http://qist.lanl.gov/qcrypt map.shtml.

the notion of Quantum Message Authentication [7] Bennett, C.H., and G. Brassard (1984). âQuan-

[3] that allows Alice to send Bob a message in tum cryptography: Public key distribution and

such a way that any tampering of the transmit- coin tossing.â In Proceedings of IEEE International

Conference on Computers, Systems and Signal Pro-

ted message will either result in detection of the

cessing, Bangalore, India, 175â“179.

tampering or actual correction of the tampering

[8] Bennett, C.H., G. Brassard, C. CrÂ´ peau, R. Jozsa,

e

back to the original message. Surprisingly, quan-

A. Peres, and W.K. Wootters (1993). âTeleport-

tum authentication requires quantum encryption,

ing an unknown quantum state via dual classi-

whereas classically these two tasks are fairly in-

cal and Einsteinâ“Podolskyâ“Rosen channels.â Phys.

dependent of each other. A very interesting notion Rev. Lett., 70, 1895â“1899.

of Uncloneable Encryption, linking Quantum En- [9] Bennett, C.H., G. Brassard, C. CrÂ´ peau, and

e

cryption and Quantum Authentication, was later U. Maurer (1995). âGeneralized privacy ampliď¬-

introduced by Gottesman [30]. cation.â IEEE Transaction on Information Theory,

We conclude with a short list of recent 41 (6), 1915â“1923.

quantum cryptographic applications: Quantum [10] Bennett, C.H., G. Brassard, C. CrÂ´ peau, and

e

M.-H. Skubiszewska (1991). âPractical quantum

Secret Sharing [17] where the secret to be

oblivious transfer.â In Advances in Cryptology: Pro-

shared is a quantum state, Veriď¬able Quantum

ceedings of Cryptoâ™91, 351â“366.

Secret Sharing [20] offers the extra guarantee

[11] Bennett, C.H., G. Brassard, and A.K. Ekert

that if enough honest people are involved the se-

(1992). âQuantum cryptography.â Scientiď¬c Ameri-

cret may be uniquely reconstructed, Multi-Party

can, 267 (4), 50â“57.

Quantum Computation [20] allows multiparty [12] Bennett, C.H., G. Brassard, S. Popescu, B.

evaluation of a quantum circuit in which each Schumacher, J.A. Smolin, and William K. Wootters

party secretly provides some of the input quantum (1996). âPuriď¬cation of noisy entanglement and

states, and Quantum Zero-Knowledge [21] that faithful teleportation via noisy channels.â Physical

generalizes the classical notion although ârewind- Review Letters, 76, 722â“725.

ingâ a quantum computer is impossible. [13] Ben-Or, M., M. Horodecki, D.W. Leung, D.

Mayers, and J. Oppenheim (2005). âThe universal

Gilles Brassard composable security of quantum key distribution.â

Claude CrÂ´ peau

e In Proceedings of Second Theory of Cryptogra-

phy Conference: TCC 2005, Cambridge, MA, USA,

February 10â“12, 2005. http://arXiv.org/abs/quant-

References ph/0409078.

[14] Biham, E., M. Boyer, P.O. Boykin, T. Mor, and

V. Roychowdhury (2000). âA proof of the security

[1] Ambainis, A. (2004). âA new protocol and lower

of quantum key distribution (extended abstract).â

bounds for quantum coin ď¬‚ipping.â J. Comput. Syst.

In STOCâ™00: Proceedings of the 32nd Annual

Sci., 68 (2), 398â“416.

ACM Symposium on Theory of Computing, 715â“

[2] Ambainis, A., M. Mosca, A. Tapp, and R. de Wolf

724.

(2000). âPrivate quantum channels.â In FOCSâ™00:

Quantum cryptography 499

[30] Gottesman, D. (2003). âUncloneable encryption.â

[15] Brassard, G., C. CrÂ´ peau, R. Jozsa, and D. Lan-

e

Quantum Information and Computation, 3, 581â“

glois (1993). A quantum bit commitment scheme

602. http://arXiv.org/abs/quant-ph/0210062.

provably unbreakable by both parties. In FOCSâ™93:

[31] Gottesman, D., and H.-K. Lo (2003). âProof of se-

Proceedings of the 34th IEEE Symposium on Foun-

curity of quantum key distribution with two-way

dations of Computer Science, 362â“371.

classical communications.â IEEE Trans. Inf. The-

[16] Brassard, G., and L. Salvail (1993). âSecret-

ory, 49, 457â“475.

key reconciliation by public discussion.â In Ad-

[32] Hayden, P., D. Leung, P.W. Shor, and A. Winter

vances in Cryptology: Proceedings of Eurocryptâ™93,

(2004). Randomizing quantum states: Construc-

410â“423.

tions and applications. Commun. Math. Phys., 250,

[17] Cleve, R., D. Gottesman, and H.-K. Lo (1999). âHow

(2), 371â“391.

to share a quantum secret.â Phys. Rev. Lett., 83 (3),

[33] Hughes, R.J., J.E. Nordholt, D. Derkacs, and C.G.

648â“651.

Peterson (2002). âPractical free-space quantum

[18] Collins, D., N. Gisin, and H. De Riedmatten (2005).

key distribution over 10 km in daylight and at

âQuantum relays for long distance quantum cryp-

night.â New Journal of Physics, 4, 43.1â“43.14.

tography.â J. Mod. Optics, 52 (5), 735.

[34] Impagliazzo, R., and S. Rudich (1989). âLimits on

[19] CrÂ´ peau, C., P. Dumais, D. Mayers, and L. Salvail

e

the provable consequences of one-way permuta-

(2004). âComputational collapse of quantum state

tions.â In STOCâ™89: Proceedings of the 21st An-

with application to oblivious transfer.â In Proceed-

nual ACM Symposium on Theory of Computing,

ings of First Theory of Cryptography Conference:

44â“61.

TCC 2004, Cambridge, MA, USA, February 19â“21,

[35] Kimura, T., Y. Nambu, T. Hatanaka, A. Tomita,

374â“393.

H. Kosaka, and K. Nakamura (2004). âSingle-

[20] CrÂ´ peau, C., D. Gottesman, and A. Smith

e

photon interference over 150-km transmission us-

(2002). âSecure multi-party quantum computa-

ing silica-based integrated-optic interferometers

tion.â In STOCâ™02: Proceedings of the 34th Annual

for quantum cryptography.â Electronics Letters,

ACM Symposium on Theory of Computing, 643â“

43 (9), L1217â“L1219.

652.

Ë [36] C. Kurtsiefer, P. Zarda, M. Halder, H. Weinfurter,

[21] Damgard, I., S. Fehr, and L. Salvail (2004). âZero-

P.M. Gorman, P.R. Tapster, and J.G. Rarity (2002).

knowledge proofs and string commitments with-

âQuantum cryptography: A step towards global

standing quantum attacks.â In Advances in Cryp-

key distribution.â Nature, 419, 450.

tology: Proceedings of Cryptoâ™04, 254â“272.

Ë [37] Lo, H.-K., and H.F. Chau (1997). âIs quan-

[22] Damgard, I., T. Pedersen, and L. Salvail (2004).

tum bit commitment really possible?â Physical

âOn the key-uncertainty of quantum ciphers and

Review Letters, 78 (17), 3410â“3413. Originally

the computational security of one-way quantum

http://arXiv.org/abs/quant-ph/9603004.

transmission.â In Advances in Cryptology: Proceed-

[38] Lo, H.-K., and H.F. Chau (1998). âWhy quantum

ings of Eurocryptâ™04, 91â“108.

bit commitment and ideal quantum coin tossing

[23] Deutsch, D., A.K. Ekert, R. Jozsa, C. Macchiavello,

are impossible.â Physica D, 120, 177â“187.

S. Popescu, and A. Sanpera (1996). âQuantum pri-

[39] Mayers, D. (1995). âThe trouble with quan-

vacy ampliď¬cation and the security of quantum

tum bit commitment.â http://arXiv.org/abs/quant-

cryptography over noisy channels.â Physical Re-

ph/9603015. The author ď¬rst discussed the result

view Letters, 77, 2818â“2821. Erratum (1998). Phys-

in MontrÂ´ al at a workshop on quantum informa-

e

ical Review Letters, 80, 2022.

tion theory held in October 1995.

[24] Einstein, A., B. Podolsky, and N. Rosen (1935).

[40] Mayers, D. (1997). âUnconditionally secure quan-

âCan quantum-mechanical description of physical

tum bit commitment is impossible.â Physical Re-

reality be considered complete?â Physical Review,

view Letters, 78 (17), 3414â“3417.

47, 777â“780.

[41] Mayers, D. (2001). âUnconditional security in

[25] Ekert, A.K. (1991). âQuantum cryptography based

quantum cryptography.â J. ACM, 48 (3), 351â“406.

on Bellâ™s theorem.â Phys. Rev. Lett., 67, 661â“663.

[42] Ouellette, J. (2005). âQuantum key distribution.â

[26] Ekert, A.K., J. Rarity, P. Tapster, and G. Palma

The Industrial Physicist, 10 (6), 22â“25.

(1992). âPractical quantum cryptography based on

[43] Rabin, M. (1981). âHow to exchange secrets

two-photon interferometry.â Physical Review Let-

by oblivious transfer.â Technical Report TR-81,

ters, 69, 1293â“1295.

Harvard Aiken Computation Laboratory.

[27] Enzer, D.G., P.G. Hadley, R.J. Hughes, C.G.

[44] Rarity, J.G., P.R. Tapster, P.M. Gorman, and

Peterson, and P.G. Kwiat (2002). âEntangled-

P. Knight (2002). âGround to satellite secure key

photon six-state quantum cryptography.â New

exchange using quantum cryptography.â New Jour-

Journal of Physics, 4, 45.1â“45.8.

nal of Physics, 4, 82.1â“82.21.

[28] Even, S., O. Goldreich, and A. Lempel (1985). âA

[45] Shor, P.W., and J. Preskill (2000). âSimple proof of

randomized protocol for signing contracts.â Com-

security of BB84 quantum key distribution proto-

mun. ACM, 28 (6), 637â“647.

col.â Phys. Rev. Lett., 85, 441â“444.

[29] Gisin, N., G. Ribordy, W. Tittel, and H. Zbinden

[46] Stix, G. (2005). âBest-kept secretsâ”quantum cryp-

(2002). âQuantum cryptography.â Reviews of Mod-

tography has marched from theory to laboratory

ern Physics, 74, 145â“195.

500 Quantum cryptography

to real products.â Scientiď¬c American, 280 (1), bre interferometer.â Electronics Letters, 29, 1291â“

78â“83. 1293.

[47] Stucki, D., N. Gisin, O. Guinnard, G. Ribordy, and [49] Wegman, M., and J. Carter (1981). âNew hash func-

H. Zbinden (2002). âQuantum key distribution over tions and their use in authentication and set equal-

67 km with a plug & play system.â New Journal of ity.â J. Comput. Syst. Scz., 22, 265â“279.

Physics, 4, 41.1â“41.8. [50] Wiesner, S. (1983). âConjugate coding.â Sigact

[48] Townsend, P., J. Rarity, and P. Tapster (1993). âSin- News, 15 (1), 78â“88. Original manuscript written

gle photon interference in 10 km long optical ď¬- circa 1970.