Quantum Homomorphic Encryption for Polynomial-Size Circuits

Authors Yfke Dulek, Christian Schaffner, Florian Speelman,

Plaintext

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45
www.theoryofcomputing.org

Quantum Homomorphic Encryption for
Polynomial-Size Circuits
Yfke Dulek Christian Schaffner∗ Florian Speelman†
Received December 24, 2016; Revised July 5, 2017; Published May 17, 2018

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

ACM Classification: E.3, F.1.2
AMS Classification: 68P25, 69Q12, 81P68, 81P94, 94A60
Key words and phrases: quantum computing, quantum cryptography, homomorphic encryption, quan-
tum teleportation, garden-hose model
A conference version of this paper appeared in Advances in Cryptology: Proceedings of the 36th International Cryptology
Conference (CRYPTO 2016) [22].
∗ 7th framework EU SIQS and QALGO, and a NWO VIDI grant.
† ERC Grant Agreement no 337603, Danish Council for Independent Research, and VILLUM FONDEN Grant no 10059.

© 2018 Yfke Dulek, Florian Speelman, and Christian Schaffner
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2018.v014a007
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

1 Introduction
Fully homomorphic encryption (FHE) is the holy grail of modern cryptography. Rivest, Adleman and
Dertouzous were the first to observe the possibility of manipulating encrypted data in a meaningful
way, rather than just storing and retrieving it [46]. After some partial progress [33, 45, 10, 37] over
the years, a breakthrough happened in 2009 when Gentry presented a fully-homomorphic encryption
(FHE) scheme [29]. Since then, FHE schemes have been simplified [56] and based on more standard
assumptions [12]. The exciting developments around FHE have sparked a large amount of research in
other areas such as functional encryption [31, 34, 32, 49] and obfuscation [28].
Developing quantum computers is a formidable technical challenge, so it currently seems likely that
quantum computing will not be available immediately to everyone and hence quantum computations
have to be outsourced. Given the importance of classical1 FHE for “computing in the cloud,” it is natural
to wonder about the existence of encryption schemes which can encrypt quantum data in such a way
that a server can carry out arbitrary quantum computations on the encrypted data (without interacting
with the encrypting party2 ). While previous work on quantum homomorphic encryption has mostly
focused on information-theoretic security (see Section 1.2 below for details), schemes that are based on
computational assumptions have only recently been thoroughly investigated by Broadbent and Jeffery.
In [16], they give formal definitions of quantum fully homomorphic encryption (QFHE) and its security
and they propose three schemes for quantum homomorphic encryption assuming the existence of classical
FHE.
A natural idea is to encrypt a message qubit with the quantum one-time pad (i. e., by applying a
random Pauli operation), and send the classical keys for the quantum one-time pad along as classical
information, encrypted by the classical FHE scheme. This basic scheme is called CL in [16]. It is easy to
see that CL allows an evaluator to compute arbitrary Clifford operations on encrypted qubits, simply by
performing the actual Clifford circuit, followed by homomorphically updating the quantum one-time pad
keys according to the commutation rules between the performed Clifford gates and the Pauli encryptions.
The CL scheme can be regarded as analogous to additively homomorphic encryption schemes in the
classical setting. The challenge, like multiplication in the classical case, is to perform non-Clifford gates
such as the T gate. Broadbent and Jeffery propose two different approaches for doing so, accomplishing
homomorphic encryption for circuits with a limited number of T gates. These results lead to the following
main open problem:

Is it possible to construct a computationally secure quantum homomorphic scheme that allows evaluation
of arbitrary quantum circuits of polynomial size?

1.1 Our contributions
We answer the above question in the affirmative by presenting a new scheme TP (as abbreviation for
teleportation) for quantum homomorphic encryption which is both compact and efficient. The scheme is
secure against chosen-plaintext attacks from quantum adversaries, as formalized by the security notion
1 Here and throughout the article, we use “classical” to mean “non-quantum.”
2 In contrast to blind or delegated quantum computation where some interaction between client and server is usually required,

see Section 1.2 for references.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 2
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

q-IND-CPA security defined by Broadbent and Jeffery [16], as long as the number of T gates in the
evaluated circuit (and thus the total size of the evaluated circuit) is polynomial3 in the security parameter.
Like the schemes proposed in [16], our scheme is an extension of the Clifford scheme CL. We add
auxiliary quantum states to the evaluation key which we call quantum gadgets and which aid in the
evaluation of the T gates. The size of a gadget depends only on (a certain form of) the space complexity
of the decryption function of the classical FHE scheme. This relation turns out to be very convenient, as
classical FHE schemes are often optimized with respect to the complexity of the decryption operation
(in order to make them bootstrappable). As a concrete example, if we instantiate our scheme with the
classical FHE scheme by Brakerski and Vaikuntanathan [12], each evaluation gadget of our scheme
consists of a number of qubits which is polynomial in the security parameter.
In TP, the quantum gadgets are used as follows. After a T gate is performed on a one-time-pad
encrypted qubit Xa Zb |ψi, the result might contain an unwanted phase Pa depending on the key a with
which the qubit was encrypted, since TXa Zb |ψi = Pa Xa Zb T|ψi. Obviously, the evaluator is not allowed
to know the key a. Instead, he holds an encryption ã of the key, produced by a classical FHE scheme.
The evaluator can teleport the encrypted qubit “through the gadget” [36] in a way that depends on ã, in
order to remove the unwanted phase. In more detail, the quantum part of the gadget consists of a number
of EPR pairs which are prepared in a way that depends on the secret key of the classical FHE scheme.
Some classical information is provided with the gadget that allows the evaluator to homomorphically
update the encryption keys after the teleportation steps. On a high level, the use of an evaluation gadget
corresponds to a instantaneous non-local quantum computation4 where one party holds the secret key of
the classical FHE scheme, and the other party holds the input qubit and a classical encryption of the key
to the quantum one-time pad. Together, this information determines whether an inverse phase gate P†
needs to be performed on the qubit or not. Very recent results by Speelman [53] show how to perform
such computations with a bounded amount of entanglement. These techniques are the crucial ingredients
for our construction and are the reason why the garden-hose complexity [17] of the decryption procedure
of the classical FHE is related to the size of our gadgets.
We require exactly one evaluation gadget for every T gate that is to be homomorphically evaluated.
For this reason, TP is leveled: in order to produce enough gadgets, the key generation algorithm requires
an upper bound to the number of T gates as an argument. Note that this also means that key generation
scales (linearly) with this upper bound. However, since the work that is done at key generation time is
completely independent of the input to the circuit, we can view key generation as an offline preparation
phase.
The quantum part of our evaluation gadget consists only of a number of Bell pairs arranged in a
specific way. This structural simplicity provides a number of advantages in the construction and analysis
of TP. To start with, the evaluation of a T gate does not cause errors to accumulate on the quantum state.
The scheme is very compact in the sense that the state of the system after the evaluation of a T gate has
the same form as after the initial encryption, except for any classical changes caused by the classical FHE
evaluation. This kind of compactness also implies that individual evaluation gadgets can be supplied “on
3 It is important for compactness that the size of the circuit can be chosen as an arbitrary polynomial of the security parameter,

and in particular doesn’t influence the complexity of decryption. We give a precise specification of the quantifiers involved in
Section 2.2.
4 This term is not related to the term “instantaneous quantum computation” [51], and instead first was used as a specific form

of non-local quantum computation, one where all parties have to act simultaneously.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 3
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

demand” by the holder of the secret key. Once an evaluator runs out of gadgets, the secret key holder can
simply supply more of them.
Furthermore, TP does not depend on a specific classical FHE scheme, hence any advances in classical
FHE can directly improve our scheme. Our requirements for the classical FHE scheme are quite modest:
we only require the classical scheme to have a space-efficient decryption procedure and to be secure
against quantum adversaries. In particular, no circular-security assumption is required. Since we supply at
most a polynomial number of evaluation gadgets, our scheme TP is leveled homomorphic by construction,
and we can simply switch to a new classical key after every evaluation gadget. In fact, the Clifford
gates in the quantum evaluation circuit only require additive operations from the classical homomorphic
scheme, while each T gate needs a fixed (polynomial) number of multiplications. Hence, we do not
actually require fully homomorphic classical encryption, but leveled fully homomorphic schemes suffice.
Finally, circuit privacy in the passive setting almost comes for free. When wanting to hide which
circuit was evaluated on the data, the evaluating party can add an extra randomization layer to the output
state by applying his own one-time pad. We show that if the classical FHE scheme has the circuit-privacy
property, then this extra randomization completely hides the circuit from the decrypting party. This is not
unique to our specific scheme: the same is true for CL.
In terms of applications, our construction can be appreciated as a constant-round scheme for blind
delegated quantum computation, using computational assumptions. The server can evaluate a univer-
sal quantum circuit on the encrypted input, consisting of the client’s quantum input and a (classical)
description of the client’s circuit. In this context, it is desirable to minimize the quantum resources
needed by the client. We argue that our scheme can still be used for constant-round blind delegated
quantum computation if we limit either the client’s quantum memory or the types of quantum operations
the client can perform. In both cases, the client still needs some quantum computational power and a
reliable quantum channel to the server, but it seems unlikely that one can get rid of these requirements
completely [1].
As another application, we can instantiate our construction with a classical FHE scheme that allows
for distributed key generation and decryption amongst different parties that all hold a share of the secret
key [6]. In that case, it is likely that our techniques can be adapted to perform multiparty quantum
computation [9] in the semi-honest case. However, the focus of this article lies on the description and
security proof of the new construction, and more concrete applications are the subject of upcoming work.

1.2 Related work
Early classical FHE schemes were limited in the sense that they could not facilitate arbitrary operations
on the encrypted data: some early schemes only implemented a single operation (addition or multiplica-
tion) [47, 33, 45]; later on it became possible to combine several operations in a limited way [10, 30, 50].
Gentry’s first fully homomorphic encryption scheme [29] relied on several non-standard computational
assumptions. Subsequent work [11, 12] has relaxed these assumptions or replaced them with more
conventional assumptions such as the hardness of learning with errors (LWE), which is believed to be
hard also for quantum attackers. It is impossible to completely get rid of computational assumptions
for a classical FHE scheme, since the existence of such a scheme would imply the existence of an
information-theoretically secure protocol for private information retrieval (PIR) [39] that breaks the lower

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 4
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

bound on the amount of communication required for that task [20, 24].
While quantum fully homomorphic encryption (QFHE) is closely related to the task of blind or
delegated quantum computation [18, 15, 2, 57, 25, 13, 41], QFHE does not allow interaction between
the client and the server during the computation. Additionally, in QFHE, the server is allowed to choose
which unitary it wants to apply to the (encrypted) data.
Yu, Pérez-Delgado and Fitzsimons [58] showed that perfectly information-theoretically secure QFHE
is not possible for arbitrary unitary transformations, unless the size of the encryption grows exponentially
in the input size. Thus, any scheme that attempts to achieve information-theoretically secure QFHE has
to leak some proportion of the input to the server [5, 48] or can only be used to evaluate a subset of all
unitary transformations on the input [48, 40, 54]. Information-theoretically secure QFHE is not known to
be achievable for the subset of our interest, that of all unitary transformations for which efficient quantum
circuits exist. Like the multiplication operation is hard in the classical case, the hurdle in the quantum case
seems to be the evaluation of non-Clifford gates. A recent result by Ouyang, Tan and Fitzsimons provides
information-theoretic security for circuits with at most a constant number of non-Clifford operations [44].
Broadbent and Jeffery [16] proposed two schemes that achieve homomorphic encryption for nontrivial
sets of quantum circuits. Instead of trying to achieve information-theoretic security, they built their
schemes based on a classical FHE scheme and hence any computational assumptions on the classical
scheme are also required for the quantum schemes. Computational assumptions allow bypassing the
impossibility result from [58] and work toward a (quantum) fully homomorphic encryption scheme.
Both of the schemes presented in [16] are extensions of the scheme CL described in Section 1.1.
These two schemes use different methods to implement the evaluation of a T gate, which we briefly
discuss here. In the EPR scheme, some entanglement is accumulated in a special register during every
evaluation of a T gate, and stored there until it can be resolved in the decryption phase. Because of this
accumulation, the complexity of the decryption function scales (quadratically) with the number of T gates
in the evaluated circuit, thereby violating the compactness requirement of QFHE. The scheme AUX also
extends CL, but handles T gates in a different manner. The evaluator is supplied with auxiliary quantum
states, stored in the evaluation key, that allow him to evaluate T gates and immediately remove any error
that may have occurred. In this way, the decryption procedure remains very efficient and the scheme is
compact. Unfortunately, the required auxiliary states grow doubly exponentially in size with respect to
the T depth of the circuit, rendering AUX useful only for circuits with constant T depth. Our scheme
TP is related to AUX in that extra quantum resources for removing errors are stored in the evaluation
key. In sharp contrast to AUX, the size of the evaluation key in TP only grows linearly in the number of
T gates in the circuit (and polynomially in the security parameter), allowing the scheme to be leveled
fully homomorphic. Since the evaluation of the other gates causes no errors on the quantum state, no
gadgets are needed for those; any circuit containing a number of T gates that is polynomial in the security
parameter can be efficiently and securely evaluated.

1.3 Structure of this paper
We start by introducing some notation in Section 2 and presenting the necessary preliminaries on quantum
computation, (classical and quantum) homomorphic encryption, and the garden-hose model which is
essential to the most-general construction of the gadgets. In Section 3, we describe the scheme TP
and show that it is compact. The security proof of TP is somewhat more involved, and is presented in

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 5
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

several steps in Section 4, along with an informal description of a circuit-private variant of the scheme. In
Section 5, the rationale behind the quantum gadgets is explained, and some examples are discussed to
clarify the construction. We conclude our work in Section 6 and propose directions for future research.

2 Preliminaries
2.1 Quantum computation
We assume the reader is familiar with the standard notions in the field of quantum computation. (For
an introduction, see [43].) In this subsection, we only mention the concepts that are essential to our
construction.
The single-qubit Pauli group is, up to global phase, generated by the bit flip and phase flip operations,

0 1 1 0
X= , Z= .
1 0 0 −1

A Pauli operator on n qubits is simply any tensor product of n independent single-qubit Pauli operators.
All four single-qubit Pauli operators are of the form Xa Zb with a, b ∈ {0, 1}. Here, and in the rest of the
paper, we ignore the global phase of a quantum state, as it is not observable by measurement.
The Clifford group on n qubits consists of all unitaries C that commute with the Pauli group, i. e.,
the Clifford group is the normalizer of the Pauli group. Since all Pauli operators are of the form
Xa1 Zb1 ⊗ · · · ⊗ Xan Zbn , this means that C is a Clifford operator if for any a1 , b1 , . . . , an , bn ∈ {0, 1} there
exist a01 , b01 , . . . , a0n , b0n ∈ {0, 1} such that (ignoring global phase):
0 0 0 0
C(Xa1 Zb1 ⊗ · · · ⊗ Xan Zbn ) = (Xa1 Zb1 ⊗ · · · ⊗ Xan Zbn )C.

All Pauli operators are easily verified to be elements of the Clifford group, and the entire Clifford group
is generated by
 
1 0 0 0
1 0 1 1 1  0 1 0 0 
P= , H= √ , and CNOT =   0 0 0 1 .

