Device-independent quantum cryptography

Mayers and Yao[1] proposed the idea of designing quantum protocols using "self-testing" quantum apparatus, the internal operations of which can be uniquely determined by their input-output statistics. Subsequently, Roger Colbeck in his Thesis[2] proposed the use of Bell tests for checking the honesty of the devices. Since then, several problems have been shown to admit unconditional secure and device-independent protocols, even when the actual devices performing the Bell test are substantially "noisy," i.e., far from being ideal. These problems include quantum key distribution,[3][4] randomness expansion,[4][5] and randomness amplification.[6]

The goal of quantum key distribution is for two parties, Alice and Bob, to share a common secret string through communications over public channels. This was a problem of central interest in quantum cryptography. It was also the motivating problem in Mayers and Yao's paper.[1] A long sequence of works aim to prove unconditional security with robustness. Vazirani and Vidick[3] were the first to reach this goal. Subsequently, Miller and Shi[4] proved a similar result using a different approach.

The goal of randomness expansion is to generate a longer private random string starting from a uniform input string and using untrusted quantum devices. The idea of using Bell test to achieve this goal was first proposed by Roger Colbeck in his Ph.D. Thesis.[2] Subsequent works have aimed to prove unconditional security with robustness and the increase the rate of expansion. Vazrani and Vidick were the first to prove full quantum security for an exponentially expanding protocol.[7] Miller and Shi[4] achieved several additional features, including cryptographic level security, robustness, and a single-qubit requirement on the quantum memory. The approach was subsequently extended by the same authors to show that the noise level can approach the obvious upper bound, when the output may become deterministic.[5]

The goal of randomness amplification is to generate near-perfect randomness (approximating a fair coin toss) starting from a single source of weak randomness (a coin each of whose tosses is somewhat unpredictable, though it may be biased and correlated with previous tosses). This is known to be impossible classically.[8] However, by using quantum devices, it becomes possible even if the devices are untrusted. Roger Colbeck and Renato Renner were motivated by physics considerations to ask the question first.[9] Their construction and the subsequent improvement by Gallego et al.[10] are secure against a non-signalling adversary, and have significant physical interpretations. The first construction that does not require any structural assumptions on the weak source is due to Chung, Shi, and Wu.[6]