Key Size for Symmetric Homomorphic Encryption Over the Integers 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.
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 &gt; 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.