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$)?
1 Answer
$\begingroup$
$\endgroup$
2
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$
-
$\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$– wdcMay 28, 2021 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, 2021 at 16:35