4
$\begingroup$

I'm looking at the description of NTRUEncrypt given on page 21 of http://archive.dimacs.rutgers.edu/Workshops/Post-Quantum/Slides/Silverman.pdf and using its notation. So in NTRU there are always two private parameters $F$ and $G$. However, decryption only requires knowledge of $F$. I'm confused about what the purpose of $G$ is because it doesn't come into the decryption and I don't see why removing $G$ hurts the security of NTRU - more specifically, is NTRU still hard if $G$ is always set to 1 (i.e., $(1,0,0,...,0)\in \{-1,0,1\}^N$)?

$\endgroup$
3
$\begingroup$

If $G$ is set to $1$, then the adversary can easily decrypt the ciphertext because in this case $h = pf^{-1} \mod q, p$ is coprime with $q$, then inverting $p \mod q$ is possible and after that he calculates $f \mod q$ from $h$, then he calculates $f^{-1} \mod p$ from $f$

$\endgroup$
2
  • $\begingroup$ Thanks, I have a follow-up, in the case where $g$ is no longer set to $1$ so that $h=pf^{-1}g \mod q$, would being able to factor $h$ break NTRU? $\endgroup$
    – dcw
    May 28 at 16:14
  • 1
    $\begingroup$ no but if you could retrieve f or g from h, you have broken Ntru, I'll look for an example $\endgroup$ May 28 at 16:35

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.