Introduction {#Sec1}
============

Due to the great challenge of building large-scale quantum computers, it is very likely that only a few powerful quantum computers are initially available and act as quantum servers. Suppose Alice has some confidential data and wishes to search on them with the aid of a remote quantum server, Bob, but is unwilling to reveal the data to him. A natural approach to achieving this is to encrypt the data before handing them over and to let Bob directly search on the cipher-state, namely, to employ a quantum search scheme on encrypted data.

The classical counterpart of this issue has been studied extensively, where mainly two approaches are adopted: (1) devising a special cryptosystem supporting search operations and (2) utilizing a pre-built searchable cipher index offered by the client, both of which provide computational security rather than information-theoretic security^[@CR1]^. In the quantum context, Sun proposed a quantum symmetric searchable encryption scheme for classical inputs^[@CR2]^, in which encryption and decryption are rotations along a coordinate axis, and the secret key composes of random rotation angles. The search procedure of this scheme is to linearly check and compare the encrypted items, which is inefficient for a large search space. Intuitively, linear search on encrypted data could be accelerated by Grover's algorithm^[@CR3]^, provided that there exists an encryption method allowing quantum operations without the encryption key. Fortunately, quantum homomorphic encryption (QHE) satisfies this requirement, which intrigued us to take advantage of its merits and to construct a quantum homomorphic search protocol.

The notion of QHE was first introduced by Liang^[@CR4]^ in 2013, who observed the commutation rules between the encryption operators of quantum one-time pad (QOTP)^[@CR5]^ and a universal set of quantum gates (containing rotation operators and CNOT gate) and demonstrated a symmetric one-party QHE scheme where homomorphic evaluations require the secret key. Later, he presented an interactive two-party scheme^[@CR6]^ based on commutation rules for another universal gate set (consisting of *H*, *S*, CNOT and *T* gates). Aside from QHE, there are many other closely related constructions based on the combination of QOTP and commutation rules, such as secure assisted quantum computation^[@CR7]^, quantum computing on encrypted data^[@CR8]^, and delegating private quantum computations^[@CR9]^, which could be considered as early forms of QHE.

In 2014, Yu *et al*.^[@CR10]^ came up with a no-go result on QHE, which concludes that "quantum mechanics does not allow for efficient information-theoretically-secure fully homomorphic encryption scheme". In view of this result, Broadbent and Jeffery devised two remarkable *T* gadgets for non-Clifford circuits and presented three efficient QHE schemes based on classical q-IND-CPA secure homomorphic encryption (CHE), one of which is designed for Clifford circuits and the other two are for non-Clifford circuits with a limited number of *T* gates^[@CR11]^. They also formally defined an important property---compactness---for QHE. In outline, a QHE scheme is compact if the circuit complexity of the decryption procedure for any allowed evaluation *C* is independent of the circuit complexity of *C*; the decryption procedure is the task being performed by the client to recover the outcome evaluated by the server. For example, the interactive schemes^[@CR4],[@CR6]--[@CR9]^ based on QOTP are not compact, and some non-interactive ones---the CL scheme for Clifford circuits and the AUX scheme for circuits with constant *T*-depth---provided by Broadbent and Jeffery^[@CR11]^ are compact. Subsequently, Dulek and Schaffner extended Broadbent's work and proposed a QHE scheme for polynomial-sized *T* gates utilizing another kind of *T* gadget^[@CR12]^. In addition, other issues, such as multi-party decryption, circuit privacy, quasi-compactness, and generalization to classical encrypted data are also investigated in various QHE schemes^[@CR13]--[@CR15]^. It should be noted that introducing CHE (combining with some sophisticated techniques) into QHE is double edged: it not only reduces the communication complexity and gains compactness or quasi-compactness but also compromises security and narrows the schemes' applicability. These hybrid QHE schemes cannot reach perfect security as many pure quantum cryptosystems do, and they become inefficient for circuits with a large number of *T* gates (e.g. the circuit of Grover's search).

Apart from the foregoing QHE schemes based on CHE and QOTP, constructions utilizing other techniques are explored, such as a private-key QHE protocol based on the centralizer of a subgroup of operations^[@CR16]^, a practical somewhat-secure QHE on coherent states^[@CR17]^, a QHE scheme for circuits with constant number of *T* gates based on quantum codes^[@CR18]^, and a QHE scheme with multiple evaluators based on (*k*,*n*)-threshold quantum state sharing^[@CR19]^. These schemes only apply to limited circuit families.

In consideration of the huge number of iterations in Grover's search, where each Grover iteration contains *T* gates, we need to fall back on the early QHE schemes with interactions^[@CR6],[@CR8],[@CR9]^ rather than non-interactive ones^[@CR11],[@CR12]^ based on CHE, because the latter is unable to handle so many *T* gates. To reduce Alice's workload, a trusted third party is introduced. To prevent Bob from knowing the original search condition (say, *C*~o~), the proposed search protocol encrypts the qubits involved in *C*~o~ twice and let Bob searches on the cipher state according to a new search condition *C*~n~, which can be viewed as the cipher-text of *C*~o~.

As for Clifford circuits without any *T* gate, their homomorphic evaluations become much easier, since the Clifford gates can be applied on a cipher state without causing any undesirable error. For this type of circuits, a compact and perfectly secure homomorphic evaluating protocol is proposed. A main distinction between the two protocols lies in the different treatments on the key-update process, which is an important part of QOTP-based QHE.

Key Update in Quantum Homomorphic Encryption Based on Quantum One-time Pad {#Sec2}
==========================================================================

A QHE scheme consists of four components: key generation, encryption, decryption, and homomorphic evaluation. In a QOTP-based QHE scheme, quantum states are encrypted or decrypted using QOTP, which transforms the input state qubit by qubit with Pauli operators {*X*, *Z*} depending on a classical encryption key *ek* = (*x*~0~, *z*~0~). In this scheme, the homomorphic evaluation for a Clifford gate is to apply this gate directly on an encrypted state, whereas the evaluation for a non-Clifford gate (the *T* gate) is to perform a *T* gadget on the cipher-state. Additionally, the decryption key for *ek* needs to be refreshed synchronously with respect to the evaluation.

For clarity, we rephrase the key-update rules for arbitrary unitary transforms and quantum measurements in Algorithms 1 and 2, respectively, which are derived from refs. ^[@CR7],[@CR8]^. The frequently used variables in this paper are listed in Table [1](#Tab1){ref-type="table"}.Table 1Explanations for frequently used variables and notations.Variables and notationsExplanations$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$M,m,n(m,n\in {{\mathbb{N}}}^{+})$$\end{document}$*M* = 2^*m*^ is the number of items to be searched, and each item data(*j*) (*j* \< *M*) contains *n* bits.*ek*, *dk*, *sk*, *eek*, *ddkek* and *dk* are encryption and decryption keys for Alice's data, respectively; *sk* is used to encrypt *dk* in Protocol 1; *eek* and *ddk* are used to encrypt *ek* and recover *dk*, respectively, in Protocol 2.$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${x}_{r}(k),{z}_{r}(k)(r,k\in {\mathbb{N}})$$\end{document}$*eek*(*k*)(*x*~*r*~, *z*~*r*~) (*r* \> 0) is the 2*n*-bit intermediate key for the *r*^th^ round of key-updating; *x*~0~ and *z*~0~ constitute *ek*; *x*~*r*~(*k*), *z*~*r*~(*k*), and *eek*(*k*) are the *k*^th^ bit of *x*~*r*~, *z*~*r*~, and *eek*, respectively.*X*~*i*~, *Y*~*i*~, *Z*~*i*~, *H*~*i*~, *S*~*i*~, *T*~*i*~CNOT~*i*,*l*~*X*~*i*~, *Y*~*i*~, *Z*~*i*~, *H*~*i*~, *S*~*i*~ or *T*~*i*~ denotes applying a *X*, *Y*, *Z*, *H*, *S* or *T* gate on the *i*^th^ qubit of the input state and letting the other qubits unchanged; CNOT~*i*,*l*~ denotes performing a CNOT gate on the *i*^th^ and *l*^th^ qubits of the input, which act as the control and target qubits, respectively. Note that *S* and *T* gates are called *P* and *R* gates, respectively, in ref. ^[@CR8]^.

**Algorithm 1** (Key update for unitary transforms). Suppose that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\psi \right\rangle $$\end{document}$ is an *n*-qubit state, *V* is an *n*-qubit unitary transform consisting of gates from the universal gate set $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{G}}=\{I,X,Y,Z,H,S,\,{\rm{CNOT}}\,,T\}$$\end{document}$, and *G* is a two-level unitary transform that merely performs one gate from $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{G}}$$\end{document}$ on two or fewer qubits. Let *ek* = (*x*~0~, *z*~0~) be an encryption key and *dk*~*r*~ = (*x*~*r*~, *z*~*r*~) the decryption key for *V* and *ek*, such that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$V\left({\otimes }_{k=1}^{n}{Z}^{{z}_{0}(k)}{X}^{{x}_{0}(k)}\right)\left|\psi \right\rangle =\left({\otimes }_{k=1}^{n}{Z}^{{z}_{r}(k)}{X}^{{x}_{r}(k)}\right)V\left|\psi \right\rangle $$\end{document}$. Then the updated decryption key *dk*~*r*+1~ = (*x*~*r*+1~, *z*~*r*+1~) for *G* ⋅ *V* and *ek* satisfying $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$G\cdot V({\otimes }_{k=1}^{n}{Z}^{{z}_{0}(k)}{X}^{{x}_{0}(k)})| \psi \rangle =$$\end{document}$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$({\otimes }_{k=1}^{n}{Z}^{{z}_{r+1}(k)}{X}^{{x}_{r+1}(k)})G\cdot V| \psi \rangle $$\end{document}$ is calculated as follows: If *G* = *I*, *X*~*i*~, *Y*~*i*~, or*Z*~*i*~, then *dk*~*r*+1~ = *dk*~*r*~.If *G* = *H*~*i*~, then (*x*~*r*+1~(*i*), *z*~*r*+1~(*i*)) = (*z*~*r*~(*i*), *x*~*r*~(*i*)).If *G* = *S*~*i*~, then (*x*~*r*+1~(*i*), *z*~*r*+1~(*i*)) = (*x*~*r*~(*i*), *x*~*r*~(*i*) ⊕ *z*~*r*~(*i*)).If *G* = CNOT~*i*,*l*~, then (*x*~*r*+1~(*i*), *z*~*r*+1~(*i*)) = (*x*~*r*~(*i*), *z*~*r*~(*i*) ⊕ *z*~*r*~(*l*)) and (*x*~*r*+1~(*l*), *z*~*r*+1~(*l*)) = (*x*~*r*~(*i*) ⊕ *x*~*r*~(*l*), *z*~*r*~(*l*)).If *G* = *T*~*i*~ (suppose the secret bits Alice chooses for this *T* gate are $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\hat{y}}$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\widehat{d}$$\end{document}$, and the related one-bit measurement result from the server is $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\hat{c}}$$\end{document}$), then $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left({x}_{r+1}(i),{z}_{r+1}(i)\right)=[{x}_{r}(i)\oplus {\hat{c}},{x}_{r}(i)\cdot ({\hat{c}}\oplus {\hat{y}}\oplus 1)\oplus {z}_{r}(i)\oplus \widehat{d}\oplus {\hat{y}}]$$\end{document}$ (where  ⊕  denotes addition modulo 2).

