Entanglement

QUANTUM INFORMATION PROCESSING

QUANTUM CRYPTOGRAPHY

The science of cryptography was developed to enable people exchange messages in absolute secrecy. Humans have invented some ingenious ways to encode their conversations. The Enigma machine invented by the Nazis during World War II produced one of the most difficult to decipher encrypted messages of the pre-computer era.

Two of the main goals of cryptography are (a) encrypting messages to render them unintelligible to third parties and (b) authenticating to certify that they have not been modified. To explain how cryptographic systems work, we need to introduce the important features of classical cryptography first (no entangled photons needed here). Typically, for a message to be communicated confidentially between a sender and a recipient, a piece of information, called a key (a secret random bit sequence), is needed. By combining the message with the key, encryption is achieved so that the result is incomprehensible to an eavesdropper who has no knowledge of the key. To decrypt the encrypted message (called the cryptogram), the recipient needs to use his or her copy of the key.

The first truly unbreakable cryptogram, called the Vernam cipher, was created during the first World War by Gilbert S. Vernam of American Telephone and Telegraph Company and Major Joseph O. Mauborgne of the U.S. Army Signal Corps. A distinctive feature of this code is that it used a key that was as long as the transmitted message itself and was never reused to send another message. Although the Vernam scheme was implemented with considerable success, its massive key requirement made it impractical for general use and people started to use shorter keys making the cipher susceptible to malicious attacks.

A variant of the Vernam scheme is the public key cryptography (PKC), developed in the mid-1970s by Whitfield Diffie, Martin E. Hellman and Ralph C. Merkle of Stanford University. A practical implementation came shortly later, in 1977, due to the work of Ronald L. Rivest, Adi Shamir and Leonard M. Adleman10 of the Massachusetts Institute of Technology.

PKC differs from all previous schemes of cryptography in one important aspect. Here, the communicating parties to do not have to agree on a secret key prior to transmitting the cryptogram. The idea is this:

  1. For encryption and decryption, the sender, Alice, randomly chooses a pair of mutually inverse transformations.
  2. She then publishes the instructions for encrypting the message but not how to decrypt it.
  3. The recipient, Bob, prepares a message using Alice’s public-encryption algorithm that only she can decrypt. Similarly, anyone, including Alice, can use Bob’s public encryption algorithm to prepare a message that only he can decrypt. Thus, Alice and Bob can communicate secretly but they do not have to share any secrets to begin with.

Today the encryption and decryption procedures are broadcast in the public domain, but the key is a closely guarded secret. An adversary who has managed to intercept the message will not be able to decipher it without the key. So while the cryptogram may be “open to the public”, the key must be transmitted through a very secure private channel.

In the 1940s, Claude E. Shannon of Bell Laboratories wrote two brilliant papers to show that the security of a cryptogram ultimately depends on the length of the key. Some information about the message can always be inferred from the cryptogram by an ingenious code breaker if the key is shorter than the message being encrypted. This leakage of information occurs regardless of how complicated the encryption process may be. In contrast, the message can be completely and unconditionally hidden from the eavesdropper by cryptosystems such as the Vernam cipher (encoded message), in which the key is as long as the message, is purely random and is used only once.

There is one important drawback of the classical PKC: it is possible for an eavesdropper to passively monitor any classical private channel without the sender or receiver knowing about it. The eavesdropper doesn’t even have to be a human being—it can be a high-resolution x-ray scanner or some sophisticated imaging technique. The important thing to note here is, any physical property of an object can be measured without disturbing the object itself which is the well-known aphorism in classical physics. In contrast, the act of measurement is an integral part of quantum mechanics, not just a passive, external process as in classical physics. We will presently see how the latter cliché of quantum physics was brilliantly exploited in designing quantum cryptographic devices.

Quantum cryptography, the science of exploiting quantum mechanical properties to perform cryptographic tasks, was proposed first by Stephen Wiesner, when he was at Columbia University in New York. Charles Bennett and Gilles Brassard, building on the ideas of Wiesner, showed how quantum measurements provided a secure mechanism for establishing a cryptographic key.

Today’s quantum cryptographic devices make use of individual photons. A unique aspect of quantum cryptography is that Heisenberg’s uncertainty principle ensures that if Eve, the eavesdropper, attempts to intercept and measure Alice’s photons, her activities must produce an irreversible change in the photons (collapse of the photon’s wave function) that are retransmitted to Bob. These changes will introduce an anomalously high error rate in the transmissions between Alice and Bob, allowing them to detect the attempted eavesdropping.

BB84.png
Figure 13: Quantum key distribution according to BB84. Source: Quantum Cryptography by Charles H. Bennett, Gilles Brassard and Artur K. Ekert, Scientific American, 1992.

