Limitations on information-theoretically-secure quantum homomorphic encryption

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.

Figure 1

A schematic diagram for a general quantum homomorphic encryption scheme with input data $|{\psi }_i\rangle$ and output $|{\psi }_o\rangle$. The state $|{\psi }_e\rangle$ represents the initial state of Alice's key, while $U_e$ and $U_d$ are Alice's encryption and decryption operators. Both parties are also allowed an ancilla system, and access to a shared entanglement resource. Alice's decryption key corresponds to the subsystem she retains after applying $U_e$ to her system. Note that no assumption is made about the dimensionality of subsystems. Time points $t_1$ and $t_2$, used in the proof of Theorem 1, are also shown.