0 i 2 1 −1
0 0 1 0

(See for example [35].) The commutation rules for single-qubit Clifford gates on wire i, or two-qubit
Clifford gates on wires i and j, are given by

PXai Zbi = Xai Zai ⊕bi P,
HXai Zbi = Xbi Zai H,
CNOT(Xai Zbi ⊗ Xa j Zb j ) = (Xai Zai ⊕b j ⊗ Xa j ⊕ai Zb j )CNOT.

These commutation rules are important to our construction, because they describe how the encryption
key should be updated after the application of a Clifford gate. They can be found in many places in the
literature (or can be easily calculated by hand), see also, e. g., [16, Appendix C].

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 6
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

The Clifford group does not suffice to simulate arbitrary quantum circuits, but by adding any single
non-Clifford gate, any quantum circuit can be efficiently simulated with only a small error. As in [16], we
choose this non-Clifford gate to be the T gate,

1 0
T= .
0 eiπ/4
Note that the T gate, because it is non-Clifford, does not commute with the Pauli group. More specifically,
we have TXa Zb = Pa Xa Zb T. It is exactly the formation of this P gate that has proven to be an obstacle to
the design of an efficient quantum homomorphic encryption scheme.
We use |ψi or |ϕi to denote pure quantum states. Mixed states are denoted with ρ or σ . Let Id denote
the identity matrix of dimension d, this allows us to write the d-dimensional completely mixed state as
Id /d.
Define
1
Φ+ := √ (|00i + |11i)
2
to be an EPR pair.
If X is a random variable ranging over the possible basis states B for a quantum system, then let ρ(X)
be the density matrix corresponding to X, i. e., ρ(X) := ∑b∈B Pr[X = b]|bihb|.
Applying a Pauli operator that is chosen uniformly at random results in a single-qubit completely
mixed state, since
1 a b b a I2
∀ρ : ∑ X Z ρZ X = .
a,b∈{0,1}
4 2

This property is used in the construction of the quantum one-time pad: applying a random Pauli Xa Zb to
a qubit completely hides the content of that qubit to anyone who does not know the key (a, b) to the pad.
Anyone in possession of the key can decrypt simply by applying Xa Zb again.

2.2 Homomorphic encryption
This subsection provides the definitions of (classical and quantum) homomorphic encryption schemes,
and the security conditions for such schemes. In the current work, we only consider homomorphic
encryption in the public-key setting. For a more thorough treatment of these concepts, and how they can
be transferred to the symmetric-key setting, see [16].

2.2.1 The classical setting
A classical homomorphic encryption scheme HE consists of four algorithms: key generation, encryption,
evaluation, and decryption. The key generator produces three keys: a public key and evaluation key, both
of which are publicly available to everyone, and a secret key which is only revealed to the decrypting
party. Anyone in possession of the public key can encrypt the inputs x1 , . . . , x` , and send the resulting
ciphertexts c1 , . . . , c` to an evaluator who evaluates some circuit C on them. The evaluator sends the result
to a party that possesses the secret key, who should be able to decrypt it to C(x1 , . . . , x` ).
More formally, HE consists of the following four algorithms which run in probabilistic polynomial
time in terms of their input and parameters [12].

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 7
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

(pk, evk, sk) ← HE.KeyGen(1κ ) where κ ∈ N is the security parameter. Three keys are generated: a
public key pk, which can be used for the encryption of messages; a secret key sk used for decryption;
and an evaluation key evk that may aid in evaluating the circuit on the encrypted state. The keys pk
and evk are announced publicly, while sk is kept secret.

c ← HE.Encpk (x) for some one-bit message x ∈ {0, 1}. This probabilistic procedure outputs a ciphertext
c, using the public key pk.

c0 ← HE.EvalCevk (c1 , . . . , c` ) uses the evaluation key to output some ciphertext c0 which decrypts to the
evaluation of circuit C on the decryptions of c1 , . . . , c` . We will often think of Eval as an evaluation
f
of a function f instead of some canonical circuit for f , and write HE.Evalevk (c1 , . . . , c` ) in this case.

x0 ← HE.Decsk (c0 ) outputs a message x0 ∈ {0, 1}, using the secret key sk. (In general, the decryption
functionality could be defined to also sometimes output x0 = ⊥, representing an undefined output.
For the purpose of defining a scheme that is correct for an honest evaluator and that maintains
secrecy against a dishonest evaluator, it suffices to only consider x0 ∈ {0, 1}.)

In principle, HE.Encpk can only encrypt single bits. When encrypting an n-bit message x ∈ {0, 1}n , we
encrypt the message bit-by-bit, applying the encryption procedure n times. We sometimes abuse the
notation HE.Encpk (x) to denote this bitwise encryption of the string x. Similarly, we define HE.Decsk
only for ciphertexts that decrypt to a single bit. If we want to evaluate a more general circuit that outputs
m bits, then we have to apply HE.Decsk bit-by-bit (m times in total) to all ciphertext output bits separately.
Note that this assumes that the output of HE.EvalC consists of m distinct parts: schemes with this property
are called divisible, because they allow bit-by-bit decryption.
For HE to be a C-homomorphic encryption scheme for some class of circuits C, we require correctness
in the sense that for any circuit C ∈ C, there exists a negligible5 function η such that, for any input x,

Pr[HE.Decsk (HE.EvalCevk (HE.Encpk (x))) 6= C(x)] ≤ η(κ) .

In this article, we assume for clarity of exposition that classical schemes HE are perfectly correct, and
that it is possible to immediately decrypt after encrypting (without doing any evaluation).
Another desirable property is compactness, which states that the complexity of the decryption function
should not depend on the size of the circuit. More formally, a C-homomorphic encryption scheme is
compact if there exists a polynomial p such that for any security parameter κ, any circuit C ∈ C, and any
ciphertext c, the time complexity of running HE.Decsk on the output of HE.EvalC (c) is at most p(κ).
A compact C-homomorphic encryption scheme where C is the class of all circuits is called fully
homomorphic. If C is only a subset of all possible circuits (e. g., all circuits with no multiplication gates)
or if the scheme is not compact, it is considered to be a somewhat homomorphic scheme. Finally, a leveled
fully homomorphic scheme is (compact and) homomorphic for all circuits up to a variable depth L, which
is supplied as an extra argument to the key generation function [55]. For leveled FHE, the definition of
compactness is slightly more subtle: there should exist a polynomial p such that for any set of parameters
(κ, L), any polynomial q, any circuit C with at most q(L) gates, and any ciphertext c, the output size of
5 A negligible function η is a function such that for every positive integer d, η(n) < 1/nd for big enough n.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 8
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

