A quantum cryptographic protocol is device-independent if its security does not rely on trusting that the quantum devices used are truthful. Thus the security analysis of such a protocol needs to consider scenarios of imperfect or even malicious devices. Several important problems have been shown to admit unconditional secure and device-independent protocols. A closely related topic (that is not discussed in this article) is measurement-device independent quantum key distribution.

Overview and history

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]

Key distribution

This section needs expansion with: significant works between the Colbeck thesis and the full security proofs. You can help by adding to it. (February 2015)

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.[citation needed] Vazirani and Vidick[3] were the first to reach this goal. Subsequently, Miller and Shi[4] proved a similar result using a different approach.

Randomness expansion

This section needs expansion with: unbounded expansion. You can help by adding to it. (February 2015)

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.[citation needed] 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]

Randomness amplification

This section needs expansion with: physical interpretations. You can help by adding to it. (February 2015)

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]

References

  1. ^ a b Mayers, Dominic; Yao, Andrew C.-C. (1998). Quantum Cryptography with Imperfect Apparatus. IEEE Symposium on Foundations of Computer Science (FOCS). arXiv:quant-ph/9809039. Bibcode:1998quant.ph..9039M.
  2. ^ a b Colbeck, Roger (December 2006). "Chapter 5". Quantum And Relativistic Protocols For Secure Multi-Party Computation (Thesis). University of Cambridge. arXiv:0911.3814.
  3. ^ a b Vazirani, Umesh; Vidick, Thomas (2014). "Fully Device-Independent Quantum Key Distribution". Physical Review Letters. 113 (14): 140501. arXiv:1210.1810. Bibcode:2014PhRvL.113n0501V. doi:10.1103/physrevlett.113.140501. PMID 25325625. S2CID 119299119.
  4. ^ a b c d Miller, Carl; Shi, Yaoyun (2016). "Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices". Journal of the ACM. 63 (4): 33. arXiv:1402.0489. doi:10.1145/2885493. S2CID 53234710.
  5. ^ a b Miller, Carl; Shi, Yaoyun (2017). "Universal security for randomness expansion". SIAM Journal on Computing. 46 (4): 1304–1335. arXiv:1411.6608. doi:10.1137/15m1044333. S2CID 6792482.
  6. ^ a b Chung, Kai-Min; Shi, Yaoyun; Wu, Xiaodi (2014). "Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions". arXiv:1402.4797 [quant-ph].
  7. ^ Vazirani, Umesh; Vidick, Thomas (2012). "Certifiable quantum dice: or, true random number generation secure against quantum adversaries". The 44th Symposium on Theory of Computing (STOC). pp. 61–76.
  8. ^ Miklos Santha, Umesh V. Vazirani (1984-10-24). "Generating quasi-random sequences from slightly-random sources" (PDF). Proceedings of the 25th IEEE Symposium on Foundations of Computer Science. University of California. pp. 434–440. ISBN 0-8186-0591-X. Retrieved 2006-11-29.
  9. ^ Colbeck, Roger; Renner, Roger (2012). "Free randomness can be amplified". Nature Physics. 8 (6): 450–453. arXiv:1105.3195. Bibcode:2012NatPh...8..450C. doi:10.1038/nphys2300. S2CID 118309394.
  10. ^ Gallego, Rodrigo; Masanes, Lluis; De La Torre, Gonzalo; Dhara, Chirag; Aolita, Leandro; Acín, Antonio (2014). "Full randomness from arbitrarily deterministic events". Nature Communications. 4: 2654. arXiv:1210.6514. Bibcode:2013NatCo...4.2654G. doi:10.1038/ncomms3654. PMID 24173040. S2CID 14630558.
Category