142 COMMUNICATIONS OF THE ACM | APRIL 2019 | VOL. 62 | NO. 4 correlations. Although the relevance of non-local correlations for cryptography was already pointed out by Ekert, the first concrete results considered the related task of randomness amplification, in which a single user, Alice, wishes to certify that two devices in her possession generate random bits, while using as few possible seed bits of randomness to test the device.

A protocol for randomness certification was first proposed in Colbeck, 10 and the task was experimentally demonstrated in 2012.25 Some of the ideas present in this paper were first formulated in the analysis of a protocol for exponential randomness expansion we introduced in previous work of the authors; 34 subsequently it was shown that even unbounded expansion is possible. 11

Subsequent to our work on quantum key distribution a second proof of security for DIQKD was put forward in Miller and Shi. 23 Neither proof achieves practical parameters, a gap recently filled by a third proof3 which establish security of a protocol with essentially optimal noise tolerance and key rate. Although the three proofs inevitably bear some similarity, they seem to rely on essentially different arguments; it remains a challenge to find a unifying framework for device-independence that would combine their respective advantages.

Recent progress in experiments15, 18, 30 place the implementation of protocols for entanglement-based quantum key distribution just around the corner. One may even start to see emerging the possibility for entanglement generation not only between single-qubit devices, as are needed for QKD, but small multi-qubit “quantum computers in the cloud” such as the one recently demonstrated by IBM. Computing devices sharing quantum entanglement may be able to implement tasks beyond quantum key distribution, from simple protocols such as, for example, quantum secret sharing or entanglement swapping, to the complex task of verifiable delegated computation. Although this remains a distant prospect, it is our hope that the techniques developed in this work will find far broader applicability in the future of quantum cryptography!

Acknowledgments

We thank the Communications editors and Gilles Brassard for useful feedback on an earlier version of this article.

Umesh Vazirani is supported by NSF Grant CCF-1410022, MURI Grant FA9550-18-1-0161 and a Vannevar Bush Faculty Fellowship. Thomas Vidick is supported by AFOSR YIP award number FA9550-16-1-0495, MURI Grant FA9550-18-1-0161, and a CIFAR Azrieli Global Scholar award.

8. Brassard, G., Lütkenhaus, N., Mor, T., Sanders, B.C. Limitations on practical quantum cryptography. Phys. Rev.

Lett. 85 (Aug 2000), 1330–1333.

9. Clauser, J. F., Horne, M. A., Shimony, A.,
Holt, R.A. Proposed experiment to
test local hidden-variable theories.

Phys. Rev. Lett. 23 (1969), 880–884.

10. Colbeck, R. Quantum and Relativistic Protocols for Secure Multi-Party Computation. PhD thesis, Trinity College, University of Cambridge, Cambridge, UK, Nov. 2006.

11. Coudron, M., Yuen, H. Infinite randomness expansion with a constant number of devices. In

Proceedings of the 46th Annual ACM Symposium on Theory of Computing

(ACM, 2014), 427–436.

12. De, A., Portmann, C., Vidick, T., Renner, R. Trevisan’s extractor in the presence of quantum side information. SIAM J.

Comp. 41, 4 (2012), 915–940.

13. Einstein, A., Podolsky, P., Rosen, N. Can quantum-mechanical description of physical reality be considered complete?

Phys. Rev. 47 (1935), 777–780.

14. Ekert, A.K. Quantum cryptography based on Bell’s theorem. Phys. Rev.

Lett. 67 (1991), 661–663.

15. Giustina, M., Versteegh, M.A., Wengerowsky, S., Handsteiner, J., Hochrainer, A., Phelan, K., Steinlechner, F., Kofler, J., Larsson, J.-Å., Abellán, C., et al. Significant-loophole-free test of Bell’s theorem with entangled photons. Phys. Rev.

Lett. 115, 25 (2015), 250401.

16. Goldwasser, S., Micali, S. Probabilistic encryption & how to play mental poker keeping secret all partial information.

In Proceedings of the fourteenth annual ACM symposium on Theory of computing (ACM, 1982), 365–377.

17. Hausladen, P., Wootters, W.K. A “pretty good” measurement for distinguishing quantum states. J.

Mod. Opt. 41, 12 (1994), 2385–2390.

18. Hensen, B., Bernien, H., Dréau, A.E., Reiserer, A., Kalb, N., Blok, M.S., Ruitenberg, J., Vermeulen, R.F., Schouten, R.N., Abellán, C., et al.

Loophole-free bell inequality violation using electron spins separated by 1. 3 kilometres. Nature

526, 7575 (2015), 682–686.

19. Kalai, Y. T., Raz, R., Rothblum, R. D. How to delegate computations: the power of no-signaling proofs. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing

(ACM, 2014), 485–494.

