Given the continual press coverage of the insecurity of electronic information, it is amazing to realise that the solution to the problem of the perfect cipher, the technique for absolute disguise of a message from unintended recipients, has been known for a century, and is remarkably simple. To implement the Vernam cipher, the sender, who we call Alice for lack of imagination, simply expresses the text that she wants to send in binary, a string of 0s and 1s. Call this a. If she and Bob, the intended recipient, already share a random string of bits of the same length (or longer), b, then Alice computes the addition modulo 2 of the two strings and sends that to Bob, $M=a\oplus b$. When he receives M, he can decode that message by also adding on b: $M\oplus b=a\oplus b\oplus b=a$, so he perfectly recovers Alice’s message. On the other hand, anybody who doesn’t know what b is cannot decode the message. All possible bit strings are equally likely, so you can’t just guess. You can’t even keep making guesses until you find a message that isn’t just a string of gobbledygook – going through all possible guesses of b returns all possible initial strings, including all feasible messages of the same length as the real message, with nothing to pick between them, provided Alice and Bob never reuse the string b.

The reason why this cipher is not applied more extensively is the practical problem of key distribution – you have to make sure that Alice and Bob share the same string b and that nobody else is able to get hold of it, and they must not reuse it. In cases where Alice and Bob meet regularly, this presents little problem, but in this age of massive, worldwide, data consumption, this situation is rarely realistic. Instead, imperfect solutions such as public key cryptography abound. Their security is founded only on the assumption that certain functions are impractical for a computer (or set of computers) to evaluate in a reasonable time. It is fitting that the same quantum technology that promises to bring these assumptions crashing down also provides the solution; a way of testing the incoming data in a key distribution scenario that proves that nobody else has read or copied this data. Moreover, it is not even necessary to know any details of quantum mechanics. You simply have to believe that information cannot travel faster than some upper limit, the speed of light.

The main component of such a proof is known as a Bell test. The term Bell test refers to a general class of possible tests, but we will only consider a specific one, known as CHSH after its inventors Clauser, Horne, Shimony and Holt. The CHSH test is best viewed as a game between 3 players – Alice, Bob and Eve. In each round of the game, Alice and Bob each ask Eve one of two questions, to be chosen completely at random. Let’s denote their individual choices by x_A and x_B respectively (each either 0 or 1), and Eve will answer each of them with answers y_A and y_B respectively, which either take values +1 or -1. Eve wins a point if her answers satisfy $y_Ay_B=(-1)^{x_Ax_B}$, and loses a point otherwise. The aim of the game is for Eve to score as highly as possible. As expressed, this game is trivial and boring. Whatever questions Eve is asked, she can use the values x_A and x_B to figure out what answers she should give, and she always wins, giving an average score of S=1.

Instead, let us alter the game a bit. Alice and Bob move a long way apart. They will ask their questions (approximately) simultaneously, and demand the answers be given to them in a time that is much less than the time it takes for light to travel between Alice and Bob. The only way that Eve can operate under this scenario is to split herself into two agents, one near Alice and the other near Bob. These agents will receive the respective question and can only act based on that information. They cannot know the other question because the information about what the question is does not have enough time to travel to that agent before the question has to be answered.

What is Eve’s best strategy in this situation? There are certainly valid strategies in which she can score S=˝. For example, whatever question each agent is asked, they could always answer +1. Thus, she always gets the correct answer for question pairs (0,0), (0,1) and (1,0). However, she always gets the (1,1) question wrong. Any other such strategy has a similar conclusion; she always gets either 1 or 3 questions wrong. If this is the best that a deterministic strategy can achieve, then it’s also the best a probabilistic strategy can achieve. So, if Eve has a pre-determined strategy for trying to win the game, even a probabilistic one, she can never score better than S=˝.

