In order for the client not to learn anything about the computation, one must "hide" the quantum state one sends to the server. This is done via a Quantum One-Time Pad:
$$\newcommand\ket[1]{\left|#1\right\rangle}\ket{\psi}\to Z^zX^x\ket{\psi}$$
where $Z$ and $X$ are the corresponding Pauli gates, and $z$ and $x$ are classical bitstrings. For instance, if the $i$-th bit of $z$ is equal to $1$, we apply a $Z$ gate on the state. Otherwise we don't.
It's a well-known result that if you don't know $x$ and $z$ and have access to a single copy of the state, you don't have any information about it (this is just like the classical one-time pad). So, we know that if the server has access to such a state it can't deduce any information from it.
Now, the difficulty of Homomorphic encryption is to perform computation on encrypted data. That, we want the server to be able to prepare $Z^{z'}X^{x'}U\ket{\psi}$ while being given $Z^zX^x\ket{\psi}$ where $z'$ and $x'$ are known by the user but not by the server, and where $U$ is a unitary gate.
For instance, let us say that we want the server to apply a $Z$ gate on the state we send. We first send the server:
$$Z^zX^x\ket{\psi}$$
The server applies a $Z$ gate and send back the state:
$$Z^{z'}X^x\ket{\psi}$$
with $z'$ being equal to $z$ except on the qubit where the $Z$ gate has been applied. The client can then apply $Z^zX^x$ to end up with $Z\ket{\psi}$.
Of course, this is not a very interesting scenario: if the user is able to implement $X$ and $Z$ gate, there is no point asking the server to perform them. The logic here is that we would want to be able to perform this task but for arbitrary (potentially "hard") unitaries.
The good news is, we are only interested in a limited amount of gates. If we can show that we can perform this type of operation for a universal set of gates, then we know that we'll be able to do it for any unitary. The author then uses the fact that the Clifford gates along with the Toffoli gate form a universal set of gates. So, to put it in a nutshell, if the server is able to implement Clifford gates and the Toffoli gate, then we can perform any computation we'd like.
Clifford gates are easy enough. Let us say that the client wants to implement a Clifford gate $C$, so that it is able to recover $C\ket{\psi}$ at the end of the computation. By definition of the Clifford group, we have that:
$$CZ^zX^xC^\dagger=Z^{z'}X^{x'}$$
for some known $z'$ and $x'$, assuming $z$ and $x$ are known (note that the equality holds up to a global phase here). So if the server owns the state:
$$Z^zX^x\ket{\psi}$$
and applies a $C$ gate on it, the state becomes:
$$CZ^zX^x\ket{\psi}=Z^{z'}X^{x'}C\ket{\psi}$$
The last important point here is that the server also owns $\text{Enc}(x)$ and $\text{Enc}(z)$ and is able to compute $\text{Enc}(x')$ and $\text{Enc}(z')$ from them, since $\text{Enc}$ is a classical homomorphic scheme (which we assume has such a property).
Applying the Toffoli gate is a bit more involved, since we can't use the same trick. What the authors show in subsection 3.3.2 equation 32 is that if you know how to apply CNOT gates in a homomorphic way, then you are able to implement Toffoli gates in a homomorphic way.
So, to put it in a nutshell and to answer your questions:
- Since we know how to implement the Clifford gates and the Toffoli one, we can perform any operation we'd like. However, it will at least take $3$ qubits, even if we wish only to perform a single-qubit rotation. The $2$ additional qubits will be used as ancillas and will return to the state $\ket{0}$ after the computation.
- Yes, there is no need for a communication between the server and the client after each gate. The client can directly send the whole circuit to the server.
There's something one must be careful about though, which is the very first operation. If the computation starts from a state that is known to the server, it can learn the Pauli twirling, or even directly performs the computation by itself to get the desired state.
Thus, this must be thought as if the server wanted to compute a function $f(x)$. The client will tell the server to create the state $\left|x'\right\rangle=X^{x\oplus x'}|x\rangle$ and send the server $\text{Enc}\left(x\oplus x'\right)$. This is essentially a One-Time Pad, which means that the server has no information whatsoever (computationally speaking at least, since they have access to $\text{Enc}\left(x\oplus x'\right)$) on $x$.
Thanks to squiggles for correcting me about this crucial last point!
To put it in a nutshell, here's how the protocol goes in its entirety, assuming the client wants to compute $f(x)$.
- The client samples a random string $x'$ and tells the server to prepare the state $\left|x'\right\rangle$. The client also sends $\text{Enc}\left(x\oplus x'\right)$ to the server as its Pauli $X$-twirl. The Pauli $Z$-twirl is set to $0$.
- If the client wants the server to apply a Clifford gate, the server can do so by applying said gate on the current state and updating the Pauli $X$ and $Z$-twirl accordingly.
- If the client wants the server to apply a Toffoli gate, the server can also do so by the scheme presented in the paper, without the server needing to know the initial $X$ and $Z$ twirl. Once again, the server can update those twirls accordingly.
- At the end of the computation, the server ends up with the basis state $X^y|f(x)\rangle=|f(x)\oplus y\rangle$ and the classical data $\text{Enc}(y)$. It sends both $f(x)\oplus y$ and $\text{Enc}(y)$ to the client which is thus able to recover $f(x)$.