20. Lydersen, L., Wiechers, C., Wittmann, C., Elser, D., Skaar, J., Makarov, V. Hacking commercial quantum cryptography systems by tailored bright illumination.

Nat. Photonics 4, 10 (2010), 686–689.

21. Mayers, D. Unconditional security in quantum cryptography. J. ACM 48, 3

(May 2001), 351–406.

22. Mayers, D., Yao, A. Quantum cryptography with imperfect apparatus. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS ‘ 98 (IEEE Computer Society, 1998), Washington, DC, USA, 503.

23. Miller, C.A., Shi, Y. Robust protocols
for securely expanding randomness
and distributing keys using untrusted
quantum devices. J. ACM 63, 4 (2016), 33.
24. Pironio, S., Acín, A., Brunner, N., Gisin,
N., Massar, S., Scarani, V. Device-
independent quantum key distribution
secure against collective attacks.
New J. Phys. 11, 4 (2009), 045021.
25. Pironio, S., Acin, A., Massar, S., De
La Giroday, A.B., Matsukevich, D.N.,
Maunz, P., Olmschenk, S., Hayes, D.,
Luo, L., Manning, T.A., et al. Random
numbers certified by Bell’s theorem.
Nature 464, 7291 (2010), 10.
26. Raz, R. A parallel repetition theorem.
SIAM J. Comput. 27 (1998), 763–803.
27. Reichardt, B. W., Unger, F., Vazirani, U.
Classical command of quantum
systems. Nature 496, 7446 (2013), 456.
28. Rivest, R.L., Shamir, A., Adleman, L.
A method for obtaining digital signatures
and public-key cryptosystems.
Comm. ACM 21, 2 (1978), 120–126.
29. Scarani, V., Gisin, N., Brunner, N.,
Masanes, L., Pino, S., Acín, A. Secrecy
extraction from no-signaling correlations.
Phys. Rev. A 74, (Oct 2006), 042339.
30. Shalm, L.K., Meyer-Scott, E.,
Christensen, B.G., Bierhorst, P.,
Wayne, M.A., Stevens, M.J., Gerrits, T.,
Glancy, S., Hamel, D.R., Allman, M.S.,
et al. Strong loophole-free test of
local realism. Phys. Rev. Lett. 115, 25
(2015), 250402.

31. Shor, P. W., Preskill, J. Simple proof of security of the BB84 quantum key distribution protocol. Phys. Rev. Lett. 85 (Jul 2000), 441–444.

32. Tomamichel, M., Schaffner, C., Smith, A., Renner, R. Leftover hashing against quantum side information. IEEE Transactions on Information Theory 57, 8 (2011), 5524–5535.

33. Trevisan, L. Extractors and pseudorandom generators. J. ACM 48 (July 2001), 860–879.

34. Vazirani, U., Vidick, T. Certifiable
quantum dice: Or, true random
number generation secure against
quantum adversaries. In Proceedings
of the 44th symposium on Theory of
Computing, STOC ‘ 12 (ACM, 2011), 61–
76. Also available as arXiv:1111.6054.
35. Vazirani, U., Vidick, T. Fully device-
independent quantum key distribution.
Phys. Rev. Lett. 113, 14 (2014), 140501.
36. Yin, J., Cao, Y., Li, Y.-H., Liao, S.-K.,
Zhang, L., Ren, J.-G., Cai, W.-Q., Liu,
W.-Y. Li, B., Dai, H., et al. Satellite-
based entanglement distribution over
1200 kilometers. Science 356, 6343
(2017), 1140–1144.

 

1. Acín, A., Brunner, N., Gisin, N., Massar, S., Pironio, S., Scarani, V. Device-independent security of quantum cryptography against collective attacks.

Phys. Rev. Lett. 98, 230501 (2007).

2. Acín, A., Gisin, N., Masanes, L. From Bell’s theorem to secure quantum key distribution. Phys. Rev. Lett. 97,

120405 (2006).

3. Arnon-Friedman, R., Renner, R., Vidick, T.

Simple and tight device-independent security proofs. arXiv preprint arXiv:1607.01797 (2016).

4. Barrett, J., Colbeck, R., Kent, A.

Unconditionally secure device-
independent quantum key distribution
with only two devices. Technical
report arXiv:1209.0435 (2012).

5. Barrett, J., Hardy, L., Kent, A.

No signaling and quantum key distribution. Phys. Rev. Lett. 95,

010503 (2005).

6. Bell, J.S. On the Einstein-Podolsky-Rosen paradox. Physics 1 (1964), 195–200.

7. Bennett, C., Brassard, G. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of the International Conference on Computers, Systems, and Signal Processing (1984), 175–179. Copyright held by authors/owners. Publication rights licensed to ACM.

Umesh Vazirani (vazirani@eecs. berkeley.edu), Department of Computer Science, UC Berkeley, Berkeley, California, USA.

Thomas Vidick ( [e-mail]. edu), Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, California, USA.

References