25 years of quantum cryptography

ABSTRACT

The fates of SIGACT News and Quantum Cryptography are inseparably entangled. The exact date of Stephen Wiesner's invention of "conjugate coding" is unknown but it cannot be far from April 1969, when the premier issue of SIGACT News---or rather SICACT News as it was known at the time---came out. Much later, it was in SIGACT News that Wiesner's paper finally appeared [74] in the wake of the first author's early collaboration with Charles H. Bennett [7]. It was also in SIGACT News that the original experimental demonstration for quantum key distribution was announced for the first time [6] and that a thorough bibliography was published [19]. Finally, it was in SIGACT News that Doug Wiedemann chose to publish his discovery when he reinvented quantum key distribution in 1987, unaware of all previous work but Wiesner's [73, 5].Most of the first decade of the history of quantum cryptography consisted of this lone unpublished paper by Wiesner. Fortunately, Bennett was among the few initiates who knew of Wiesner's ideas directly from the horse's mouth. His meeting with the first author of this column in 1979 was the beginning of a most fruitful lifelong collaboration. It took us five more years to invent quantum key distribution [4], which is still today the best-known application of quantum mechanics to cryptography. The second author joined in slightly later, followed by a few others. But until the early 1990's, no more than a handful of people were involved in quantum cryptographic research. Since then, the field has taken off with a vengeance, starting with Artur K. Ekert's proposal to use quantum nonlocality for cryptographic purposes [33].The golden age started in earnest when Ekert organized the first international workshop on quantum cryptography in Broadway, England, in 1993. Since then, many conferences have been devoted at least partly to quantum cryptography, which has become a major international topic. The purpose of the aforementioned 1993 bibliography in SIGACT News was to cite as much as possible all papers ever written on the subject, including unpublished manuscripts: there were 57 entries in total. Today, such an undertaking would be nearly impossible owing to the explosion of new research in the field.The purpose of this column is to give an overview of the current research in quantum cryptography. It is not our intention to be exhaustive and we apologize in advance to any researcher whose work we may have omitted. Note that we do not necessarily agree with the claims in every paper mentioned here: this column should not be construed as a seal of approval!

REFERENCES

