Frontiers of secrecy - the story of Eve, Alice and Bob

Oxford Mathematician Artur Ekert describes how his research in to using Quantum properties for cryptography led to some very strange results.

"The most secure methods of communication rely on pre-distributed, random and secret sequences of bits, known as cryptographic keys. Any two parties who share the key, we call them Alice and Bob (not their real names, of course), can then use it to communicate secretly. The key bits must be truly random, never reused, and securely delivered to Alice and Bob, which is by no means easy for Alice and Bob may be miles apart. Still, it can be done. About thirty years ago my work triggered an active field of research by showing that quantum entanglement and peculiar non-local quantum correlations can be used for secure key distribution. More recently, building upon this work, cryptologists started probing the ultimate limits of security and showed that what looks like an insane scenario is actually possible - devices of unknown or dubious provenance, even those that are manufactured by our enemies, can be safely used to generate secure keys.

In this more dramatic version, known as the device independent scenario, an omniscient adversary, called Eve, is in charge of the key distribution. She prepares two sealed and impregnable devices, and gives one to Alice and one to Bob. The inner working of the devices is unknown to Alice and Bob but they can take them to their respective locations and probe them with randomly and independently chosen binary inputs to which the devices respond with binary outputs. For Alice's and Bob's inputs and y their devices generate outputs a and b, respectively. If in the repetitive use the responses of the two devices show a certain pattern then the output bits can be turned into a secret key.

At first this narrative makes no sense. Surely, if Eve manufactured the two devices she must also have pre-programmed them, and hence she would know how they respond to all possible inputs, which, of course, renders the resulting keys insecure. Surprisingly enough, if Alice and Bob prepare their inputs freely, so that Eve does not know in advance which inputs will be chosen in each run, and the devices are kept separated and incommunicado, then some patterns of outputs cannot be pre-programmed. For example, requesting that in each run the outputs are identical for all inputs except when Alice prepares input 1 and Bob prepares input 1, in which case the outputs must be different, that is \[ x y=a\oplus b, \] defeats the coding prowess of any, no matter how powerful, Eve. The best Eve can do in this case is to have this request satisfied in 75% runs of the devices. Anything more than 75% indicates outputs that are not pre-programmed or pre-determined and hence unknown to any third party, Eve included. No classical devices can deliver such a correlated performance but quantum devices can, pushing the success rate to roughly 86%. Thus, if Eve is prepared to offer Alice and Bob quantum devices that beat the 75% classical limit she has to concede that at least some of the outputs bits will be unknown to her. Alice and Bob infer how much Eve knows about the output bits from the success rate and then, if Eve does not know too much, they can use conventional cryptographic tools to turn the partially secret bits into fewer secret ones, which will then form a cryptographic key.

The key distribution proceeds as follows. Alice and Bob run their devices choosing their inputs randomly, and independently from each other. In each run, once the outputs are registered, Alice and Bob communicate in public, with Eve listening, and reveal their inputs, but not the outputs. The repetitive use of the devices results in two binary output strings, one held by Alice and one by Bob. In a subsequent public communication, again with Eve listening, Alice and Bob agree on a random sample of the recorded runs for which they reveal the outputs. This allows them to estimate the success rate on the data in the fully disclosed runs. If the estimated success rate is below 75% the key distribution is abandoned, otherwise Alice and Bob turn the remaining undisclosed outputs into a secret key.

Needless to say, proving security under such weak assumptions, with all the nuts and bolts, is considerably more challenging than in the case of trusted devices. Between the two extremes - at the success rate of 75% Eve may know everything about the key and at 86% Eve knows nothing - lies an important uncharted twilight zone. Suppose the success rate is 80% then what? We must put an upper bound on Eve's knowledge for any intermediate success rate, as this determines how Alice and Bob turn their raw output strings into a shorter but secret key. This is not easy.

The important technical figure of merit to be evaluated here is called (just in case you want to impress your friends with the mathematical lingo) "the conditional smooth min-entropy", and it should be expressed as a function of the success rate. This quantity determines the length of the final key that can be distilled from a given raw output, but deriving it required considerable mathematical gymnastics. The early results provided an explicit expression for the asymptotic key rate (the ratio between the distillable key length and the length of raw output in the limit of a large number of runs), but the analysis applied only to cases where the devices behaved in the same way in each run, unaffected by the previous or subsequent runs. This is known as the independent and identically distributed (i.i.d.) assumption. At the time even the most fervent advocates of the device independent cryptography had to admit that the result, as neat as it was, had no direct bearing on the device independent scenario, for Eve can manufacture the devices as she sees fit, making successive outputs dependent on what happened in all the previous runs. More recently, the most general case has been finally worked out. It turns out that a realistic device independent scenario can be reduced to the i.i.d. case, showing that Eve cannot do better than making each run of the devices independent from and statistically identical to all other runs. This is of great comfort to both mathematicians and experimentalists for it shows that reasonable key rates can be achieved even in noisy implementations.

One should perhaps mention that the device independent scenario does not have to involve untrusted devices. The protocol is more likely to offer an additional security layer to quantum cryptography with trusted devices, protecting against attacks that exploit unintentional flaws in the design. What is crucial here, however, is the assumption that Alice and Bob prepare their respective inputs randomly and independently from each other. If Alice's and Bob's choices were known in advance then Eve can easily pre-program the results and Alice and Bob would foolishly believe that they generated a secret key. However, as long as Alice's and Bob's choices are their own, unknown and unpredictable, then the most mind-boggling cryptographic scheme ever proposed works just fine and can see the light of the day sooner than many of us expected."