Privacy And Correctness Trade-offs For Information-theoretically Secure Quantum Homomorphic Encryption

Republished By Plato

Followers: 0

Yanglin Hu¹, Yingkai Ouyang¹, and Marco Tomamichel^1,2

¹Centre of Quantum Technologies, National University of Singapore, Singapore
²Department of Electrical and Computer Engineering, National University of Singapore

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

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.

Featured image: Quantum homomorphic encryption, the Swiss army knife of quantum cryptography, can construct quantum oblivious transfer.

[embedded content]

Popular summary

Imagine going to an accounting firm to consult your accountant about your tax. You do not want your accountant to know your private data private, such as your income and tax. On the contrary, your accountant does not want you to learn how she computes your tax. Otherwise, you will do it yourself next time, and she’ll lose her job. Is it possible that both of you are satisfied?
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.

► BibTeX data

@article{Hu2023privacycorrectness, doi = {10.22331/q-2023-04-13-976}, url = {https://doi.org/10.22331/q-2023-04-13-976}, title = {Privacy and correctness trade-offs for information-theoretically secure quantum homomorphic encryption}, author = {Hu, Yanglin and Ouyang, Yingkai and Tomamichel, Marco}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {976}, month = apr, year = {2023}
}

► References

[1] Joseph F Fitzsimons. ``Private quantum computation: an introduction to blind quantum computing and related protocols''. npj Quantum Information 3, 1–11 (2017).
https://doi.org/10.1038/s41534-017-0025-3

[2] Dorit Aharonov, Michael Ben-Or, and Elad Eban. ``Interactive proofs for quantum computations'' (2008) arXiv:0810.5375.
https://doi.org/10.48550/arXiv.0810.5375
arXiv:0810.5375

[3] 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).
https://doi.org/10.1109/FOCS.2009.36

[4] Tomoyuki Morimae and Keisuke Fujii. ``Blind quantum computation protocol in which alice only makes measurements''. Phys. Rev. A 87, 050301 (2013).
https://doi.org/10.1103/PhysRevA.87.050301

[5] Ben W Reichardt, Falk Unger, and Umesh Vazirani. ``Classical command of quantum systems''. Nature 496, 456–460 (2013).
https://doi.org/10.1038/nature12035

[6] 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).
https://doi.org/10.1103/PhysRevX.7.031004

[7] 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).
https://doi.org/10.1103/PhysRevA.90.050303

[8] 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.
https://doi.org/10.1007/978-3-662-48000-7_30

[9] 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.
https://doi.org/10.1007/978-3-662-53015-3_1

[10] 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).
https://doi.org/10.1038/srep33467

[11] Yingkai Ouyang, Si-Hui Tan, and Joseph F. Fitzsimons. ``Quantum homomorphic encryption from quantum codes''. Phys. Rev. A 98, 042334 (2018).
https://doi.org/10.1103/PhysRevA.98.042334

[12] Urmila Mahadev. ``Classical homomorphic encryption for quantum circuits''. SIAM Journal on Computing 0, FOCS18–189 (2020).
https://doi.org/10.1137/18M1231055

[13] Yingkai Ouyang and Peter P. Rohde. ``A general framework for the composition of quantum homomorphic encryption & quantum error correction'' (2022) arXiv:2204.10471.
https://doi.org/10.48550/arXiv.2204.10471
arXiv:2204.10471

[14] Craig Gentry. ``Fully homomorphic encryption using ideal lattices''. In Proceedings of the 41st annual ACM Symposium on Theory of computing. Pages 169–178. (2009).
https://doi.org/10.1145/1536414.1536440

[15] Craig Gentry. ``A fully homomorphic encryption scheme''. PhD thesis. Stanford University. (2009). url: crypto.stanford.edu/craig.
https://crypto.stanford.edu/craig

[16] 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.
https://doi.org/10.1007/978-3-642-14623-7_9

[17] Baoz Barak and Zvika Brakerski. ``The swiss army knife of cryptography'' (2012) url: windowsontheory.org/2012/05/01/the-swiss-army-knife-of-cryptography/.
https://windowsontheory.org/2012/05/01/the-swiss-army-knife-of-cryptography/

[18] Yehuda Lindell. ``Tutorials on the foundations of cryptography: Dedicated to oded goldreich''. Springer Publishing Company, Incorporated. (2017). 1st edition.
https://doi.org/10.1007/978-3-319-57048-8

[19] 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).
https://doi.org/10.1007/s11227-021-03826-0

[20] 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.
https://doi.org/10.1007/978-3-540-24638-1_1

