Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1705.00139 · Quantum Information and Computation

On statistically-secure quantum homomorphic encryption

Ching–Yi Lai, Kai-Min Chung

Published Aug 1, 2018• 29 citations
arXivHTMLPDF

Abstract

Homomorphic encryption is an encryption scheme that allows computations to be evaluated on encrypted inputs without knowledge of their raw messages. Recently Ouyang et al. constructed a quantum homomorphic encryption (QHE) scheme for Clifford circuits with statistical security (or information-theoretic security (IT-security)). It is desired to see whether an information-theoretically-secure (ITS) quantum FHE exists. If not, what other nontrivial class of quantum circuits can be homomorphically evaluated with IT-security? We provide a limitation for the first question that an ITS quantum FHE necessarily incurs exponential overhead. As for the second one, we propose a QHE scheme for the instantaneous quantum polynomial-time (IQP) circuits. Our QHE scheme for IQP circuits follows from the one-time pad.

DOI
10.26421/qic18.9-10-4

Related papers

A quantum homomorphic encryption scheme for polynomial-sized circuits

Li Zhi Yu

Quantum homomorphic encryption (QHE) is an encryption method that allows quantum computation to be performed on one party's private data with the program provided by another party, without revealing much information about the data nor about the program to the opposite party. It is known that information-theoretically-secure QHE for circuits of unrestricted size would require exponential resources, and efficient computationally-secure QHE schemes for polynomial-sized quantum circuits have been constructed. In this paper we first propose a QHE scheme for a type of circuits of polynomial depth, based on the rebit quantum computation formalism. The scheme keeps the restricted type of data perfectly secure. We then propose a QHE scheme for a larger class of polynomial-depth quantum circuits, which has partial data privacy. Both schemes have good circuit privacy. We also propose an interactive QHE scheme with asymptotic data privacy, however, the circuit privacy is not good, in the sense that the party who provides the data could cheat and learn about the circuit. We show that such cheating would generally affect the correctness of the evaluation or cause deviation from the protocol. Hence the cheating can be caught by the opposite party in an interactive scheme with embedded verifications. Such scheme with verification has a minor drawback in data privacy. Finally, we show some methods which achieve some nontrivial level of data privacy and circuit privacy without resorting to allowing early terminations, in both the QHE problem and in secure evaluation of classical functions. The entanglement and classical communication costs in these schemes are polynomial in the circuit size and the security parameter (if any).

arXiv:1810.01166•Oct 2, 2018•3 citations

A rebit-based quantum homomorphic encryption scheme

Li Zhi Yu

Quantum homomorphic encryption (QHE) is an encryption method that allows quantum computation to be performed on one party's private data with the program provided by another party, without revealing much information about the data nor about the program to the opposite party. It is known that information-theoretically-secure QHE for circuits of unrestricted size would require exponential resources, and efficient computationally-secure QHE schemes for polynomial-sized quantum circuits have been constructed. In this paper we first propose a QHE scheme for a type of circuits of polynomial depth, based on the rebit quantum computation formalism. The scheme keeps the restricted type of data perfectly secure. We then propose a QHE scheme for a larger class of polynomial-depth quantum circuits, which has partial data privacy. Both schemes have good circuit privacy. We also propose an interactive QHE scheme with asymptotic data privacy, however, the circuit privacy is not good, in the sense that the party who provides the data could cheat and learn about the circuit. We show that such cheating would generally affect the correctness of the evaluation or cause deviation from the protocol. Hence the cheating can be caught by the opposite party in an interactive scheme with embedded verifications. Such scheme with verification has a minor drawback in data privacy. Finally, we show some methods which achieve some nontrivial level of data privacy and circuit privacy without resorting to allowing early terminations, in both the QHE problem and in secure evaluation of classical functions. The entanglement and classical communication costs in these schemes are polynomial in the circuit size and the security parameter (if any).

•Oct 2, 2018•0 citations

Limitations on information-theoretically-secure quantum homomorphic encryption

Li Zhi Yu, Carlos A. Pérez-Delgado, Joseph F. Fitzsimons

