What is Quantum Cryptography?

by Artur Ekert

What is Wrong with Classical Cryptography?

The purpose of cryptography is to transmit information in such a way that access to it is restricted entirely to the intended recipient. Originally the security of a cryptotext depended on the secrecy of the entire encrypting and decrypting procedures; however, today we use ciphers for which the algorithm for encrypting and decrypting could be revealed to anybody without compromising the security of a particular cryptogram. In such ciphers a set of specific parameters, called a key, is supplied together with the plaintext as an input to the encrypting algorithm, and together with the cryptogram as an input to the decrypting algorithm.The encrypting and decrypting algorithms are publicly announced; the security of the cryptogram depends entirely on the secrecy of the key, and this key must consist of any randomly chosen, sufficiently long string of bits.

Once the key is established, subsequent communication involves sending cryptograms over a public channel which is vulnerable to total passive eavesdropping (e.g. public announcement in mass-media). However in order to establish the key, two users, who share no secret information initially, must at a certain stage of communication use a reliable and a very secure channel. Since the interception is a set of measurements performed by the eavesdropper on this channel, however difficult this might be from a technological point of view, in principle any classical key distribution can always be passively monitored, without the legitimate users being aware that any eavesdropping has taken place.

Mathematicians have tried hard to solve the key distribution problem. The 1970s brought a clever mathematical discovery in the shape of ``public key" systems [1,2]. In these systems users do not need to agree on a secret key before they send the message. They work on the principle of a safe with two keys, one public key to lock it, and another private one to open it. Everyone has a key to lock the safe but only one person has a key that will open it again, so anyone can put a message in the safe but only one person can take it out. These systems exploit the fact that certain mathematical operations are easier to do in one direction than the other. The systems avoid the key distribution problem but unfortunately their security depends on unproven mathematical assumptions, such as the difficulty of factoring large integers (RSA - the most popular public key cryptosystem gets its security from the difficulty of factoring large numbers [2]). This means that if and when mathematicians or computer scientists come up with fast and clever procedures for factoring large integers the whole privacy and discretion of public-key cryptosystems could vanish overnight. Indeed, recent work in quantum computation shows that quantum computers can factorize much faster than classical computers [3].

QUANTUM CRYPTOGRAPHY - BASIC IDEAS

While classical cryptography employs various mathematical techniques to restrict eavesdroppers from learning the contents of encrypted messages, in quantum mechanics the information is protected by the laws of physics. In classical cryptography an absolute security of information cannot be guaranteed. The Heisenberg uncertainty principle and quantum entanglement can be exploited in a system of secure communication, often referred to as "quantum cryptography" [4]. Quantum cryptography provides means for two parties to exchange a enciphering key over a private channel with complete security of communication.

There are at least three main types of quantum cryptosystems for the key distribution, these are:

  • (A) Cryptosystems with encoding based on two non-commuting observables proposed by S.Wiesner (1970), and by C.H.Bennett and G.Brassard (1984) [5].
  • (B) Cryptosystems with encoding built upon quantum entanglement and the Bell Theorem proposed by A.K.Ekert (1990) [6].
  • (C) Cryptosystems with encoding based on two non-orthogonal state vectors proposed by C.H.Bennett (1992) [7].