How can this be used as the basis of a key distribution protocol? Let’s say some information is to be shared between Alice and Bob. They need key distribution because they are distantly separated from each other. They both have secure labs, and anything that happens inside those labs cannot be communicated to the outside unless Alice/Bob chooses to do so. Alice and Bob are going to buy a device or piece of software off an external company “Eve” which claims to perform a particular protocol which can be used to implement a secure key distribution protocol. This hardware/software has to be assumed to be an agent of Eve’s that Alice and Bob each take into their labs (but, note, they cannot report information back to the main Eve, outside the labs, who is the person they want to exclude from the communication). One of the main functions is to be able to play the CHSH game. If Eve ever scores $S\leq\half$, which will be ascertained by Alice and Bob communicating a proportion of their results over a public channel, Alice and Bob know that those results can be described by a pre-defined strategy. Being truly paranoid, if their results could be explained by the intervention of a malicious party, then it must be assumed that such a party exists, and knows everything. On the other hand, if the score were somehow greater than a half, the two agents of Eve must be acting in a different way that is not entirely pre-programmed by Eve. The extent to which it violates this threshold conveys how little information Eve must have, and hence about how much privacy amplification is sufficient to exclude Eve from any distributed key.

At this point, you may be tearing your hair out! We started by arguing that the CHSH score cannot be greater than a half, but now we’re suddenly relying on that as a no eavesdropping proof. That’s all well and good, but only suggests that you would never pass the test! This is where quantum mechanics steps in. Einstein was famously quoted as saying “God doesn’t play dice”. In this, he was expressing his belief that any measurable entity in the physical world must have a predetermined value before measurement; the answers to measurements are not random at all, it’s just our lack of information that makes them appear random (compare this to eavesdropping – if a measurement has a predetermined value, that can be read by an eavesdropper without changing the system). On this, Einstein was mistaken, and the CHSH test constitutes the refutation. Any system with predetermined values scores $S\leq\half$. On the other hand, if we let Alice and Bob’s questions specify measurement settings on a quantum system, it turns out that S can be as large as $\frac{1}{\sqrt{2}}\approx 0.707$ for the right set of measurements and quantum state. They cannot have been predetermined, and there is some sort of “collapse” to the given answer when the measurement is made. Such values are now routinely measured in laboratories around the world. If the measurement results could not possibly have been predetermined, and are only “decided” at the moment that the measurement is made, and yet the random answers are correlated between Alice and Bob, then this is exactly what they need for generating a secure key.

The Bell test constitutes the main ingredient of the quantum key distribution so, with this tool in place, let’s properly describe the protocol. Alice and Bob put out a tender for a pair of boxes with the following specifications:

• Alice’s box must have 3 buttons (0, 1 and 2), and a readout consisting of two possible answers +1 and -1.
• Bob’s box must have 2 buttons (0 and 1), and a readout consisting of two possible answers +1 and -1.
• When any button is pressed, an answer must be presented on the corresponding readout within a time t.
• If Alice presses button 2, and Bob presses button 1, the answers must be opposite, y_Ay_B=-1.
• If Alice presses buttons 0 or 1, and Bob presses either button, the answers must contribute to as large an average CHSH score as possible, say $\frac{1}{\sqrt{2}}$.

While Alice and Bob could specify what they want their boxes to do at a more physical level rather than this abstract one, all such specifications are equivalent and the beauty of this scheme is that they are irrelevant; it is not necessary to rely on the precise generation of a specific quantum state and our ability to correctly characterise it. We perform these simple checks and that’s all that will be necessary because the CHSH test is physics-agnostic – its only concern is with the possible correlations of random variables.

Once their supplier has been chosen, Alice and Bob take their boxes and head to distant locations, separated by a distance much greater than the distance light can travel in time t. They will then coordinate many repetitions of (approximately) simultaneous button presses, recording their choices of button press and corresponding answers. While Bob picks completely at random between his two choices, Alice chooses 0 or 1 with equal probability, but chooses 2 with a different bias. The boxes give random (but partially correlated) answers. After recording a large amount of this data, Alice and Bob publicly announce their choices of button press. In the instances where Alice pressed 0 or 1 (green rows of Table 1), the pair of boxes must behave exactly like the pair of agents for Eve, who are playing (and trying to win) the CHSH game. In such cases, Alice and Bob both announce the corresponding answers as well. This lets them compute the score for the CHSH game, S (the last column) and to average it¹. If Alice pressed 2 and Bob pressed 0, as will happen in some fraction of runs, they should have some perfectly (anti)correlated data that constitutes the shared key. In their public communication stage, they select a small fraction of these instances to announce the answers of, just to check that the boxes are behaving as claimed (and, if not, to establish the degree of error correction required). Most of these results are not announced, and are hopefully secret, and we now use the value S to determine just how secret they can be safely considered to be.