Homomorphic encryption is a form of encryption which allows computation to be carried out on the encrypted data without the need for decryption. The success of quantum approaches to related tasks in a delegated computation setting has raised the question of whether quantum mechanics may be used to achieve information-theoretically-secure fully homomorphic encryption. Here we show, via an information localization argument, that deterministic fully homomorphic encryption necessarily incurs exponential overhead if perfect security is required.

arXiv:1406.2456•Physical Review A•Nov 10, 2014•77 citations

Quantum fully homomorphic encryption on single qubit

Min Liang

Suppose some data have been encrypted, can you compute with the data without decrypting them? This problem has been studied as homomorphic encryption and blind computing. We consider this problem in the context of quantum information processing, and present the definitions of quantum homomorphic encryption (QHE) and quantum fully homomorphic encryption (QFHE). Then, based on quantum one-time pad (QOTP), we construct a symmetric QFHE scheme, where the evaluate algorithm depends on the secret key. This scheme permits any unitary transformation on any $n$-qubit state that has been encrypted. Compared with classical homomorphic encryption, the QFHE scheme has perfect security. Finally, we also construct a QOTP-based symmetric QHE scheme, where the evaluate algorithm is independent of the secret key.

•Apr 18, 2013•0 citations

Privacy and correctness trade-offs for information-theoretically secure quantum homomorphic encryption

Yanglin Hu, Yingkai Ouyang, Marco Tomamichel

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.

arXiv:2205.12127•Quantum•Apr 13, 2023•9 citations

Quantum homomorphic encryption for polynomial-sized circuits

Yfke Dulek, Christian Schaffner, Florian Speelman

We present a new scheme for quantum homomorphic encryption which is compact and allows for efficient evaluation of arbitrary quantum circuits, as long as those circuits are of size, polynomial in the security parameter. Building on the framework of Broadbent and Jeffery (CRYPTO'15) and recent results in the area of instantaneous non-local quantum computation by Speelman (TQC'16), we show how to construct quantum gadgets that allow perfect correction of the errors which occur during the homomorphic evaluation of $\mathsf{T}$ gates on encrypted quantum data. Our scheme can be based on any classical (leveled) fully homomorphic encryption (FHE) scheme and requires no computational assumptions besides those already used by the classical scheme. The size of our quantum gadget depends on the space complexity of the classical decryption function -- which aligns well with the current efforts to minimize the complexity of the decryption function. Our scheme (or slight variants of it) offers a number of additional advantages such as ideal compactness, the ability to supply gadgets “on demand,” circuit privacy for the evaluator against passive adversaries, and a three-round scheme for blind delegated quantum computation which puts only very limited demands on the quantum abilities of the client. A conference version of this paper appeared in Advances in Cryptology: Proceedings of the 36th International Cryptology Conference (CRYPTO 2016).

