Follow up to last-week’s post on the EPR paper, a guest post by Roger Colbeck on its significance for cryptography.
80 years ago, Einstein, Podolsky and Rosen put to paper an argument that the use of the wave function for describing the state of a physical system is incomplete [7]. Looking back, it is remarkable to see where their complaint about the status of the theory—that it is merely part of a deeper, more prescriptive theory—has led. Arguably the whole field of device-independent cryptography can be traced back to this. This field is about the use of a stronger notion of security for information processing tasks, such as the transmission of private messages and gives a means to certify the generation of random numbers. In this post I will discuss the first of these and its connection to the EPR thought experiment.
First the experiment. EPR imagined two particles that interact, forming an entangled state, after which they separate and are measured. EPR’s original example involved particles whose positions and momenta are correlated; Bohm later simplified this [5] to an experiment in which the same component of spin is measured on each particle resulting in outcomes that are perfectly anti-correlated—that is, they always yield opposite results.
But what does this have to do with cryptography? Imagine two parties, Alice and Bob, want to communicate in secret. Perhaps Alice would like to buy something from Bob and needs to tell him her credit card number, for example. A proven means of doing this is using a one-time pad, a sequence of random numbers shared between Alice and Bob. If this sequence is as long as the message Alice wants to send, then Alice can encode her message such that it is only readable by someone with the pad (Bob). However, how can two parties set up such a pad without the inconvenience of meeting? It turns out that there is no provably secure way to do this by classical means; an all-powerful eavesdropper listening in to Alice and Bob’s attempt to do so can always learn the sequence on the pad in principle.
Enter quantum theory. Its power for cryptography was first realized by Wiesner in the early 70s (although published much later [9]), and in 1984 led Bennett and Brassard [4] to come up with (what we now know to be) a provably secure means for establishing a one-time pad between distant parties, called BB84, and hence for performing secure communication. There is already an interesting connection to EPR. In order to prove the BB84 protocol secure, one needs to model what an eavesdropper can do. It is natural to limit her to any action allowed in quantum theory but in doing so the proof is implicitly relying on quantum theory being compete. Had EPR been correct, i.e., were this not the case, an eavesdropper with knowledge of the complete theory might break the scheme.
However, there is an even deeper relation to EPR that was discovered by Ekert in 1991 [8]. He suggested a cryptographic protocol that is conceptually different from BB84 and based on the EPR-Bohm setup, or, more precisely, Bell’s generalization of it. How does this work, and why is Bell’s generalization needed?
In the EPR-Bohm experiment, distant particles measured in a fixed way generate perfectly anti-correlated outcomes (“up” / “down” or “down” / “up”). This already looks like a promising way to set up a one-time pad. If Alice and Bob perform these measurements and Bob flips his outcome (turning anti-correlation to correlation), then Alice and Bob can share a sequence of random bits. However, the essence of the EPR argument is that the observation of anti-correlation between distant particles has an explanation more natural than the one quantum mechanics prescribes: the same correlations would be observed if the source simply tagged the left-going particle with “up” and the right-going one with “down”, or vice-versa with probability ½ each.
Were this the true underlying picture, sharing EPR pairs would not be useful for cryptography: a sophisticated agent who could read the tag of the particle heading to Bob could share the same anti-correlation with Alice, and hence know the one-time pad. The great leap made by Bell was to adjust EPR’s setup by allowing Alice and Bob to make different measurements. Bell showed that if the distribution of measurement outcomes follows quantum theory, and if the choice of measurement on one side has no influence on the outcome of the other, then the joint statistics of these measurements are such that no such tag can exist [3]. Said another way, if there were some information that would allow Bob’s outcome to be perfectly predicted, then the particles couldn’t reproduce the statistics predicted by quantum theory. This is the essence of why this is useful for cryptography.
It was several years before the full significance of Ekert’s idea was realized. Since the argument for a lack of such a tag relies only on the observed statistics then it is irrelevant how the devices are doing this. They could be old or damaged or too hot, or may even have been tampered with by a malicious adversary! Remarkably none of this matters. Either they reproduce the expected correlations in which case Alice and Bob can make a secure one-time pad, or else not, in which case they abort. In the latter case the message remains secure, since it is only used after a pad has been successfully generated. This has been termed device-independent cryptography [1].
Like in the discussion of BB84 above, many device-independent protocols assume an eavesdropper limited by quantum theory, and hence also implicitly assume quantum theory to be complete. However, in a remarkable work from 2005, Barrett, Hardy and Kent (BHK) showed this assumption to be unnecessary [2]. More precisely, they gave a protocol and showed that it is secure against an eavesdropper who can exploit any potential post-quantum theory provided it does not permit signalling. Their result hinges on a particular set of correlations—stronger even than those considered by Bell—for which quantum theory is complete in an even deeper sense than EPR asked for: not only can there be no tag that betrays Bob’s outcome perfectly, but no information accessible to an agent in any non-signalling theory can enable any prediction about Bob’s outcome that is more precise than the quantum one. This idea has been developed into a general completeness theorem for quantum mechanics [6].
Thus the contemplations of EPR acted as the seed of what has become a rather grand tree. It is one that took a long time to grow, but now device-independent information processing has seen numerous applications and has developed into a field in its own right. Without a doubt, no-one could have anticipated such a legacy back in 1935.
[1] A. Acín, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, “Device-Independent Security of Quantum Cryptography Against Collective Attacks,” Phys. Rev. Lett. 98, 230501 (2007).
[2] J. Barrett, L. Hardy, and A. Kent, “No Signalling and Quantum Key Distribution” Phys. Rev. Lett. 95, 010503 (2005).
[3] J.S. Bell, “On the Einstein-Podolsky-Rosen Paradox.” Physics 1, 195-200 (1964).
[4] C.H. Bennett and G. Brassard, “Quantum cryptography: Public Key Distribution and Coin Tossing” in Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing (IEEE, New York, 1984), pp. 175–179.
[5] D. Bohm, Quantum Theory, New York: Prentice Hall (1951).
[6] R. Colbeck and R. Renner “The completeness of quantum theory for predicting measurement outcomes”, arXiv:1208.4123 (2012).
[7] A. Einstein, B. Podolsky, and N. Rosen “Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?” Physical Review 47, 777-780 (1935).
[8] A. K. Ekert, “Quantum Cryptography Based on Bell’s Theorem” Phys. Rev. Lett. 67, 661 (1991).
[9] S. Wiesner, “Conjugate coding”, SIGACT News, 15, pp. 78–88, (1983).
