Quantum homomorphic encryption, which allows computation by a server directly on encrypted data, is a fundamental primitive out of which more complex quantum cryptography protocols can be built. For such constructions to be possible, quantum homomorphic encryption must satisfy two privacy properties: data privacy which ensures that the input data is private from the server, and circuit privacy which ensures that the ciphertext after the computation does not reveal any additional information about the circuit used to perform it, beyond the output of the computation itself. While circuit privacy is well-studied in classical cryptography and many homomorphic encryption schemes can be equipped with it, its quantum analogue has received little attention. Here we establish a definition of circuit privacy for quantum homomorphic encryption with information-theoretic security. Furthermore, we reduce quantum oblivious transfer to quantum homomorphic encryption. By using this reduction, our work unravels fundamental trade-offs between circuit privacy, data privacy and correctness for a broad family of quantum homomorphic encryption protocols, including schemes that allow only the computation of Clifford circuits.
If one of you cannot solve a specific complicated problem, then yes, and you can use classical homomorphic encryption. However, can we get rid of the questionable assumption? The hope is to bring quantum mechanics to quantum homomorphic encryption, which usually improves security.
In our paper, we answer the question with a no. One of you and your accountant cannot be satisfied. There is a trade-off between the information you leak and the information your accountant leaks.
 Joseph F Fitzsimons. ``Private quantum computation: an introduction to blind quantum computing and related protocols''. npj Quantum Information 3, 1–11 (2017).
 Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. ``Universal blind quantum computation''. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. Pages 517–526. (2009).
 Atul Mantri, Tommaso F. Demarie, Nicolas C. Menicucci, and Joseph F. Fitzsimons. ``Flow ambiguity: A path towards classically driven blind quantum computation''. Phys. Rev. X 7, 031004 (2017).
 Li Yu, Carlos A. Pérez-Delgado, and Joseph F. Fitzsimons. ``Limitations on information-theoretically-secure quantum homomorphic encryption''. Phys. Rev. A 90, 050303 (2014).
 Anne Broadbent and Stacey Jeffery. ``Quantum homomorphic encryption for circuits of low t-gate complexity''. In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology – CRYPTO 2015. Pages 609–629. Berlin, Heidelberg (2015). Springer Berlin Heidelberg.
 Yfke Dulek, Christian Schaffner, and Florian Speelman. ``Quantum homomorphic encryption for polynomial-sized circuits''. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology – CRYPTO 2016. Pages 3–32. Berlin, Heidelberg (2016). Springer Berlin Heidelberg.
 Si-Hui Tan, Joshua A. Kettlewell, Yingkai Ouyang, Lin Chen, and Joseph F. Fitzsimons. ``A quantum approach to homomorphic encryption''. Scientific Reports 6, 33467 (2016).
 Yingkai Ouyang and Peter P. Rohde. ``A general framework for the composition of quantum homomorphic encryption & quantum error correction'' (2022) arXiv:2204.10471.
 Craig Gentry. ``Fully homomorphic encryption using ideal lattices''. In Proceedings of the 41st annual ACM Symposium on Theory of computing. Pages 169–178. (2009).
 Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. ``I-hop homomorphic encryption and rerandomizable yao circuits''. In Proceedings of the 30th Annual Conference on Advances in Cryptology. Pages 155–172. CRYPTO'10Berlin, Heidelberg (2010). Springer-Verlag.
 Baoz Barak and Zvika Brakerski. ``The swiss army knife of cryptography'' (2012) url: windowsontheory.org/2012/05/01/the-swiss-army-knife-of-cryptography/.
 Yehuda Lindell. ``Tutorials on the foundations of cryptography: Dedicated to oded goldreich''. Springer Publishing Company, Incorporated. (2017). 1st edition.
 Saeid Esmaeilzade, Nasrollah Pakniat, and Ziba Eslami. ``A generic construction to build simple oblivious transfer protocols from homomorphic encryption schemes''. The Journal of Supercomputing 78, 72–92 (2022).
 Omer Reingold, Luca Trevisan, and Salil Vadhan. ``Notions of reducibility between cryptographic primitives''. In Moni Naor, editor, Theory of Cryptography. Pages 1–20. Berlin, Heidelberg (2004). Springer Berlin Heidelberg.
 Ashwin Nayak. ``Optimal lower bounds for quantum automata and random access codes''. In 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039). Pages 369–376. (1999).
 Si-Hui Tan, Yingkai Ouyang, and Peter P. Rohde. ``Practical somewhat-secure quantum somewhat-homomorphic encryption with coherent states''. Phys. Rev. A 97, 042308 (2018).
 Yingkai Ouyang, Si-Hui Tan, Joseph Fitzsimons, and Peter P. Rohde. ``Homomorphic encryption of linear optics quantum computation on almost arbitrary states of light with asymptotically perfect security''. Physical Review Research 2, 013332 (2020).
 André Chailloux and Jamie Sikora. ``Optimal bounds for semi-honest quantum oblivious transfer''. Chicago Journal of Theoretical Computer Science 2016 (2016).
 Ryan Amiri, Robert Stárek, David Reichmuth, Ittoop V. Puthoor, Michal Mičuda, Ladislav Mišta, Jr., Miloslav Dušek, Petros Wallden, and Erika Andersson. ``Imperfect 1-out-of-2 quantum oblivious transfer: Bounds, a protocol, and its experimental implementation''. PRX Quantum 2, 010335 (2021).
 Koenraad M. R. Audenaert and Milán Mosonyi. ``Upper bounds on the error probabilities and asymptotic error exponents in quantum multiple state discrimination''. Journal of Mathematical Physics 55, 102201 (2014).
 Alexander S. Holevo. ``Bounds for the quantity of information transmitted by a quantum communication channel''. Problems of Information Transmission 9, 177–183 (1973). url: http://mi.mathnet.ru/ppi903.
 C.A. Fuchs and J. van de Graaf. ``Cryptographic distinguishability measures for quantum-mechanical states''. IEEE Transactions on Information Theory 45, 1216–1227 (1999).
 André Chailloux and Iordanis Kerenidis. ``Optimal quantum strong coin flipping''. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. Pages 527–533. IEEE (2009).
 Dorit Aharonov, André Chailloux, Maor Ganz, Iordanis Kerenidis, and Loïck Magnin. ``A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias''. SIAM Journal on Computing 45, 633–679 (2016).
 Carl A. Miller. ``The impossibility of efficient quantum weak coin flipping''. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Pages 916–929. New York, NY, USA (2020). Association for Computing Machinery.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.