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 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.
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
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
1. 2013. Stored Encrypted Emails; https://www.
2. 2017. Quantum Internet Alliance; http://quantum-internet.team/
3. 2018. Google aims for quantum supremacy; https://
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,
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.
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),
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;
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
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
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
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,
Petros Wallden ( email@example.com) is Lecturer at
the University of Edinburgh, Scotland, U.K.
Elham Kashefi ( firstname.lastname@example.org) is a
professor at the University of Edinburgh, Scotland,
U.K. and Sorbonne Université, CNRS, Laboratoire
d’Informatique de Paris, France.
Copyright held by authors/owners.
Watch the author discuss
this work in the exclusive