I am working through the "Computing Arbitrary Functions of Encrypted Data" by Gentry, trying to understand more about Fully Homomorphic Encryption. I'm stuck trying to understand why his "Somewhat Homomorphic Scheme" presented in section 3 is correct. Ignoring the homomorphic aspects of his scheme, I'm struggling just to prove that $\text{decrypt}(p, \text{encrypt}(p,m)) \stackrel{?}{=} m$.

Gentry defines $N = \lambda, P = \lambda^2, Q = \lambda^5$ and

$\operatorname{KeyGen}(\lambda)$: A random $P$-bit, odd integer

$\operatorname{Encrypt}(p,m)$: Let $m'$ be an $N$-bit number s.t. $m' \equiv m \pmod 2$. Output $c = m' + pq$, where $q$ is a random $Q$-bit number

$\operatorname{Decrypt}(p,c):$ Output $(c \mod p)\mod 2)$, where $(c \mod p)$ is the integer $c'$ in $(-p/2, p/2)$ s.t. $p$ divides $c - c'$

I think there's a counterexample when $p = 1$ (you can force this by setting $\lambda = 1$, because $(c\mod 1) = 0$. Thus, it seems that $p \in \{3,5,\ldots 2^{P}\}$. I'm wondering if there are other restrictions on the domain of $p$, for example, if we knew that $p > m'$, it would be nearly trivial to show that decrypt works: $(c \mod p) \mod 2 = (m' + pq \mod p) \mod 2 = (m' \mod 2) = m$.

  • $\begingroup$ $\lambda$ is the security parameter. Setting it to 1, yes you have obviously had no security. It is like saying have a block cipher with $\lambda$ key size. Now set it 1! $\endgroup$ – kelalaka Nov 22 '19 at 20:27
  • $\begingroup$ This is a fair criticism of $\lambda =1$, but, for any $\lambda$, $1$ is a possible random $P$-bit odd integer, so the counter-example holds. Unless Gentry means $p \in [2^{P-1}, 2^{P} -1]$ when he says $P$-bit integer. $\endgroup$ – arquinn Nov 22 '19 at 20:57
  • $\begingroup$ The probability of sampling $p = 1$ is negligible. $\endgroup$ – fkraiem Nov 22 '19 at 21:24
  • $\begingroup$ $p$ has $\lambda^2$ bits, that is $p \in [2^{\lambda^2-1}, 2^{\lambda^2} - 1]\cap \mathbb{Z}$, therefore, $p > 2\cdot 2^\lambda > 2\cdot m'$, therefore, the decryption works even if you use the "centered" reduction modulo $p$. $\endgroup$ – Hilder Vitor Lima Pereira Nov 23 '19 at 16:48

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.