**Algorithm 2** (Key update for quantum measurements). Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\widetilde{\psi }\right\rangle =\left({\otimes }_{k=1}^{n}{Z}^{{z}_{r}(k)}{X}^{{x}_{r}(k)}\right)\left|\psi \right\rangle $$\end{document}$ be an *n*-qubit cipher state under key *dk*~*r*~ = (*x*~*r*~, *z*~*r*~) and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{M}}$$\end{document}$ a computational basis measurement. Then the updated decryption key *dk*~*r*+1~ for the classical measurement outcome $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{M}}\left|\widetilde{\psi }\right\rangle \equiv {\widetilde{\psi }}_{{\mathcal{M}}}$$\end{document}$ satisfying $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\widetilde{\psi }}_{{\mathcal{M}}}\oplus d{k}_{r+1}={\psi }_{{\mathcal{M}}}$$\end{document}$ is *dk*~*r*+1~ = *x*~*r*~, where $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\psi }_{{\mathcal{M}}}$$\end{document}$ is the underlying plaintext of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\widetilde{\psi }}_{{\mathcal{M}}}$$\end{document}$.

It follows that, the final decryption key *dk* for a unitary transform *U* depends on the encryption key *ek*, the concrete circuit $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${{\mathcal{C}}}_{U}$$\end{document}$ of *U*, the secret parameters (*y*, *d*) for the *T* gates in $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${{\mathcal{C}}}_{U}$$\end{document}$, and the measurement result *c* corresponding to those *T* gates. Hence, during a homomorphic execution of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${{\mathcal{C}}}_{U}$$\end{document}$, there is a unitary decryption-key-obtaining transform $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$D{K}_{{{\mathcal{C}}}_{U}}$$\end{document}$ that satisfies the equation $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|ek,y,d,c,dk\right\rangle =D{K}_{{{\mathcal{C}}}_{U}}\left|ek,y,d,c,0\right\rangle $$\end{document}$, where $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|0\right\rangle $$\end{document}$ serve as the auxiliary qubits in workspace.

A critical barrier on the route to an efficient and perfectly secure quantum fully homomorphic encryption scheme is caused by the *T* gate, which, however, is an indispensable ingredient of universal gate set. To homomorphically perform a *T* gate, a phase correction depending on the encryption key has to be applied, whereas the key cannot be revealed to the server. To overcome this obstacle, some schemes introduce a round of communication conveying some evaluated information determined by the encryption key between the client and the server^[@CR6],[@CR8],[@CR9]^, whereas others resort to classical homomorphic encryption^[@CR11],[@CR12]^.

On the other hand, homomorphically performing a Clifford circuit (not involving any *T* gate) could be more convenient. Before we present this, we conclude an important feature of the key-update procedure for Clifford circuits in Lemma 1, which will be used in our second protocol.

**Lemma 1**. The key-update process corresponding to a Clifford circuit $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ acting on *n* qubits can be encoded as a 4*n*^2^-bit string $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$st{r}_{\,{\rm{ku}}\,}^{{\mathcal{C}}}$$\end{document}$, whose computational complexity is *O*(*n*log2*n*).

