A Bibliography of Quantum Cryptography

by

Gilles Brassard

Département IRO, Université de Montréal.
C.P. 6128, Succursale "Centre-Ville"
Montréal (Québec) Canada H3C 3J7

The original PostScript file from Gilles Brassard - provided by Edith Stoeveken -
was converted to ASCII and reformatted in HTML; Sept 2 1994, Stephan Kaufmann.
HTTP pointers to DVI files added by Claude Crépeau, March 6 1995.
Multiple file format added July 21st 1996 by Claude.

FORMATS: D = DVI, P = POSTSCRIPT, G = POSTSCRIPT+GZIP

Abstract

This paper provides an extensive annotated bibliography of papers that have been written on quantum cryptography and related topics.

1. Introduction

For ages, mathematicians have searched for a system that would allow two people to exchange messages in perfect privacy. Quantum Cryptography was born in the early seventies when Stephen Wiesner wrote "Conjugate Coding", which unfortunately took more than ten years to see the light of print [1]. In the mean time, Charles H. Bennett (who knew of Wiesner's idea) and Gilles Brassard picked up the subject and brought it to fruition in a series of papers that culminated with the demonstration of an experimental prototype that established the technological feasibility of the concept [2]. Quantum cryptographic systems take advantage of Heisenberg's uncertainty principle, according to which measuring a quantum system in general disturbs it and yields incomplete information about its state before the measurement. Eavesdropping on a quantum communication channel therefore causes an unavoidable disturbance, alerting the legitimate users. This yields a cryptographic system for the distribution of a secret random cryptographic key between two parties initially sharing no secret information that is secure against an eavesdropper having at her disposal unlimited computing power. Once this secret key is established, it can be used together with classical cryptographic techniques such as the one-time-pad to allow the parties to communicate meaningful information in absolute secrecy.

In addition to key distribution, quantum techniques may also assist in the achievement of subtler cryptographic goals, important in the post-cold war world, such as protecting private information while it is being used to reach public decisions. Such techniques, pioneered by Claude Crépeau [3, 4], allow two people to compute an agreed-upon function f(x; y) on private inputs x and y when one person knows x, the other knows y, and neither is willing to disclose anything about their private input to the other, except for what follows logically from one's private input and the function's output. The classic example of such discreet decision making is the "dating problem", in which two people seek a way of making a date if and only if each likes the other, without disclosing any further information. For example, if Alice likes Bob but Bob doesn't like Alice, the date should be called off without Bob finding out that Alice likes him|on the other hand, it is logically unavoidable for Alice to learn that Bob doesn't like her, because if he did the date would be on.

In the past few years, a remarkable surge of interest in the international scientific and industrial community has propelled quantum cryptography into mainstream computer science and physics. Furthermore, quantum cryptography is becoming increasingly practical at a fast pace. The first quantum key distribution prototype [2] worked over a distance of 32 centimetres in 1989. Two additional experimental demonstrations have been set up since, which work over significant lengths of optical fibre [13, 14].

The purpose of this work is to provide an extensive bibliography of most papers ever written on quantum cryptography, including some unpublished papers. In addition, a limited selection of key papers that describe techniques of crucial importance to quantum cryptography, such as privacy amplification [63, 73], is included. The papers are listed in chronological order within each section.

2. The various uses of quantum physics for cryptography

Quantum cryptography is best known for key distribution. The most complete paper written on the subject, which also describes the original prototype, is [2]. However, two applications of quantum physics to cryptography were discovered well before quantum key distribution: quantum bank notes are impossible to counterfeit and quantum multiplexing allows one party to send two messages to another party in a way that the receiver can obtain either message at his choice, but reading one destroys the other irreversibly [1]. (The notion of multiplexing was reinvented ten years later in the context of classical cryptography under the name of oblivious transfer, which will be used henceforth in this paper.) A more elaborate quantum oblivious transfer protocol was designed subsequently [3]. Another quantum cryptographic task that has been studied extensively is bit commitment [4]. Applications of bit commitment and oblivious transfer are mentioned in Section 9.

3. Alternative quantum key distribution protocols

The original quantum key distribution protocol uses four different polarization states of single photons as carrier of quantum information [2], but other approaches have been put forward. Early variations were to use Einstein-Podolsky-Rosen entangled pairs [5], to use only two nonorthogonal states rather than four [6], and to use phase modulation rather than polarization [6, 7]. A theoretical advantage of using entangled pairs is to allow the key to remain protected by the uncertainty principle even in storage, rather than merely in transit. More recent variations use rejected-data protocols [8, 9], photon pairs [10], and bright light [11].

4. Implementation

At least three experimental apparatuses have been built for implementing quantum key distribution, in addition to the original 32 centimetre implementation [2]. A prototype built in Geneva follows the original protocol of [2]: it uses four different polarization states to carry the quantum information over more than one kilometre of optical fibre [14]. Another prototype built independently by British Telecom in association with the Defence Research Agency works by phase modulation over a distance of 10 kilometres of fibre; it is described in a sequence of two papers [12, 13]. Yet another experimental demonstration is in the works, which uses Einstein-Podolsky-Rosen entangled pairs sent over kilometres of fibre [15].

5. Eavesdropping

The key distribution protocol described in [2] has been proven secure regardless of the eavesdropper's computing power, but assuming some restrictions on the type of attack, such as requiring eavesdropping to be independent from one light pulse to another. More sophisticated attacks have been analysed in the papers quoted below, but none of them has yet presented a direct threat to quantum key distribution. Note that, contrary to all known quantum key distribution schemes, the quantum bit commitment protocol of [4] has been formally proven invulnerable to all attacks consistent with the laws of quantum mechanics.

6. Popular accounts

These papers appeared in popular science magazines. Many of them offer easy reading for the non specialist. The best introduction to quantum cryptography is perhaps [33].

7. Historical papers

These papers are superseded by other papers listed above; nevertheless they are of historical interest. Of particular importance are the first paper ever published on quantum cryptography [37] (recall that [1] was written earlier) and the first paper that gives a complete description of the quantum key distribution protocol [42].

8. Other papers

Here are various other papers, theses and book chapters that have been written on quantum cryptography.

9. Useful tools and related papers

Raw quantum cryptography is useless in practice because limited eavesdropping may be undetectable, yet it may leak some information, and errors are to be expected even in the absence of eavesdropping. Also, we must protect against an eavesdropper who would impersonate Alice for Bob and Bob for Alice. For these reasons, quantum cryptography must be supplemented by classical tools such as privacy amplification [63, 73], error correction [71] and authentication [62]. Additional useful information-theoretic tools are provided in [70]. Quantum bit commitment [4] can be used to obtain zero-knowledge proofs [67] for arbitrary NP statements [68, 65]. Quantum oblivious transfer [3] can be used for discreet decision making [64, 66]. High-efficiency single- photon detectors [72] are crucial for photon-based quantum cryptography. Quantum teleportation [69] may be useful to increase the distance for quantum key distribution. The Einstein-Podolsky- Rosen effect is ubiquitous in quantum cryptography [61].

10. Bibliographies

This bibliography of quantum cryptography [76] has evolved from an earlier version [75]. An earlier bibliography is available [74].

Acknowledgements

I wish to thank Charles H. Bennett, Claude Crépeau, Artur K. Ekert, Neil Gershenfeld, Simon J. D. Phoenix and Paul D. Townsend, who helped me put this bibliography together by supplying corrections, updates and additions to previous versions. I am also grateful to Ron Rivest, whose request for a quantum cryptography bibliography set me in motion for this work. Finally I am most grateful to the Rank Foundation and Artur K. Ekert for making possible the first international workshop on quantum cryptography, which was held in Broadway, England, in March 1993. That was a historical event for the field.

Latest update: 22 July 1998, Claude CRÉPEAU

Recent papers on Quantum Cryptography

JMO Special Issue: Quantum Communication

Various Sources