Bit Security of NTRU
Igor E. Shparlinski · Birkhäuser Basel eBooks · 2003
We recall that in theNTRU cryptosystem[267, 269], one selects integer parameters(N q)and four setsG f Gg L: Lof polynomialsf gcp, m in the ring $$ \[R = {\mathbb{Z}_q}\left[ X \right]/\left( {{X^N} - 1} \right)\] $$ . The coefficients of these polynomials are constrained by the choice of an additional parameter, p, a small integer or polynomial. In the original presentation of NTRU, see [267], the choicep =3 is considered, and thus the polynomialsf g cp mare ternary. The authors of NTRU have since recommended [269] that to choose p =X +2. This choice for p, along with other optimisations suggested in [269], leads tof g cp mbeing constructed from binary polynomials. In particular this leads to the message representative polynomial m being binary.