In the original paper of NTRU cryptosystem, we have the following proposition (that is said to be suggested by Don Coppersmith):

For any $\epsilon > 0$, there are constants $\gamma_1,\gamma_2 > 0$, depending on $\epsilon$ and $N$, such that, for randomly chosen polynomials $f,g \in R$, the probability that they satisfy \begin{align*} \gamma_1 |f|_2 |g|_2 \leq |f \circledast g|_\infty \leq \gamma_2 |f|_2 |g|_2 \end{align*} is greater than $1-\epsilon$.

However, it lacks of a proof (we only can see experimental evidences).

The paper (and many others found) says that is a proposition, so:

Where can I find a proof of this?

  • $\begingroup$ what is $R$? Do you mean $R[x]$ where $R$ is a ring of some kind? $\endgroup$
    – kodlu
    Aug 30, 2016 at 4:05
  • $\begingroup$ $R=\mathbb{Z}[X]/\langle X^N-1 \rangle$. In this case $f$ and $g$ take coefficients in $\{-r,-r+1,\ldots,r\}$ with large $r \in \mathbb{Z}$. $\endgroup$
    – Leafar
    Aug 31, 2016 at 18:27
  • $\begingroup$ $N$ is fixed and $\circledast$ is the multiplication in $R$. All the information is here: assets.securityinnovation.com/static/downloads/NTRU/resources/… $\endgroup$
    – Leafar
    Aug 31, 2016 at 18:32


Your Answer

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