Unbreakable Codes: the path to quantum cryptography
Part 1: From classical encryption to the first quantum algorithm
In WWII, the U.S. Marine Corps enlisted Navajo indians to pass secret messages in the Pacific war theater. These code talkers proved extremely effective, keeping American communication secure through the war's end (as opposed to communication by axis powers). Secure communication has always been vital for states. The rapid rise of the internet and electronic banking has also made it crucial for individuals.
To keep pace with ever-more sophisticated eavesdroppers and hackers, increasingly advanced cryptographic methods are required. Cryptography relies on a set of keys which is shared between the sender and receiver. These keys may just be an uncommon language. But a Navajo indian (or Henry Kissinger clones, for that matter) at everyone's computer would not be practical. Nowadays code talkers are replaced by numerical encryption, most commonly public-key RSA protocols[1].
Cryptography Today
Suppose Bob wants to send an email message to Alice. In the RSA scheme, he asks Alice to send him a particular encoding scheme, called a 'public key.' Alice creates this public key, together with a uniquely matched private key. She sends the public key over the insecure network and keeps the private one. Bob applies the public key -- a series of mathematical operations -- to his message and sends the encrypted message back to Alice over the insecure network. Even though an eavesdropper has access to this public communication, only Alice can unlock the encryption using her private key.
The public and private keys are related to the product N of two large prime numbers. And here's the rub: by finding the prime factors of the public key, a spy can deduce the private key and unlock the code. In fact, all classical encryption scheme rely on the fact that some mathematical operation is computationally difficult. But difficult is not impossible, and so all classical encryption protocols are in fact vulnerable.
The RSA protocol requires a set of public and private keys. If Alice wants to receive a message m from Bob, she first sends him a public key consisting of a set of two numbers (N,E). Bob uses (N,E) to encrypt his message m and sends it back to Alice. Now Alice retrieves m using a private key K that is uniquely matched to the public key (N,E). Thought of another way, Alice gives bob the address (N,E) of a publicly available drop-box that only she can open with her key K .
The RSA protocol, termed so for the initials of its three inventors Ron Rivest, Adi Shamir, and Leonard Adleman, is the most widely used cryptography protocol across the internet. But it is vulnerable. Messages can be decrypted by factoring the public key n into its prime numbers p and q. It is then possible to deduce the private key K .
To date, no efficient method for factoring large N on a classical computer is known to exist. So with a pretty large N, Alice and Bob can be reasonably sure that Eve isn't eavesdropping on their communication. In most RSA implementations, N is 1024–2048 bits long, but experts fear that such a length of N could be hackable in a few years. Already, an N of length 640 bits has been factored (in 2005)[3].
So either you can hope that no-one finds a way to efficiently factor the key N, and puts the algorithm in the next version of Kismac or other public hacking program. If you're not comfortable with that hope, you can instead turn to quantum mechanics for a completely different way.
In 1984, Charles Bennett and Gilles Brassard developed a quantum key distribution protocol now called BB84 (again, after the inventors). Instead of relying on the difficulty of factoring large numbers, it relies on the impossibility of measuring a quantum system without disturbing it. Thus, if Alice and Bob send information over single quantum states -- for example, single photons -- then any attempt by Eve to listen in will disturb the transmission and alert Alice and Bob that their communication is compromised.
Photons are quanta of light energy. They correspond to oscillations of the electromagnetic field. The oscillation direction of the electric field (called polarization) can be in any direction and may be described by any two-dimensional coordinate system, such as "up-down" or "left-right". In a measurement of the photon's polarization, it possible to distinguish perfectly between these two directions of the electric field (for example, send the photons through polarized glasses; if the photon passes, it's a '1' and if it doesn't, it's a '0'). Thus we can use polarized photons to transmit binary information; for example, we can call up-down a '0' and left-right a '1'.
Of course, there's nothing special about the directions up-down and left-right. We could equally well rotate our coordinate system 45 degrees clockwise, and call these two diagonal directions our 1s and 0s. Let's this coordinate system '45deg' (x) and the earlier one '0deg' (+).
To understand BB84 quantum cryptography, we need a few rules that follow from quantum mechanics. The rules of the game are:
1. If you measure a photon in the same coordinate system as it was sent, then you measure its bit (0 or 1) correctly. If you measure in the wrong coordinate system, then you randomly measure 0 or 1, regardless of the actual polarization of the photon -- i.e., you loose all information.
2. When you measure a photon in the wrong coordinate system, you alter it.
3. It's not possible to copy photons ('no-cloning theorem')
Now Alice and Bob can create a secret key as follows (refer to the diagram below). Alice sends Bob a stream of photons, encoding either 1 or 0 (Alice records which). Each photon is sent randomly in either the 0deg or 45deg coordinate system. Bob then measures each photon in a coordinate system which he randomly chooses.
Then Alice announces publicly which coordinate system she used to send each photon. Bob will find that about half of the time, he randomly chose the right coordinate system and throws out all the records where he chose the wrong one. In this way, he distills all the transmissions down to a set where he knows that he correctly measured 0s or 1s from Alice's photons. Thus Alice and Bob know that they've created a secure key.
Before discussing how quantum cryptography foils Eve's attempts at spying on the message, the reader may be interested in this YouTube video discussing a recent implementation of a quantum cryptographic system very similar to the one we discussed.
3
