A rebit-based quantum homomorphic encryption scheme

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).

arXiv:1810.01166Oct 2, 20182 citations

A framework for quantum homomorphic encryption with experimental demonstration

Yu Zhang, Li Zhi Yu, Qi-Ping Su +7 more

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 the program to the opposite party. We propose a framework for (interactive) QHE based on the universal circuit approach. It contains a subprocedure of calculating a classical linear polynomial, which can be implemented with quantum or classical methods; apart from the subprocedure, the framework has low requirement on the quantum capabilities of the party who provides the circuit. We illustrate the subprocedure using a quite simple classical protocol with some privacy tradeoff. For a special case of such protocol, we obtain a scheme similar to blind quantum computation but with the output on a different party. Another way of implementing the subprocedure is to use a recently studied quantum check-based protocol, which has low requirement on the quantum capabilities of both parties. The subprocedure could also be implemented with a classical additive homomorphic encryption scheme. We demonstrate some key steps of the outer part of the framework in a quantum optics experiment.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 the program to the opposite party. We propose a framework for (interactive) QHE based on the universal circuit approach. It contains a subprocedure of calculating a classical linear polynomial, which can be implemented with quantum or classical methods; apart from the subprocedure, the framework has low requirement on the quantum capabilities of the party who provides the circuit. We illustrate the subprocedure using a quite simple classical protocol with some privacy tradeoff. For a special case of such protocol, we obtain a scheme similar to blind quantum computation but with the output on a different party. Another way of implementing the subprocedure is to use a recently studied quantum check-based protocol, which has low requirement on the quantum capabilities of both parties. The subprocedure could also be implemented with a classical additive homomorphic encryption scheme. We demonstrate some key steps of the outer part of the framework in a quantum optics experiment.

arXiv:1910.03500Oct 8, 20190 citations

On statistically-secure quantum homomorphic encryption

Ching–Yi Lai, Kai-Min Chung

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.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.

arXiv:1705.00139Quantum Information and ComputationAug 1, 201820 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).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.09717Theory of ComputingJan 1, 20186 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.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.12127QuantumApr 13, 20237 citations

Secure Multi-Party Quantum Summation Based on Quantum Homomorphic Encryption

Gang Xu, Fan Yun, Xiu‐Bo Chen +5 more

Secure multi-party computation has been playing a fundamental role in terms of classical cryptography. Quantum homomorphic encryption (QHE) could compute the encrypted data without decryption. At present, most protocols use a semi-honest third party (TP) to protect participants’ secrets. We use a quantum homomorphic encryption scheme instead of TP to protect the privacy of parties. Based on quantum homomorphic encryption, a secure multi-party quantum summation scheme is proposed in which N participants can delegate a server with strong quantum computing power to assist computation. By delegating the computation and key update processes to a server and a semi-honest key center, participants encrypt their private information data using Pauli operators to get the sum. Besides, the server can design and optimize the summation lines itself, and the correct results can be obtained even if the secret information is negative. The correctness analysis showed that the participants could correctly obtain the results of the calculation. The security analysis proves the scheme is resistant to both outside attack and participant’s attack, and is secure against collusive attack by up to N-2 participants. From the theoretical point of view, our protocol can extend to other secure multi-party computing problems.Secure multi-party computation has been playing a fundamental role in terms of classical cryptography. Quantum homomorphic encryption (QHE) could compute the encrypted data without decryption. At present, most protocols use a semi-honest third party (TP) to protect participants’ secrets. We use a quantum homomorphic encryption scheme instead of TP to protect the privacy of parties. Based on quantum homomorphic encryption, a secure multi-party quantum summation scheme is proposed in which N participants can delegate a server with strong quantum computing power to assist computation. By delegating the computation and key update processes to a server and a semi-honest key center, participants encrypt their private information data using Pauli operators to get the sum. Besides, the server can design and optimize the summation lines itself, and the correct results can be obtained even if the secret information is negative. The correctness analysis showed that the participants could correctly obtain the results of the calculation. The security analysis proves the scheme is resistant to both outside attack and participant’s attack, and is secure against collusive attack by up to N-2 participants. From the theoretical point of view, our protocol can extend to other secure multi-party computing problems.

Intelligent Automation & Soft ComputingJan 1, 202217 citations

\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).