# Why is this homomorphic encryption correct?

In LTV-FHE, section 3.3.2 Formal description, a ciphertext looks like this $c=hs+2e+b = (2g/f)s+2e+b$, where $h = 2g/f$ is the public key, $f$ is the secret key, $g, s$ and $e$ are chosen randomly, and $b$ is the bit to be encrypted.

Following the equation $c = (2g/f)s+2e+b$, the bit $b$ can be obtained easily performing a modulo 2 operation for a ciphertext.

What is the hardness that protects against this simple modulo reduction ?

• Why can the bit b "be obtained easily performing a modulo 2 operation for a ciphertext"? ​ It looks like the parity of (2g/f)s would be unknown. ​ ​ ​ ​ – user991 Mar 5 '16 at 21:56
• In fact, when you ask "why is it correct" you are asking "why the decryption algorithm works"... But the body of your question makes clear that what you really want to know is why this scheme is secure. So, maybe you should edit the title of your question. – Hilder Vítor Lima Pereira Mar 6 '16 at 23:09
• @Ricky Demer : Why is the parity of (2g/f)s unknown ? Only if g/f is rational, then is multiplied by 2 and then the rational numbers are approximated to integers. Is g/f a rational polynomial ? – guglielmo london Mar 7 '16 at 8:56

Note that $h\in R_q$, which hides the parity of $2g/f$ since $q$ is a prime. For example, $h=[2x^2-6x-8]_{17}$. In addition, all the operations (including addition and multiplication) to compute $c$ are done in $R_q$.
• Well, the NTRU assumes that $q$ is prime, but I am not sure that the LTV does it too. Some lemmas (3.2 or 3.3 for instance) say "let $q = 2^{n^\epsilon}$" – Hilder Vítor Lima Pereira Mar 6 '16 at 23:21
• @Vitor Right, the correctness of NTRU is based on $q$ being prime. The LTV should also consider this, unless otherwise the system in insecure. What it matters in those two lemmas is $\log(q)$ not $q$. Hence, they can be adapted for any other $q$ too. The security of the LTV is based on "circular security". For more detail, please see: degruyter.com/view/books/9783110317916/9783110317916.179/… – Luckyluck63 Mar 7 '16 at 3:05