*Proof*. According to Algorithm 1, the key-update operations for gates except *T* only involve bit exchanges and some  ⊕. Since bit exchange (*d*~*j*~, *d*~*k*~) → (*d*~*k*~, *d*~*j*~) (where *d*~*j*~ is the *j*^th^ bit of *d*, *j* ≠ *k*, and *d* ∈ {0, 1}^2*n*^) can be implemented with three  ⊕ : (*d*~*j*~, *d*~*k*~) → (*d*~*j*~, *d*~*j*~ ⊕ *d*~*k*~), (*d*~*j*~, *d*~*j*~ ⊕ *d*~*k*~) → (*d*~*j*~ ⊕ (*d*~*j*~ ⊕ *d*~*k*~), *d*~*j*~ ⊕ *d*~*k*~) = (*d*~*k*~, *d*~*j*~ ⊕ *d*~*k*~), (*d*~*k*~, *d*~*j*~ ⊕ *d*~*k*~) → (*d*~*k*~, (*d*~*j*~ ⊕ *d*~*k*~) ⊕ *d*~*k*~) = (*d*~*k*~, *d*~*j*~), the key-update procedure for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ can be implemented by a sequence of commands of the form (*d*~*j*~, *d*~*k*~) → (*d*~*j*~, *d*~*j*~ ⊕ *d*~*k*~); that is, add (modulo 2) one key bit *d*~*j*~ to a target key bit *d*~*k*~. During this procedure, each key bit may act as a target and other key bits that are *effectively* added to this target constitute a set of size less than 2*n*. Here, a bit *d*~*j*~ is *effectively* to *d*~*k*~ if *d*~*j*~ is added to *d*~*k*~ odd times. Note that the operations that adding one bit to another bit for even times are also part of the key-update process and convey considerable information about $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$, which are ignored due to the calculating rule of  ⊕ . Thus, each decryption key bit can be expressed as *u*~0~ ⋅ *d*~0~ ⊕ *u*~1~ ⋅ *d*~1~ ⊕ ⋯ ⊕ *u*~2*n*−1~ ⋅ *d*~2*n*−1~ (*u*~*j*~ ∈ {0, 1}), which can be encoded as a 2*n*-bit string *u*~0~*u*~1~...*u*~2*n*−1~. Since 2*n* additions can be parallelized, they can be computed with log2*n* steps. As a result, the complete decryption key can be encoded as a 4*n*^2^-bit string $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$st{r}_{\,{\rm{ku}}\,}^{{\mathcal{C}}}$$\end{document}$ and be computed with *O*(*n*log2*n*) steps.□

