Fully Homomorphic Encryption over the Integers - Runtime Question

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?

Answer 1

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$.