Communications of the ACM

is a topic of great importance, both theoretically and practically, in its own right irrespective of whether it is used in a cryptographic setting or not. 22 Another method to achieve verification of quantum computation in the post-quantum computational security setting, which does not necessarily rely in hiding the computation, was proposed in Mahadev. 32

In Cojocaru et al., 15 a quantum channel is replaced by a functionality of delegated pseudo-secret random qubit generator. Communicating random (secret) qubits is the only quantum communication required in many protocols (for example, Broadbent et al. 12 and Fitzsimons et al. 20). The key idea to achieve this functionality is to instruct the server to generate a state where some qubits are entangled, while some are unentangled. This is done in such a way that the connectivity is known to the client (that has access to trap-door information) but is unknown to the server (that does not have access). The client uses this advantage and instructs the server to prepare an output qubit in a random state, of which the client knows its classical description while the server is totally ignorant. This exactly mimics a random single-qubit quantum channel.

The Future

The ability to communicate securely and compute efficiently is more important than ever to society. The Internet and increasingly the Internet of Things, has had a revolutionary impact on our world. Over the next 5–10 years, we will see a flux of new possibilities, as quantum technologies become part of this mainstream computing and communicating landscape. Future networks will certainly consist of both classical and quantum devices and links, some of which are expected to be dishonest, with functionalities of various sophistication, ranging from simple routers to servers executing universal quantum algorithms (see Figure 3). The realization of such a complex network of classical and quantum communication must rely on a solid novel foundation that, nevertheless, is able to foresee and handle the in-tricacies of real-life implementations and novel applications.

While post-quantum security paves the way for our classical Internet to remain safe in that era, quantum enhanced security aims to benefit actively from the development of quantum Internet in order to achieve unparalleled performances that are provably impossible using classical communication. Meanwhile quantum cloud services with various capabilities are becoming available. Quantum enabled security provides the platform that will ensure potential users that this new, unprecedented computational power in the quantum cloud, comes with the appropriate standards of accuracy, reliability and privacy.

References

1. 2013. Stored Encrypted Emails; https://www.

technewsworld.com/story/79117.html

2. 2017. Quantum Internet Alliance; http://quantum-internet.team/

3. 2018. Google aims for quantum supremacy; https:// physicsworld.com/a/google-aims-for-quantum-supremacy/

4. Aaronson, S., Cojocaru, A., Gheorghiu, A. and Kashefi, E. On the implausibility of classical client blind quantum computing, 2017; arXiv:1704.08482.

5. Belovs, A. et al. Provably secure key establishment against quantum adversaries. In Proceedings of the 12th Conf. Theory of Quantum Computation, Communication and Cryptography. M. M. Wilde, ed.

Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik,

2018, 3:1–3: 17.

6. Bennett, C.H. and Brassard, G. Quantum cryptography: Public key distribution and coin tossing. Theor.

Comput. Sci. 560, P1 (2014), 7–11.

7. Bernstein, D.J. Introduction to post-quantum cryptography. Postquantum Cryptography. Springer,

2009, 1–14.

8. Boneh, D. et al. Random oracles in a quantum world. Advances in Cryptology—ASIACRYPT 2011. D. H Lee and X. Wang, eds. Springer.

9. Boneh, D. and Zhandry, M. Secure signatures and chosen ciphertext security in a quantum computing world. Advances in Cryptology–CRYPTO 2013.

Springer, 361–379.

10. Brassard, G., Lütkenhaus, N., Mor, T. and Sanders, B.C. Limitations on practical quantum cryptography.

Physical Review Letters 85, 6 (2000),

11. Braunstein, S.L. and Pirandola, S. Side-channel-free quantum key distribution. Physical Review Letters 108,

13 (2012), 130502.

12. Broadbent, A., Fitzsimons, J. and Kashefi, E. Universal blind quantum computation. In Proceedings of the 50th Annual Symp. Foundations of Computer Science. IEEE CS, 2009, 517–526.

13. Broadbent, A. and Schaffner, C. Quantum cryptography beyond quantum key distribution.

Designs, Codes and Cryptography 78, 1 (2016),

351–382.

14. Buhrman, H. et al. Position-based quantum cryptography: Impossibility and constructions. SIAM J. Comput. 43, 1 (2014), 150–178.

15. Cojocaru, A., Colisson, L., Kashefi, E. and Wallden, P. On the possibility of classical client blind quantum computing, 2018; arXiv:1802.08759.

