Key Size for Symmetric Homomorphic Encryption Over the Integers

Question

In the paper Fully Homomorphic Encryption over the Integers, it mentions a symmetric key scheme on page 1 and 2.

Key Generation: Pick a random odd number $p \epsilon [2^{N-1},2^N)$
Encrypt A Bit m: $c = pq + 2r + m$
Decrypt A Bit c: $m = (c \% p) \% 2$
Homomorphic XOR: $result = c + c'$
Homomorphic AND: $result = c * c'$

Note that when encrypting a bit, $q$ is a random number to help hide the key, and $r$ is a small noise value to turn breaking the encryption into a "learning with error" problem. $N$ is effectively the number of bits in the key.

In the second to last paragraph on page 1, the paper suggests these values to make the above secure:
$r ≈ 2√N$
$q ≈ 2N^3$

However, the font used is rather unfortunate and I can't tell if the paper means the way i wrote it above, or the way I wrote it below:
$r ≈ 2^{√N}$
$q ≈ 2^{N^3}$

Is anyone able to understand which way it should be? Also, I'm kind of curious where these specific values for security came from, if anyone is able to shed light on that.

Edit:

Later in the paper, on page 5, it talks about how to calculate some parameters for the public key implementation:

γ is the bit-length of the integers in the public key
η is the bit-length of the secret key (which is the hidden approximate-gcd of all the public-key integers),
ρ is the bit-length of the noise (i.e., the distance between the public key elements and the nearest multiples of the secret key), and
τ is the number of integers in the public key

These parameters must be set under the following constraints:

• ρ = ω(log λ), to protect against brute-force attacks on the noise;
• η ≥ ρ · Θ(λ log^2 λ), in order to support homomorphism for deep enough circuits to evaluate the “squashed decryption circuit” (cf. Sections 3.2 and 6.2);
• γ = ω(η^2 log λ), to thwart various lattice-based attacks on the underlying approximate-gcd problem (cf. Section 5);
• τ ≥ γ + ω(log λ), in order to use the leftover hash lemma in the reduction to approximate gcd (cf. Lemma 4.3).

We also use a secondary noise parameter ρ′ = ρ + ω(log λ). A convenient parameter set to keep in mind is ρ = λ, ρ′ = 2λ, η = O˜(λ^2), γ = O˜(λ^5) and τ = γ + λ. (This setting results in a scheme with complexity O˜(λ^10).)

It never explains what ω is. Is that some commonly known notation? How did the "convenient parameter set" come from those formulas?

Also, what exactly does it mean when they say that using that parameter set results in a scheme with complexity O˜(λ^10)? Does that mean that the attack against the encryption has that for complexity? I'm wondering about the case where maybe increased speed is desired, even at the cost of decreased security, to understand what to change to get those results.

Answer 1

-- Introduction

First of all, I know that you are trying to have a better understanding about the symmetric scheme, but, since the authors focused on the public key scheme, you will have to understand the choice of parameters of this one to understand the choice of parameters for the symmetric scheme.

When we say that a scheme is secure, it means that we know how much effort an attacker needs to do to break such scheme. So, we try to quantify this effort as a function of a security parameter $\lambda$ and we choose a value for $\lambda$ that makes an attack impractical.

But, to be able to quantify this effort, we need to know how an attacker may attack our scheme. And this is how the authors got these values for the parameters: they analysed the known attacks (section 5 and appendix B) and found out what is the effort an attacker must to do in each attack. But they did it only for the public key scheme...

-- Choice of parameters for the symmetric scheme

The authors say that we have to choose $ r \approx 2^\sqrt{\eta}$ and $q \approx 2^{\eta^3}$.

Let's start by the $q$: At the end of section 5, it says that using the Lagarias' algorithm for simultaneous Diophantine approximation, an attacker can recover the private key $p$ from the public key in time $2^{\frac{\gamma}{\eta^2}}$ (this is "quantify the effort").

Note that if $\gamma = \eta^3$, then $2^{\frac{\gamma}{\eta^2}} = 2^\eta $, so, if we set $\gamma = \eta^3$, this attack will take time $2^\eta$. Since $\gamma$ is the number of bits of $q$, it means that we have to choose $q \approx 2^{\eta^3}$.

Now, let's analyse the case of $r$: Again, in the section 5, the authors conclude that the known attacks on the noise can recover the private key $p$ in time $2^{2\rho}$ or $2^{\rho + \sqrt{\eta}}$. If we choose $\rho = \sqrt{\eta}$, the time complexity for this attack is about $2^{2 \cdot\sqrt{\eta}}$. Since $\rho$ is the number of bits of $r$, it means we will have $ r \approx 2^\sqrt{\eta}$.

