On the section 3 of the paper Fully Homomorphic Encryption over the Integers, there is a construction of a somewhat encryption scheme, as follow:

key generation Choose an odd η-bit integer $p$ in $(2Z + 1) ∩ [2^{η−1} , 2^η)$ to be the secret key.

For the public key, sample $x_i ← pq_i + r_i$ for $i = 0, ..., τ$, where $q_i \in Z∩[0, \frac{2^γ}{p})$ and $r_i \in Z∩(−2^ρ, 2^ρ)$.

Relabel so that $x_0$ is the largest. Restart unless $x_0$ is odd and $r_p(x_0)$ is even. The public key is $pk = \{x_0, x_1, ... , x_τ\}$ .


Choose a random subset $S ⊆ \{1,2, ..., τ \}$ and a random integer $r$ in $(−2^{2\lambda}, 2^{2\lambda})$, and output $c ← (m + 2r + 2 \sum_{i \in S} x_i) \mod x_0$


Output $m ← (c \mod p) \mod 2$

You can find more information on the paper (it's linked above).

So, I have some questions:

1 - Why we have to make $\mod p$ in decryption step? Since the sum is multiplied by two, we could just apply the $\mod 2$ to recovery the message $m$, couldn't?


There is a lemma that shows that $c$ is of the form $ap + (2b + m)$ for some integers $a$ and $b$, then, since $2b + m$ is smaller than $p$, we have $c \mod p$ equal to $2b + m$, then, $(c \mod p) \mod 2$ is equal to $m$.

Therefore, I consider this question 1 answered.

----- END EDIT

2 - What is the maximum number of adding and multiplications operations that we can do over the ciphertexts?

Any help will be appreciated.

Thank you very much.

  • $\begingroup$ 1. The “$\dots\bmod x_0$” in the definition of $c$ does not preserve parity. This is kind of the whole point, as otherwise you could as well send $c=m$ for all attackers to see and don’t bother with the padding. $\endgroup$ – Emil Jeřábek supports Monica Nov 25 '14 at 15:27
  • $\begingroup$ Ok, I agree about the parity, but it means that $c \mod p$ is of the form $m + 2u$ for some integer $u$ (otherwise, the $\mod 2$ wouldn't work). This is not clear too. $\endgroup$ – Hilder Vítor Lima Pereira Nov 25 '14 at 15:58
  • $\begingroup$ See Lemma A.1. You need to know something about the magnitude of the parameters for this to work, it does not follow from what you’ve written here. $\endgroup$ – Emil Jeřábek supports Monica Nov 25 '14 at 16:40
  • $\begingroup$ Thank you, @EmilJeřábek, I'll check this out tonight and come back here. $\endgroup$ – Hilder Vítor Lima Pereira Nov 25 '14 at 19:31
  • $\begingroup$ Well, I read the Lemma A.1 and, Ok, it gave me a good understand about the scheme. However, I must point out that there are some errors there: the definition of $c$ is different (in the original definition, there is a $2$ multiplying the sum) and the sentence "there exist integers $q_i$ and $r_i$ with $|r_i| ≤ 2^ρ$ such that $x_i = q_i·p + 2r_i$ , and also $|r_i| ≤ 2^ρ$" cite $r_i$ two times and let $q_i$ as a free variable... $\endgroup$ – Hilder Vítor Lima Pereira Nov 25 '14 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.