• 1: [1] ARDEHALI, M., "Quantum cryptography based on Wheeler's delayed choice experiment", manuscript, 1995. Available at http://xxx.lanl.gov/ps/quant-ph/9508008.
• 2: [2] BENNETT, C.H., "Quantum cryptography using any two nonorthogonal states", Physical Review Letters, Vol. 68, no. 21, 25 May 1992, pp. 3121-2124.
• 3: Charles H. Bennett , François Bessette , Gilles Brassard , Louis Salvail , John Smolin, Experimental quantum cryptography, Journal of Cryptology, v.5 n.1, p.3-28, 1992
• 4: [4] BENNETT, C.H. and G. BRASSARD, "Quantum cryptography: Public key distribution and coin tossing", Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, December 1984, pp. 175-179.
• 5: Charles H. Bennett , Gilles Brassard, Quantum public key distribution reinvented, ACM SIGACT News, v.18 n.4, p.51-53, Summer 1987 [doi>10.1145/36068.36070]
• 6: C. H. Bennett , G. Brassard, Experimental quantum cryptography: the dawn of a new era for quantum cryptography: the experimental prototype is working], ACM SIGACT News, v.20 n.4, p.78-80, Nov. 1989 [doi>10.1145/74074.74087]
• 7: [7] BENNETT, C.H., G. BRASSARD, S. BREIDBART and S. WIESNER, "Quantum cryptography, or Unforgeable subway tokens", Advances in Cryptology: Proceedings of Crypto 82, August 1982, Plenum Press, New York, 1983, pp. 267-275.
• 8: [8] BENNETT, C.H., G. BRASSARD, C. CRÉPEAU, R. JOZSA, A. PERES and W.K. WOOTTERS, "Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels", Physical Review Letters, Vol. 70, no. 13, 29 March 1993, pp. 1895-1899.
• 9: [9] BENNETT, C.H., G. BRASSARD, C. CRÉPEAU and U.M. MAURER, "Generalized privacy amplification", IEEE Transactions on Information Theory, Vol. IT-41, no. 6, November 1995, pp. 1915-1923.
• 10: Charles H. Bennett , Gilles Brassard , Claude Crépeau , Marie-Hélène Skubiszewska, Practical Quantum Oblivious Transfer, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.351-366, August 11-15, 1991
• 11: [11] BENNETT, C.H., G. BRASSARD and N.D. MERMIN, "Quantum cryptography without Bell's theorem", Physical Review Letters, Vol. 68, no. 5, 3 February 1992, pp. 557-559.
• 12: [12] BENNETT, C.H., G. BRASSARD, S. POPESCU, B. SCHUMACHER, J.A. SMOLIN and W.K. WOOTTERS, "Purification of noisy entanglement and faithful teleportation via noisy channels" Physical Review Letters, Vol. 76, no. 5, 29 January 1996, pp. 722-725.
• 13: Charles H. Bennett , Gilles Brassard , Jean-Marc Robert, Privacy amplification by public discussion, SIAM Journal on Computing, v.17 n.2, p.210-229, April 1988 [doi>10.1137/0217014]
• 14: [14] BENNETT, C.H., T. MOR and J. SMOLIN, "The parity bit in quantum cryptography", Physical Review A, Vol. 54, no. 3, September 1996, in press.
• 15: Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62223]
• 16: [16] BIHAM, E., B. HUTTNER and T. MOR, "Quantum cryptography network based on quantum memories", Physical Review A, Vol. 54, no. 3, September 1996, in press.
• 17: [17] BIHAM, E. and T. MOR, "On the security of quantum cryptography against collective attacks", manuscript, 1996. Available at http://xxx.lanl.gov/ps/quant-ph/9605007.
• 18: [18] BIHAM, E. and T. MOR, "Bounds on information and the security of quantum cryptography", manuscript, 1996. Available at http://xxx.lanl.gov/ps/quant-ph/9605010.
• 19: [19] BRASSARD, G., "Cryptology column - Quantum cryptography: A bibliography", Sigact News, Vol. 24, no. 3, 1993, pp. 16-20.
• 20: [20] BRASSARD, G., "A quantum jump in computer science", in Computer Science Today, J. van Leeuwen (editor), Lecture Notes in Computer Science, Vol. 1000, Springer-Verlag, Berlin, 1995, pp. 1-14.
• 21: [21] BRASSARD, G., "Recent developments in quantum cryptography", Proceedings of Pragocrypt '96: 1st International Conference on the Theory and Applications of Cryptology, Prague, October 1996.
• 22: Gilles Brassard , David Chaum , Claude Crépeau, Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences, v.37 n.2, p.156-189, October 1988 [doi>10.1016/0022-0000(88)90005-0]
• 23: Gilles Brassard , Claude Crépeau, Quantum Bit Commitment and Coin Tossing Protocols, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.49-61, August 11-15, 1990
• 24: [24] BRASSARD, G., C. CRÉPEAU, R. JOZSA and D. LANGLOIS, "A quantum bit commitment scheme provably unbreakable by both parties", Proceedings of 34th Annual IEEE Symposium on the Foundations of Computer Science, November 1993, pp. 362-371.
• 25: [25] CRÉPEAU, C., Correct and private reductions among oblivious transfers, PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1990. (Supervised by Silvio Micali.).
• 26: [26] CRÉPEAU, C., "Quantum oblivious transfer", Journal of Modern Optics, Vol. 41, no. 12, December 1994, pp. 2445-2454.
• 27: [27] CRÉPEAU, C., "What is going on with quantum bit commitment?", Proceedings of Pragocrypt '96: 1st International Conference on the Theory and Applications of Cryptology, Prague, October 1996.
• 28: Claude Crépeau , Jeroen van de Graaf , Alain Tapp, Committed Oblivious Transfer and Private Multi-Party Computation, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.110-123, August 27-31, 1995
• 29: [29] CRÉPEAU, C. and J. KILIAN, "Achieving oblivious transfer using weakened security assumptions", Proceedings of 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 42-52.
• 30: [30] CRÉPEAU, C. and L. SALVAIL, "Quantum oblivious mutual identification", Advances in Cryptology -- Proceedings of Eurocrypt '95, May 1995, Springer-Verlag, pp. 133-146.
• 31: [31] CRÉPEAU, C. and L. SALVAIL, "Quantum bit commitment in multiparty model", in preparation, 1996.
• 32: [32] DEUTSCH, D., A.K. EKERT, R. JOZSA, C. MACCHIAVELLO, S. POPESCU and A. SANPERA, "Quantum privacy amplification and the security of quantum cryptography over noisy channels", submitted to Physical Review Letters, 1996. Available at http://eve.physics.ox.ac.uk/Articles/QC.Articles.html.
• 33: [33] EKERT, A.K., "Quantum cryptography based on Bell's theorem", Physical Review Letters, Vol. 67, no. 6, 5 August 1991, pp. 661-663.
• 34: [34] EKERT, A.K., B. HUTTNER, G.M. PALMA and A. PENES, "Eavesdropping on quantum cryptosystems", Physical Review A, Vol. 50, 1994, pp. 1047-1056.
• 35: [35] EVEN, S., O. GOLDREICH and A. LEMPEL, "A randomized protocol for signing contracts", Advances in Cryptology: Proceedings of Crypto 82, August 1982, Plenum Press, New York, 1983, pp. 205-210.
• 36: [36] FRANSON, J.D. and H. ILVES, "Quantum cryptography using optical fibres", Applied Optics, Vol. 33, 1994, pp. 2949-2954.
• 37: [37] FRANSON, J.D. and H. ILVES, "Quantum cryptography using polarization feedback", Journal of Modern Optics, Vol. 41, no. 12, December 1994, pp. 2391-2396.
• 38: [38] FRANSON, J.D. and B.C. JACOBS, "Operational system for quantum cryptography", Electronics Letters, Vol. 31, 1995, pp. 232-234.
• 39: [39] FUCHS, C.A., Distinguishability and Accessible Information in Quantum Theory, Ph.D. Dissertation, University of New Mexico, 1996. Available at http://xxx.lanl.gov/ps/quant-ph/9601020.
• 40: [40] FUCHS, C.A., "Information gain vs. state disturbance in quantum theory", submitted to Fourth Workshop on Physics and Computation -- PhysComp '96, Boston, November 1996. Available at http://xxx.lanl.gov/ps/quant-ph/9605014.
• 41: [41] FUCHS, C.A. and A. PERES, "Quantum state disturbance vs. information gain: Uncertainty relations for quantum information", Physical Review A, Vol. 53, no. 4, April 1996, pp. 2038-2045.
• 42: [42] GOLDENBERG, L. and L. VAIDMAN, "Quantum cryptography based on orthogonal states", Physical Review Letters, Vol. 75, no. 7, 14 August 1995, pp. 1239-1243.
• 43: [43] GOLDENBERG, L. and L. VAIDMAN, "Reply to comment: Quantum cryptography based on orthogonal states?", Physical Review Letters, 1996, in press. Available at hetp://xxx.lanl.gov/ps/quant-ph/9604029.
• 44: Jaroslav Hruby, Smart Card with Interferometric Quantum Cryptography Device, Proceedings of the International Conference on Cryptography: Policy and Algorithms, p.282-289, July 03-05, 1995
• 45: [45] HRUBY, J., "Q-deformed quantum cryptography and verification of minimal uncertainty", Proceedings of Pragocrypt '96: 1st International Conference on the Theory and Applications of Cryptology, Prague, October 1996.
• 46: R. J. Hughes , G. G. Luther , G. L. Morgan , C. G. Peterson , C. M. Simmons, Quantum Cryptography over Underground Optical Fibers, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.329-342, August 18-22, 1996
• 47: [47] HUGHSTON, L.P., R. JOZSA and W.K. WOOTTERS, "A complete classification of quantum ensembles having a given density matrix", Physics Letters A, Vol. 183, 1993, pp. 14-18.
• 48: [48] HUTTNER, B. and A.K. EKERT, "Information gain in quantum eavesdropping", Journal of Modern Optics, Vol. 41, no. 12, December 1994, pp. 2455-2466.
• 49: [49] HUTTNER, B., N. IMOTO, N. GISIN and T. MOR, "Quantum cryptography with coherent states", Physical Review A, Vol. 51, March 1995, pp. 1863-1869.
• 50: [50] HUTTNER, B. and A. PERES, "Quantum cryptography with photon pairs", Journal of Modern Optics, Vol. 41, no. 12, December 1994, pp. 2397-2403.
• 51: Joe Kilian, Founding crytpography on oblivious transfer, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.20-31, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62215]
• 52: [52] Lo, H.-K. and H.F. CHAU, "Quantum cryptography in noisy channels", manuscript, 1995. Available at http://xxx.lanl.gov/ps/quant-ph/9511025.
• 53: [53] LO, H.-K. and H.F. CHAU, "Is quantum bit commitment really possible?", manuscript, 1996. Available at http://xxx.lanl.gov/ps/quant-ph/9603004.
• 54: [54] LÜTKENHAUS, N., "Security against eavesdropping in quantum cryptography", Physical Review A, 1996, in press.
• 55: [55] MARAND, C. and P.D. TOWNSEND, "Quantum key distribution over distances as long as 30km", Optics Letters, Vol. 20, 15 August 1995, pp. 1695-1697.
• 56: [56] MATSUEDA, H., "Quantum cryptography by modulating spontaneous photon emissions", CLEO Pacific Rim Conference, July 1995, page 46.
• 57: [57] MAYERS, D., "The trouble with quantum bit commitment", Presented at a workshop on quantum information theory, Montréal, October 1995. Available at http://xxx.lanl.gov/ps/quant-ph/9603015.
• 58: Dominic Mayers, Quantum Key Distribution and String Oblivious Transfer in Noisy Channels, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.343-357, August 18-22, 1996
• 59: [59] MAYERS, D., "Unconditionally secure quantum bit commitment is impossible", submitted to Fourth Workshop on Physics and Computation -- PhysComp '96, Boston, November 1996. Available at http://xxx.lanl.gov/ps/quant-ph/9605044.
• 60: [60] MAYERS, D., personal communication, 1996.
• 61: [61] MAYERS, D. and L. SALVAIL, "Quantum oblivious transfer is secure against all individual measurements", Proceedings of the Third Workshop on Physics and Computation -- PhysComp '94, Dallas, November 1994, IEEE Computer Society Press, pp. 69-77.
• 62: [62] Mu, Y., Quantum Communication and Security, Masters Thesis, University of Wollongong, Australia, 1994.
• 63: [63] MULLER, A., H. ZBINDEN and N. GISIN, "Underwater quantum coding", Nature, Vol. 378, 30 November 1995, page 449.
• 64: [64] PERES, A., "Quantum cryptography based on orthogonal states?", Physical Review A, Vol. 54, no. 1, July 1996, pp. 97-111. Available at http://xxx.lanl.gov/ps/quant-ph/9509003.
• 65: [65] PHOENIX, S.J.D., S.M. BARNETT, P.D. TOWNSEND and K.J. BLOW, "Multi-user quantum cryptography on optical networks" Journal of Modern Optics, Vol. 42, 1995, pp. 1155-1163.
• 66: [66] RABIN, M.O., "How to exchange secrets by oblivious transfer", Technical Memo TR-81, Aiken Computation Laboratory, Harvard University, 1981.
• 67: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 68: [68] SALVAIL, L., Variations sur le transfert inconscient en cryptographie quantique, Ph.D. Thesis, Département d'informatique et de recherche opérationnelle, Université de Montréal, 1996.
• 69: [69] SALVAIL, L., personal communication, 1996.
• 70: [70] SHOR, P., "Algorithms for quantum computation: Discrete logarithm and factoring", Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 124-134.
• 71: [71] TOWNSEND, P.D., personal communication, July 1996.
• 72: [72] TOWNSEND, P.D., C. MARAND, S.J.D. PHOENIX, K.J. BLOW and S.M. BARNETT, "Secure optical communications systems using quantum cryptography", Philosophical Transactions of the Royal Society of London A, Vol. 354, 1996, pp. 805-817.
• 73: D Wiedemann, Quantum cryptography, ACM SIGACT News, v.18 n.2, p.48-51, Sept. 1986 - March 1987 [doi>10.1145/24652.24654]
• 74: Stephen Wiesner, Conjugate coding, ACM SIGACT News, v.15 n.1, p.78-88, Winter-Spring 1983 [doi>10.1145/1008908.1008920]
• 75: [75] WIESNER, S., "Quantum cryptography with bright light", manuscript, 1993.
• 76: Andrew Chi-Chih Yao, Security of quantum protocols against coherent measurements, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.67-75, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225085]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

General Terms:
Documentation, Security, Theory