Quantum Search on Encrypted Data {#Sec3}
================================

Since Grover's algorithm excepting the final measurement is a unitary transform, one can certainly apply it homomorphically on a cipher-state and then obtain the encrypted search result. Here, we consider the situation that Alice wants Bob to search on her encrypted superposition state (which could be obtained by a QRAM addressing scheme^[@CR20]^) but does not care how he carries out the operations exactly. In other words, Alice prefers to prepare the input data and handles the evaluated output rather than participate in the entire process of the evaluation. This requirement is reasonable in the sense that it coincides with the relationship between the client and the server in cloud computing, which is a prevalent paradigm nowadays.

It is known that Grover's search is made up of a sequence of Grover iterations, each of which contains an oracle that is able to mark items satisfying a specific search condition. When it is used to speed up the solution of an NP problem of size *m* (there are at least 2^*m*^ candidates for the solution of this problem), the oracle requires *O*(poly(*m*)) elementary gates (where poly(*m*) is a polynomial in *m*), since a solution of an NP problem can be recognized in polynomial time. Since each Grover iteration contains poly(*m*)*T* gates, the total number of *T* gates in the search circuit reaches *O*(2^*m*/2^ ⋅ poly(*m*)), which is beyond the capability of CHE-based QHE schemes. A dilemma seems to appear: the key shall neither be updated homomorphically using CHE by Bob^[@CR11],[@CR12]^ nor be renewed interactively by Alice. As a way out of this impasse, we introduce a third party---a trusted key center, Carol---between Alice and Bob, to undertake the interactive work.

Outsourcing key update to a trusted key center {#Sec4}
----------------------------------------------

In QHE, key generation includes randomly choosing a classical encryption key and calculating the decryption key using the key update algorithm, which becomes long and tedious if there are a large number of *T* gates in the evaluation. To ease the burden of Alice and to keep the homomorphic search going successfully, we introduce a trusted key center, Carol, to negotiate a random encryption key with Alice and then to calculate the corresponding decryption key by communicating with Bob. That is, we divide the client in the interactive QHE scheme^[@CR9]^ into two parts: a thin client (Alice) and a trusted key center (Carol). The requirements and constraints on Carol are given in Constraint 1.

**Constraint 1** (Requirements and constraints on the key center). The key center Carol obeys the following four constraints: Carol is a classical computer augmented with the ability to prepare qubits in $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{| +\rangle =(| 0\rangle +| 1\rangle )/\sqrt{2}$$\end{document}$, $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$|-\rangle =(|0\rangle -|1\rangle )/\sqrt{2}$$\end{document}$, $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\,| \,{+}_{y}\rangle =(| 0\rangle +i| 1\rangle )/\sqrt{2}$$\end{document}$, $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$| {-}_{y}\rangle =(| 0\rangle -i| 1\rangle )/\sqrt{2}\}$$\end{document}$, which serve as auxiliary qubits for *T* gates in homomorphic evaluations as well as the encoded results of random bits in quantum key distribution (QKD).Carol honestly obeys the subsequent search protocol and would not reveal the encryption and decryption keys to parties other than Alice.Carol would not reveal the circuit detail (including the auxiliary states and the measurement outcomes) performed by Bob to parties other than Bob.Carol would not be corrupted by any adversary who wishes to obtain some information about the plain input provided by Alice or the quantum circuit performed by Bob.She would not reveal the key-update procedure (including the intermediate keys) to others (including Alice and Bob).

Our search protocol runs among Alice (the client), Bob (the search server), and Carol (the trusted key center) as illustrated in Fig. [1](#Fig1){ref-type="fig"}, where key generation is split into three parts: Alice negotiates an encryption key with Carol, Carol calculates the corresponding decryption key using the key-update algorithm, and Carol securely sends the decryption key to Alice. With the help of QKD and classical one-time pad (COTP), these tasks can be accomplished with perfect security. Moreover, since the key update operations are classical, Carol could be a classical computer augmented with the ability to prepare only four types of quantum states listed in Constraint 1. In this protocol, Alice needs to prepare superposed data items using QRAMs and to perform single-qubit measurements (in the Pauli-*X* and *Y* bases), Pauli operators {*X*, *Z*}, and classical bitwise additions (modulo 2) to implement the BB84 protocol, encrypt the plain data, and decrypt the evaluated result, respectively.Figure 1Tasks of each party and interactions among parties. First, Alice negotiates an encryption key for her data with Carol. Then, Alice encrypts her superposed data with the encryption key and sends the encrypted state to Bob. Once Bob receives the encrypted data, the homomorphic search and the key-update process (performed by Carol) begin and proceed synchronously. During the homomorphic search, Carol sends some auxiliary data to Bob and then receives some related measurement results, which are needed for key update. When Bob finishes the homomorphic search and obtains an encrypted solution, Carol finishes the key-update process and produces the corresponding decryption key as well. After that, Alice receives the search result and the decryption key from Bob and Carol, respectively. Finally, Alice decrypts the ciphered search result with the decryption key.

A homomorphic search protocol with a key center {#Sec5}
-----------------------------------------------

With the assistance of the key center, an interactive protocol for quantum search on encrypted data proceeds as shown in Protocol 1. For clarity, we call the the collection of qubits (identified by their locations in Alice's data $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|{\psi }_{0}\right\rangle $$\end{document}$) appearing in the plain (original) search condition *C*~o~ "the search field" of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|{\psi }_{0}\right\rangle $$\end{document}$, and denote it by $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\zeta \right\rangle $$\end{document}$, which is a part of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|{\psi }_{0}\right\rangle $$\end{document}$. In the first two steps, Alice encrypts $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\zeta \right\rangle $$\end{document}$ and produces a modified search condition to conceal the original one from Bob, so that Bob knows nothing about her plain search target. To briefly explain this, suppose that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\zeta \right\rangle $$\end{document}$ consists of the 3rd, 5th and 6th qubits of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|{\psi }_{0}\right\rangle $$\end{document}$, Alice wants to find out the items satisfying the clause $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${C}_{{\rm{o}}}={d}_{3}\vee \bar{{d}_{5}}\vee {d}_{6}$$\end{document}$ (a clause in 3-conjunctive normal form, where *d*~*j*~ is the *j*th bit of a data item *d*, $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\bar{{d}_{j}}\equiv 1\oplus {d}_{j}$$\end{document}$, the symbol "∨ " indicates "OR"), and the 3-bit encryption key *srk* for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\zeta \right\rangle $$\end{document}$ is *r*~0~*r*~1~*r*~2~ (*r*~0~, *r*~1~, *r*~2~ ∈ {0, 1}), then $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${C}_{{\rm{n}}}=({d}_{3}\oplus {r}_{0})\vee \left(\bar{{d}_{5}}\oplus {r}_{1}\right)\vee ({d}_{6}\oplus {r}_{2})$$\end{document}$. From Bob's point of view, *srk* can be arbitrary 3-bit string, each with the same probability 1/8 and maps the received *C*~n~ to one of the eight possible clauses associated with $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\zeta \right\rangle $$\end{document}$, that is, *P*(*C*~o~∣*C*~n~) = *P*(*C*~o~) for any *C*~n~ and any *C*~o~, so Bob knows nothing about the plain search condition from a given *C*~n~.

The schematic circuit for this protocol is depicted in Fig. [2](#Fig2){ref-type="fig"}. To make our circuit more comprehensible, we adapt the *T* gadget in ref. ^[@CR8]^ to Fig. [2](#Fig2){ref-type="fig"} and illustrate the *j*^th^  *T* gadget in the *l*^th^  *G* iteration on the *g*^th^ wire in Fig. [3](#Fig3){ref-type="fig"}, where $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|{\psi }_{g}\right\rangle $$\end{document}$ is the *g*^th^ qubit of the plain state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\psi \right\rangle $$\end{document}$, and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${Z}^{ {\hat{z}} }{X}^{\widehat{x}}\left|{\psi }_{g}\right\rangle $$\end{document}$ is the encrypted qubit of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|{\psi }_{g}\right\rangle $$\end{document}$ just before the application of this *T* gadget.Figure 2Schematic circuit implementing Protocol 1. There are $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$t=O\left(\sqrt{M}\right)$$\end{document}$*G* iterations in the circuit, which carries out the homomorphic search transform denoted by *hGrv*. A *G* iteration is a homomorphic version of the standard Grover iteration, which is obtained by replacing each *T* gate in the normal Grover iteration with the *T* gadget illustrated in Fig. [3](#Fig3){ref-type="fig"}. Suppose there are *sT* gadgets in each *G* iteration; then, the *l*^th^  *G* iteration (*l* ∈ {1, 2, ..., *t*}) needs an auxiliary state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|au{x}_{l}\right\rangle $$\end{document}$ of *s* qubits and an evaluation key *w*~*l*~ of *s* bits to perform *sS* corrections. $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${P}_{{y}_{l},{d}_{l}}\equiv {\otimes }_{j=1}^{s}{P}_{{y}_{l}(j),{d}_{l}(j)}$$\end{document}$ is the phase transform for the *l*^th^  *G* iteration, where *y*~*l*~ and *d*~*l*~ are *s*-bit binary strings randomly chosen by Carol for all *T* gadgets in the *l*^th^  *G* iteration, and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${P}_{{y}_{l}(j),{d}_{l}(j)}\equiv {Z}^{{d}_{l}(j)}{S}^{{y}_{l}(j)}$$\end{document}$ is the phase transform for the *j*^th^  *T* gadget in the *l*^th^  *G* iteration. Applying $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${P}_{{y}_{l}(j),{d}_{l}(j)}$$\end{document}$ on $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|+\right\rangle $$\end{document}$ gives the *j*^th^ qubit of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|au{x}_{l}\right\rangle $$\end{document}$, which is $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|+\right\rangle ,\left|-\right\rangle ,\left|{+}_{y}\right\rangle $$\end{document}$ or $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|{-}_{y}\right\rangle $$\end{document}$. *w*~*l*~ is the Boolean XOR result between some intermediate key bits and *y*~*l*~; *c*~*l*~ is an *s*-bit measurement result from the *l*^th^  *G* iteration. *y*~*l*~, *d*~*l*~ and *c*~*l*~ are involved in key update for the *l*^th^  *G* iteration.Figure 3The *T* gadget within the schematic circuit.

**Protocol 1**. Homomorphic quantum search on encrypted states Alice prepares a plain superposition state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|{\psi }_{0}\right\rangle =\frac{1}{\sqrt{M}}{\sum }_{j=0}^{M-1}\left|\,{\rm{data}}\,(j)\right\rangle $$\end{document}$ from her classical database.Alice encrypts the search fields $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\zeta \right\rangle $$\end{document}$ (within her plain state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|{\psi }_{0}\right\rangle $$\end{document}$) with a random encryption key *srk* using QOTP and obtains an encrypted result $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$En{c}_{srk}\left|\zeta \right\rangle $$\end{document}$, which is a part of the partially encrypted state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\psi \right\rangle =En{c}_{srk}\left|{\psi }_{0}\right\rangle $$\end{document}$ (Here, *Enk*~*srk*~ is the extended encryption transform on $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|{\psi }_{0}\right\rangle $$\end{document}$, which applies the encryption on $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\zeta \right\rangle $$\end{document}$ and leaves the other qubits unaffected).Alice translates the original search condition *C*~o~ (on $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\zeta \right\rangle $$\end{document}$) into the new condition *C*~n~ on $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$En{c}_{srk}\left|\zeta \right\rangle $$\end{document}$ such that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\zeta \right\rangle $$\end{document}$ satisfies *C*~o~ if and only if $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$En{c}_{srk}\left|\zeta \right\rangle $$\end{document}$ satisfies *C*~n~.Alice sends a number *n*---the length of her encrypted state---to Carol.Carol shares a binary string of 3*n* random bits with Alice by the BB84 protocol^[@CR21]^, where $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|+\right\rangle ,\left|{+}_{y}\right\rangle $$\end{document}$ stands for 0, and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|-\right\rangle ,\left|{-}_{y}\right\rangle $$\end{document}$ stands for 1. The first 2*n* bits of the binary string act as *ek* and the remaining *n* bits act as the encryption key *sk* for *dk*.Alice encrypts $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\psi \right\rangle $$\end{document}$ with *ek* = (*x*~0~, *z*~0~) and sends the encrypted state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${Enc}_{ek}\left|\psi \right\rangle ={\otimes }_{k=1}^{n}{Z}^{{z}_{0}(k)}{X}^{{x}_{0}(k)}\left|\psi \right\rangle $$\end{document}$ along with *C*~n~ to Bob.Bob searches on $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$En{c}_{ek}\left|\psi \right\rangle $$\end{document}$ homomorphically using *hGrv*, and Carol updates the key synchronously. During the search, once a *T* gate appears, Bob asks Carol to send an auxiliary qubit from $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{\left|+\right\rangle ,\left|-\right\rangle ,\left|{+}_{y}\right\rangle ,\left|{-}_{y}\right\rangle \}$$\end{document}$ along with a related evaluating key bit (*w*~*l*~(*j*) in Fig. [3](#Fig3){ref-type="fig"}) to him and then performs the *T* gadget with those data. After that, he returns a one-bit measurement result (*c*~*l*~(*j*) in Fig. [3](#Fig3){ref-type="fig"}) to Carol for key update.When the homomorphic search is completed, Bob measures the search result $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$hGrv(En{c}_{ek}\left|\psi \right\rangle )$$\end{document}$ and returns the (encrypted) classical outcome $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{M}}[hGrv(En{c}_{ek}\left|\psi \right\rangle )]$$\end{document}$ to Alice. Meanwhile, Carol finishes the key update process and obtains the decryption key *dk* for *ek* and *hGrv*; she then encrypts *dk* with *sk* using COTP and sends it to Alice.Alice first recovers *dk* with *sk* and decrypts $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{M}}[hGrv(En{c}_{ek}\left|\psi \right\rangle )]$$\end{document}$ with *dk* to obtain the partially encrypted search result, then recovers the search fields in the search result with *srk*. After that, she can check this result with her search condition and decide whether Bob honestly performed the homomorphic search.

In step 1, Alice needs to utilize two kinds of QRAMs: the first one maps $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\frac{1}{\sqrt{M}}{\sum }_{j=0}^{M-1}\left|j\right\rangle \left|0\right\rangle $$\end{document}$ to $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\frac{1}{\sqrt{M}}{\sum }_{j=0}^{M-1}\left|j\right\rangle \left|\,{\rm{data}}\,(j)\right\rangle $$\end{document}$, which is connected to a memory array where data (*j*) is stored in the *j*th memory cell; the second one maps $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\frac{1}{\sqrt{M}}{\sum }_{j=0}^{M-1}\left|j\right\rangle \left|\,{\rm{data}}\,(j)\right\rangle $$\end{document}$ to $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\frac{1}{\sqrt{M}}{\sum }_{j=0}^{M-1}\left|0\right\rangle \left|\,{\rm{data}}\,(j)\right\rangle $$\end{document}$, which is connected to a memory where *j* is stored in the data(*j*)th memory cell (we assume that data(*i*) ≠ data(*j*) if *i* ≠ *j*).

In Fig. [2](#Fig2){ref-type="fig"}, Carol gives $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|au{x}_{l}\right\rangle ={P}_{{y}_{l},{d}_{l}}{\otimes }_{j=1}^{s}H\left|0\right\rangle $$\end{document}$ and *w*~*l*~ to Bob for the *l*^th^  *G* iteration, and Bob then returns an *s*-bit measurement result *c*~*l*~ from this iteration to Carol, which is used to update the key. More precisely, as illustrated in Fig. [3](#Fig3){ref-type="fig"}, the *j*^th^ qubit of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|au{x}_{l}\right\rangle $$\end{document}$ and the *j*^th^ bit of *w*~*l*~ (or *w*~*l*~(*j*)) together with an encrypted qubit $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${Z}^{ {\hat{z}} }{X}^{\widehat{x}}\left|{\psi }_{g}\right\rangle $$\end{document}$ under key $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$(\widehat{x}, {\hat{z}} )(\widehat{x}, {\hat{z}} \in \{0,1\})$$\end{document}$ act as the input of the *j*^th^  *T* gadget in the *l*^th^  *G* iteration. This *T* gadget then outputs a one-bit measurement outcome *c*~*l*~(*j*) and an encrypted result of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$T\left|{\psi }_{g}\right\rangle $$\end{document}$ under a refreshed key $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left(\widehat{x}{\prime} , {\hat{z}} {\prime} \right)\ \left(\widehat{x}{\prime} , {\hat{z}} {\prime} \in \{0,1\}\right)$$\end{document}$, which satisfies $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\widehat{x}{\prime} =\widehat{x}\oplus {c}_{l}(j)$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$ {\hat{z}} {\prime} =\widehat{x}[{c}_{l}(j)\oplus {y}_{l}(j)\oplus 1]\oplus  {\hat{z}} \oplus {d}_{l}(j)\oplus {y}_{l}(j)$$\end{document}$. The classical decryption (performing a bitwise addition between the encrypted search result and the decryption key) after the quantum measurement is omitted.

Simulation of two-qubit homomorphic search {#Sec6}
------------------------------------------

To verify the effectiveness of Protocol 1, we present the detailed circuit for two-qubit homomorphic search in Supplementary Fig. [S1](#MOESM1){ref-type="media"} and simulate its process using MATLAB. The detailed simulation code is listed in the Supplementary [File](#MOESM1){ref-type="media"}, which always outputs the expected search target.

Without loss of generality, suppose Alice wants to find the item 10 out of the set {00, 01, 10, 11} (the partially encrypted results corresponding to $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$En{c}_{srk}\left|{\psi }_{0}\right\rangle $$\end{document}$); thus, a single Grover iteration is enough, and the oracle within the iteration can be built with *X* and Toffoli gates as illustrated in Fig. [4](#Fig4){ref-type="fig"}^[@CR22]^. After decomposing the Toffoli gate into the universal gates supporting homomorphic evaluations (i.e. *X*, *Z*, *H*, *S*, CNOT, *T*), a quantum circuit for two-qubit plain-state search is obtained as depicted in Fig. [5](#Fig5){ref-type="fig"}. To perform a two-qubit cipher-state search, this circuit needs to be transformed into its homomorphic version, which is achieved by replacing each *T* gate (or *T*^†^ gate) in Fig. [5](#Fig5){ref-type="fig"} with a *T* gadget (or *T*^†^ gadget). The *T*^†^ gadget is obtained by replacing each *S* gate in Fig. [3](#Fig3){ref-type="fig"} with an *S*^†^ gate. The key-update rules for *T*^†^ and *T* gadgets are identical.Figure 4The oracle for finding 10 out of {00, 01, 10, 11}.Figure 5The two-qubit Grover's search circuit.

With QOTP encryption and COTP decryption being included, the resultant homomorphic quantum search circuit for two-qubit states is presented in Supplementary Fig. [S1](#MOESM1){ref-type="media"}. The input of this circuit is the superposed (partially encrypted) state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\psi \right\rangle =\frac{1}{2}(\left|00\right\rangle +\left|01\right\rangle +\left|10\right\rangle +\left|11\right\rangle )$$\end{document}$ along with the oracle qubit $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\,| \,-\rangle $$\end{document}$, and the output should be the classical search target (still partially encrypted) together with the unchanged oracle qubit.

In outline, the simulation proceeds in six steps, where the operations carried out by the three parties are included. Randomly generate a four-bit encryption key *ek* = (*x*~0~, *z*~0~) for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\psi \right\rangle $$\end{document}$.Randomly generate a 14-bit evaluation key *evk* = (*y*~1~, *d*~1~) for the seven *T* gadgets (in Supplementary Fig. [S1](#MOESM1){ref-type="media"}).Encrypt $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\psi \right\rangle \left|-\right\rangle $$\end{document}$ with *ek* using QOTP. The encrypted result acts as the input state *encState* of the quantum homomorphic search.Perform the homomorphic search circuit on *encState* and obtain the encrypted output state. Meanwhile, refresh the intermediate key using the key update algorithm.Measure the encrypted output state; update the intermediate key and then get a two-bit decryption key *dk*.Decrypt the output cipher-state with *dk* using COTP and get the search result.

The simulation indicates that with different encryption keys (*ek* = (*x*~0~, *z*~0~)), evaluation keys (*evk* = (*y*~1~, *d*~1~)) and intermediate measurement results (*c*~1~), one may get different decryption keys (*dk*) and different encrypted search results, but the decrypted outcome is always 10---the partially encrypted search target that we predetermined at the beginning of this section. Here, we list some representative outcomes in Table [2](#Tab2){ref-type="table"}, where the last bit of *x*~0~ and the last bit of *z*~0~ stay 0 since the oracle qubit does not need to be encrypted.Table 2Outcomes of the simulation.input state*ekevkc*~1~Encrypted result*dk*Decrypted result$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$| +\rangle | +\rangle $$\end{document}$*x*~0~ = 100*y*~1~ = 10101101110111011110*z*~0~ = 110*d*~1~ = 0111001*x*~0~ = 100*y*~1~ = 111001110000100010*z*~0~ = 010*d*~1~ = 1011010*x*~0~ = 100*y*~1~ = 010000100001010111*z*~0~ = 100*d*~1~ = 0000101*x*~0~ = 010*y*~1~ = 000001110011011101*z*~0~ = 110*d*~1~ = 0111110*x*~0~ = 110*y*~1~ = 010110010111011000*z*~0~ = 110*d*~1~ = 0001010

A Compact Quantum Homomorphic Evaluation Protocol for Clifford Circuits {#Sec7}
=======================================================================

In this section, we demonstrate a non-interactive homomorphic evaluation protocol for Clifford circuits, where the decryption key can be calculated by Alice with polynomial overhead (with respect to the size of *ek*) by Lemma 1.

**Protocol 2**. Quantum homomorphic evaluation for a Clifford circuit $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$. Alice randomly chooses a 2*n*-bit encryption key *ek* for her *n*-qubit plain input $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\psi \right\rangle $$\end{document}$.Alice encrypts her plain state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\left|\psi \right\rangle $$\end{document}$ with *ek* and sends the ciphered output $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${Enc}_{ek}\left|\psi \right\rangle =$$\end{document}$ $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\otimes }_{k=1}^{n}{Z}^{{z}_{0}(k)}{X}^{{x}_{0}(k)}\left|\psi \right\rangle $$\end{document}$ to Bob.Bob initiate a 4*n*^2^-bit binary string $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$st{r}_{\,{\rm{ku}}\,}^{{\mathcal{C}}}$$\end{document}$, which will encode the simplified key-update expressions for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$, then applies $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ on $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${Enc}_{ek}\left|\psi \right\rangle $$\end{document}$. During the performance of *C*, he synchronously updates $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$st{r}_{\,{\rm{ku}}\,}^{{\mathcal{C}}}$$\end{document}$. When the evaluation is completed, Bob returns the evaluated result $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${U}_{{\mathcal{C}}}({Enc}_{ek}\left|\psi \right\rangle )$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$st{r}_{\,{\rm{ku}}\,}^{{\mathcal{C}}}$$\end{document}$ to Alice.Alice performs the simplified key-update process indicated by $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$st{r}_{\,{\rm{ku}}\,}^{{\mathcal{C}}}$$\end{document}$ on *ek* and obtains the decryption key *dk*, then decrypts $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${U}_{{\mathcal{C}}}({Enc}_{ek}\left|\psi \right\rangle )={Enc}_{dk}({U}_{{\mathcal{C}}}\left|\psi \right\rangle )$$\end{document}$ and gets the plain evaluated result $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${U}_{{\mathcal{C}}}\left|\psi \right\rangle $$\end{document}$.

In step 3, $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${U}_{{\mathcal{C}}}$$\end{document}$ is the unitary transform corresponding to $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$. The simplified key-update expressions for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ consists of 2*n* binary polynomials $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\{{p}_{j}\}}_{j=0}^{2n-1}$$\end{document}$, where *p*~*j*~ indicates the relationship between *ek* and *dk*~*j*~. Concretely, the *k*^th^ bit of *ek* is denoted by a binary-coefficient monomial *x*^*k*^ (which satisfies *x*^*k*^ ⊕ *x*^*k*^= 0) and *dk*~*j*~ is a binary polynomial *dk*~*j*~ = *u*~0~*x*^0^ ⊕ *u*~1~*x*^1^ ⊕ ⋯ ⊕ *u*~2*n*−1~*x*^2*n*−1^ (*u*~*j*~ ∈ {0, 1}). Since *dk* = *ek* before the evaluation, Bob initially sets *p*~*j*~ = *x*^*j*^ for all *j*, which corresponds to the initial value {2^0^, 2^1^, ..., 2^2*n*−1^} of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$st{r}_{\,{\rm{ku}}\,}^{{\mathcal{C}}}$$\end{document}$. As an example, suppose the key-update commands for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ are sequentially (*dk*~*i*~, *dk*~*j*~) → (*dk*~*i*~, *dk*~*j*~ ⊕ *dk*~*i*~), (*dk*~*j*~, *dk*~*k*~) → (*dk*~*j*~ ⊕ *dk*~*k*~, *dk*~*k*~), (*dk*~*i*~, *dk*~*l*~) → (*dk*~*i*~ ⊕ *dk*~*l*~, *dk*~*l*~), (*dk*~*i*~, *dk*~*j*~) → (*dk*~*i*~ ⊕ *dk*~*j*~, *dk*~*j*~), then Bob updates the corresponding polynomials as follows: (1) *p*~*j*~ = *p*~*j*~ ⊕ *p*~*i*~ = *x*^*j*^ ⊕ *x*^*i*^; (2) *p*~*j*~ = *p*~*j*~ ⊕ *p*~*k*~ = (*x*^*j*^ ⊕ *x*^*i*^) ⊕ *x*^*k*^; (3) *p*~*i*~ = *p*~*i*~ ⊕ *p*~*l*~ = *x*^*i*^ ⊕ *x*^*l*^; (4) *p*~*i*~ = *p*~*i*~ ⊕ *p*~*j*~ = (*x*^*i*^ ⊕ *x*^*l*^) ⊕ (*x*^*j*^ ⊕ *x*^*i*^ ⊕ *x*^*k*^) = *x*^*j*^ ⊕ *x*^*k*^ ⊕ *x*^*l*^. At this point, the *i*^th^ and *j*^th^ substrings of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$st{r}_{\,{\rm{ku}}\,}^{{\mathcal{C}}}$$\end{document}$ become 2^*j*^ + 2^*k*^ + 2^*l*^ and 2^*i*^ + 2^*j*^ + 2^*k*^, respectively.

Security and Performance {#Sec8}
========================

In what follows, we discuss four important properties---data security, circuit privacy, computational complexity, and compactness---of Protocol 1 and Protocol 2, which characterize the security level and performance of each protocol.

Data security and circuit privacy {#Sec9}
---------------------------------

Since protocol 1 involves a trusted third party (TTP), which does not appear in standard quantum homomorphic encryption schemes, we thus define a new type of security for quantum homomorphic evaluation protocols assisted by TTP. Intuitively, such type of security can be achieved by a quantum cryptographic protocol with a well-defined TTP if the presence of this TTP can preserve the same level of security as that of the underlying (perfectly secure) cryptographic primitives (without TTP).

**Definition 1**. (TTP-assisted perfect security). Let Π be a quantum homomorphic evaluation protocol assisted by a trusted third party, Carol, who honestly follows Π and would not be corrupted by any adversary. For an arbitrary plain-state *ρ*~*M*~ (the input state, a density matrix) provided by Alice, if The cipher-states of *ρ*~*M*~ (including the initial cipher-state that has not yet been evaluated, the intermediate cipher-states that have undergone some unitary transforms, and the output cipher-state of the evaluation, which can be accessed by the evaluator Bob) are all equivalent to the totally mixed state;The decryption keys for the input state and the ultimate output (a quantum state or a classical binary string after quantum measurement) cannot be (undetectably) obtained by parties other than Alice and Carol; andThe decryption keys for the intermediate outcomes during the homomorphic evaluation cannot be obtained by parties other than Carol;then Π satisfies TTP-assisted perfect security.

The first condition in the above is due to the definition of perfect security for quantum encryption schemes^[@CR23],[@CR24]^. A requirement for the (classical) evaluated result after quantum measurement is not included in Definition 1, since the measured outcome of a totally mixed state would not reveal any information about *ρ*~*M*~: the probability of getting a specific classical ciphertext *C* (*C* ∈ {0, 1}^*n*^) is $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\,{\rm{tr}}\,\left[\left|C\right\rangle \left\langle C| C\right\rangle \left\langle C\right|(I/{2}^{n})\right]=1$$\end{document}$/2^*n*^, namely the a posteriori distribution of the ciphertext given *ρ*~*M*~ is the same as the a priori distribution of a valid cryptogram of size *n*.

Definition 1 is mainly concerned with data privacy, which ensures that the plain-states of the input, the intermediate outcomes, and the output can only be accessible to legitimate parties. Taking into account circuit privacy, we exclude Alice from knowing the intermediate keys (calculated by Carol) in the last condition. In particular, if Alice has two intermediate keys (*x*~*r*~, *z*~*r*~) and (*x*~*r*+1~, *z*~*r*+1~) for the cipher-states immediately before and after an elementary Clifford gate, then she can deduce which kind of gate was performed by comparing (*x*~*r*~, *z*~*r*~) and (*x*~*r*+1~, *z*~*r*+1~). With the previous definition, we can now prove that the proposed homomorphic search protocol satisfies this new kind of security.

**Theorem 1**. Protocol 1 satisfies TTP-assisted perfect security.

*Proof*. In Protocol 1, the initial cipher-state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{0}$$\end{document}$ of the plain input *ρ*~*M*~ is an encryption of *ρ*~*M*~ using quantum one-time pad under key (*x*~0~, *z*~0~), where *x*~0~, *z*~0~ ∈ {0, 1}^*n*^ and each candidate value is assumed to be chosen with the same probability 1∕2^2*n*^. Taking into account all possible key values, the initial cipher-state is $$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{0}=\frac{1}{{2}^{2n}}\mathop{\sum }\limits_{{x}_{0},{z}_{0}=0}^{{2}^{n}-1}\left({\otimes }_{k=1}^{n}{Z}^{{z}_{0}(k)}{X}^{{x}_{0}(k)}\right)\ {\rho }_{M}\ \left({\otimes }_{k=1}^{n}{X}^{{x}_{0}(k)}{Z}^{{z}_{0}(k)}\right)=\frac{1}{{2}^{2n}}\mathop{\sum }\limits_{{x}_{0},{z}_{0}=0}^{{2}^{n}-1}{Z}^{{z}_{0}}{X}^{{x}_{0}}{\rho }_{M}{X}^{{x}_{0}}{Z}^{{z}_{0}}=\frac{I}{{2}^{n}},$$\end{document}$$where $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${X}^{{x}_{0}}={\otimes }_{k=1}^{n}{X}^{{x}_{0}(k)}$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${Z}^{{z}_{0}}={\otimes }_{k=1}^{n}{Z}^{{z}_{0}(k)}$$\end{document}$. The detailed derivation of the equation above can be found in ref. ^[@CR24]^. Thus, $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{0}$$\end{document}$ is the totally mixed state. After Bob performs a Clifford gate or a *T* gadget (denoted by *G*~1~) on $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{0}$$\end{document}$, it becomes the encrypted result of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${G}_{1}{\rho }_{M}{G}_{1}^{\dagger }$$\end{document}$ under the updated key (*x*~1~, *z*~1~). According to Algorithm 1, there is a one-to-one correspondence between (*x*~0~, *z*~0~) and (*x*~1~, *z*~1~), which means that the distribution of an original key is the same as that of its updated key. So the intermediate cipher-state after the first elementary gate can be written as $$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{1}=\frac{1}{{2}^{2n}}\mathop{\sum }\limits_{{x}_{1},{z}_{1}=1}^{{2}^{n}-1}{Z}^{{z}_{1}}{X}^{{x}_{1}}\left({G}_{1}{\rho }_{M}{G}_{1}^{{\rm{\dagger }}}\right){X}^{{x}_{1}}{Z}^{{z}_{1}}.$$\end{document}$$ By ref. ^[@CR24]^, $$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\frac{1}{{2}^{2n}}\mathop{\sum }\limits_{\gamma ,\delta =0}^{{2}^{n}-1}{X}^{\gamma }{Z}^{\delta }\rho {Z}^{\delta }{X}^{\gamma }=\frac{1}{{2}^{2n}}\mathop{\sum }\limits_{\gamma ,\delta =0}^{{2}^{n}-1}{Z}^{\delta }{X}^{\gamma }\rho {X}^{\gamma }{Z}^{\delta }=\frac{I}{{2}^{n}}$$\end{document}$$ for an arbitrary density operator *ρ*. Take $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\rho ={G}_{1}{\rho }_{M}{G}_{1}^{\dagger }$$\end{document}$, *x*~1~ = *γ*, and *z*~1~ = *δ*, the two equations above gives $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{1}=I$$\end{document}$/2^*n*^. Analogously, during the sequential performances of the elementary gates within the homomorphic search circuit, all intermediate cipher-states and the ultimate cipher-state obtained by Bob equal the totally mixed state. Therefore, the first requirement of Definition 1 is satisfied.

The decryption key *ek* for *ρ*~*M*~ is shared between Alice and Carol by using the BB84 protocol; thus, *ek* cannot be obtained by any eavesdropper without being detected. Since the decryption key *dk* for the measurement outcome is encrypted with *sk* using perfectly secure COTP and *sk* is also protected under the BB84 protocol, so *dk* cannot be obtained without *sk*, which cannot be undetectably accessed by parties except Alice and Carol. Therefore, the second requirement of Definition 1 is fulfilled.

Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{j}$$\end{document}$ (*j* ≥ 1) be the intermediate outcome after the first *j* elementary gates are applied on $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{c}^{0}$$\end{document}$ and suppose the total number of quantum gates is *η*. To get the decryption key *dk*~*j*~ for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{j}$$\end{document}$, either the value of the decryption key *dk*~*i*~ for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{i}$$\end{document}$ (0 ≤ *i* \< *j*) plus the key-update procedure between *dk*~*i*~ and *dk*~*j*~ (or the gate-sequence between $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{i}$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{j}$$\end{document}$) need to be known, or the value of *dk*~*k*~ for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{k}$$\end{document}$ (*j* \< *k* ≤ *η*) plus the key-update procedure between *dk*~*j*~ and *dk*~*k*~ (or the gate-sequence between $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{j}$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{k}$$\end{document}$) should be known. According to the third constraint on the key center, the only party except Carol knowing the gate-sequence between $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{i}$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{j}$$\end{document}$ or between $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{j}$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{k}$$\end{document}$ is Bob, who can obtain neither *dk*~*i*~ nor *dk*~*k*~ from Carol due to the last constraint. According to the second constraint, the only party except Carol knowing *dk*~0~ (or *dk*, the partial content of *dk*~*η*~) is Alice, who can learn neither the gate-sequence between $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{0}$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{j}$$\end{document}$ (or between $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{j}$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\rho }_{C}^{\eta }$$\end{document}$) nor the key-update procedure between *dk*~0~ and *dk*~*j*~ (or between *dk*~*j*~ and *dk*~*η*~) due to the last two constraints on Carol. Therefore, the last requirement of Definition 1 is satisfied.

Consequently, Protocol 1 provides TTP-assisted perfect security. □

Since the privacy of the plain search condition in Protocol 1 has been addressed before the detailed description of this protocol, the security definition (as well as the security proof) only considers the confidentiality of decryption keys and the relationship between the plain and cipher states, so that Definition 1 is applicable to general quantum homomorphic evaluation protocols with TTP.

In the proof of Theorem 1, the derivation of the fulfilment of the first condition in Definition 1 can also be used to prove that the initial cipher-state, every intermediate cipher-states, and the ultimate cipher-state in Protocol 2 are also equivalent to the totally mixed state, so Protocol 2 satisfies (standard) perfect security defined in ref. ^[@CR24]^. Apart from data security, circuit privacy is also an important property of homomorphic encryption. Here, we define two kinds of circuit privacy and then prove that they are achieved by Protocol 1 and Protocol 2, respectively.

**Definition 2**. (TTP-assisted circuit privacy). A quantum homomorphic evaluation protocol Π assisted by a trusted third party, Carol, satisfies TTP-assisted circuit privacy if, for any circuit $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ supported by Π, Alice cannot obtain any information about $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ from the homomorphically evaluated result $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${U}_{{\mathcal{C}}}(En{c}_{ek}\left|\psi \right\rangle )$$\end{document}$ on any cipher-state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$En{c}_{ek}\left|\psi \right\rangle $$\end{document}$ (or the measurement outcome of this result), except for what can be learned from the decrypted output state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${U}_{{\mathcal{C}}}\left|\psi \right\rangle $$\end{document}$ (or the decrypted result of the measurement outcome).Alice cannot gain any information about $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ from Carol.

**Theorem 2**. Protocol 1 satisfies TTP-assisted circuit privacy.

*Proof*. In protocol 1, Alice asks Bob to perform *hGrv* for her. By Theorem 1, the density operator of the output state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$hGrv(En{c}_{ek}\left|\psi \right\rangle )$$\end{document}$ is a totally mixed state. Without decryption, this state reveals nothing about the details of the homomorphic search except the input/output length of *hGrv*, which has been known by Alice. Clearly, the measurement outcome of a totally mixed state would not reveal any circuit detail, too. After decryption, Alice can get the plain search result, which is the only thing she can learn about *hGrv*. Therefore, the first requirement of Definition 1 is satisfied.

According to Algorithm 1, one can derive some details of *hGrv* if he learns some key-update steps, some intermediate keys, some auxiliary qubits for *T* gadgets, or some measurement outcomes from *T* gadgets. However, the last two constraints on the key center ensure that no one can obtain such information from Carol, including Alice. Therefore, the second requirement of Definition 1 is satisfied. □

Due to the deterministic relationship between the key-update process and a Clifford circuit evaluated in a QOTP-based QHE, the circuit information cannot be completely hidden from the key-updater. For schemes using CHE, the key is homomorphically updated by the evaluator, so that circuit privacy can be achieved if a circuit private CHE is adopted^[@CR12]^. However, the use of CHE leads to q-IND-CPA security rather than perfect security (on input data). Besides, the data owner can always learn *O*(*n*) bits of information about the evaluated circuit by looking at the output^[@CR14]^, where *n* is the input/output size of the circuit. Although a QOTP-based QHE protocol not using CHE cannot achieve standard circuit privacy (where the key is updated by the data owner), it may satisfy bounded circuit privacy, which is a weaker notion for circuit privacy.

**Definition 3**. (*O*(*n*^2^)-bounded circuit privacy). A quantum homomorphic evaluation protocol Π with an input of size *n* satisfies *O*(*n*^2^)-bounded circuit privacy if, for any circuit $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ supported by Π, the information about $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ obtained by the data owner is bounded by *O*(*n*^2^).

**Theorem 3**. Protocol 2 satisfies *O*(*n*^2^)-bounded circuit privacy.

*Proof*. In addition to the evaluated cipher-state $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${U}_{{\mathcal{C}}}(En{c}_{ek}\left|\psi \right\rangle )$$\end{document}$, the data owner Alice gets a 4*n*^2^-bit string $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$st{r}_{\,{\rm{ku}}\,}^{{\mathcal{C}}}$$\end{document}$ that depends on the key-update procedure for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$. If the decrypted result $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${U}_{{\mathcal{C}}}\left|\psi \right\rangle $$\end{document}$ is also included (which surely depends on $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ and may be related with $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$st{r}_{\,{\rm{ku}}\,}^{{\mathcal{C}}}$$\end{document}$), then the information (after measurement) obtained by Alice does not exceed 4*n*^2^ + *n*. Thus, the information about *C* obtained by Alice is bounded by *O*(*n*^2^). If one views $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ as a sequence of random choices from the set {*H*, *S*, CNOT} (a universal gate set for Clifford circuits), and each choice of gate is followed another random choice (indexing the input qubit or qubits of the chosen gate) from {0, 1, ..., *n* − 1} or {0, 1, ..., *n* − 1} × {0, 1, ..., *n* − 2}, then the whole information contained in $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$ can be measured by the entropy of those choices. By Shannon's information theory^[@CR25]^, this entropy equals *L*\[log3 + log*n* + (1/3)log(*n* − 1)\], where *L* is the number of gates in $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$. Therefore, the leakage ratio of the circuit information is bounded by $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\frac{4{n}^{2}+n}{L[\,{\rm{\log }}3+{\rm{\log }}\,n+(1/3)\,{\rm{\log }}\,(n-1)]}$$\end{document}$, which is negligible if *L* is exponential in *n*. □

Computational complexity and compactness {#Sec10}
----------------------------------------

In both protocols, the client needs to encrypt her plain data before the homomorphic evaluation and to decrypt the ciphered result after the evaluation (additionally, to measure qubits in the Pauli-*X* and *Y* basis in Protocol 1), which is linear in the size of the input; the server performs the homomorphic evaluation, whose computational complexity is the same as that of the non-homomorphic version (up to a multiplicative constant).

In Protocol 1, the communication complexity between the key center and the server is in proportion to the size of the evaluated circuit, so it is not compact. In Protocol 2, the simplified key-update procedure performed by the client is polynomial in the input size of the evaluated circuit $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$, which is independent of the length of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\mathcal{C}}$$\end{document}$. Thus, Protocol 2 is compact and is especially suitable for a long evaluation with a short input.

Protocol 2 satisfies perfect security and compactness simultaneously, which is rarely achieved among related works. After this work is completed, we find a similar work in ref. ^[@CR26]^, where the server in scheme GT also generates a key-update polynomial *f*(*x*~0~, *z*~0~) for the final decryption key (when considering only Clifford circuits). However, the formulas for this polynomial is not presented in detail and the calculation rule for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$${\{{p}_{j}\}}_{j=0}^{2n-1}$$\end{document}$ in Protocol 2 is derived independently.

In Table [3](#Tab3){ref-type="table"}, we give a comparison between our protocols and other closely related schemes. The abbreviations CI, QI, and q-IND-CPA is short for classical interaction, quantum interaction, and indistinguishability under chosen plaintext attack by quantum polynomial-time adversary. The variable "*R*" is the number of *T* gates in the circuit to be evaluated. For a detailed definition of "*R*^2^-quasi-compact", please refer to Definition 9 in Section 3.4 of ref. ^[@CR11]^.Table 3Comparison with related works. The former nine proposals are for circuits containing *T* gates and the latter two are for Clifford circuits.SchemesSecurityCompactnessInteraction during evaluationL15^[@CR6]^perfectnot compacttwo-way QIFBS14^[@CR8]^perfectnot compacttwo-way CI & one-way QIB15^[@CR9]^perfectnot compacttwo-way CI & one-way QIEPR^[@CR11]^q-IND-CPA*R*^2^-quasi-compactnon-interactiveAUX^[@CR11]^q-IND-CPAcompactnon-interactiveTP^[@CR12]^q-IND-CPAcompactnon-interactiveGT^[@CR26]^perfect*R*log*R*-quasi-compactnon-interactiveVGT^[@CR26]^perfect*R*-quasi-compactnon-interactiveProtocol 1perfectnot compacttwo-way CI & one-way QICL^[@CR11]^q-IND-CPAcompactnon-interactiveProtocol 2perfectcompactnon-interactive

Conclusion {#Sec11}
==========

In this paper, we have presented a homomorphic quantum search protocol on encrypted superposition states based on QHE. To homomorphically perform the Grover's algorithm successfully, the QHE schemes utilizing CHE are ruled out. Instead, a trusted third party is introduced to communicate with the search server and update the key, which greatly alleviates the client's workload. This idea is not only applicable to homomorphic quantum search but also adapted to delegated quantum computing wherein the computing purpose is easy to describe but the computing process is long and complex. Moreover, this search protocol can be combined with other delegated quantum computing schemes, so that general tasks including normal computing as well as quantum search can be accomplished homomorphically. Besides, we have provided a non-interactive QHE protocol for Clifford circuits, which is both secure and compact. Based on a new security definition for QHE schemes with TTP, we have proved that the first protocol satisfies this security. We have also defined two kinds of circuit privacy and proved that they are fulfilled by the two protocols, respectively.

Supplementary information
=========================

 {#Sec12}

Supplementary figure.

**Publisher's note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary information
=========================

is available for this paper at 10.1038/s41598-020-61791-9.

We gratefully acknowledge this work is supported by the Science and Technology Program of Shenzhen of China under Grant Nos. JCYJ20180306124612893. The 5th author also gratefully acknowledges the support from the China Postdoctoral Science Foundation under Grant No. 2017M620322.

Q.Z. and S.L. proposed the idea, Y.C. designed the quantum circuits, L.L. and J.S. analyzed the security. Q.Z. wrote the manuscript. All authors discussed and reviewed the manuscript.

All data generated or analysed during this study are included in this published article (and its Supplementary Information [Files](#MOESM1){ref-type="media"}).

The authors declare no competing interests.