It is very important to note that this analysis on section 5 was done regarding attacks over the public key

$x_0 = pq_0 + r_0$

$x_1 = pq_1 + r_1$

$ \vdots $

$x_\tau = pq_\tau + r_\tau$

But, since in the symmetric case the ciphertexts have almost the same format of these public key's elements, which is $pq + 2r + m$, these attacks can be used to recover the key $p$ from ciphertexts $c_0, c_1, c_2,...$

Finally, if we choose $\eta = \lambda^2$, the best attack will run in time $2^{\sqrt{\eta}} = 2^\lambda$.

-- The notation

As the other users have said, it is the "asymptotic notation". There is a lot of material on the internet explaining it but to understand this paper, you just have to think that

$\omega(\log\lambda)$ means a function that is "greater" than $\log \lambda$, for instance, $\lambda$ or $\lambda^2$;

and

$ \tilde O(\lambda^5)$ means a function that is "smaller than or equal to" $\lambda^5 \cdot \log^k \lambda$, for any non-negative integer $k$. For instance, $\lambda^5$, or $\lambda^4$;

and

$\Theta(\lambda \log^2 \lambda)$ means a function that "behave" like $\lambda \log^2 \lambda$, for instance, any multiple like $2\cdot \lambda \log^2 \lambda$, or $3 \cdot \lambda \log^2 \lambda$, ..., or even $\lambda \log^2 \lambda$ itself.

-- Scheme's complexity

I think the authors are talking about the space complexity, because with such setting of parameters, the public key has $\tau$ integers of $\tilde O(\lambda^5)$ bits each, then, the public key's size is

$\tau \cdot \tilde O(\lambda^5) = (\tilde O(\lambda^5) + \lambda ) \cdot \tilde O(\lambda^5) = \tilde O(\lambda^{10})$

Therefore, this complexity is not valid to the symmetric scheme.

Answer 2

The paper says that the parameters are $r ≈ 2^{\sqrt \eta}$ and $q ≈ 2^{\eta^3}$. Note that these values are expressed as functions of $\eta$, not $N$.

With regard to the parameters, it is common practice to describe them using the asymptotic notation. $\omega(\cdot), \Theta(\cdot)$ and $\tilde O(\cdot)$ are instances of this notation. $\omega(g(n))$ denotes a function that dominates $g(n)$ asymptotically; that is, $f(n) = \omega(g(n))$ means that $f(n)$ is asymptotically greater than $g(n)$. For example, a linear function (e.g., $f(n) = n$) dominates a logarithmic function (e.g., $g(n) = \log n$), since, asymptotically, it grows much faster; thus, $n = \omega (\log n)$. $\Theta(g(n))$ denotes a function that, also asymptotically, can be "sandwiched" between $k_0 \cdot g(n)$ and $k_1 \cdot g(n)$, for some real values $k_0, k_1 > 0$. Finally, $\tilde O(n)$ is like the traditional Big-O notation but ignoring any logarithmic factors.

Therefore, these parameters are actually functions of the parameter $\lambda$, since they vary when $\lambda$ varies, although they are not expressed as functions. The expressions given are only a way of specifying how to choose them according to $\lambda$.

Also note that these expressions are somewhat "abusing the notation", since these asymptotic "functions" are actually sets of functions. Therefore, when you see something like $\rho = \omega(\log \lambda)$, it actually means $\rho(\lambda) \in \omega(\log \lambda)$. Anyway, this is a fairly common convention that simplifies the reading.

Knowing this, you can deduce your own example values for the parameters. For example:

$$\rho = \omega(\log \lambda) \to \rho = \lambda$$ $$\eta \geq \rho \cdot \Theta(\lambda\log^2 \lambda) \to \eta = \lambda \cdot (\lambda\log^2 \lambda) = \lambda^2\log^2 \lambda $$ $$\gamma = \omega(\eta^2\log \lambda) \to \gamma = \eta^2\lambda = (\lambda^2\log^2 \lambda)^2\lambda = \lambda^5\log^4 \lambda$$ $$\tau \geq \gamma + \omega(\log \lambda) \to \tau = \gamma + \lambda = \lambda^5\log^4 \lambda +\lambda $$ $$\rho' = \rho + \omega(\log \lambda) \to \rho' = \rho + \lambda = 2\lambda$$

As you can see, this gives a result that is consistent with the part that says:

A convenient parameter set to keep in mind is $ρ = λ$, $ρ′ = 2λ$, $η = \tilde O(λ^2)$, $γ = \tilde O(λ^5)$ and $τ = γ + λ$. (This setting results in a scheme with complexity $\tilde O(λ^{10})$.)

When it says that the scheme has complexity $O(\lambda^{10})$, I guess it means the time complexity.