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.