16. Dowling, J.P. and Milburn, G. J. Quantum technology: The second quantum revolution. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 361,

1809 (2003), 1655–1674.

17. Ekert, A. and Renner, R. The ultimate physical limits of privacy. Nature 507, 7493 (2014), 443.

18. Faugere, J.C. et al. Fast Quantum Algorithm for Solving Multivariate Quadratic Equations, 2017; arXiv:1712.07211.

19. Fitzsimons, J. F. Private quantum computation: An introduction to blind quantum computing and related protocols. NPJ Quantum Information 3, 1 (2017), 23.

20. Fitzsimons, J.F. and Kashefi, E. Unconditionally
verifiable blind quantum computation. Physical Review
A 96 (2017), 012303.

21. Gagliardoni, T., Hülsing, A. and Schaffner, C. Semantic security and indistinguishability in the quantum world. Advances in Cryptology—CRYPTO 2016. M. Robshaw and J. Katz, eds. Springer, 60–89.

22. Gheorghiu, A., Kapourniotis, T. and Kashefi, E.

Verification of quantum computation: An overview of existing approaches. Theory of Computing Systems

(Jul 6, 2018).

23. Gheorghiu, A., Kashefi, E. and Wallden, P. Robustness and device independence of verifiable blind quantum computing. New J. Physics 17, 8 (2015), 083040.

24. Hanneke, D., Fogwell, S. and Gabrielse, G. New measurement of the electron magnetic moment and the fine structure constant. Physical Review Letters

100, 12 (2008), 120801.

25. Kaplan, M., Leurent, G., Leverrier, A. and Naya-Plasencia, M. Breaking symmetric cryptosystems using quantum period finding. Advances in Cryptology—CRYPTO 2016. M. Robshaw and J. Katz, eds. Springer, 207–237.

26. Kashefi, E., Music, L. and Wallden, P. The Quantum Cut-and-Choose Technique and Quantum Two-Party Computation, 2017; arXiv:1703.03754 (2017).

27. Liao, S.K. et al. Satellite-relayed intercontinental quantum network. Physical Review Letters 120, 3

(2018), 030501.

28. Lindell. Y. How to simulate it—A tutorial on the simulation proof technique. Tutorials on the Foundations of Cryptography. Springer, 2017, 277–346.

29. Lo, H. K., Curty, M. and Qi, B. Measurement-device-independent quantum key distribution. Physical Review Letters 108, 13 (2012), 130503.

30. Lydersen, L. et al. Hacking commercial quantum cryptography systems by tailored bright illumination.

Nature Photonics 4, 10 (2010), 686.

31. Mahadev, U. Classical homomorphic encryption for quantum circuits. In Proceedings of the IEEE 59th Annual Symposium on Foundations of Computer Science (Paris, France, 2018), 332–338.

32. Mahadev, U. Classical verification of quantum computations. In Proceedings of the IEEE 59th Annual Symposium on Foundations of Computer Science

(Paris, France, 2018), 259–267.

33. Bohr, N. On the constitution of atoms and molecules.

The London, Edinburgh, and Dublin Philosophical Magazine and J. Science 26, 151 (1913), 1–25.

34. Reichardt, B. W., Unger, F. and Vazirani, U. Classical command of quantum systems. Nature 496, 7446

(2013), 456.

35. Shor, P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review 41, 2 (1999), 303–332.

36. Unruh, D. Quantum proofs of knowledge. Advances in Cryptology—EUROCRYPT 2012. D. Pointcheval and T.

Johansson, eds. Springer, 135–152.

37. van de Graaf, J. Towards a Formal Definition of Security for Quantum Protocols. Ph.D. Dissertation,

1998. Montreal, Canada.

38. Von Neumann, J. Mathematical Foundations of Quantum Mechanics. Number 2. Princeton University Press, 1955.

39. Watrous, J. Zero-knowledge against quantum attacks.

SIAM J. Comput. 39, 1 (2009), 25–58.

40. Xu, F. et al. Experimental quantum fingerprinting with weak coherent pulses. Nature Communications, (2015), 8735.

Petros Wallden ( petros.wallden@ed.ac.uk) is Lecturer at the University of Edinburgh, Scotland, U.K.

Elham Kashefi ( ekashefi@staffmail.ed.ac.uk) is a professor at the University of Edinburgh, Scotland, U.K. and Sorbonne Université, CNRS, Laboratoire d’Informatique de Paris, France.