2
$\begingroup$

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 ?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. ​ ​ ​ ​ $\endgroup$ – user991 Mar 5 '16 at 21:56
  • $\begingroup$ 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. $\endgroup$ – Hilder Vitor Lima Pereira Mar 6 '16 at 23:09
  • $\begingroup$ @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 ? $\endgroup$ – guglielmo london Mar 7 '16 at 8:56
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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}$" $\endgroup$ – Hilder Vitor Lima Pereira Mar 6 '16 at 23:21
  • $\begingroup$ @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/… $\endgroup$ – Luckyluck63 Mar 7 '16 at 3:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.