Firstly, it helps to recognise that an eavesdropper could never hope to guess which instances Alice presses 2 and only eavesdrop those (at both locations). The success probability of such a strategy vanishes exponentially in the number of rounds that Alice and Bob use. Hence, the degree of eavesdropping on the CHSH test portion of the protocol is representative of the degree of eavesdropping on the key generation component. The degree of secrecy of the string depends on paranoia levels. If one is willing to believe in quantum mechanics as the foundation of the ultimate physical laws or that, at least, nobody has any better ideas at the moment, and certainly isn’t implementing technology based on it, then $S=\frac{1}{\sqrt{2}}$ proves that no eavesdropping occurred whatsoever. Values $\half\lt S\lt \frac{1}{\sqrt{2}}$ indicate that some eavesdropping has potentially occurred, and imposes a level of privacy amplification that Alice and Bob should apply to their key before use. The ultra-paranoid among you may not be willing to believe in quantum mechanics. Nevertheless, it is clear that it is impossible to score larger than 1 in the CHSH game. Hence, if Eve attempts to eavesdrop a fraction of cases p, the ultimate CHSH score is S=˝p+(1-p). At this point, Eve would have full knowledge of a fraction p of the cases, and would be able to just guess all the other bits and be right half the time, so she’d know a fraction p+(1-p)/2=3/2 -S of the bits. This parameter defines the level of privacy amplification applied.

With a shared, secret, key in place, Alice and Bob can proceed with communication using the Vernam cipher.

Technologically, quantum key distribution schemes have matured to the level of being able to distribute a key over distances of up to about 250km, and, given that this is much longer than the optical path through the atmosphere and into orbit, investigations are already underway for how one might use a satellite to route pairs of entangled photons between Alice and Bob when separated by much greater distances. One can even buy commercial quantum cryptography systems (although these are based on slightly different protocols than the one described here). However, in truth, while the CHSH test is routinely violated in laboratories around the world, we cannot claim to have implemented the key distribution protocol as stringently as defined here. These experiments have primarily been geared towards verifying the violation of the CHSH threshold, and all have shortcomings. However, we believe the results because it would be crazy indeed if Nature could selectively violate different shortcomings depending on which are available for exploitation. Of course, such power is freely available to an eavesdropper! Some of these primary shortcomings, or loopholes, are merely engineering problems that will be solved with time and, indeed, the timescales are anticipated to be short. These include the locality loophole, when it is not possible to sufficiently separate Alice and Bob compared to the time that a measurement takes (allowing an adversary to give answers based on simultaneous knowledge of both button presses), and the measurement loophole, when it cannot be guaranteed that a measurement gives the correct answer (or even gives an answer at all). However, some loopholes are more fundamental, such as the problem of “free will”. An absolutely essential step in the proof is the assumption that Alice and Bob can independently and randomly select the questions they ask in the CHSH test. This might seem reasonable at small data rates, with Alice and Bob explicitly making such choices (if an eavesdropper can directly manipulate these choices, the final message is hardly going to be secure anyway²). At higher data rates, it would be preferable to replace the decision making with a random number generator, but this could also be manipulated by an eavesdropper to skew the results. This issue remains an area of active research.

As with any cryptography scheme, there is always the risk of a gap between the theoretical specification of the protocol and its implementation, leaving it open to attack. Equally, there is the “secure labs” assumption. We can’t do anything about proving the labs are secure, but some such assumption must be applied in both quantum and classical cryptography, otherwise the theorist can never get started, but it is down to the experimentalist to achieve the best available approximation to this assumption. The classic example is in the earliest implementation of a quantum cryptography scheme, the devices used to change between the different measurement bases (corresponding to the different button presses) could be audibly heard to make their change. Many known issues that must be handled are described in this paper. While such vulnerabilities have been used to eavesdrop on established practical devices without any apparent disturbance, these hacks require a new level of knowledge, that of practical hardware that functions at the quantum level. This particular instance, for example, used a method of “blinding” a photon detector, knowing that there is a way of pushing it outside its intended operating regime which can nevertheless fake the intended functionality. Security through obscurity provides little defence, but heralds the requirement for a different skill set in the security researchers and hackers of tomorrow.