[21] Ching-Yi Lai and Kai-Min Chung. ``On statistically-secure quantum homomorphic encryption''. Quantum Info. Comput. 18, 785–794 (2018).
https://doi.org/10.26421/QIC18.9-10-4

[22] Michael Newman. ``Further limitations on information-theoretically secure quantum homomorphic encryption'' (2018) arXiv:1809.08719.
https://doi.org/10.48550/arXiv.1809.08719
arXiv:1809.08719

[23] 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).
https://doi.org/10.1109/SFFCS.1999.814608

[24] 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).
https://doi.org/10.1103/PhysRevA.97.042308

[25] 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).
https://doi.org/10.1103/PhysRevResearch.2.013332

[26] André Chailloux, Iordanis Kerenidis, and Jamie Sikora. ``Lower bounds for quantum oblivious transfer''. Quantum Info. Comput. 13, 158–177 (2013).
https://doi.org/10.26421/QIC13.1-2-9

[27] André Chailloux and Jamie Sikora. ``Optimal bounds for semi-honest quantum oblivious transfer''. Chicago Journal of Theoretical Computer Science 2016 (2016).
https://doi.org/10.4086/cjtcs.2016.013

[28] 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).
https://doi.org/10.1103/PRXQuantum.2.010335

[29] 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).
https://doi.org/10.1063/1.4898559

[30] Carl W. Helstrom. ``Detection theory and quantum mechanics''. Information and Control 10, 254–291 (1967).
https://doi.org/10.1016/S0019-9958(67)90302-6

[31] 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.
http://mi.mathnet.ru/ppi903

[32] John Watrous. ``The theory of quantum information''. Cambridge University Press. (2018).
https://doi.org/10.1017/9781316848142

[33] C.A. Fuchs and J. van de Graaf. ``Cryptographic distinguishability measures for quantum-mechanical states''. IEEE Transactions on Information Theory 45, 1216–1227 (1999).
https://doi.org/10.1109/18.761271

[34] A. Uhlmann. ``The ``transition probability'' in the state space of a *-algebra''. Reports on Mathematical Physics 9, 273–279 (1976).
https://doi.org/10.1016/0034-4877(76)90060-4

[35] Michael A Nielsen and Isaac Chuang. ``Quantum computation and quantum information: 10th anniversary edition''. Cambridge University Press. (2010).
https://doi.org/10.1017/CBO9780511976667

[36] Hoi-Kwong Lo. ``Insecurity of quantum secure computations''. Phys. Rev. A 56, 1154–1162 (1997).
https://doi.org/10.1103/PhysRevA.56.1154

[37] Roger Colbeck. ``Impossibility of secure two-party classical computation''. Phys. Rev. A 76, 062308 (2007).
https://doi.org/10.1103/PhysRevA.76.062308

[38] Carlos Mochon. ``Quantum weak coin flipping with arbitrarily small bias'' (2007) arXiv:0711.4114.
https://doi.org/10.48550/arXiv.0711.4114
arXiv:0711.4114

[39] 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).
https://doi.org/10.1109/FOCS.2009.71

[40] 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).
https://doi.org/10.1137/14096387X

[41] 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.

[42] Hoi-Kwong Lo and H. F. Chau. ``Is quantum bit commitment really possible?''. Phys. Rev. Lett. 78, 3410–3413 (1997).
https://doi.org/10.1103/PhysRevLett.78.3410

[43] Dominic Mayers. ``Unconditionally secure quantum bit commitment is impossible''. Phys. Rev. Lett. 78, 3414–3417 (1997).
https://doi.org/10.1103/PhysRevLett.78.3414

Cited by

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.

SEO Powered Content & PR Distribution. Get Amplified Today.
Platoblockchain. Web3 Metaverse Intelligence. Knowledge Amplified. Access Here.
Minting the Future w Adryenn Ashley. Access Here.
Source: https://quantum-journal.org/papers/q-2023-04-13-976/

Time Stamp: April 13, 2023

Time Stamp: Jan 25, 2024

Republished By Plato

Experimental Communication Through Superposition of Quantum Channels

Forging quantum data: classically defeating an IQP-based quantum test

State Preparation in the Heisenberg Model through Adiabatic Spiraling

On the energy landscape of symmetric quantum signal processing

Differentiable matrix product states for simulating variational quantum computational chemistry

Multivariate trace estimation in constant quantum depth

Two-Unitary Decomposition Algorithm and Open Quantum System Simulation

Local Probabilistic Decoding of a Quantum Code

Bounds on approximating Max $k$XOR with quantum and classical local algorithms

Experimental entanglement generation for quantum key distribution beyond 1 Gbit/s

A complete and operational resource theory of measurement sharpness

About Us

Vertical Search & Ai

Platform

Stay Connected

Account