arXiv:1603.09717•Theory of Computing•Jan 1, 2018•22 citations
Homomorphic encryption is an encryption scheme that allows computations to be evaluated on encrypted inputs without knowledge of their raw messages. Recently Ouyang et al. constructed a quantum homomorphic encryption (QHE) scheme for Clifford circuits with statistical security (or information-theoretic security (IT-security)). It is desired to see whether an information-theoretically-secure (ITS) quantum FHE exists. If not, what other nontrivial class of quantum circuits can be homomorphically evaluated with IT-security? We provide a limitation for the first question that an ITS quantum FHE necessarily incurs exponential overhead. As for the second one, we propose a QHE scheme for the instantaneous quantum polynomial-time (IQP) circuits. Our QHE scheme for IQP circuits follows from the one-time pad.
Quantum homomorphic encryption (QHE) is an encryption method that allows quantum computation to be performed on one party's private data with the program provided by another party, without revealing much information about the data nor about the program to the opposite party. It is known that information-theoretically-secure QHE for circuits of unrestricted size would require exponential resources, and efficient computationally-secure QHE schemes for polynomial-sized quantum circuits have been constructed. In this paper we first propose a QHE scheme for a type of circuits of polynomial depth, based on the rebit quantum computation formalism. The scheme keeps the restricted type of data perfectly secure. We then propose a QHE scheme for a larger class of polynomial-depth quantum circuits, which has partial data privacy. Both schemes have good circuit privacy. We also propose an interactive QHE scheme with asymptotic data privacy, however, the circuit privacy is not good, in the sense that the party who provides the data could cheat and learn about the circuit. We show that such cheating would generally affect the correctness of the evaluation or cause deviation from the protocol. Hence the cheating can be caught by the opposite party in an interactive scheme with embedded verifications. Such scheme with verification has a minor drawback in data privacy. Finally, we show some methods which achieve some nontrivial level of data privacy and circuit privacy without resorting to allowing early terminations, in both the QHE problem and in secure evaluation of classical functions. The entanglement and classical communication costs in these schemes are polynomial in the circuit size and the security parameter (if any).
Quantum homomorphic encryption (QHE) is an encryption method that allows quantum computation to be performed on one party's private data with the program provided by another party, without revealing much information about the data nor about the program to the opposite party. It is known that information-theoretically-secure QHE for circuits of unrestricted size would require exponential resources, and efficient computationally-secure QHE schemes for polynomial-sized quantum circuits have been constructed. In this paper we first propose a QHE scheme for a type of circuits of polynomial depth, based on the rebit quantum computation formalism. The scheme keeps the restricted type of data perfectly secure. We then propose a QHE scheme for a larger class of polynomial-depth quantum circuits, which has partial data privacy. Both schemes have good circuit privacy. We also propose an interactive QHE scheme with asymptotic data privacy, however, the circuit privacy is not good, in the sense that the party who provides the data could cheat and learn about the circuit. We show that such cheating would generally affect the correctness of the evaluation or cause deviation from the protocol. Hence the cheating can be caught by the opposite party in an interactive scheme with embedded verifications. Such scheme with verification has a minor drawback in data privacy. Finally, we show some methods which achieve some nontrivial level of data privacy and circuit privacy without resorting to allowing early terminations, in both the QHE problem and in secure evaluation of classical functions. The entanglement and classical communication costs in these schemes are polynomial in the circuit size and the security parameter (if any).
Homomorphic encryption is a form of encryption which allows computation to be carried out on the encrypted data without the need for decryption. The success of quantum approaches to related tasks in a delegated computation setting has raised the question of whether quantum mechanics may be used to achieve information-theoretically-secure fully homomorphic encryption. Here we show, via an information localization argument, that deterministic fully homomorphic encryption necessarily incurs exponential overhead if perfect security is required.
Suppose some data have been encrypted, can you compute with the data without decrypting them? This problem has been studied as homomorphic encryption and blind computing. We consider this problem in the context of quantum information processing, and present the definitions of quantum homomorphic encryption (QHE) and quantum fully homomorphic encryption (QFHE). Then, based on quantum one-time pad (QOTP), we construct a symmetric QFHE scheme, where the evaluate algorithm depends on the secret key. This scheme permits any unitary transformation on any nnn-qubit state that has been encrypted. Compared with classical homomorphic encryption, the QFHE scheme has perfect security. Finally, we also construct a QOTP-based symmetric QHE scheme, where the evaluate algorithm is independent of the secret key.
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.
We present a new scheme for quantum homomorphic encryption which is compact and allows for efficient evaluation of arbitrary quantum circuits, as long as those circuits are of size, polynomial in the security parameter. Building on the framework of Broadbent and Jeffery (CRYPTO'15) and recent results in the area of instantaneous non-local quantum computation by Speelman (TQC'16), we show how to construct quantum gadgets that allow perfect correction of the errors which occur during the homomorphic evaluation of T\mathsf{T}T gates on encrypted quantum data. Our scheme can be based on any classical (leveled) fully homomorphic encryption (FHE) scheme and requires no computational assumptions besides those already used by the classical scheme. The size of our quantum gadget depends on the space complexity of the classical decryption function -- which aligns well with the current efforts to minimize the complexity of the decryption function. Our scheme (or slight variants of it) offers a number of additional advantages such as ideal compactness, the ability to supply gadgets “on demand,” circuit privacy for the evaluator against passive adversaries, and a three-round scheme for blind delegated quantum computation which puts only very limited demands on the quantum abilities of the client. A conference version of this paper appeared in Advances in Cryptology: Proceedings of the 36th International Cryptology Conference (CRYPTO 2016).