Quantum cryptosystem (A) can be explained with the following simple example. The system includes a transmitter and a receiver. A sender may use the transmitter to send photons in one of four polarisations: 0, 45, 90, or 135 degrees. A recipient at the other end uses the receiver to measure the polarisation. According to the laws of quantum mechanics, the receiver can distinguish between rectilinear polarisations (0 and 90), or it can quickly be reconfigured to discriminate between diagonal polarisations (45 and 135); it can never, however, distinguish both types. The key distribution requires several steps. The sender sends photons with one of the four polarisations which are chosen at random. For each incoming photon, the receiver chooses at random the type of measurement: either the rectilinear type or the diagonal type. The receiver records the results of the measurements but keeps them secret. Subsequently the receiver publicly announces the type of measurement (but not the results) and the sender tells the receiver which measurements were of the correct type. The two parties (the sender and the receiver) keep all cases in which the receiver measurements were of the correct type. These cases are then translated into bits (1's and 0's) and thereby become the key. An eavesdropper is bound to introduce errors to this transmission because he/she does not know in advance the type of polarisation of each photon and quantum mechanics does not allow him/her to acquire sharp values of two non-commuting observables (here rectilinear and diagonal polarisations). The two legitimate users of the quantum channel test for eavesdropping by revealing a random subset of the key bits and checking (in public) the error rate. Although they cannot prevent eavesdropping, they will never be fooled by an eavesdropper because any, however subtle and sophisticated, effort to tap the channel will be detected. Whenever they are not happy with the security of the channel they can try to set up the key distribution again.
The basic idea of cryptosystems (B) is as follows. A sequence of correlated particle pairs is generated, with one member of each pair being detected by each party (for example, a pair of so-called Einstein-Podolsky-Rosen photons, whose polarisations are measured by the parties). An eavesdropper on this communication would have to detect a particle to read the signal, and retransmit it in order for his presence to remain unknown. However, the act of detection of one particle of a pair destroys its quantum correlation with the other, and the two parties can easily verify whether this has been done, without revealing the results of their own measurements, by communication over an open channel.

QUANTUM CRYPTOGRAPHY - PRACTICALITIES

A photon polarization measurement scheme has been used to make a working quantum key distribution system (A) in a laboratory at the IBM Thomas J. Watson Research Center [5], which transmits over the admittedly modest length of 30 cm at a rate of 10 bits/second. However, progress in quantum optics has resulted in new photon sources, new photo-detectors, and better optical fibres; the components which have the potential for exhibiting the relevant quantum phenomena over much larger distances. For example, polarization based scheme has been sucessfuly tested over a distance of 1 km [8], quantum entanglement has been tested over a distance of 4 km [9], and single-photon interference fringes have recently been produced [10] in transmission over 10 km of fiber optic cable. This holds out a reasonable prospect for implementation of a secure key distribution system on a large local area network, transmitting at about 20k bits per second with present technology.

REFERENCES

  1. W. Diffie and M.E. Hellman, IEEE Trans. Inf. Theory IT-22, 644 (1977).
  2. R. Rivest, A. Shamir, and L. Adleman, "On Digital Signatures and Public-Key Cryptosystems", MIT Laboratory for Computer Science, Technical Report, MIT/LCS/TR-212 (January 1979).
  3. P.W. Shor, Proceedings of the 35th Annual Symposium on the Foundations of Computer Science (IEEE Computer Society, Los Alamitos, CA, 1994) p. 124.
  4. C.H. Bennett, G. Brassard, and A.K. Ekert, "Quantum cryptography", Scientific American, October 1992, p. 50.
  5. S. Wiesner, SIGACT News 15, 78 (1983); original manuscript written circa 1970. C.H. Bennett and G. Brassard, in "Proc. IEEE Int. Conference on Computers, Systems and Signal Processing", IEEE, New York (1984). C.H. Bennett, F. Bessette, G. Brassard, L. Salvail, and J. Smolin, "Experimental quantum cryptography," J. Cryptology 5, 3 (1992).
  6. A.K. Ekert, Phys. Rev. Lett. 67, 661 (1991); A.K. Ekert, J.G. Rarity, P.R. Tapster, and G.M. Palma, Phys. Rev. Lett. 69, 1293 (1992).
  7. C.H. Bennett, Phys. Rev. Lett. 68, 3121 (1992).
  8. A. Muller, J. Breguet, and N. Gisin, Europhys. Lett. 23, 383 (1993).
  9. P.R. Tapster, J.G. Rarity and P.C.M. Owens, Phys. Rev. Lett. 73, 1923 (1994).
  10. P D. Townsend, J.G. Rarity, and P.R. Tapster, Electron. Lett. 29, 1291 (1993).