"Fully Homomorphic Encryption over the Integer" described a simple FHE scheme based on the GACD assumption. Its encryption function (on page 6) has the form $c \leftarrow (m + 2r + 2*\sum_{i \in S} x_i) \mod x_0$, where $\sum_{i \in S} x_i$ can be viewed as some ciphertexts of plaintext 0 (which can be divided by the secret key $p \in 2\mathbb{Z}+1$), and $r$, as the paper informed us, is randomly chosen from $(-2^{\rho'}, 2^{\rho'})$.

Decryption is taken by $m' = (c \mod p) \mod 2$.

It seems that "mod p" is used to drop $2*\sum_{i \in S} x_i$ and "mod 2" is used to drop $2r$.

If $r > 0$, the item $2r \mod p$ is even. It will not change the parity of $c \mod p$.

However, since $p$ is odd, for any $r < 0$, the item $2r \mod p$ in fact equals $p + 2r \mod p$, which is odd and will change the parity of $(c \mod p)$. I have programed for this algorithm and the result matchs the observation above.

What's the mistake of my reasoning and/or my understanding?

  • 1
    $\begingroup$ You are using a wrong representation. ​ ​ $\endgroup$ – user991 Aug 28 '15 at 10:32
  • $\begingroup$ In my opinion (and as the authors of the paper mentioned), here we do not need the knowledge of lattice (except the case to attack the scheme). The scheme itself is written in simple mathematics (though the proof is advanced). So just think about (elementary ) number theory, what's the mistake? Do you mean $(-2^{\rho'}, 2^{\rho'})$ is in fact $(0, 2^{\rho'+1})$? $\endgroup$ – phan Aug 28 '15 at 10:54
  • $\begingroup$ In that post tylo pointed out elements in lattices are not integers, but vectors. But here $r$ is 'verily' an integer... $\endgroup$ – phan Aug 28 '15 at 11:05
  • $\begingroup$ The mistake is that you're just thinking about (elementary ) number theory, $\hspace{1.8 in}$ rather than using the symmetric representation. $\;$ $\endgroup$ – user991 Aug 28 '15 at 11:25
  • 1
    $\begingroup$ Yes. ​ ((x+((p-1)/2))%p)-((p-1)/2) ​ ​ ​ ​ $\endgroup$ – user991 Aug 28 '15 at 12:58

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.