# Fully Homomorphic Encryption over the Integers - Runtime Question

I have a question regarding the paper "Fully Homomorphic Encryption over the Integers" (http://eprint.iacr.org/2009/616.pdf): On page 6 after they set their parameters, it says

"This setting results in a scheme with complexity $\overset{\sim}{\mathcal{O}}(λ^{10}).$"

What exactly do they mean by this? That the runtime is $\overset{\sim}{\mathcal{O}}(λ^{10})$? If yes, the runtime of what exactly - performing a multiplication on encrypted data? After all, the overall runtime of the scheme depends on the depth of the circuit that is being evaluated, so such a generic bound on runtime of the whole scheme would not make much sense, would it?

My second question (which assumes that "complexity" refers to runtime) is the following: In section 5 (page 13), the authors present an attack which has running time $2^{2\rho}$, where $\rho = \omega(\log(\lambda))$. Wouldn't that make the attack in general much faster than the runtime of the scheme? On page 6, it says that "A convenient parameter set to keep in mind is $\rho = \lambda,$ [...]", in which case I understand why we do not need to worry about the attack, as it runs exponential in $\lambda$. But is it really enough to require $\rho = \omega(\log(\lambda))$ in general, or wouldn't values of $\rho$ that are very close to $\log(\lambda)$ make this scheme extremely unsafe? Also, does $\overset{\sim}{\mathcal{O}}(λ)$ mean linear in the bitlength of $\lambda$, whereas $2^{2\rho}$ refers to the actual numerical value of $\rho$?

I looked at runtime tables here: http://eprint.iacr.org/2011/440.pdf (where both the scheme and the attack have been slightly modified) and the scheme is way faster than the attack, even though they chose $\rho$ smaller than $\lambda$. Although not logarithmically smaller, I actually have no idea how they derived $\rho$ from $\lambda$.

So am I missing something, or is everyone just using $\rho \approx \lambda$ and the bound $\rho = \omega(\log(\lambda))$ is not safe?

# On the first question

The public key of DGHV's SHE scheme consists of $\tau+1$ $\gamma$-bit numbers, that is, $pk = (x_0,\dots,x_\tau)$, where $x_i$ is chosen from the distribution $\mathcal{D}_{\gamma,\rho}(p)$ over $[0,2^{\gamma})$. Therefore, the length of $pk$ is $O(\tau \gamma)$, which is $\tilde{O}(\lambda^{10})$ if we adopt the parameters $\gamma = \tilde{O}(\lambda^5)$ and $\tau = \gamma + \lambda$ as the authors said.

In order to encrypt a bit $m$, we sample a random subset $S$ and a "relatively small" integer $r$, and compute $c = m + 2r + 2 \sum_{i \in S} x_i \bmod{x_0}$. Here, we have to read the whole of the public key and the main task is adding $x_i$ randomly. Hence, the complexity of encryption is $\tilde{O}(\lambda^{10})$, which is the result of $\tau$-time addition of $\gamma$-bit integers.

In order to multiply two fresh ciphertexts, which are $\gamma$-bit integers, we require about $O(\gamma^2)$ bit operations. (By using more sophisticated multiplication, it is reduced to $\tilde{O}(\gamma)$.)

As you said, the time of evaluating a circuit and encrypted data mainly depends on the depth of the circuit. Getting worse, we are often required to adopt the FHE scheme and "refresh" intermediate ciphertexts.

# On the second question

As an example, we take $\rho = \log^{2}(\lambda)$. This results in $2^{2\rho} = \lambda^{2 \log(\lambda)}$, which is asymptotically greater than any polynomial of $\lambda$. Hence, asymptotically speaking, the attack is not faster than the runtime of the scheme. As you thought, if we take $\rho$ is very close to $\log(\lambda)$, the scheme is unsafe for small $\lambda$.