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.
Subsequent to our work on quantum key distribution a
second proof of security for DIQKD was put forward in Miller
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!
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
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
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,
3. Arnon-Friedman, R., Renner, R., Vidick, T.
Simple and tight device-independent
security proofs. arXiv preprint
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,
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,
Thomas Vidick ( firstname.lastname@example.org.
edu), Department of Computing and
Mathematical Sciences, California
Institute of Technology, Pasadena,