HE.EvalC (c) is at most p(κ). Note that the polynomial p should be independent of the number of gates
in the circuit (given by q(L)). Our quantum scheme TP will be leveled fully homomorphic.
We will use the notation xe to denote the result of running HE.Encpk (x). That is, Decsk (e x) = x with
overwhelming probability. In our construction, we will often deal with multiple classical key sets
(pki , evki , ski )i∈I indexed by some set I. In that case, we use the notation xe[i] to denote the result of
HE.Encpki (x), in order to avoid confusion. Also note that, e. g., pki does not refer to the ith bit of the
public key. In case we want to refer to the ith bit of some string s, we will use the notation s[i].
When working with multiple key sets, it will often be necessary to transform an already encrypted
message xe[i] into an encryption xe[ j] using a different key set j 6= i. To achieve this transformation, we
define the procedure HE.Reci→ j that can always be used for this recryption task as long as we have access
to an encrypted version sk fi [ j] of the old secret key ski . Effectively, HE.Reci→ j homomorphically evaluates
the decryption of xe[i] :
[ j]
x[i] ) := HE.EvalHE.Dec
HE.Reci→ j (e evk j
fi , HE.Encpk (e
sk j
x [i]
) .

2.2.2 The quantum setting
A quantum homomorphic encryption scheme QHE, as defined in [16], is a natural extension of the
classical case, and differs from it in only a few aspects. The secret and public keys are still classical, but
the evaluation key is allowed to be a quantum state. This means that the evaluation key is not necessarily
reusable, and can be consumed during the evaluation procedure. The messages to be encrypted are qubits
instead of bits, and the evaluator should be able to evaluate quantum circuits on them.
All definitions given above carry over quite naturally to the quantum setting (see also [16]):

(pk, ρevk , sk) ← QHE.KeyGen(1κ ) where κ ∈ N is the security parameter. In contrast to the classical
case, the evaluation key is a quantum state.

σ ← QHE.Encpk (ρ) produces, for every valid public key pk and input state ρ from some single-qubit
message space, to a quantum cipherstate σ in some cipherspace.

σ 0 ← QHE.EvalCρevk (σ ) represents the evaluation of a circuit C. If C requires n input qubits, then σ
should be the result of applying QHE.Enc⊗n to the plaintext input. The evaluation function maps it
to a state in the n0 -fold tensor product of the ciphertext output space, where n0 is the number of
qubits that C would output. The evaluation key ρevk is consumed in the process.

ρ 0 ← QHE.Decsk (σ 0 ) maps a single state σ 0 from the output space to a quantum state ρ 0 in the message
space. Note that if the evaluation procedure QHE.Eval evaluated a circuit with n0 output wires,
then QHE.Dec needs to be run n0 times.

Again, we require the encryption and decryption procedure to act on single qubits, and hence we only
consider divisible schemes. Divisible schemes form a subclass to the more general notion of indivisible
schemes [16], where an auxiliary quantum register may be built up for the entire state, and the output
cipherstate is decrypted as a whole. For divisible schemes, the auxiliary quantum register is empty.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 9
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

2.2.3 Quantum security

The notion of security that we aim for is that of indistinguishability under chosen-plaintext attacks, where
the attacker may have quantum computational powers (q-IND-CPA). This security notion was introduced
in [16, Definition 3.3] (see [27] for a similar notion of the security of classical schemes against quantum
attackers) and ensures semantic security [3]. We restate it here for completeness.

Definition 2.1. [16] The quantum CPA indistinguishability experiment with respect to a scheme QHE
and a quantum polynomial-time adversary A = (A1 , A2 ), denoted by PubKcpa
A ,QHE (κ), is defined by the
following procedure:

1. KeyGen(1κ ) is run to obtain keys (pk, ρevk , sk).

2. Adversary A1 is given (pk, ρevk ) and outputs a quantum state on M ⊗ E.

3. For r ∈ {0, 1}, let Ξcpa,r
QHE : D(M) → D(C) be:

Ξcpa,0
QHE (ρ) = QHE.Enc pk (|0ih0|) and Ξcpa,1
QHE (ρ) = QHE.Enc pk (ρ) .

A random bit r ∈ {0, 1} is chosen and Ξcpa,r
QHE is applied to the state in M (the output being a state
in C).

4. Adversary A2 obtains the system in C ⊗ E and outputs a bit r0 .

5. The output of the experiment is defined to be 1 if r0 = r and 0 otherwise. In case r = r0 , we say that
A wins the experiment.

pk
KeyGen(1κ )

cpa,r
Revk M ΞQHE C
A1 A2 r0
pk E

Figure 1: [16, reproduced with permission of the authors] The quantum CPA indistinguishability ex-
periment PubKcpaA ,QHE (κ). Double lines represent classical information flow, and single lines represent
quantum information flow. The adversary A is split up into two separate algorithms A1 and A2 , which
share a working memory represented by the quantum state in register E. For the definition of Ξcpa,r
QHE , see
step 3 in Definition 2.1.

The game PubKcpa A ,QHE (κ) is depicted in Figure 1. Informally, the challenger randomly chooses
whether to encrypt some message, chosen by the adversary, or instead to encrypt the state |0ih0|. The
adversary has to guess which of the two happened. If he cannot do so with more than negligible advantage,
the encryption procedure is considered to be q-IND-CPA secure:

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 10
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

Definition 2.2. [16, Definition 3.3] A (classical or quantum) homomorphic encryption scheme S is
q-IND-CPA secure if for any quantum polynomial-time adversary A = (A1 , A2 ) there exists a negligible
function η such that:
1
Pr[PubKcpa
A ,S (κ) = 1] ≤ 2 + η(κ).

Analogously to PubKcpa cpa−mult
A ,S (κ), in the game PubKA ,S (κ), the adversary can give multiple messages
to the challenger, which are either all encrypted, or all replaced by zeros. Broadbent and Jeffery [16]
show that these notions of security are equivalent.

2.3 Garden-hose complexity
The garden-hose model is a model of communication complexity which was introduced by Buhrman,
Fehr, Schaffner and Speelman [17] to study a protocol for position-based quantum cryptography. The
model recently saw new use, when Speelman [53] used it to construct new protocols for the task of
instantaneous non-local quantum computation, thereby breaking a wider class of schemes for position-
based quantum cryptography. (Besides the garden-hose model, this construction used tools from secure
delegated computation. These techniques were first used in the setting of instantaneous non-local quantum
computation by Broadbent [14].)
We will not explain the garden-hose model thoroughly, but instead give a short overview. The
garden-hose model involves two parties, Alice with input x and Bob with input y, that jointly want to
compute a function f . To do this computation, they are allowed to use garden hoses to link up pipes that
run between them, one-to-one, in a way which depends on their local inputs. Alice also has a water tap,
which she connects to one of the pipes. Whenever f (x, y) = 0, the water has to exit at an open pipe on
Alice’s side, and whenever f (x, y) = 1 the water should exit on Bob’s side.
The applicability of the garden-hose model to our setting stems from a close correspondence between
protocols in the garden-hose model and teleporting a qubit back-and-forth; the “pipes” correspond to EPR
pairs and the “garden hoses” can be translated into Bell measurements. Our construction of the gadgets
in Section 5.3 will depend on the number of pipes needed to compute the decryption function HE.Dec
of a classical fully homomorphic encryption scheme. It will turn out that any log-space computable
decryption function allows for efficiently constructable polynomial-size gadgets.

3 The TP scheme
Our scheme TP (for teleportation) is an extension of the scheme CL presented in [16]: the quantum state
is encrypted using a quantum one-time pad, and Clifford gates are evaluated simply by performing the
gate on the encrypted state and then homomorphically updating the encrypted keys to the pad. The new
scheme TP, like AUX, includes additional resource states (gadgets) in the evaluation key. These gadgets
can be used to immediately correct any P errors that might be present after the application of a T gate.
The size of the evaluation key thus grows linearly with the upper bound to the number of T gates in the
circuit: for every T gate the evaluation key contains one gadget, along with some classical information on
how to use that gadget.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 11
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

3.1 Gadget
In this section we only give the general form of the gadget, which suffices to prove security. The
explanation on how to construct these gadgets, which depend on the decryption function of the classical
homomorphic scheme HE.Dec, is deferred to Section 5.
Recall that when a T gate is applied to the state Xa Zb |ψi, an unwanted P error may occur since
TX Zb = Pa Xa Zb T. If a is known, this error can easily be corrected by applying P† whenever a = 1.
a

However, as we will see, the evaluating party only has access to some encrypted version ae of the key a,
and hence is not able to decide whether or not to correct the state.
We show how the key generator can create a gadget ahead of time that corrects the state, conditioned
on a, when the qubit Pa Xa Zb T|ψi is teleported through it. The gadget will not reveal any information
about whether or not a P gate was present before the correction. Note that the value of a is completely
unknown to the key generator, so the gadget cannot depend on it. Instead, the gadget will depend on the
secret key sk, and the evaluator will use it in a way that depends on ae.
The intuition behind our construction is as follows. A gadget consists of a set of fully entangled
pairs that are crosswise linked up in a way that depends on the secret key sk and the decryption function
of the classical homomorphic scheme HE. If the decryption function HE.Dec is simple enough, i. e.,
computable in logarithmic space or by low-depth binary circuit, the size of this state is polynomial in the
security parameter.
Some of these entangled pairs have an extra inverse phase gate applied to them. Note that teleporting
any qubit Xa Zb |ψi through, for example, (P† ⊗ I)|Φ+ i, effectively applies an inverse phase gate to the
0 0
qubit, which ends up in the state Xa Zb P† |ψi, where the new Pauli corrections a0 ,b0 depend on a,b and
the outcome of the Bell measurement.
When wanting to remove an unwanted phase gate, the evaluator of the circuit teleports a qubit through
this gadget state in a way which is specified by ae. The gadget state is constructed so that the qubit follows
a path through this gadget which passes an inverse phase gate if and only if HE.Decsk (e a) equals 1. The
Pauli corrections can then be updated using the homomorphically-encrypted classical information and the
measurement outcomes.

Specification of gadget

Assume HE.Dec is computable in space logarithmic in the security parameter κ. In Section 5 we will
show that there exists an efficient algorithm TP.GenGadgetpk0 (sk) which produces a gadget, i. e., a
quantum state Γ pk0 (sk) of the form specified in this section.
The gadget will be able to remove a single phase gate Pa , using only knowledge of ae, where ae decrypts
to a under the secret key sk. The public key pk0 is used to encrypt all classical information associated
with the gadget.
The quantum part of the gadget consists of 2m qubits, with m some number which is polynomial
in the security parameter κ. Let {(s1 ,t1 ), (s2 ,t2 ), . . . , (sm ,tm )} be disjoint pairs in {1, 2, . . . , 2m}, and let
p ∈ {0, 1}m be a string of m bits. Let g(sk) be a shorthand for the tuple of both of these, together with the
secret key sk;
g(sk) := ({(s1 ,t1 ), (s2 ,t2 ), . . . , (sm ,tm )}, p, sk) .

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 12
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

The tuple g(sk) is the classical information that determines the structure of the gadget as a function of
the secret key sk. It will be the case that the variables (s1 ,t1 ), (s2 ,t2 ), . . . , (sm ,tm ) and p that describe
the gadget structure are themselves determined by sk, and therefore the variable si , for example, should
always be read in context as si (sk).
For any bitstring x, z ∈ {0, 1}m , define the quantum state
m p[i] +
Φ+ siti P p[i] Zz[i] Xx[i] .
O
γx,z g(sk) := Xx[i] Zz[i] P† Φ
i=1

(Here the single-qubit gates are applied to si , the first qubit of the entangled pair.) This quantum state is a
collection of maximally-entangled pairs of qubits, some with an extra inverse phase gate applied, where
the pairs are determined by the disjoint pairs {(s1 ,t1 ), (s2 ,t2 ), . . . , (sm ,tm )} chosen earlier. The entangled
pairs have arbitrary Pauli operators applied to them, described by the bitstrings x and z.
Note that, no matter the choice of gadget structure, averaging over all possible x, z gives the completely
mixed state on 2m qubits,
1 I 2m
2m ∑ γx,z g(sk) = 22m .
2x,z∈{0,1}m 2

This property will be important in the security proof; intuitively it shows that these gadgets do not reveal
any information about sk whenever x and z are encrypted with a secure classical encryption scheme.
The entire gadget then is given by
1
Γpk0 (sk) = ρ(HE.Encpk0 g(sk) ) ⊗ 2m ∑ ρ(HE.Encpk0 (x, z)) ⊗ γx,z g(sk) ,
2x,z∈{0,1}m

where g(sk) denotes a canonical encoding of g(sk) into a bit string. The length of g(sk) (and thus of
g(sk)) is not dependent on the secret key: the number of qubits m and the size of sk itself are completely
determined by the choice of protocol HE and the security parameter κ.
To summarize, the gadget consists of a quantum state γx,z g(sk) , instantiated with randomly chosen
x, z, the classical information denoting the random choice of x, z, and the other classical information g(sk)
which specifies the gadget. All classical information is homomorphically encrypted with a public key pk0 .
Since this gadget depends on the secret key sk, simply encrypting this information using the public
key corresponding to sk would not be secure, unless we assume that HE.Dec is circularly secure. In order
to avoid the requirement of circular security, we will always use a fresh, independent key pk0 to encrypt
this information. The evaluator will have to do some recrypting before he is able to use this information,
but otherwise using independent keys does not complicate the construction much. More details on how
the evaluation procedure deals with the different keys is provided in Section 3.4.

Usage of gadget
The gadget is used by performing Bell measurements between pairs of its qubits, together with an input
qubit that needs a correction, without having knowledge of the structure of the gadget.
The choice of measurements is generated by an efficient classical algorithm TP.GenMeasurement(e a)
which produces a list M containing m disjoint pairs of elements in {0, 1, 2, . . . , 2m} that only depend

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 13
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

on ciphertext ae. Here the labels 1 to 2m refer to the qubits that make up a gadget and 0 is the label of
the qubit with the possible P error. The pairs represent which qubits will be connected through Bell
measurements; note that all but a single qubit will be measured according to M.
Consider an input qubit, in some arbitrary state Pa |ψi, i. e., the qubit has an extra phase gate if
a = 1. Let ae be an encrypted version of a, such that a = HE.Decsk (e a). Then the evaluator performs
Bell measurements on Γpk0 (sk) and the input qubit, according to M ← TP.GenMeasurement(e a). By
a0 b0
construction, one out the 2m + 1 qubits is still unmeasured. This qubit will be in the state X Z |ψi, for
some a0 and b0 , both of which are functions of the specification of the gadget, the measurement choices
which depend on ae, and the outcomes of the teleportation measurements. Also see Section 3.4 and
Appendix A for a more in-depth explanation of how the accompanying classical information is updated.
Intuitively, the “path” the qubit takes through the gadget state, goes through one of the fully entan-
gled pairs with an inverse phase gate whenever HE.Decsk (e a) = 1, and avoids all such pairs whenever
HE.Decsk (ea) = 0.

3.2 Key generation
Using the classical HE.KeyGen as a subroutine to create multiple classical homomorphic keysets, we
generate a classical secret and public key, and a classical-quantum evaluation key that contains L gadgets,
allowing evaluation of a circuit containing up to L T gates. Every gadget depends on a different secret key,
and its classical information is always encrypted using the next public key. The key generation procedure
TP.KeyGen(1κ , 1L ) is defined as follows:

1. For i = 0 to L: execute (pki , evki , ski ) ← HE.KeyGen(1κ ) to obtain L + 1 independent classical
homomorphic key sets.

2. Set the public key to be the tuple (pki )Li=0 .

3. Set the secret key to be the tuple (ski )Li=0 .

4. For i = 0 to L − 1: Run the procedure TP.GenGadgetpki+1 (ski ) to create the gadget Γpki+1 (ski ) as
described in Section 3.1.

5. Set the evaluation key to be the set of all gadgets created in the previous step (including their
encrypted classical information), plus the tuple (evki )Li=0 . The resulting evaluation key is the
quantum state
L−1
O
Γpki+1 (ski ) ⊗ |evki ihevki | ⊗ |evkL ihevkL |.
i=0

3.3 Encryption
The encryption procedure TP.Enc is identical to CL.Enc, using the first public key pk0 for the encryption
of the one-time-pad keys. We restate it here for completeness.
Every single-qubit state σ is encrypted separately with a quantum one-time pad, and the pad key is
(classically) encrypted and appended to the quantum encryption of σ , resulting in the classical-quantum

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 14
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

state
1
∑ ρ(HE.Encpk0 (a), HE.Encpk0 (b)) ⊗ Xa Zb σ Zb Xa .
a,b∈{0,1}
4

3.4 Circuit evaluation
Consider a circuit with n wires. The evaluation of the circuit on the encrypted data is carried out one gate
at a time.
Recall that our quantum circuit is written using a gate set that consists of the Clifford group generators
{H, P, CNOT} and the T gate. A Clifford gate may affect multiple wires at the same time, while T gates
can only affect a single qubit. Before the evaluation of a single gate U, the encryption of an n-qubit state
ρ is of the form
Xa1 Zb1 ⊗ · · · ⊗ Xan Zbn ρ Zb1 Xa1 ⊗ · · · ⊗ Zbn Xan .

[i] [i]
The evaluating party holds the encrypted versions ae1 [i] , . . . , aen [i] and be1 , . . . , ben , with respect to the
ith key set for some i (initially, i = 0). The goal is to obtain a quantum encryption of the state Uρ U † ,
such that the evaluator can homomorphically compute the encryptions of the new keys to the quantum
one-time pad. If U is a Clifford gate, these encryptions will still be in the ith key. If U is a T gate, then all
encryptions are transferred to the (i + 1)th key during the process.

• If U is a Clifford gate, we proceed exactly as in CL.Eval. The gate U is simply applied to the
encrypted qubit, and since U commutes with the Pauli group, the evaluator only needs to update
the encrypted keys in a straightforward way, given by the commutation rules from Section 2.1.

• If U = T, the evaluator should start out by applying a T gate to the appropriate wire w. Afterwards,
the qubit at wire w is in the state

Paw Xaw Zbw T ρw T† Zbw Xaw (P† )aw .

In order to remove the P error, the evaluator uses one gadget Γpki+1 (ski ) from the evaluation key;
[i]
he possesses the classical information af w , encrypted with the ith key and therefore matching this
gadget, to be able to compute measurements M ← TP.GenMeasurement(f aw [i] ) and performs the
measurements on the pairs given by M. Afterwards, using his own measurement outcomes, the
[i]
classical information accompanying the gadget (encrypted using pki+1 ), and the recryptions of af w
[i] [i+1] [i+1] [i+1]
and bf 0
w into a fw and bf
w , the evaluator homomorphically computes the new keys af w
[i+1]
and bf0 . See also Figure 2 and Appendix A. After these computations, he should also recrypt
w
the keys of all other wires into the (i + 1)th key set.

At the end of the evaluation of some circuit C containing k T gates, the evaluator holds a one-time-pad
encryption of the state C|ψi, together with the keys to the pad, classically encrypted in the kth key. The
last step is to recrypt (in L − k steps) this classical information into the Lth (final) key. Afterwards, the
quantum state and the key encryptions are sent to the decrypting party. Any unused gadgets are discarded.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 15
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

0 0 0 0
Xaw Zbw ρXaw Zbw T Xaw Zbw TρT† Zbw Xaw
gadget
γx,z (g(ski ))
HE.Encpki+1

HE.Eval
[i] HE.Reci→i+1 [i+1] [i+1]
afw 0
af 0
, bf
[i] HE.Reci→i+1 w w
[i+1]
bfw
^
g(ski) , xe[i+1] ,e
z[i+1]

Figure 2: The homomorphic evaluation of the (i + 1)th T gate of the circuit. The gadget is consumed
during the process. After the use of the gadget, the evaluator encrypts his own classical information
(including measurement outcomes) in order to use it in the homomorphic computation of the new keys.
HE.Eval evaluates this fairly straightforward computation that consists mainly of looking up values in a
list and adding them modulo 2. Note that sk fi [i+1] , needed for the recryption procedures, is contained in
the evaluation key and that the keys of the wires that are not shown are also recrypted.

3.5 Decryption
The decryption procedure is identical to CL.Dec. For each qubit, HE.DecskL is run twice in order to
retrieve the keys to the quantum pad. The correct Pauli operator can then be applied to the quantum state
in order to obtain the desired state C|ψi.
The decryption procedure is fairly straightforward, and its complexity does not depend on the circuit
that was evaluated. This is formalized in a compactness theorem for the TP scheme:

Theorem 3.1. If HE is compact, then TP is compact.

Proof. Note that because the decryption only involves removing a one-time pad from the quantum
ciphertext produced by the circuit evaluation, this decryption can be carried out a single qubit at a time.
By compactness of HE, there exists a polynomial p(κ) such that for any function f and any ciphertext c,
the output size of HE.Eval f (c) is at most p(κ). Since the keys to the quantum one-time pad of any wire
w are two single bits encrypted with the classical HE scheme, decrypting the keys for one wire requires at
most 2p(κ) steps. Obtaining the qubit then takes at most two steps more for (conditionally) applying
Xaw and Zbw . The total number of steps is polynomial in κ and independent of C (and in particular,
independent of L), so we conclude that TP is compact.

4 Security of TP
In order to guarantee the privacy of the input data, we need to argue that an adversary that does not
possess the secret key cannot learn anything about the data with more than negligible probability. To this
end, we show that TP is q-IND-CPA secure, i. e., no polynomial-time quantum adversary can tell the
difference between an encryption of a real message and an encryption of |0ih0|, even if he gets to choose
the message himself (recall the definition of q-IND-CPA security from Section 2.2.3). Like in the security
proofs in [16], we use a reduction argument to relate the probability of being able to distinguish between

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 16
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

the two encryptions to the probability of winning an indistinguishability experiment for the classical HE,
which we assume to be close to 1/2. The aim of this section is to prove the following theorem:

Theorem 4.1. If HE is q-IND-CPA secure, then TP is q-IND-CPA secure for circuits containing up to
polynomially (in κ) many T gates.

In order to prove Theorem 4.1, we first prove that an efficient adversary’s performance in the
indistinguishability game is only negligibly different when he receives a real evaluation key with real
gadgets, versus just a completely mixed quantum state with encryptions of 0’s accompanying them
(Corollary 4.3). Then we argue that without the evaluation key, an adversary does not receive more
information than in the indistinguishability game for the scheme CL, which has already been shown to be
q-IND-CPA secure whenever HE is.
We start with defining a sequence of variations on the TP scheme. For ` ∈ {0, . . . , L}, let TP(`) be
identical to TP, except for the key generation procedure: TP(`) .KeyGen replaces, for every i ≥ `, all
classical information accompanying the ith gadget with the all-zero string before encrypting it. For any
number i, define the shorthand
gi := g(ski ).
Similarly, gi := g(ski ), the canonical bit string representation of gi . As seen in Section 3.1, the length
of the classical information does not depend on ski itself, so a potential adversary cannot gain any
information about ski just from this encrypted string. In summary, the evaluation key produced by
TP(`) .KeyGen(1κ , 1L ) is
`−1
O
|evki ihevki | ⊗ Γpki+1 (ski ) ⊗
i=0
L−1
O 1
|evki ihevki | ⊗ ρ(HE.Encpki+1 (0|gi | )) ⊗ ∑ ρ(HE.Enc pk (0 m m
, 0 )) ⊗ γ x,z (gi ) .
i=`
22mx,z∈{0,1}m i+1

The secret key and public key remain the same as in TP. Intuitively, one can view TP(`) as the scheme
that provides only ` usable gadgets in the evaluation key. Note that TP(L) = TP, and that in TP(0) , only
the classical evaluation keys remain, since without the encryptions of the classical x and z, the quantum
part of the gadget is just the completely mixed state. That is, we can rewrite the final line of the previous
equation as
1 m m
∑ ρ(HE.Enc pki+1 (0 , 0 )) ⊗ γx,z (gi )
22mx,z∈{0,1}m
(4.1)
I 2m
= ρ(HE.Encpki+1 (0 , 0 )) ⊗ 22m .
m m
2
With the definitions of the new schemes, we can lay out the steps to prove Theorem 4.1 in more
detail. First, we show that in the quantum CPA indistinguishability experiment, any efficient adversary
interacting with TP(`) only has negligible advantage over an adversary interacting with TP(`−1) , i. e. the

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 17
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

scheme where the classical information g`−1 is removed (Lemma 4.2). By iteratively applying this
argument, we are able to argue that the advantage of an adversary who interacts with TP(L) over one who
interacts with TP(0) is also negligible (Corollary 4.3). Finally, we conclude the proof by arguing that
TP(0) is q-IND-CPA secure by comparison to the CL scheme.
Lemma 4.2. Let 0 < ` ≤ L. If HE is q-IND-CPA secure, then for any quantum polynomial-time adversary
A = (A1 , A2 ), there exists a negligible function η such that
Pr[PubKcpa (κ) = 1] − Pr[PubKcpa (κ) = 1] ≤ η(κ).
A ,TP(`) A ,TP(`−1)

Proof. The difference between schemes TP(`) and TP(`−1) lies in whether the gadget state
γx`−1 ,z`−1 (g`−1 )
|g |+2m .
`−1 , xg
is supplemented with its classical information gg `−1 , zg
`−1 , or just with an encryption of 0 `−1
cpa
Let A = (A1 , A2 ) be an adversary for the game PubK (`) (κ). We will define an adversary
A ,TP
A 0 = (A10 , A20 ) for PubKcpa−mult
A 0 ,HE (κ) that will either simulate the game

PubKcpa (κ) or PubKcpa (κ) .
A ,TP(`) A ,TP(`−1)

Which game is simulated will depend on some s ∈R {0, 1} that is unknown to A 0 himself. Using the
assumption that HE is q-IND-CPA secure, we are able to argue that A 0 is unable to recognize which of
the two schemes was simulated, and this fact allows us to bound the difference in success probabilities
between the security games of TP(`) and TP(`−1) . The structure of this proof is very similar to, e. g.,
Lemma 5.3 in [16]. The adversary A 0 acts as follows (see also Figure 3):
A10 takes care of most of the key generation procedure: he generates the classical key sets 0 through
` − 1 himself, generates the random strings x0 , z0 , . . . , x`−1 , z`−1 , and constructs the gadgets
γx0 ,z0 (g0 ), . . . , γx`−1 ,z`−1 (g`−1 ) and their classical information g0 , . . . , g`−1 . He encrypts the clas-
sical information using the appropriate public keys. Only g`−1 , x`−1 and z`−1 are left unencrypted.
Instead of encrypting these strings himself using pk` , A10 sends the strings for encryption to the
challenger. Whether the challenger really encrypts g`−1 , x`−1 and z`−1 or replaces the strings with
a string of zeros, determines which of the two schemes is simulated. A 0 is unaware of the random
choice of the challenger.
The adversary A10 also generates the extra padding inputs that correspond to the already-removed
gadgets ` up to L − 1. Since these gadgets consist of all-zero strings encrypted with independently
chosen public keys that are not used anywhere else, together with a completely mixed quantum
state (as shown in equation (4.1)), the adversary can generate them without needing any extra
information.
A20 feeds the evaluation key and public key, just generated by A10 , to A1 in order to obtain a chosen
message M (plus the auxiliary state E). He then picks a random r ∈R {0, 1} and replaces M by 0
if and only if r = 0. He encrypts the result according to the TP.Enc procedure (using the public
key (pki )Li=0 received from A10 ), and gives the encrypted state, plus E, to A2 , who outputs r0 in an
attempt to guess r. A20 now outputs 1 if and only if the guess by A was correct, i. e., r ≡ r0 .

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 18
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

r
$

pk`

Ξcpa,r
TP
for i = 0 to ` − 1 do: 0|g`−1 |+2m Ξ cpa−mult,s
g`−1 , x`−1 , z`−1 HE
xi , zi
$ g`−2 , x`−2 , z`−2 M
HE.Encpk`−1
build gadget

..
HE.KeyGen(1κ )

gi , xi , zi . s0 :=
g0 , x0 , z0 A2 r0 (r ≡ r0 )
HE.KeyGen(1κ )

ski HE.Encpk1
A1 E
γxi ,zi (gi ) N`−1
i=0 γxi ,zi (gi )

evki `−1
(evki )i=0
pki (pki )`−1
i=0

evk`

create padding

A10
A20

Figure 3: A strategy for the game PubKcpa−mult cpa
A 0 ,HE (κ), using an adversary A for PubKA ,TP(`) (κ) as a
subroutine. All the wires that form an input to A1 together form the evaluation key and public key for
TP(`) or TP(`−1) , depending on s. Note that Ξcpa,r cpa,r cpa,r
TP = ΞTP(`) = ΞTP(`−1) , so A2 can run either one of
0

these independently of s (i. e., without having to query the challenger). The “create padding” subroutine
generates dummy gadgets for ` up to L − 1, as described in the definition of A1 .

Because HE is q-IND-CPA secure, the probability that A 0 wins
PubKcpa−mult
A 0 ,HE (κ) ,

i. e., that s0 ≡ s, is at most 1/2 + η 0 (κ) for some negligible function η 0 . There are two scenarios in which
A 0 wins the game:
• s = 1 and A guesses r correctly: If s = 1, the game that is being simulated is
PubKcpa (κ) .
A ,TP(`)

If A wins the simulated game (r ≡ r0 ), then A 0 will correctly output s0 = 1. (If A loses, then A 0
outputs 0, and loses as well.)
• s = 0 and A does not guess r correctly: If s = 0, the game that is being simulated is
PubKcpa (κ) .
A ,TP(`−1)

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 19
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

If A loses the game (r 6≡ r0 ), then A 0 will correctly output s0 = 0. (If A wins, then A 0 outputs 1
and loses.)

From the above, we conclude that
1
Pr[s = 1] · Pr[PubKcpa (κ) = 1] + Pr[s = 0] · Pr[PubKcpa (`−1) (κ) = 0] ≤ + η 0 (κ)
A ,TP(`) A ,TP 2
1 1 1
⇔ Pr[PubKcpa (`) (κ) = 1] + 1 − Pr[PubKcpa (`−1) (κ) = 1] ≤ + η 0 (κ)
2 A ,TP 2 A ,TP 2
⇔ Pr[PubKcpa (`) (κ) = 1] − Pr[PubKcpa (`−1) (κ) = 1] ≤ 2η 0 (κ).
A ,TP A ,TP

Set η(κ) := 2η 0 (κ), and the proof is complete.

By applying Lemma 4.2 iteratively, L times in total, we can conclude that the difference between TP(L)
and TP(0) is negligible, because the sum of polynomially many negligible functions is still negligible:

Corollary 4.3. If L is polynomial in κ, then for any quantum polynomial-time adversary A = (A1 , A2 ),
there exists a negligible function η such that

Pr[PubKcpa (κ) = 1] − Pr[PubKcpa (κ) = 1] ≤ η(κ).
A ,TP(L) A ,TP(0)

Using Corollary 4.3, we can finally prove the q-IND-CPA security of our scheme TP = TP(L) .

Proof of Theorem 4.1. The scheme TP(0) is very similar to CL in terms of its key generation and encryp-
tion steps. The evaluation key consists of several classical evaluation keys, plus some completely mixed
states and encryptions of 0 which we can safely ignore because they do not contain any information
about the encrypted message. In both schemes, the encryption of a qubit is a quantum one-time pad
together with the encrypted keys. The only difference is that in TP(0) , the public key and evaluation key
form a tuple containing, in addition to pk0 and evk0 which are used for the encryption of the quantum
one-time pad, a list of public/evaluation keys that are independent of the encryption. These keys do not
provide any advantage (in fact, the adversary could have generated them himself by repeatedly running
HE.KeyGen(1κ , 1L )). Therefore, we can safely ignore these keys as well.
In [16, Lemma 5.3], it is shown that CL is q-IND-CPA secure. Because of the similarity between CL
and TP(0) , the exact same proof shows that TP(0) is q-IND-CPA secure as well, that is, for any A there
exists a negligible function η 0 such that
1
Pr[PubKcpa (κ) = 1] ≤ + η 0 (κ).
A ,TP(0) 2
Combining this result with Corollary 4.3, it follows that

Pr[PubKcpa
A ,TP (κ) = 1] ≤ Pr[PubK
cpa
(κ) = 1] + η(κ)
A ,TP(0)
1
≤ + η 0 (κ) + η(κ).
2
Since the sum of two negligible functions is itself negligible, we have proved Theorem 4.1.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 20
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

4.1 Circuit privacy
The scheme TP as presented above ensures the privacy of the input data. It does not guarantee, however,
that whoever generates the keys, encrypts, and decrypts cannot gain information about the circuit C
that was applied to some input ρ by the evaluator. Obviously, the output value CρC† often reveals
something about the circuit C, but apart from this necessary leakage of information, one may require
a (quantum) homomorphic encryption scheme to ensure circuit privacy in the sense that an adversary
cannot statistically gain any information about C from the output of the evaluation procedure that it could
not already gain from CρC† itself and the value of L.
We claim that circuit privacy for TP in the semi-honest setting (i. e., against passive adversaries6 ) can
be obtained by modifying the scheme only slightly, given that the classical encryption scheme has the
circuit privacy property.

Theorem 4.4. If HE has circuit privacy in the semi-honest setting, then TP can be adapted to a quantum
homomorphic encryption scheme with circuit privacy against honest-but-curious adversaries.

Proof sketch. If the evaluator randomizes the encryption of the output data by applying a quantum one-
time pad to the (already encrypted) result of the evaluation, the keys themselves are uniformly random
and therefore do not reveal any information about what circuit was evaluated. The evaluator can then
proceed to update the classical encryptions of those keys accordingly, and by the circuit privacy of the
classical scheme, the resulting encrypted keys will also contain no information about the computations
performed. A more thorough proof is given in Appendix B.

5 Constructing the gadgets
In this section we will first show how apply Barrington’s theorem to construct gadgets that have polynomial
size whenever the scheme HE has a decryption circuit with logarithmic depth, i. e., the decryption function
is in NC1 . To illustrate these techniques, we apply them to create gadgets for schemes that are based on
Learning With Errors (LWE).
This construction will already be powerful enough to instantiate TP with current classical schemes
for homomorphic encryption, since these commonly have low-depth decryption circuits. In Section 5.3
and Appendix C, we will present a larger toolkit to construct gadgets, which is efficient for a larger class
of possible decryption functions. This construction is based on the garden-hose model [17], and may be
read as an alternative to Section 5.1 and 5.2 by readers already familiar with that model.
Finally, we will reflect on the possibility of constructing both types of gadgets in scenarios where
quantum power is limited.

5.1 Gadget construction for log-depth decryption circuits
The main tool for creating gadgets that encode log-depth decryption circuits comes from Barrington’s
theorem, a classic result in complexity theory, which states that all Boolean circuits of logarithmic depth
6 Note that there various ways to define passive adversaries in the quantum setting [23, 8]. Here, we are considering
adversaries that follow all protocol instructions exactly.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 21
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

can be encoded as polynomial-size width-5 permutation branching programs. Every instruction of such a
branching program will be encoded as connections between five Bell pairs.

Definition 5.1. A width-k permutation branching program of length M on an input x ∈ {0, 1}n is a list of
M instructions of the form him , σm1 , σm0 i, for 1 ≤ m ≤ M, such that im ∈ [n], and σm1 and σm0 are elements
of Sk , i. e., permutations of [k]. The program is executed by composing the permutations given by the
instructions 1 through M, selecting σm1 if xim = 1 and selecting σm0 if xim = 0. The program rejects if this
product equals the identity permutation and accepts if it equals a fixed k-cycle.

Since these programs have a very simple form, it came as a surprise when they were proven to be
quite powerful [7].

Theorem 5.2 (Barrington [7]). Every fan-in 2 Boolean circuit C of depth d can be simulated by a width-5
permutation branching program of length at most 4d .

Our gadget construction will consist of first transforming the decryption function HE.Dec into a
permutation branching program, and then encoding this permutation branching program as a specification
of a gadget, as produced by TP.GenGadgetpk0 (sk), and usage instructions TP.GenMeasurement(e a).

Theorem 5.3. Let HE.Decsk (e a) be the decryption function of the classical homomorphic encryption
scheme HE. If HE.Dec is computable by a Boolean fan-in 2 circuit of depth O(log(κ)), where κ is the
security parameter, then there exist gadgets for TP of size polynomial in κ.

Proof. Our description will consist of three steps. First, we write HE.Dec as a width-5 permutation
branching program, of which the instructions alternately depend on the secret key sk and on the cipher-
text ae. Secondly, we specify how to transform these instructions into a gadget which almost works
correctly, but for which the qubit ends up at an unknown location. Finally, we complete the construction
by executing the inverse program, so that the qubit ends up at a known location.
The first part follows directly from Barrington’s theorem. The effective input of HE.Dec can be seen
as the concatenation of the secret key sk and the ciphertext ae. Since by assumption the circuit is of depth
O(log κ), there exists width-5 permutation branching program P of length M = κ O(1) , with the following
properties. We write
P = hi1 , σ11 , σ10 i, hi2 , σ21 , σ20 i, . . . , hiM , σM
1 0

, σM i
as the list of instructions of the width-5 permutation branching program. Without loss of generality,7 we
can assume that the instructions alternately depend on bits of ae and bits of sk. That is, the index im refers
to a bit of ae if m is odd, and to a bit of sk if m is even. There are M instructions in total, of which M/2 are
odd-numbered and M/2 are even.
The output of TP.GenGadgetpk0 (sk), i. e., the list of pairs {(si ,ti )}i in g(sk) that defines the structure
of the gadget, will be created from the even-numbered instructions, evaluated using the secret key
sk. For every even-numbered m ≤ M, we connect ten qubits in the following way. Suppose the mth
sk
instruction evaluates to some permutation σm := σm im . Label the 10 qubits of this part of the gadget
7 This can be seen by inserting dummy instructions that always perform the identity permutation between any two consecutive

instructions that depend on the same variable. Alternatively, it would be possible to improve the construction by “multiplying
out” consecutive instructions whenever they depend on the same variable.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 22
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

by 1m,in , 2m,in , . . . , 5m,in and 1m,out , 2m,out , . . . , 5m,out . These will correspond to 5 EPR pairs, connected
according to the permutation:

(1m,in , σm (1)m,out ), (2m,in , σm (2)m,out ), etc., up to (5m,in , σm (5)m,out ) .

After the final instruction of the branching program, σM , also perform an inverse phase gate P† on
the qubits labeled as 2M,out , 3M,out , 4M,out , 5M,out . Execution of the gadget will teleport the qubit through
one of these whenever HE.Dec(e a) = 1.
For this construction, TP.GenMeasurement(e a) will be given by the odd instructions, which depend
ae
only on the bits of ae (and the function HE.Dec, but not on sk). Again, for all odd m ≤ M, let σm := σmim
be the permutation given by the evaluation of instruction m on ae. For all m strictly greater than one, the
measurement instructions will be: perform a Bell measurement according to the permutation σm between
the “out” qubits of the previous set, and the “in” qubits of the next. The measurement pairs will then be

(1m−1,out , σ (1)m,in ), (2m−1,out , σ (2)m,in ), up to (5m−1,out , σ (5)m,in ) .

For ` = 1, there is no previous layer to connect to, only the input qubit. For that, we add the
measurement instruction (0, σ (1)1,in ), where 0 is the label of the input qubit.
By Barrington’s theorem, if HE.Decsk (e a) = 0 then the product, say τ, of the permutations coming
from the evaluated instructions equals the identity. In that case, consecutively applying these permutations
on “1,” results in the unchanged starting value, “1.” If instead the decryption would output 1, the
consecutive application results in another value in {2, 3, 4, 5}, because in that case, τ is a k-cycle. After
teleporting a qubit through these EPR pairs, with teleportation measurements chosen accordingly, the
input qubit will be present at τ(1)M,out , with an inverse phase gate if τ(1) is unequal to 1. Thus, if an
inverse phase P† is applied to the output qubits at position 2 through 5 (but not position 1), then a phase
gate is applied whenever HE.Decsk (e a) = 1. The positions where an inverse phase is applied define the
bitstring p in g(sk).
The gadget constructed so far would correctly apply the phase gate, conditioned on HE.Decsk (e a),
with one problem: afterward, the qubit is at a location unknown to the user of the gadget, because the
user cannot compute τ.
We fix this problem in the following way: execute the inverse branching program afterwards. The
entire construction is continued in the same way, but the instructions of the inverse program are used.
The inverse program can be made from the original program by reversing the order of instructions, and
then for each permutation using its inverse permutation instead. The first inverse instruction is
1 −1 0 −1
hiM , (σM ) , (σM ) i, 1
then hiM−1 , (σM−1 )−1 , (σM−1
0
)−1 i ,

with final instruction
hi1 , (σ11 )−1 , (σ10 )−1 i .
One small detail is that iM is used twice in a row, breaking the alternation; the user of the gadget can
simply perform the measurements that correspond to the identity permutation in between, since
0 0 −1 1 1 −1
(σM )(σM ) = (σM )(σM ) =e (the identity permutation).

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 23
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

he
a1 , e, (12345)i hsk1 , e, (12453)i he
a1 , e, (54321)ihsk1 , (14235), (15243)i

P†

Figure 4: Structure of the (first half of the) gadget, with measurements, coming from the 5-permutation
branching program for the OR function on the input (0, 0). The example program’s instructions are
displayed above the permutations. The solid lines correspond to Bell measurements, while the wavy lines
represent EPR pairs.

After having repeated the construction with the inverse permutation branching program, the qubit is
guaranteed to be at the location where it originally started: σ1 (1) of the final layer of five qubits—that
will then be the corrected qubit which is the output of the gadget.
The total number of qubits which form the gadget, created from a width-5 permutation branching
program of length M, of which the instructions alternate between depending on ae and depending on sk, is
2 · (5M) = 10M.

Example. The OR function on two bits can be computed using a width-5 permutation branching
program of length 4, consisting of the following list of instructions:

1. h1, e, (12345)i

2. h2, e, (12453)i

3. h1, e, (54321)i

4. h2, (14235), (15243)i

As a simplified example, suppose the decryption function HE.Decsk (e a) is sk1 OR ae1 . Then, for one
possible example set of values of ae and sk, half of the gadget and measurements will be as given in
Figure 4. To complete this gadget, the same construction is appended, reflected horizontally.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 24
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

5.2 Specific case: Learning With Errors
The scheme by Brakerski and Vaikuntanathan [12] is well-suited for our construction, and its decryption
function is representative for a much wider class of schemes which are based on the hardness of Learning
With Errors (LWE). As an example, we construct gadgets that enable quantum homomorphic encryption
based on the BV11 scheme. Let κ be the security parameter, and let p be the modulus of the integer ring
over which the scheme operates.
The ciphertext c is given by a pair (v, w), with v ∈ Zκp and w ∈ Z p . The secret key s is an element of
κ
Z p . The decryption to a message x involves computation of an inner product over the ring Z p ,

x = Decs ((v, w)) := (w − hv, si) (mod p) (mod 2) . (5.1)

The BV11 scheme is able to make the modulus small, i. e., polynomial in κ, before encryption. We
present an explicit construction for the case of small modulus p, which can be illustrative to read as
example of our construction, and an implicit construction for more complicated gadgets for the case of
superpolynomial p. Both constructions lead to gadgets that are polynomial in κ.

Small modulus
Take the modulus p to be polynomial in κ. We describe a series of small “permutation gadgets” that
move an arbitrary qubit to a location, depending on whether x = 0 or x = 1. By doubling the construction
as seen before, it is easy to turn these into a gadget which applies an inverse phase gate whenever x = 1.
Note that we could just apply Theorem C.1 in order to construct a gadget directly from a log-space Turing
machine of the decryption function. In this example, however, we choose to exhibit a more efficient
gadget that exploits the structure of the BV11 scheme.
We follow [12, Section 4.5] in rewriting equation (5.1) in terms of binary arithmetic. Let s[i]( j)
denote the jth bit of the ith entry of s, then the inner product can be written as
k
w − hv, si (mod p) = w − ∑ v[i]s[i] (mod p)
i=1
k log p
= w − ∑ ∑ v[i]( j) · 2 j · s[i] (mod p) . (5.2)
i=1 j=0

Let a permutation gadget be a subgadget of size 2p, parametrized by a number q ∈ Z p . Label the first
p qubits by 0in to (p − 1)in , and the second p qubits by 0out to (p − 1)out . The gadget simply creates EPR
pairs between yin and (y + q (mod p))out , for all y ∈ Z p . Such a gadget can effectively simulate addition
with q over Z p .
For each element of the vector s we will create log p permutation gadgets. The intuition behind
the construction is as follows. The inner product which computed the decryption of the ciphertext is
written as a sum of κ log p numbers, that either contribute to the sum or not, depending on a bit of the
ciphertext v.
For each i from 1 to κ, and each j from 0 to log p, we create a permutation gadget, labeled by (i, j),
for the number 2 j · s[i].

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 25
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

The evaluator uses this gadget in the following way. He performs a Bell measurement between the
input qubit and the 0in qubit of the first gadget such that v[i]( j) = 1. Then, he connects all output qubits
0out to (p − 1)out of this gadget to all the input qubits of the next gadget for which v[i]( j) = 1.
After teleporting his qubit through all gadgets, the qubit will be exactly at the location zout of the final
gadget the evaluator used, where
κ
z = ∑ v[i]s[i] (mod p) ,
i=1

although of course the evaluator has no way of knowing which of the p locations this is. He can then, by
simple permutation, apply an inverse phase gate whenever w − z (mod 2) = 1.
Finally, as in the construction from the previous section, we double the entire construction to route
the unknown qubit back to a known location. The size of the total gadget is then bounded by 4κ p log p.

Large modulus

In case the modulus p is superpolynomially large, constructing the gadget explicitly appears to be much
harder, and a log-space algorithm for this inner product is not immediately obvious. For completeness,
we sketch a proof strategy to reiterate that such a polynomial-size gadget does still exist in this case.
The decryption function of equation (5.1) has depth O(log κ + log log p), see for example [12, Lemma
4.5]. This can be proved by writing the decomposition of equation (5.2) as a Wallace tree.
Given a low-depth circuit, we could now apply Theorem 5.3 to convert this circuit into a garden-hose
protocol. In contrast to the small-modulus case, we do not exploit the structure of the decryption function
to construct a more efficient gadget.

5.3 Gadget construction for log-space computable decryption functions
Even though the construction based on Barrington’s theorem has enough power for current classical
homomorphic schemes, it is possible to improve on this construction in two directions. Firstly, we extend
our result to be able to handle a larger class of decryption functions: those that can be computed in
logarithmic space, instead of only NC1 . Secondly, for some specific decryption functions, executing the
construction of Section 5.1 might produce significantly larger gadgets than necessary. For instance, even
for very simple circuits of depth log κ, Barrington’s theorem produces programs of length κ 2 —a direct
approach can often easily improve on the exponent of the polynomial. See also the garden-hose protocols
for equality [42, 19] and the majority function [38] for examples of non-trivial protocols that are much
more efficient than applying Barrington’s theorem as a black box.
In Appendix C we describe a construction for log-space computation in depth. The explanation in the
appendix uses a different language than the direct encoding of the previous section: Namely, there is a
natural way of writing the requirements on the gadgets as a two-player task, and then writing strategies
for this task in the garden-hose model.

Theorem 5.4. Let HE.Decsk (e a) be the decryption function of the classical homomorphic encryption
scheme HE. If HE.Dec is computable by a Turing machine that uses space O(log κ), where κ is the
security parameter, then there exist gadgets for TP of size polynomial in κ.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 26
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

Writing these gadgets in terms of the garden-hose model, even though it adds a layer of complexity to
the construction, gives more insight into the structure of the gadgets, and forms its original inspiration. We
therefore sketch the link between log-space computation and gadget construction within this framework.
Viewing the gadget construction as instance of the garden-hose model, besides clarifying the log-
space construction, also makes it easier to construct gadgets for specific cases. Earlier work developed
protocols in the garden-hose model for several functions, see for instance [52, 17, 38], and connections to
other models of computation. These results on the garden-hose model might serve as building blocks to
create more efficient gadgets for specific decoding functions of classical homomorphic schemes, that
are potentially much smaller than those created as a result of following the general constructions of
Theorem 5.3 or 5.4.

5.4 Constructing gadgets using limited quantum resources
In a setting where a less powerful client wants to delegate some quantum computation to a more powerful
server, it is important to minimize the amount of effort required from the client. In delegated quantum
computation, the complexity of a protocol can be measured by, among other things, the total amount of
communication between client and server, the number of rounds of communication, and the quantum
resources available to the client, such as possible quantum operations and memory size.
We claim that TP gives rise to a three-round delegated quantum computation protocol in a setting
where the client can perform only Pauli and swap operations. TP.Enc and TP.Dec only require local
application of Pauli operators to a quantum state, but TP.KeyGen is more involved: in the current
description of the gadget generation, the key generator has to generate EPR-pairs, as well as perform P†
gates and Bell measurements. We show in this section how the gadgets can be generated securely using
only X, Z and swaps, when the key generator is given resources by some computationally more powerful
(but potentially malicious) party, for example the evaluator.
As described in Section 3.1, the gadget Γpk0 (sk) is effectively a list of 2m EPR-pairs, some of which
have an extra (P† ⊗ I) transformation on them, with the qubits ordered in some way that depends on
sk. See also Figure 7 in Appendix C. If the key generator is supplied with a list of 2m EPR-pairs |Φ+ i
and as many pairs (I ⊗ P† )|Φ+ i, it is clear that he can create the gadget by swapping some of the qubits
(e. g., using CNOT gates), and applying a single random Pauli operation (using X and Z gates) on every
pair. Any unused pairs are discarded. If the supplier of these pairs follows the protocol and sends actual
EPR-pairs to the key generator, this tactic suffices to hide all information about sk. However, we need
to make sure that even if the supplier acts maliciously and actively tries to gather information about
sk, this information is still secure. The key generator, upon receiving the (real or fake) EPR-pairs, will
instead apply an independently-selected random Pauli transformation on each of the qubits individually,
i. e., the key generator applies a quantum one-time pad. From the perspective of a supplier that has no
knowledge of the quantum one-time pad key, this is equivalent to tracing out these qubits and replacing
them with a completely mixed state—even if the malicious supplier was entangled with these qubits
before sending them to the client. Since it doesn’t make a difference whether or not qubits are swapped
amongst themselves before they are replaced by a completely mixed state, the supplier can not learn
whether this happened and therefore no information about sk will be revealed to the supplier. Of course,
the correctness of the outcome is not guaranteed in the case of a malicious supplier.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 27
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

We just discussed a three-round delegated protocol in a setting where the client is limited in the
types of operations he can perform. Alternatively, TP can be regarded as a two-round delegated protocol
in a setting where the client can perform arbitrary Clifford operations, but is limited to a constant-size
quantum memory, given that HE.Dec is in NC1 . In that case, the gadgets can be constructed ten qubits at
a time, by constructing the sets of five EPR pairs as specified in Section 5.1. By decomposing the 5-cycles
into products of 2-cycles, the quantum memory can even be reduced to only four qubits. The client sends
these small parts of the gadgets to the server as they are completed. Because communication remains
one-way until all gadgets have been sent, this can be regarded as a single round of communication.
These two delegated-computation protocols exhibit a trade-off between the extensiveness of the
client’s quantum storage and his quantum computing power. Other known protocols for delegated
quantum computation often require even less from the client both in terms of computing power and
storage, but these generally sacrifice on a third parameter: the number of communication rounds. For
example, the universal blind quantum computing protocol introduced by Broadbent et al. [15] only
requires the client to generate single-qubit states from a fixed, small set of possible states, but client
and server need to communicate separately for every quantum gate in the circuit. In our scheme, we
minimize communication during the evaluation phase using the gadgets, the generation of which involves
more quantum computational power and/or quantum storage from the client. An instructive overview
of the current state of the art in delegated quantum computing can be found in a recent survey paper by
Fitzsimons [26].

6 Conclusion
We have presented the first quantum homomorphic encryption scheme TP that is compact and allows
evaluation of circuits with polynomially many T gates in the security parameter, i. e., arbitrary polynomial-
size circuits. Assuming that the number of wires involved in the evaluation circuit is also polynomially
related to the security parameter, we may consider TP to be leveled fully homomorphic. The scheme is
based on an arbitrary classical FHE scheme, and any computational assumptions needed for the classical
scheme are also required for security of TP. However, since TP uses the classical FHE scheme as a black
box, any FHE scheme can be plugged in to change the set of computational assumptions.
Our constructions are based on a new and interesting connection between the area of instantaneous
non-local quantum computation and quantum homomorphic encryption. Recent techniques developed by
Speelman [53], based on the garden-hose model [17], have turned out to be crucial for our construction
of quantum gadgets which allow homomorphic evaluation of T gates on encrypted quantum data.

6.1 Future work
Since Yu, Pérez-Delgado and Fitzsimons [58] showed that information-theoretically secure QFHE is
impossible (at least in the exact case), it is natural to wonder whether it is possible to construct a non-
leveled QFHE scheme based on computational assumptions. If such a scheme is not possible, can one
find lower bounds on the size of the evaluation key of a compact scheme? Other than the development of
more efficient QFHE schemes, one can consider the construction of QFHE schemes with extra properties,
such as circuit privacy against active adversaries. It is also interesting to look at other cryptographic

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 28
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

tasks that might be executed using QFHE. In the classical world for example, multiparty computation
protocols can be constructed from fully homomorphic encryption [21]. We consider it likely that our new
techniques will also be useful in other contexts such as quantum indistinguishability obfuscation [4].

Acknowledgements
We acknowledge useful discussions with Anne Broadbent, Harry Buhrman, and Leo Ducas. We thank
Stacey Jeffery for providing the inspiration for a crucial step in the security proof, and Gorjan Alagic and
Anne Broadbent for helpful comments on a draft of this article.

A Using the gadget
After using the gadget, but before updating any classical information, the evaluator has the following
pieces of classical information. The encrypted one-time pad keys ae, e b, a list of m pairs for Bell
measurements M ← TP.GenMeasurement(e a) and a list of outcomes for each of these m measurements,
say c, d ∈ {0, 1}m .
The evaluator also has encrypted versions of {(s1 ,t1 ), (s2 ,t2 ), . . . , (sm ,tm )}, p ∈ {0, 1}m , and x, z ∈
{0, 1}m that specify the structure of the gadget.
Say an arbitrary qubit8 was teleported through the gadget, so that the qubit started in some state
0 0
P Xa Zb |ψi and is currently in state Xa Zb |ψi. We sketch the algorithm an evaluator would execute on
a

this encrypted state, to compute (encrypted versions of) the updated keys a0 and b0 . Updating the keys is
not complicated, it mostly involves bookkeeping to keep track of the current location of the qubit, and its
current X-correction, Z-correction and phase.
We explain the calculation as if performed with the unencrypted versions; in the actual execution, only
the encrypted versions of all variables are used, and this entire calculation is performed homomorphically.
Since all the mentioned classical information either is or can be encrypted with the same public key, this
calculation can be handled by the classical homomorphic scheme HE.
The algorithm tracks the path the qubit takes through the gadget, by resolving the teleportations that
involve the qubit one by one. Even though the measurements were all performed at the same time, we
will describe them as if ordered in this manner. All additions of the keys of the one-time pad will be
performed modulo 2, since X2 = Z2 = I.
Let a, b be variables that hold the current key to the one-time pad at every step of the algorithm. We
initialize these as a ← a and b ← b. Let q be a variable that stores whether or not the qubit currently has an
extra phase gate, initialized as q ← a. Let r be the variable that contains the current location of the qubit,
with possible locations 0 to 2m, initialized to 0. That is, we view the current state as being Pq Xa Zb |ψi at
location r. For every step we update the location depending on M and {(s1 ,t1 ), (s2 ,t2 ), . . . , (sm ,tm )}, and
update the keys depending on the corresponding measurement outcomes.
First, find the pair in M that contains the current location r, say pair i which consists of (r, s) for some
other location s. The outcome of this measurement is given by c[i] and d[i]. Effectively, these outcomes
8 The input qubit is not necessarily a pure state, but we write an arbitrary pure state without loss of generality, to simplify

notation.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 29
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

change the current state to

Xc[i] Zd[i] Pq Xa Zb |ψi = Pq Xa+c[i] Zb+d[i]+q·c[i] |ψi ,

therefore we update a ← a + c[i] and b ← b + d[i] + q · c[i]. Note that the key update rules also involve
multiplication—an extra Z gate is added if the phase gate was present, q = 1, and the teleportation
measurement required an X correction, c[i] = 1.
Next, find the pair in {(s1 ,t1 ), (s2 ,t2 ), . . . , (sm ,tm )} that contains the new location s, say pair j
containing (s,t). The teleportation of the qubit through this pair effectively applies Xx[ j] Zz[ j] (P† ) p[ j] to
the state. Then, if we already use the updated a and b, the quantum state at this step equals

Xx[ j] Zz[ j] (P† ) p[ j] Pq Xa Zb |ψi = Xx[ j] Zz[ j] P p[ j] Pq Xa Zb+p[ j] |ψi
= P p[ j]+q (mod 2) Xa+x[ j] Zb+z[ j]+p[ j]·(1+q)+x[ j]·(p[ j]+q) |ψi .

For rewriting, we used the fact that P2 = Z and that P† = PZ, together with the commutation relations
from the previous section. We therefore update the phase q ← p[ j] + q (mod 2), and the components of
the quantum one-time pad to a ← a + x[ j] and b ← b + z[ j] + p[ j] · (1 + q[ j]) + x[ j] · (p[ j] + q[ j]). Finally,
set the new location of the qubit r ← t.
The previous two steps are then repeated m times, where 2m is the size of the gadget, to eventually
(homomorphically) compute the new updated keys a0 ,b0 to the quantum one-time pad. Afterwards, all
temporary variables can be discarded, and only the updated keys will be needed for continuing the
protocol.

B Circuit privacy
In this appendix, we demonstrate that with only a slight modification of TP, the scheme has circuit
privacy in the semi-honest setting, i. e., against passive adversaries. Classically, circuit privacy is defined
by requiring the existence of a simulator SimHE whose inputs are the public parameters and C(x) and
which produces an output which is indistinguishable from the homomorphic evaluation of C on the
encryption of x. Formally, circuit privacy is defined as follows.
Definition B.1 (Classical circuit privacy—semi-honest setting [37]). A classical homomorphic encryption
scheme HE has statistical circuit privacy in the semi-honest (“honest-but-curious”) model if there exists a
PPT algorithm SimHE and a negligible function η such that for any security parameter κ, input x, key set
(pk, evk, sk) ← HE.KeyGen(1κ ), and circuit C:

δ (HE.EvalCevk (HE.Enc pk (x)), SimHE (1κ , pk, evk, C(x))) ≤ η(κ) .

Here,
1
δ (X,Y ) := ∑ Pr[X = u] − Pr[Y = u]
2 u∈U
is the statistical distance between two random variables over a finite universe U. For notational conve-
nience, we will often write SimHE (C(x)) if the rest of the arguments are clear from the context. Also we
will sometimes write X ≈a Y to denote that δ (X,Y ) ≤ a.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 30
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

If the recryption functionality Reci→ j is defined as the composition of the procedures

HE.EvalHE.Dec
evk j
i
and HE.Encpk j ,
as in Section 2.2, then recryptions do not degrade the privacy of the computation: a homomorphic
evaluation of some function with key switching is statistically close to running the simulator directly on
the function output using only the last key set.
Lemma B.2. Suppose HE has statistical circuit privacy in the semi-honest setting, and let SimHE and η
be as in Definition B.1. Then for any security parameter κ, L polynomial in κ, list of circuits C1 , ..., CL
and list of keysets (pki , evki , ski )Li=1 generated by HE.KeyGen(1κ ), and input x, the statistical distance
between
C
HE.EvalCevkL L (HE.Rec(L−1)→L (HE.EvalevkL−1 L−1
(· · · HE.EvalCevk1 1 (HE.Encpk1 (x))))
and
SimHE (1κ , pkL , evkL , CL (CL−1 (· · ·C1 (x))))
is negligible in κ.
HE.DecskL−1
Proof. Since HE.Rec(L−1)→L = HE.EvalevkL ◦ HE.EncpkL by definition, we have that
C
HE.EvalCevkL L (HE.Rec(L−1)→L (HE.EvalevkL−1
L−1
(· · · HE.EvalCevk1 1 (HE.Encpk1 (x))))
CL ◦HE.DecskL−1 C
= HE.EvalevkL (HE.EncpkL (HE.EvalevkL−1
L−1
(· · · HE.EvalCevk1 1 (HE.Encpk1 (x))))
C
≈η(κ) SimHE (1κ , pkL , evkL , CL (HE.DecskL−1 (HE.EvalevkL−1
L−1
(· · · HE.EvalCevk1 1 (HE.Encpk1 (x))))))
which, by correctness of HE, is statistically indistinguishable from
SimHE (1κ , pkL , evkL , CL (CL−1 (CL−2 (· · · C1 (x)))))
as long as L is polynomial in κ. By triangle inequality, the statement of the lemma follows.

In the quantum setting, we need to take into account the fact that the input state may be part of some
larger (possibly entangled) system. This leads to the following definition of quantum circuit privacy in
the semi-honest setting:
Definition B.3 (Quantum circuit privacy—semi-honest setting). A quantum homomorphic encryption
scheme QHE has statistical circuit privacy in the semi-honest setting if there exists a quantum PPT
algorithm SimQHE and a negligible function η such that for any security parameter κ, depth parameter L,
key set (pk, ρevk , sk) ← QHE.KeyGen(1κ , 1L ), state σ , and circuit C with up to L T-gates:

C,ρevk ,pk ρevk ,pk
ΦQHE.Eval ◦ Φpk
QHE.Enc − Φ SimQHE ◦ ΦC ≤ η(κ).
♦

In this definition, ΦU denotes the quantum channel induced by the circuit or functionality U. The
diamond norm kΦU k♦ is defined in terms of the trace norm: kΦU k♦ := maxσ k(ΦU ⊗ I)σ k1 where the
maximization is over input states σ .
We now show that the scheme TP can, with very little overhead, be modified to provide circuit
privacy, as stated in Theorem 4.4 from Section 4.1:

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 31
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

Theorem 4.4. If HE has circuit privacy in the semi-honest setting, then TP can be adapted to a quantum
homomorphic encryption scheme with circuit privacy against honest-but-curious adversaries.

Proof. We make the following alteration to the scheme TP: at the end of the evaluation procedure, the
evaluator applies a (random) quantum one-time pad to the output of the evaluation, and updates the
classical encryptions of the keys accordingly. The rest of the scheme remains exactly the same, and it
is clear that this altered version of TP is still compact and correct. Recall from Section 3.4 that, at the
end of the evaluation procedure, the data is recrypted into the Lth key set, and all unused gadgets are
discarded. Thus, the output ciphertext is encrypted under the same key set, regardless of the number of T
gates in the circuit C. (In a setting where gadgets are supplied on-demand, one has to be more careful not
to reveal the number of T gates in the circuit.)
Intuitively, the randomization step at the end of the evaluation phase completely hides the circuit.
Namely, the keys to the quantum one-time pads themselves are now entirely independent of the circuit,
and circuit privacy of HE will ensure that even the classical encryption of these keys does not reveal any
information about the computations performed on them.
To formalize this intuition, we define a quantum algorithm SimTP satisfying the constraints given
in Definition B.3. Let SimHE be the classical simulator guaranteed to exist by the classical circuit
privacy of HE (see Definition B.1). Given some security parameter κ, some keys pk = (pk1 , ..., pkL )
and evk = (evk1 , ..., evkL ), and some quantum state σ , let SimTP apply a uniformly random quantum
one-time pad to σ , and apply SimHE (1κ , pkL , evkL , ·) to the pad keys. The resulting classical-quantum
state is the output of SimTP . This algorithm resembles TP.Enc, but instead of calling HE.Enc (with pk1 )
as a subroutine, it handles the pad key information using the classical simulator SimHE (with pkL ).
If we can show that the trace distance

C,ρevk ,pk ρevk ,pk
ΦTP.Eval ◦ Φpk
TP.Enc ⊗ I σ − (ΦSimTP ◦ ΦC ) ⊗ I σ
1

is negligible for any quantum state σ of an appropriate dimension, then quantum circuit privacy of TP
immediately follows from Definition B.3 and the definition of the diamond norm.
Write

ρevk ,pk C,ρevk ,pk pk
σsim := (ΦSim TP
◦ ΦC ) ⊗ I σ , and σ eval := Φ TP.Eval ◦ ΦTP.Enc ⊗ I σ .

We study the state σsim in more detail, and show how to transform it into σeval in only a few (negligible)
steps. As a result, the trace distance of these two states will be negligible.
By definition of the algorithm SimTP , the state σsim is equal to
n n
1 O
κ
O
2n ∑ ρ SimHE (1 , pk L , evk L , x[i]) ⊗ ρ SimHE (1κ , pkL , evkL , z[i]) ⊗
2 x,z∈{0,1}n i=1 i=1
! !!
n
O n
O
x[i] z[i] † z[i] x[i]
X Z C⊗I σ C Z X ⊗I .
i=1 i=1

During the evaluation procedure of TP, the evaluator updates the keys to the quantum one-time pad for
all n qubits in the circuit. These updates depend on the circuit that is being evaluated, some randomness r

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 32
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

from the Bell measurement outcomes9 and of course on the initial one-time pad keys. Let fiC,r (a, b) denote
the X key on the ith qubit after the evaluation of some circuit C with randomness r, with a, b ∈ {0, 1}n the
initial pad keys before the evaluation procedure. Similarly, let gC,r
i (a, b) denote the Z key for that qubit.
At the end of the evaluation phase, the evaluator chooses bit strings x and z uniformly at random,
so the final keys fiC,r (a, b) ⊕ x[i] and gC,r
i (a, b) ⊕ z[i] are themselves completely uniform for any a, b.
Therefore, the state σsim is actually equal to

n
1
ρ SimHE (1κ , pkL , evkL , fiC,r (a, b) ⊕ x[i]) ⊗
O
4n ∑ Pr(r)
2 a,b,x,z∈{0,1}n R i=1
r∈{0,1}∗
n
ρ SimHE (1κ , pkL , evkL , gC,r
O
i (a, b) ⊕ z[i]) ⊗
i=1
! !!!
n n
fiC,r (a,b)⊕x[i] giC,r (a,b)⊕z[i] gC,r
i (a,b)⊕z[i] fiC,r (a,b)⊕x[i]
O O
X Z C ⊗ I σ C† Z X ⊗I .
i=1 i=1

This is where the classical circuit privacy property kicks in: for any fixed i, a, b, C, r, x, the result of the
probabilistic computation SimHE ( fiC,r (a, b) ⊕ x[i]) is statistically indistinguishable from the evaluation
of the function fiC,r (·, ·) ⊕ x[i] on the encryptions of a and b. Note however that the evaluation of fiC,r is
performed in several steps, with key switching in between. That is, separate functions h1 through hL are
evaluated in each key set 1 through L, such that fiC,r = hL ◦ · · · ◦ h1 . We abstract away from the exact way
that the function fiC,r is broken up into these separate functions h1 , ..., hL , and simply write

i f C,r (·,·)⊕x[i]
HE.Eval1,...,L (HE.Encpk1 (a, b))

to denote
(·⊕x[i])◦hL h
HE.EvalevkL L−1
(HE.Rec(L−1)→L (HE.Evalevk L−1
(· · · HE.Evalhevk
1
1
(HE.Encpk1 (a, b)))).

By Lemma B.2, it follows that

fiC,r (·,·)⊕x[i]

δ HE.Eval1,...,L (HE.Encpk1 (a, b)), SimHE (1κ , pkL , evkL , fiC,r (a, b) ⊕ x[i]) ≤ η(κ)

for some negligible function η. We can rewrite this equation in terms of the trace distance to get

fiC,r (·,·)⊕x[i]

HE.Eval1,...,L (HE.Encpk1 (a, b)) − SimHE (1κ , pkL , evkL , fiC,r (a, b) ⊕ x[i]) ≤ 2η(κ)
1

9 Although for the scheme TP, the measurement outcomes will in principle be uniformly distributed, we will not make this

assumption here. In case of a malicious key generator, measurement outcomes might be correlated in some way. Therefore, we
will simply assume that r is distributed according to some distribution R.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 33
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

A similar result holds for gC,r
i (·, ·) ⊕ z[i]. Using subadditivity of the trace norm with respect to the tensor
product, it follows that the trace distance between σsim and

n
1 O fiC,r ⊕x[i]
4n ∑ Pr(r) ρ HE.Eval1,...,L (HE.Encpk1 (a, b)) ⊗
2 a,b,x,z∈{0,1}n R i=1
r∈{0,1}∗
n
O gC,r
i ⊕z[i]

ρ HE.Eval1,...,L (HE.Encpk1 (a, b)) ⊗
i=1
! !!!
n n
fiC,r (a,b)⊕x[i] gC,r
i (a,b)⊕z[i] gC,r
i (a,b)⊕z[i] fiC,r (a,b)⊕x[i]
O O
†
X Z C⊗I σ C Z X ⊗I
i=1 i=1

is at most 4n · η(κ). Note that this last state is exactly σeval , the result of putting σ through the channel
C,ρevk ,pk
◦ Φpk

ΦTP.Eval TP.Enc ⊗ I .

We conclude that for any σ ,
kσeval − σsim k1 ≤ 4n · η(κ)
for some negligible function η that does not depend on σ . Hence,
C,ρ ,pk ,pk
◦ Φpk
evk evk ρ
(ΦTP.Eval TP.Enc ) − (ΦSimTP ◦ ΦC ) ♦ =

C,ρevk ,pk ρevk ,pk
max (ΦTP.Eval ◦ Φpk
TP.Enc ) ⊗ I σ − (Φ SimTP ◦ Φ C ) ⊗ I σ ≤ 4n · η(κ)
σ 1

which is negligible if η is negligible.

C Gadget construction using the garden-hose model
To construct the gadgets for specific decryption functions HE.Dec, we will consider a purified version of
the construction of the gadget state.
Consider the following task among two parties Alice and Bob. Alice corresponds to the party which
creates the gadget, so she has knowledge of the secret key sk. Bob corresponds to the party which uses
the gadget, therefore Bob has some input ae and a state Pa |ψi, where a = HE.Decsk (e a). The end goal
0 0
of the task is for Bob to possess the state Xa Zb |ψi for some a0 ,b0 that are computable from classical
information known to Alice and Bob. The players pre-share a number of EPR pairs between them, and
are only allowed to perform their actions without receiving any communication from the other player. We
only consider strategies where the players perform Bell measurements and inverse phase gates on their
local halves of the given EPR pairs (and in Bob’s case also on the input qubit).
Before presenting strategies for this task, we first describe how this task translates to the creation
of a gadget. Say Alice and Bob share 2m EPR pairs between them (i. e., they start with 4m qubits in
total). Alice will perform Bell measurements between the halves of EPR pairs on her side, where the
choices she makes depend on sk. Since both players act before receiving any information from the other

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 34
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

player, the actions of Alice and Bob are not ordered—we first consider how to describe the state when
Alice has acted on her local half. If Alice measures between, say, qubits s and t, with a two-bit outcome
that describes the X and Z corrections, then we can instantly describe the qubits s and t on Bob’s side
as forming a fully entangled state—this teleportation of EPR halves is sometimes called entanglement
swapping. Which out of the four Bell states is formed depends on the outcomes of Alice’s measurement.
We also allow Alice to perform a P† gate on some qubits before teleportations. Note that if Alice
measures on the qubits given by {(s1 ,t1 ), (s2 ,t2 ), . . . , (sm ,tm )}, after applying an inverse phase gate when
specified by the bit-string p, the state on Bob’s side will exactly have the form of γx,z g(sk) , for some
random binary strings x, z that correspond to the outcomes of Alice’s Bell measurements. The quantum
part of the gadget will be given by the reduced state on Bob’s side, while the measurement choices and
outcomes of Alice will form the accompanying classical information. The pairs that Bob chooses to
perform Bell measurements on, which only depend on the encrypted information, are exactly the output
of the function TP.GenMeasurement.
An upper bound to the hardness of this task is given by the garden-hose complexity HE.Dec, written
GH(HE.Dec), which is the least number of pipes needed for the players to compute it in the garden-
hose model described in Section 2.3. This complexity measure is the main measure of hardness in the
garden-hose model, and is relevant for the size of the gadgets in our construction.
The amount of space a Turing machine needs to compute any function f is closely related to it
garden-hose complexity GH( f ). The following theorem, proved in [17], provides us with a general way
of transforming space-efficient algorithms into garden-hose protocols.
Theorem C.1. [17, Theorem 2.12] If f : {0, 1}n × {0, 1}n → {0, 1} is log-space computable, then GH( f )
is polynomial in n.
Since the garden-hose complexity is defined in a non-uniform way, the strategies of the players are
not necessarily easily computable. However, by inspection of the original proof, we see that the players
effectively have to list all configurations for the Turing machine for f , and connect them according to the
machine’s transition function. For a log-space decryption function HE.Dec, a player therefore only has to
perform a polynomial-time computation to determine the strategy for a specific input.
The general construction is a direct consequence of the following lemma,10 which was recently
derived in the context of instantaneous non-local quantum computation.
Lemma C.2. [53, Lemma 8, paraphrased] Assume Bob has a single qubit with state P f (x,y) |ψi, for binary
strings x, y ∈ {0, 1}n , where Alice knows the string x and Bob knows y. Let GH( f ) be the garden-hose
complexity of the function f . Then the following holds:

1. There exists an instantaneous protocol without any communication which uses 2GH( f ) pre-shared
EPR pairs after which a known qubit of Bob is in the state Xg(x̂,ŷ) Yh(x̂,ŷ) |ψi. Here x̂ depends only
on x and the measurement outcomes of Alice, and ŷ depends on y and the measurement outcomes
of Bob.

2. The garden-hose complexities of the functions g and h are at most linear in the complexity of the
function f .
10 The names of Alice and Bob have been swapped in order to fit the framework of this paper.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 35
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

Bob Alice

c sk
0 1 0 1
in

Figure 5: Garden-hose protocol for TOY.Dec. The snaky lines represent the EPR-pairs that form the
resources to the protocol. The bended lines represent Bell measurements that Bob and Alice perform
dependent on their inputs. For example, if c = 0 and sk = 0, the qubit starting at “in” is teleported through
the first EPR-pair by Bob, then back through the third EPR-pair by Alice. It comes out on the bottom
location on Bob’s side.

For our purposes, only the first part of this result is required. The construction used in this lemma is a
direct application of the garden-hose model [17], together with a simplifying step which was inspired
by results on the garden-hose model by Klauck and Podder [38]. In our case, the function f will be the
decryption function HE.Dec where Alice holds sk, and Bob holds ae.

C.1 Toy example
The garden-hose protocols that correspond to actual decryption functions will quickly become complicated
in their description. Therefore, as an illustrative example, we will explicitly show how to convert a
garden-hose protocol for the decryption function of a toy classical scheme TOY to a gadget. We do not
claim TOY to be homomorphic at all; we only define its very simple decryption function and leave the
rest of the scheme undefined.
Consider the following definition of TOY.Dec on ciphertext c and key sk of a single bit:

TOY.Decsk (c) = sk ⊕ c .

In Figure 5, a garden-hose protocol [17] for TOY.Dec is shown. For the protocol, Alice and Bob share
three EPR-pairs which they use to teleport some qubit through, in a way that depends only on their own
inputs c (for Bob) and sk (for Alice). The qubit always starts in the location marked “in.” After the
execution of the protocol, the qubit |ψi should end up on Bob’s side whenever TOY.Decsk (c) = 0, and
on Alice’s side otherwise. For this small function, correctness is easily verified to hold for all possible
inputs.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 36
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

Bob Alice

c sk
0 1 0 1
in

P†

out

Figure 6: Removal of a possible P error using two copies of the garden-hose protocol for TOY.Dec. For
example, if c = 0 and sk = 1, the qubit is teleported through EPR pairs 1 and 4, with a P† applied to it by
Alice in between. The input qubit always ends up on position “out.”

The garden-hose complexity GH(TOY.Dec) is the minimum amount of EPR-pairs needed for the
computation of TOY.Dec in this way. See also [17].
Suppose that Bob teleports some qubit Pa Xa Zb |ψi through the protocol, and sets his input c to be
ae. Then whenever a = TOY.Decsk (e a) = 1, the qubit will come out on Alice’s side, and we will want
†
to apply the correction P . To make sure that the correction is applied to Pa Xa Zb |ψi, Alice can apply
a P† gate on all possible locations of the qubit. However, after this step, Alice and Bob do not know
the location of the qubit, unless they share their inputs with one another non-homomorphically. The
construction from [53, Lemma 8] solves this problem by applying the entire garden-hose protocol again
in reverse: every EPR-half on which no measurement is performed, is connected through measurement
with the EPR-half at the same position in the second copy of the protocol. That way, the (corrected) qubit
follows the same path backwards, and always ends up on Bob’s side at the “in” position of the second
protocol (marked “out” in Figure 6).
After the execution of the protocol, the potential P error on the qubit Pa Xa Zb |ψi has been removed,
but additional Pauli transformations also have occurred as a result of the teleportations. The exact
transformations depend on both the path the qubit has taken and the measurement outcomes of Alice and

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 37
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

sk = 0 sk = 1

P†

Figure 7: The two possible gadgets Γ(sk) that TP.GenGadget might generate for TOY.Dec. Effectively,
a gadget consists of 2GH(TOY.Dec) EPR-pairs, ordered in a way that depends on sk. Some EPR-pairs
have an additional (P† ⊗ I) transformation applied to them. The evaluator’s input c determines whether or
not the input qubit is teleported through such a transformation, but an evaluator is unable to tell whether
it is.

Bob. Therefore, Alice has to send all of this information (homomorphically encrypted) to Bob, so that he
0 0
can update his keys to reflect the new state Xa Zb |ψi of the qubit.
Since the order of the Bell measurements does not influence the outcome of the protocol, Alice can
perform her part of the protocol already during the key-generation phase. She starts by generating enough
EPR-pairs for the gadget (six in this example), and performs the measurement on her own halves of the
EPR-pairs. Effectively, this action generates six qubits that are entangled in some way that depends on sk
(see Figure 7). Because of the random Pauli’s that arise from the Bell measurements, Bob is not able to
tell which pairs are connected without knowing Alice’s measurement outcomes. To him, the state of the
gadget is completely mixed (see equation (4.1)).

References
[1] S COTT A ARONSON , A LEXANDRU C OJOCARU , A LEXANDRU G HEORGHIU , AND E LHAM
K ASHEFI: On the implausibility of classical client blind quantum computing, 2017.
[arXiv:1704.08482] 4

[2] D ORIT A HARONOV, M ICHAEL B EN -O R , AND E LAD E BAN: Interactive proofs for quantum
computations. In Proc. 1st Innovations in Computer Science Conf. (ICS’10), pp. 453–469, 2010.
[arXiv:1704.04487] 5

[3] G ORJAN A LAGIC , A NNE B ROADBENT, B ILL F EFFERMAN , T OMMASO G AGLIARDONI , C HRIS -
TIAN S CHAFFNER , AND M ICHAEL S T. J ULES: Computational security of quantum encryption. In

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 38
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

Proc. 9th Internat. Conf. on Information Theoretic Security (ICITS’16), pp. 47–71. Springer, 2016.
[doi:10.1007/978-3-319-49175-2_3, arXiv:1602.01441] 10

[4] G ORJAN A LAGIC AND B ILL F EFFERMAN: On quantum obfuscation, 2016. [arXiv:1602.01771] 29

[5] PABLO A RRIGHI AND L OUIS S ALVAIL: Blind quantum computation. Internat. J. Quantum
Information, 4(5):883–898, 2006. [doi:10.1142/S0219749906002171, arXiv:quant-ph/0309152] 5

[6] G ILAD A SHAROV, A BHISHEK JAIN , A DRIANA L ÓPEZ -A LT, E RAN T ROMER , V INOD VAIKUN -
TANATHAN , AND DANIEL W ICHS: Multiparty computation with low communication, computation
and interaction via threshold FHE. In Proc. 31st Internat. Conf. on the Theory and Applications of
Cryptographic Techniques (EUROCRYPT’12), pp. 483–501. Springer, 2012. Cryptology Archive.
[doi:10.1007/978-3-642-29011-4_29] 4

[7] DAVID A. BARRINGTON: Bounded-width polynomial-size branching programs recognize exactly
those languages in NC1 . J. Comput. System Sci., 38(1):150–164, 1989. Preliminary version in
STOC’86. [doi:10.1016/0022-0000(89)90037-8] 22

[8] Ä MIN BAUMELER AND A NNE B ROADBENT: Quantum private information retrieval has linear
communication complexity. Journal of Cryptology, 28(1):161–175, 2015. [doi:10.1007/s00145-
014-9180-2, arXiv:1304.5490] 21

[9] M ICHAEL B EN -O R , C LAUDE C RÉPEAU , DANIEL G OTTESMAN , AVINATAN H ASSIDIM , AND
A DAM S MITH: Secure multiparty quantum computation with (only) a strict honest majority. In
Proc. 47th FOCS, pp. 249–260. IEEE Comp. Soc. Press, 2006. [doi:10.1109/FOCS.2006.68,
arXiv:0801.1544] 4

[10] DAN B ONEH , E U -J IN G OH , AND KOBBI N ISSIM: Evaluating 2-DNF formulas on ciphertexts. In
Proc. 2nd Theory of Cryptography Conf. (TCC’05), pp. 325–341. Springer, 2005. [doi:10.1007/978-
3-540-30576-7_18] 2, 4

[11] Z VIKA B RAKERSKI , C RAIG G ENTRY, AND V INOD VAIKUNTANATHAN: (Leveled) fully homo-
morphic encryption without bootstrapping. ACM Trans. Comput. Theory, 6(3):13:1–13:36, 2014.
Preliminary version in ITCS’12. Cryptology Archive. [doi:10.1145/2633600] 4

[12] Z VIKA B RAKERSKI AND V INOD VAIKUNTANATHAN: Efficient fully homomorphic encryption
from (standard) LWE. SIAM J. Comput., 43(2):831–871, 2014. Preliminary version in FOCS’11.
Cryptology Archive. [doi:10.1137/120868669] 2, 3, 4, 7, 25, 26

[13] A NNE B ROADBENT: Delegating private quantum computations. Canadian Journal of Physics,
93(9):941–946, 2015. [doi:10.1139/cjp-2015-0030, arXiv:1506.01328] 5

[14] A NNE B ROADBENT: Popescu-Rohrlich correlations imply efficient instantaneous nonlocal quan-
tum computation. Phys. Rev. A, 94(2):022318, 2016. [doi:10.1103/PhysRevA.94.022318,
arXiv:1512.04930] 11

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 39
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

[15] A NNE B ROADBENT, J OSEPH F ITZSIMONS , AND E LHAM K ASHEFI: Universal blind quan-
tum computation. In Proc. 50th FOCS, pp. 517–526. IEEE Comp. Soc. Press, 2009.
[doi:10.1109/FOCS.2009.36, arXiv:0807.4154] 5, 28
[16] A NNE B ROADBENT AND S TACEY J EFFERY: Quantum homomorphic encryption for circuits of
low T-gate complexity. In Proc. 35th Ann. Internat. Cryptology Conf. (CRYPTO’15), pp. 609–629.
Springer, 2015. [doi:10.1007/978-3-662-48000-7_30, arXiv:1412.8766] 2, 3, 5, 6, 7, 9, 10, 11, 16,
18, 20
[17] H ARRY B UHRMAN , S ERGE F EHR , C HRISTIAN S CHAFFNER , AND F LORIAN S PEELMAN: The
garden-hose model. In Proc. 4th Innovations in Theoretical Computer Science Conf. (ITCS’13), pp.
145–158. ACM Press, 2013. [doi:10.1145/2422436.2422455, arXiv:1109.2563] 3, 11, 21, 27, 28,
35, 36, 37
[18] A NDREW M. C HILDS: Secure assisted quantum computation. Quantum Inf. Comput., 5(6):456–466,
2005. ACM DL link. [arXiv:quant-ph/0111046] 5
[19] W ELL Y. C HIU , M ARIO S ZEGEDY, C HENGU WANG , AND Y IXIN X U: The garden hose complexity
for the equality function. In Proc. 10th Internat. Conf. on Algorithmic Aspects in Information
and Management (AAIM’14), pp. 112–123. Springer, 2014. [doi:10.1007/978-3-319-07956-1_11,
arXiv:1312.7222] 26
[20] B ENNY C HOR , E YAL K USHILEVITZ , O DED G OLDREICH , AND M ADHU S UDAN: Private
information retrieval. J. ACM, 45(6):965–981, 1998. Preliminary version in FOCS’95.
[doi:10.1145/293347.293350] 5
[21] RONALD C RAMER , I VAN DAMGÅRD , AND J ESPER B UUS N IELSEN: Multiparty computation from
threshold homomorphic encryption. In Proc. 20th Internat. Conf. on the Theory and Applications of
Cryptographic Techniques (EUROCRYPT’01), pp. 280–299. Springer, 2001. Cryptology Archive.
[doi:10.1007/3-540-44987-6_18] 29
[22] Y FKE D ULEK , C HRISTIAN S CHAFFNER , AND F LORIAN S PEELMAN: Quantum homomorphic en-
cryption for polynomial-sized circuits. In Proc. 36th Ann. Internat. Cryptology Conf. (CRYPTO’16),
pp. 3–32. Springer, 2016. [doi:10.1007/978-3-662-53015-3_1, arXiv:1603.09717] 1
[23] F RÉDÉRIC D UPUIS , J ESPER B UUS N IELSEN , AND L OUIS S ALVAIL: Secure two-party quan-
tum evaluation of unitaries against specious adversaries. In Proc. 30th Ann. Internat. Cryptol-
ogy Conf. (CRYPTO’10), pp. 685–706. Springer, 2010. [doi:10.1007/978-3-642-14623-7_37,
arXiv:1009.2096] 21
[24] M AXIMILIAN F ILLINGER: Lattice based cryptography and fully homomorphic encryption, 2012.
Available here. 5
[25] K ENT A. G. F ISHER , A NNE B ROADBENT, LYNDEN K. S HALM , Z HENYA YAN , J ONATHAN
L AVOIE , ROBERT P REVEDEL , T HOMAS J ENNEWEIN , AND K EVIN J. R ESCH: Quantum com-
puting on encrypted data. Nature Communications, 5(3074), 2014. [doi:10.1038/ncomms4074,
arXiv:1309.2586] 5

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 40
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

[26] J OSEPH F. F ITZSIMONS: Private quantum computation: An introduction to blind quantum comput-
ing and related protocols. npj Quantum Information, 3(23), 2017. [doi:10.1038/s41534-017-0025-3,
arXiv:1611.10107] 28

[27] T OMMASO G AGLIARDONI , A NDREAS H ÜLSING , AND C HRISTIAN S CHAFFNER: Semantic
security and indistinguishability in the quantum world. In Proc. 36th Ann. Internat. Cryptology Conf.
(CRYPTO’16), pp. 60–89. Springer, 2016. [doi:10.1007/978-3-662-53015-3_3, arXiv:1504.05255]
10

[28] S HELLY G ARG , C RAIG G ENTRY, S HAI H ALEVI , M ARIANA R AYKOVA , A NANT S AHAI , AND
B RENT WATERS: Candidate indistinguishability obfuscation and functional encryption for all
circuits. SIAM J. Comput., 45(3):882–929, 2016. Preliminary version in FOCS’13. Cryptology
Archive. [doi:10.1137/14095772X] 2

[29] C RAIG G ENTRY: Fully homomorphic encryption using ideal lattices. In Proc. 41st STOC, pp.
169–178. ACM Press, 2009. [doi:10.1145/1536414.1536440] 2, 4

[30] C RAIG G ENTRY, S HAI H ALEVI , AND V INOD VAIKUNTANATHAN: A simple BGN-type cryptosys-
tem from LWE. In Proc. 29th Internat. Conf. on the Theory and Applications of Cryptographic
Techniques (EUROCRYPT’10), pp. 506–522. Springer, 2010. Cryptology Archive. [doi:10.1007/978-
3-642-13190-5_26] 4

[31] S HAFI G OLDWASSER , YAEL K ALAI , R ALUCA A DA P OPA , V INOD VAIKUNTANATHAN , AND
N ICKOLAI Z ELDOVICH: How to run Turing machines on encrypted data. In Proc. 33rd Ann.
Internat. Cryptology Conf. (CRYPTO’13), pp. 536–553. Springer, 2013. [doi:10.1007/978-3-642-
40084-1_30] 2

[32] S HAFI G OLDWASSER , YAEL K ALAI , R ALUCA A DA P OPA , V INOD VAIKUNTANATHAN , AND
N ICKOLAI Z ELDOVICH: Reusable garbled circuits and succinct functional encryption. In Proc.
45th STOC, pp. 555–564. ACM Press, 2013. Cryptology Archive. [doi:10.1145/2488608.2488678]
2

[33] S HAFI G OLDWASSER AND S ILVIO M ICALI: Probabilistic encryption. J. Comput. System Sci.,
28(2):270–299, 1984. [doi:10.1016/0022-0000(84)90070-9] 2, 4

[34] S ERGEY G ORBUNOV, V INOD VAIKUNTANATHAN , AND H OETECK W EE: Attribute-based encryp-
tion for circuits. J. ACM, 62(6):45:1–45:33, 2015. Preliminary version in STOC’13. Cryptology
Archive. [doi:10.1145/2824233] 2

[35] DANIEL G OTTESMAN: Theory of fault-tolerant quantum computation. Phys. Rev. A, 57(1):127–137,
1998. [doi:10.1103/PhysRevA.57.127, arXiv:quant-ph/9702029] 6

[36] DANIEL G OTTESMAN AND I SAAC L. C HUANG: Quantum Teleportation is a Universal Compu-
tational Primitive. Nature, 402:390–393, 1999. [doi:10.1038/46503, arXiv:quant-ph/9908010]
3

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 41
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

[37] Y UVAL I SHAI AND A NAT PASKIN: Evaluating branching programs on encrypted data. In Proc.
4th Theory of Cryptography Conf. (TCC’07), pp. 575–594. Springer, 2007. Cryptology Archive.
[doi:10.1007/978-3-540-70936-7_31] 2, 30

[38] H ARTMUT K LAUCK AND S UPARTHA P ODDER: New bounds for the garden-hose model.
In Proc. 34th IARCS Ann. Conf. on Foundations of Software Tech. and Theor. Comput.
Sci. (FSTTCS’14), pp. 481–492. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2014.
[doi:10.4230/LIPIcs.FSTTCS.2014.481, arXiv:1412.4904] 26, 27, 36

[39] E YAL K USHILEVITZ AND R AFAIL O STROVSKY: Replication is not needed: Single database,
computationally-private information retrieval. In Proc. 38th FOCS, pp. 364–373. IEEE Comp. Soc.
Press, 1997. [doi:10.1109/SFCS.1997.646125] 4

[40] M IN L IANG: Symmetric quantum fully homomorphic encryption with perfect security. Quan-
tum Information Processing, 12(12):3675–3687, 2013. [doi:10.1007/s11128-013-0626-5,
arXiv:1304.5087] 5

[41] M IN L IANG: Quantum fully homomorphic encryption scheme based on universal quantum circuit.
Quantum Information Processing, 14(8):2749–2759, 2015. [doi:10.1007/s11128-015-1034-9,
arXiv:1410.2435] 5

[42] O DED M ARGALIT: On the riddle of coding equality function in the garden hose model. In Proc.
2014Information Theory and Applications Workshop (ITA’14), pp. 1–5. IEEE Comp. Soc. Press,
2014. [doi:10.1109/ITA.2014.6804262] 26

[43] M ICHAEL N IELSEN AND I SAAC C HUANG: Quantum Computation and Quantum Information.
Cambridge University Press, 2000. 6

[44] Y INGKAI O UYANG , S I -H UI TAN , AND J OSEPH F ITZSIMONS: Quantum homomorphic encryption
from quantum codes, 2015. [arXiv:1508.00938] 5

[45] PASCAL PAILLIER: Public-key cryptosystems based on composite degree residuosity classes. In
Proc. 18th Internat. Conf. on the Theory and Applications of Cryptographic Techniques (EURO-
CRYPT’99), pp. 223–238. Springer, 1999. [doi:10.1007/3-540-48910-X_16] 2, 4

[46] RONALD L. R IVEST, L EN A DLEMAN , AND M ICHAEL L. D ERTOUZOS: On data banks and privacy
homomorphisms. Foundations of Secure Computation, 4(11):169–180, 1978. LINK. 2

[47] RONALD L. R IVEST, A DI S HAMIR , AND L EN A DLEMAN: A method for obtaining
digital signatures and public-key cryptosystems. Comm. ACM, 21(2):120–126, 1978.
[doi:10.1145/359340.359342] 4

[48] P ETER P. ROHDE , J OSEPH F. F ITZSIMONS , AND A LEXEI G ILCHRIST: Quantum walks with
encrypted data. Phys. Rev. Lett., 109(15):150501, 2012. [doi:10.1103/PhysRevLett.109.150501,
arXiv:1204.3370] 5

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 42
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

[49] A MIT S AHAI AND B RENT WATERS: How to use indistinguishability obfuscation: Deniable
encryption, and more. In Proc. 46th STOC, pp. 475–484. ACM Press, 2014. Cryptology Archive.
[doi:10.1145/2591796.2591825] 2

[50] T OMAS S ANDER , A DAM YOUNG , AND M OTI Y UNG: Non-interactive cryptocomputing for NC1 . In
Proc. 40th FOCS, pp. 554–566. IEEE Comp. Soc. Press, 1999. [doi:10.1109/SFFCS.1999.814630]
4

[51] DAN S HEPHERD AND M ICHAEL J. B REMNER: Temporally unstructured quantum computation.
Proc. Royal Soc. A, 465(2105):1413–1439, 2009. [doi:10.1098/rspa.2008.0443] 3

[52] F LORIAN S PEELMAN: Position-Based Quantum Cryptography and the Garden-Hose Game. Mas-
ter’s thesis, University of Amsterdam, 2011. [arXiv:1210.4353] 27

[53] F LORIAN S PEELMAN: Instantaneous non-local computation of low T -depth quantum circuits. In
Proc. 11th Conf. Theory of Quantum Comput., Communic. and Cryptography (TQC’16), pp. 9:1–
9:24. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.TQC.2016.9,
arXiv:1511.02839] 3, 11, 28, 35, 37

[54] S I -H UI TAN , J OSHUA A. K ETTLEWELL , Y INGKAI O UYANG , L IN C HEN , AND J OSEPH F.
F ITZSIMONS: A quantum approach to homomorphic encryption. Scientific Reports, 6, 2016.
[doi:10.1038/srep33467, arXiv:1411.5254] 5

[55] V INOD VAIKUNTANATHAN: Computing blindfolded: New developments in fully homo-
morphic encryption. In Proc. 52nd FOCS, pp. 5–16. IEEE Comp. Soc. Press, 2011.
[doi:10.1109/FOCS.2011.98] 8

[56] M ARTEN VAN D IJK , C RAIG G ENTRY, S HAI H ALEVI , AND V INOD VAIKUNTANATHAN: Fully
homomorphic encryption over the integers. In Proc. 29th Internat. Conf. on the Theory and
Applications of Cryptographic Techniques (EUROCRYPT’10), volume 6110, pp. 24–43. Springer,
2010. Cryptology Archive. [doi:10.1007/978-3-642-13190-5_2] 2

[57] D UNJKO V EDRAN , J OSEPH F. F ITZSIMONS , C HRISTOPHER P ORTMANN , AND R ENATO R ENNER:
Composable security of delegated quantum computation. In Proc. 20th Internat. Conf. on the Theory
and Application of Cryptology and Information Security (ASIACRYPT’14), pp. 406–425. Springer,
2014. [doi:10.1007/978-3-662-45608-8_22, arXiv:1301.3662] 5

[58] L I Y U , C ARLOS A. P ÉREZ -D ELGADO , AND J OSEPH F. F ITZSIMONS: Limitations on
information-theoretically secure quantum homomorphic encryption. Phys. Rev. A, 90(5), 2014.
[doi:10.1103/PhysRevA.90.050303, arXiv:1406.2456] 5, 28

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 43
Y FKE D ULEK , F LORIAN S PEELMAN , AND C HRISTIAN S CHAFFNER

AUTHORS

Yfke Dulek
Ph. D. student
Centrum voor Wiskunde en Informatica, and
University of Amsterdam
The Netherlands
dulek cwi nl
https://www.cwi.nl/people/yfke-dulek

Christian Schaffner
Assistant professor
Centrum voor Wiskunde en Informatica, and
University of Amsterdam
The Netherlands
c.schaffner uva nl
http://homepages.cwi.nl/~schaffne

Florian Speelman
Postdoc
University of Copenhagen, Denmark
speelman math ku dk
http://www.florianspeelman.nl

ABOUT THE AUTHORS

Y FKE D ULEK is a Ph. D. student at the Centrum voor Wiskunde en Informatica and the
Institute for Logic, Language and Computation (University of Amsterdam), under the
supervision of Christian Schaffner. There, she is also part of the research center QuSoft,
where she works on quantum cryptography under computational assumptions, and in
particular, quantum computing on encrypted data. She holds a B. Sc. in Artificial
Intelligence from Utrecht University (2013) and a M. Sc. in Logic from the University of
Amsterdam (2016).

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 44
Q UANTUM H OMOMORPHIC E NCRYPTION FOR P OLYNOMIAL -S IZE C IRCUITS

C HRISTIAN S CHAFFNER received a diploma in mathematics from ETH Zurich (Switzerland)
in 2003 and a Ph. D. in computer science from Aarhus University (Denmark) in 2007
under the supervision of Louis Salvail and Ivan Damgård. He is currently an Assistant
Professor of Theoretical Computer Science at the Institute for Logic, Language and
Computation (ILLC) at the University of Amsterdam. He is also a senior researcher at
QuSoft, the Dutch research center for quantum software. Christian’s research interests
include quantum cryptography, cryptographic protocols, and (quantum) information
theory.

F LORIAN S PEELMAN performed his Ph. D. research at the Centrum voor Wiskunde en
Informatica in Amsterdam, under the supervision of Harry Buhrman, receiving his degree
in 2016. He also holds a B. Sc. in Physics and a M. Sc. in Computational Science from
the University of Amsterdam. Florian’s research interests include quantum cryptography,
computational complexity theory, and communication complexity. He is currently a
postdoctoral researcher at QMATH, the Centre for the Mathematics of Quantum Theory,
at the University of Copenhagen.

T HEORY OF C OMPUTING, Volume 14 (7), 2018, pp. 1–45 45