<p>On the section 3 of the paper  <a href="http://eprint.iacr.org/2009/616" rel="nofollow noreferrer">Fully Homomorphic Encryption over the Integers</a>, there is a construction of a somewhat encryption scheme, as follow:</p>
<p><strong>key generation</strong>
Choose an odd η-bit integer <span class="math-container">$p$</span> in <span class="math-container">$(2Z + 1) ∩ [2^{η−1} , 2^η)$</span> to be the secret key.</p>
<p>For the public key, sample <span class="math-container">$x_i ← pq_i + r_i$</span> for <span class="math-container">$i = 0, ..., τ$</span>, where <span class="math-container">$q_i \in Z∩[0, \frac{2^γ}{p})$</span> and <span class="math-container">$r_i \in Z∩(−2^ρ, 2^ρ)$</span>.</p>
<p>Relabel so that <span class="math-container">$x_0$</span> is the largest. Restart unless <span class="math-container">$x_0$</span> is odd and <span class="math-container">$r_p(x_0)$</span> is even. The public key is <span class="math-container">$pk = \{x_0, x_1, ... , x_τ\}$</span> .</p>
<p><strong>encryption</strong></p>
<p>Choose a random subset <span class="math-container">$S ⊆ \{1,2, ..., τ \}$</span> and a random integer <span class="math-container">$r$</span> in <span class="math-container">$(−2^{2\lambda}, 2^{2\lambda})$</span>, and output <span class="math-container">$c ← (m + 2r + 2 \sum_{i \in S} x_i) \mod x_0$</span></p>
<p><strong>decryption</strong></p>
<p>Output <span class="math-container">$m ← (c \mod p) \mod 2$</span></p>
<p>You can find more information on the paper (it's linked above).</p>
<p>So, I have some questions:</p>
<p>1 - Why we have to make <span class="math-container">$\mod p$</span> in decryption step? Since the sum is multiplied by two, we could just apply the <span class="math-container">$\mod 2$</span> to recovery the message <span class="math-container">$m$</span>, couldn't?</p>
<p>----- BEGIN EDIT</p>
<p>There is a lemma that shows that <span class="math-container">$c$</span> is of the form <span class="math-container">$ap + (2b + m)$</span> for some integers <span class="math-container">$a$</span> and <span class="math-container">$b$</span>, then, since <span class="math-container">$2b + m$</span> is smaller than <span class="math-container">$p$</span>, we have <span class="math-container">$c \mod p$</span> equal to <span class="math-container">$2b + m$</span>, then, <span class="math-container">$(c \mod p) \mod 2$</span> is equal to <span class="math-container">$m$</span>.</p>
<p>Therefore, I consider this question 1 answered.</p>
<p>----- END EDIT</p>
<p>2 - What is the maximum number of adding and multiplications operations that we can do over the ciphertexts?</p>
<p>Any help will be appreciated.</p>
<p>Thank you very much.</p>

CC BY-SA 3.0
2014-11-25T15:27:16.253Z
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.
Emil Jeřábek
CC BY-SA 3.0
2014-11-25T15:58:34.050Z
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.
Hilder Vitor Lima Pereira
CC BY-SA 3.0
2014-11-25T16:40:10.347Z
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.
Emil Jeřábek
CC BY-SA 3.0
2014-11-25T19:31:11.170Z
Thank you, @EmilJeřábek, I'll check this out tonight and come back here.
Hilder Vitor Lima Pereira
CC BY-SA 3.0
2014-11-25T23:16:50.847Z
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...
Hilder Vitor Lima Pereira
<homomorphic-encryption>
Fully Homomorphic Encryption over Integers
Hilder Vitor Lima Pereira
# Fully Homomorphic Encryption over Integers

(Asked by: username_0 on 2014-11-25)

On the section 3 of the paper [Fully Homomorphic Encryption over the Integers](http://eprint.iacr.org/2009/616), 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\_τ\}$ .

**encryption**

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$

**decryption**

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?

----- BEGIN EDIT

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.

**Tags:** homomorphic-encryption
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: Thank you, @EmilJeřábek, I'll check this out tonight and come back here.  
> **username_0**: 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...  

---

## 0 answers