Bennett and Brassard’s method of establishing a cryptographic key, known as the BB84 scheme, is given below. The steps are paraphrased from Bennett, Brassard and Ekert’s 1992 Scientific American article entitled “Quantum Cryptography”:

  • Alice sends a stream of photons to Bob whose polarizations she has chosen at random to be either 0, 45, 90 or 135 degrees.
  • Bob has two polarizers: a vertically oriented polarizer and a polarizer that has been rotated 45 degrees from the original orientation. He also has two photon detectors that can record single photons.
  • Bob has two polarizers: a vertically oriented polarizer and a polarizer that has been rotated 45 degrees from the original orientation. He also has two photon detectors that can record single photons.
  • On receiving the photons Bob decides randomly whether to measure each photon’s rectilinear or diagonal polarization.
  • For each photon, Bob announces publicly which type of measurement he has made (rectilinear or diagonal) but not the measurement result (for example, 0, 45, 90 or 135 degrees).
  • For each photon, Alice tells Bob publicly, whether his measurement is correctly made.
  • All cases where Bob made incorrect measurements or in which Bob’s detectors failed to register a photon at all (practical systems are not 100 percent efficient) are discarded.
  • Alice and Bob will share the secret information of the remaining polarizations if the quantum channel is eavesdropper free.
  • Alice and Bob now both know a sequence of bits (sifted key) that they next test for eavesdropping. This is done by publicly comparing and discarding a randomly selected subset of each other’s polarization data. If the comparison test shows evidence of eavesdropping, Alice and Bob discard all their data and start over with a fresh batch of photons.
  • Otherwise they accept the remaining polarizations, which have never been publicly disclosed as shared secret bits. Horizontal or 45-degree photons are interpreted as binary 0’s while vertical or 135-degree photons as binary 1 ‘s.
  • Eve would like to make a copy of the photon for herself by measuring both of its rectilinear and diagonal polarizations. She would then want to pass the accurate copy on to Bob, so that her presence will not be detected later when Alice and Bob check a random sample to see if Eve has meddled with their signal. However, because of a theorem in quantum mechanics, called the no-cloning theorem, Eve will not succeed in her task—she would not be able to faithfully copy the polarization of the same photons.

The no-cloning theorem, first formulated by Wootters and Zurek in 1982, states that it is impossible to make a perfect copy of an unknown quantum state11. The reason this is so follows from the principle of superposition which along with Heisenberg’s uncertainty principle is the cornerstone of quantum mechanics. According to the principle of superposition, when two evolving sates are solutions of Schrödinger’s equation, their linear combination is a solution as well. Wootters and Zurek showed that this property of superposition leads to the result that copying of arbitrary quantum states is prohibited in the quantum world.

While the impossibility of cloning makes quantum key distribution tenable, it is a hindrance for developing classical error correction techniques for quantum computers, as we shall see later in this article. Nevertheless, no-cloning has profound implications in quantum cryptography and related fields.

Artur Ekert proposed a method using entangled photons to devise a cryptosystem that guarantees the security of the cryptographic key. A simplified version of this system is due to N. David Mermin of Cornell University according to which Alice generates a number of entangled photons and keeps one member of each pair for herself while transmitting the other to Bob. Some of the photons are immediately tested for eavesdropping while the remainder are stored for later analysis. Just before the key is generated, some of the stored photons are measured and compared. Consistent with the EPR logic, Bob will always obtain 1 when Alice obtains 0, and vice versa, if none of the stored photons were tampered with. If no discrepancies are detected, Alice and Bob measure the remaining stored photons to obtain the desired key.

In 1999, a team of researchers from the National Laboratory was able to send a quantum key through a 31-mile-long optical fiber network providing “strong evidence for the practical feasibility of quantum key distribution over optical fibers for distances suitable for use within a city or a campus like environment.” The signal loss became significant for distances greater than that. The team also used polarized photons to send quantum key information through the air to distances up to 10 miles.

The Los Alamos team plans to take this technology even further by developing a smaller scale version that is capable of being mounted on an Earth orbiting satellite for transmitting quantum keys to distances of hundreds of miles between the satellite and a ground station.

In a paper published in Nature in 2007, Rupert Ursin and collaborators experimentally demonstrated entanglement-based quantum key distribution over 144 km. One photon is measured locally at the Canary Island of La Palma, whereas the other is sent over an optical free-space link to Tenerife, where the Optical Ground Station of the European Space Agency acts as the receiver. This exceeds previous free-space experiments by more than an order of magnitude in distance, and is an essential step towards future satellite-based quantum communication and experimental tests on quantum physics in space.

Because the transmitted photons cannot be intercepted without being destroyed, and the act of interception then tips off the legitimate users, QKD is considered the most powerful data encryption scheme ever developed and its codes are, by all indications, virtually unbreakable.


10. See “The Mathematics of Public-Key Cryptography,” by Martin E. Hellman; Scientific American, August 1979
11. Perfect copying can be achieved when the states are orthogonal.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s