It is widely believed that devising an "unbreakable" cryptographic method is an impossible task. Mankind is still on an age-old quest to find such a method, since virtually all attempts, to this day, have failed. Cryptography used to be the art of outsmarting a human enemy; nowadays it is concerned more with resisting attack by very powerful computers.
For instance, the famous Data Encryption Standard (DES) can be broken by brute force, albeit with much difficulty, at a moderate cost nowadays [20].
It was actually in the early eighties that a physicist (Stephen Wiesner) and two computer scientists (Charles Bennett and Gilles Brassard) suggested applying some simple quantum mechanical principles to the task of exchanging secret messages [1, 23].
These observations lead one naturally to ask: "What makes a cryptographic scheme perfectly secure?" and "How can we use quantum mechanical phenomena for secure communication?". These are the basic questions I intend to address in this article. I will start by explaining the classical Vernam cipher, and exactly what it means to say that a cryptosystem is perfectly secure. Then I will discuss the the BB84 scheme for quantum key distribution, which uses polarized photons to represent the individual bits in a cryptographic key. This scheme has been proved to be perfectly secure in theory, while current implementations are prone to noise and errors; this will be discussed later. Finally, I will give a brief account of current computer science research related to quantum cryptography.
Let's start by defining some basic terms (for details, refer to [16, 20]). A cryptosystem is a mechanism or convention that allows two or more legitimate users to exchange messages secretly - nobody but these users must be able to learn the content of the messages. Every message, m, is subjected to an encrypting operation, E, to produce a so-called ciphertext. To recover the message corresponding to a given ciphertext, a decrypting operation D must be performed. Formally:
c = E(m) and m = D(c)
In a symmetric cryptosystem, these two operations require one more argument: the key k. The key is a unique sequence of bits known only to the legitimate users of the system. Usually, the procedures E and D are publicly known, and the key is the only piece of information needed by an enemy to recover the contents of a transmitted message. The basic scenario that arises in most cryptographic applications is the following:
Classical cryptography is concerned to a great extent with developing operations E and D that are practically impossible to compute unless k is known. The enemy is assumed to have limited computational power, and limited time on his hands.
A perfect, or unconditionally secure cryptosystem, cannot be broken even in the face of unlimited time and computational power. The standard example of a perfect cryptosystem is the Vernam cipher, or one-time pad.
As an illustration of the one-time pad, consider the message, key and ciphertext as binary strings, such as 010 or 110111. To encrypt a message m with a key k, you need to perform a bitwise XOR operation on these two values. For example,
if m = 010 and k = 110, then c = m XOR k = 100
In other words, the encrypting operation for the one-time pad is E(m,k) = m XOR k. To recover the original message from c, you have to perform the XOR operation again, this time on c and k:
if c = 100 and k = 110, then m = c XOR k = 010
So, the decrypting operation is again, an application of exclusive-or: D(c,k) = c XOR k. In the one-time pad:
As long as these requirements are satisfied, the one-time pad is an unconditionally secure cryptosystem - and this is not a question of computational power, as is the case for most systems in current use.
Why doesn't everyone use the one-time pad? If it is perfectly secure, why do we settle for less secure systems in practice? The truth is that the one-time pad is difficult to use in practice -- you need to issue a new, secret key prior to every communication, and the key becomes too long for larger messages. Assuming that the problem of key length does not matter much, knowing the capacity of modern storage media, having to establish a fresh, truly random key secretly all the time is a major problem. Generating large quantities of truly random data is not very practical either.
For military and diplomatic applications, it may be possible to have the key delivered manually to all the legitimate users, using a trusted third party such as a courier. But not everybody can afford couriers, and even if they could, there is no guarantee that couriers can be trusted. Anyone who manages to find out the keys being used can decrypt the messages effortlessly, defeating the objective of encryption. This aspect of (symmetric) cryptography is referred to as the key distribution problem.
While traditional methods for solving this problem exist, none of them is perfectly secure (except for hand delivery, which is rarely feasible). So although a perfect cryptosystem exists in theory, the difficulty of distributing keys in the first place makes it impossible to devise a complete, practical and perfectly secure cryptographic technique. The most well-known solution to the key distribution problem is public-key cryptography, which works as follows.
In public-key cryptography, different keys are used to encrypt and decrypt a message. When sending a message to some user, the message must encrypted with that user's public key PK, which is, as its name suggests, publicly available. To decrypt the message, the user only needs his private or secret key SK. This process can be described as shown below:
c = E(m, PK)
m = D(c, SK)
or simply
D( E(m, PK), SK ) = m
The public and secret keys of any user are related in such a way that it is computationally intractable to compute the private key from the corresponding public key. The security of the well-known RSA cryptosystem, for example, relies on the difficulty of factoring large numbers into primes [20].
If substantial quantum computers are ever built, it will be possible to perform calculations in massively parallel ways -- leading to the known possibility of factoring prime numbers efficiently (using Shor's algorithm, [21]). This would make it possible to "break" public key cryptosystems such as RSA with relative ease. A quantum computer is a computational device that uses the phenomena of quantum physics to perform extremely efficient computations. Experimental prototypes of quantum computers have been built in the laboratory, but there is a long way to go before these devices become practical. Given that it is possible, if just in theory, to construct devices that "break" commonly used cryptosystems, it is essential to develop new, more powerful cryptographic techniques. These new techniques should be secure even when quantum computers become available.
It turns out that we can build a perfectly secure key distribution system using the principles of quantum physics; this is known as quantum key distribution (QKD).
Quantum key distribution takes advantage of certain phenomena that occur at the subatomic level, so that any attempt by an enemy to obtain the bits in a key not only fails, but gets detected as well. Specifically, each bit in a key corresponds to the state of a particular particle, such as the polarization of a photon. The sender of a key has to prepare a sequence of polarized photons, which are sent to the receiver through an optical fibre or a similar medium. In order to obtain the key represented by a given sequence of photons, the receiver must make a series of measurements. A few explanations are necessary before the full implications of this procedure can be understood.
A photon is an elementary particle of light, carrying a fixed amount of energy. Light may be polarized; polarization is a physical property that emerges when light is regarded as an electromagnetic wave. The direction of a photon's polarization can be fixed to any desired angle (using a polarizing filter) and can be measured using a calcite crystal.
A photon which is rectilinearly polarized has a polarization direction at 0° or 90° with respect to the horizontal. A diagonally polarized photon has a polarization direction at 45° or 135°. It is possible to use polarized photons to represent individual bits in a key or a message, with the following conventions:
| 0 | 1 | |
| Rectilinear | 0° | 90° |
| Diagonal | 45° | 135° |
That is to say, a polarization direction of 0° or 45° may be taken to stand for binary 0, while directions of 45° and 135° may be taken to stand for binary 1. This is the convention used in the quantum key distribution scheme BB84, which will be described shortly. The process of mapping a sequence of bits to a sequence of rectilinearly and diagonally polarized photons is referred to as conjugate coding, while the rectilinear and diagonal polarization are known as conjugate variables. Quantum theory stipulates that it is impossible to measure the values of any pair of conjugate variables simultaneously.
The position and momentum of a particle are the most common examples of conjugate variables. If an experimenter tries to measure a particle's position, he or she has to project light on it of a very short wavelength; however, short-wavelength light has a direct impact on the particle's momentum, making it impossible for the experimenter to measure momentum to any degree of accuracy. Similarly, to measure a particle's momentum, long-wavelength light is used, and this necessarily makes the position of the particle uncertain. In quantum mechanics, position and momentum are also referred to as incompatible observables, by virtue of the impossibility of measuring both at the same time. This same impossibility applies to rectilinear and diagonal polarization for photons: if you try to measure a rectilinearly polarized photon with respect to the diagonal, all information about the photon's rectilinear polarization is lost - permanently.
BB84 is the first known quantum key distribution scheme, named after the original paper by Bennett and Brassard, published in 1984 [1]. BB84 allows two parties, conventionally "Alice" and "Bob", to establish a secret, common key sequence using polarized photons. The steps in the procedure are listed below:
What is important to understand about this procedure is that, only if Bob's guess is correct, is it certain that he will make an accurate measurement. If Bob attempts to measure a rectilinearly polarized photon with a diagonally oriented measurement device (and vice versa), the outcome will be, at random, either 0 or 1; the original bit value represented by the photon is encoded in its rectilinear polarization (rectilinear polarization, respectively), all information about which is lost. So, an incorrect choice of measurement basis randomizes the outcome of a measurement, which is only accurate in this case with probability 50%. If n photons are transmitted in total, there is a probability 0.5n that Bob will measure all of them correctly.
A similar logical argument allows Alice and Bob to detect the presence of an eavesdropper ("Eve"). Just as Bob, Eve is incapable of knowing which type of photon is used to represent each bit. Therefore Eve must guess which measurement basis to use and, since it is impossible for her to duplicate the state of each received photon (due to the theorem of non-cloneability of quantum states [24]), she must create a new photon to send to Bob. Eve's presence is made manifest to Alice and Bob because Eve's measurements necessarily cause a disturbance to the states of the transmitted photons.
The criterion for detecting Eve's presence can be formulated as follows. For the ith bit chosen by Alice, s[i], there will correspond a choice of polarization basis, b[i], which is used to encode the bit to a photon. If Bob's chosen measurement basis is b'[i] and the outcome of his measurement is s'[i], then
b'[i] = b[i] should necessarily imply s'[i] = s[i]
If an eavesdropper tries to obtain any information about s[i], a disturbance will result and, even if Bob and Alice's bases match, s'[i] ≠ s[i]. This allows Alice and Bob to detect an eavesdropper's presence on a noiseless channel, and to reschedule their communications accordingly.
Let's consider the following scenario, illustrated in Figure 1: Alice and Bob are linked together via a noiseless optical fibre. Eve, the eavesdropper, is capable of making measurements on individual photons passing through the fibre. Consider the case in which Alice wants to communicate the binary sequence 00110 to Bob through this setup, using BB84.
Figure 1. The basic setup for quantum key distribution. The quantum channel is typically an optical fibre, capable of transmitting individual polarized photons.
Alice and Bob perform the steps described in the previous section, detailed below. The question marks indicate bit positions for which measurement will produce a random result (0 or 1 with equal probability). The whole process is illustrated in Figure 2, where instead of question marks, one of the two possible bit values are shown.
Figure 2. The sequence of steps in the BB84 quantum key distribution scheme, in the presence of an eavesdropper. For the second and third bit in this example, Eve makes an incorrect choice of measurement basis, indicated with red colored text. Bob makes an incorrect choice of basis for the third and fourth bit, similarly indicated in red. For the second bit, although Bob has chosen the correct basis (D), the outcome of measurement does not match the original bit encoded by Alice -- this allows Alice and Bob to detect Eve's presence.
The basic BB84 procedure is incomplete in the following sense: whether an eavesdropper is present or not, there will still be errors in Bob's key sequence. The final step of BB84, which was described above merely as a comparison of encoding and measurement bases, is usually much more elaborate. There are two parts involved: secret key reconciliation and privacy amplification. I will explain the first of the two in this section.
The process of reconciliation is a special error correction procedure which eliminates:
Reconciliation is performed as an interactive binary search for errors. Alice and Bob divide their bit sequences into blocks and compare each other's parity for each block. Whenever their respective parities for any given block do not match, they divide it into smaller blocks and compare parities again, repeating this process until the exact location of the error is found. When an error has been located, Alice and Bob may decide to discard the corresponding bit, or agree on the correct value. During this process, Alice and Bob can communicate over a classical (i.e. "non-quantum") channel, which is by definition insecure and accessible to an eavesdropper.
Since valuable information about the key may be obtained by an eavesdropper during reconciliation, Alice and Bob must perform a final step in order to establish a perfectly secret key: this is the process of privacy amplification.
The process of reconciliation results in a bit sequence which is common to Alice and Bob, but some of its bits may be known to an eavesdropper who has tapped the classical channel. To eliminate this "leaked" information, Alice and Bob must apply, in common, a binary transformation (usually, a random permutation) to their sequences, and discard a subset of bits from the result. The precise choice of transformation and the number of bits discarded, of course, determine the amount of secrecy of the final key. The objective of this step is to minimize the quantity of correct information which the eavesdropper may have obtained about Alice and Bob's common bit sequence.
At the end of the privacy amplification procedure, Alice and Bob's bit sequences may be shown to be identical and absolutely secret, with arbitrarily high probability. The interested reader is referred to [3, 2, 7, 10] for details.
The exposition, in the previous sections, of quantum key distribution based on BB84, raises several interesting issues. The first observation one makes about the whole procedure is that only part of it involves quantum mechanical phenomena - using polarized photons to represent a binary sequence is only half of the story. In order to distill a perfectly secret binary sequence from the bit values encoded in the photons, it is necessary to perform a set of "non-quantum" communications (namely, key reconciliation and privacy amplification). What is most astounding about these communications is the fact that they may be performed over an insecure classical channel, such as a telephone line (which is wire-tappable). Curiously, any information obtained by an eavesdropper through this channel is useless. An eavesdropper will learn, for instance, that several of her measurements were performed with the wrong measurement basis; however, quantum measurements are destructive and irreversible, so it is impossible for her to repeat any one measurement.
It has been suggested that an eavesdropper could use a "quantum memory" device to store the photons she intercepts, without performing measurements until the correct choices of basis are made known. It has also been noted that, in practice, all communication channels are prone to noise and, hence, errors will necessarily occur. Importantly, the proof of unconditional security of BB84 [14] shows that both these scenarios can be dealt with effectively - neither affects the security of the overall procedure.
Quantum key distribution does have its limitations, however. While a scheme such as BB84 can ensure that an eavesdropper is always detected, it may not always be possible to establish a secret key at the end of the procedure. Generally, as soon as an eavesdropper is detected, the procedure must be aborted and postponed to a later date. That is to say, the legitimate users (Alice and Bob) have to "keep trying" until no eavesdropper is found on the channel. It is now known that, if Alice and Bob share a small amount of information prior to quantum key distribution, it will always be possible for them to establish a secret key [11, 18]. This may sound awkward, since there is little point in performing quantum key distribution if the users are capable of establishing common, secret data via other means -- this is a known issue and remains to be tackled.
Physically breaking into Alice or Bob's communication facilities may still be a practical means of compromising the security of BB84. Should an enemy assault, say, Alice, and attempt to impersonate her toward Bob in BB84, Bob might never notice. There exists a solution to this problem as well. Alice and Bob's equipment could be fitted with a so-called authentication mechanism, preventing anyone but the true owner from activating the equipment. An unconditionally secure authentication scheme is known, quite appropriate for this purpose, and is due to Wegman and Carter [22].
So, quantum key distribution is clearly an unconditionally secure means of establishing secret keys. Combined with unconditionally secure authentication, and an unconditionally secure cryptosystem (e.g. the one-time pad), a perfect cryptographic mechanism may be built. All of this is true in principle, of course: implementing the hardware for such a mechanism is far from simple.
Note that perfect security is not strictly necessary for most applications; it is merely a desideratum. However, BB84 and similar schemes do provide a highly secure solution to the key distribution problem, and in practice the keys produced in this way may well be used in imperfect cryptosystems, such as DES and AES. After all, these cryptosystems are, for all practical purposes, very secure.
The greatest bane for the implementor of quantum key distribution is the presence of noise in all practical communications channels, including optical fibres. It is possible to combat noise with so--called quantum error correction techniques [11, 18]. Many such practicalities have been resolved by experimental physicists: fully-working, commercial quantum key distribution systems are already available on the market, from companies such as MagiQ [15] and ID Quantique [12]. Several trials of quantum key distribution have succeeded, including recent experiments under Lake Geneva [10]. Finally, the Defense and Research Projects Agency (DARPA) is involved in the development of a point-to-point communications network based on quantum key distribution [7].
BB84 is one of several protocols that implement the general idea of quantum key distribution. Charles Bennett proposed a simplified version of BB84, referred to as B92. Artur Ekert designed a protocol for the same purpose based on quantum entanglement [6], while numerous other variations can be found in the literature. Thus, a whole class of quantum communication protocols has been formed, and is worthy of careful study in its own right.
For computer scientists, these protocols pose an interesting challenge, since the phenomena involved are far more exotic than those we are all used to. Recent work in the field has included the application of modal logic to the analysis of these protocols [17], and the development of two quantum process algebras [9, 13].
Not unlike computer algorithms, protocols - and especially quantum protocols - are ideal targets for formal verification and analysis. My own work [19] has included the use of model-checking as a means of demonstrating formally the correctness and security of BB84.
There is much more to quantum cryptography than what can be said in the space of an introductory article; several accounts of the subject have appeared before in popular magazines, but not many computer scientists are aware of its implications. The fact that techniques from theoretical computer science may be applied effectively to quantum cryptographic protocols is a good indication that quantum cryptography as a whole is an exciting new area of work, and not just for physicists!
Nick Papanikolaou received his B.Sc. in Computer Systems Engineering from the University of Warwick, UK in 2003. During the academic year 2003-4 he undertook an M.Sc. by Research (thesis title: Techniques for Design and Validation of Quantum Protocols) at the same institution; he is currently a doctoral student at Warwick and a Tutor for the Higher National Certificate/Diploma in Business IT with RDI Consultants Ltd. He may be reached at http://go.warwick.ac.uk/nikos.