# On a proposition in NTRU original paper: $\gamma_1 |f|_2 |g|_2 \leq |f \circledast g|_\infty \leq \gamma_2 |f|_2 |g|_2$

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?

• what is $R$? Do you mean $R[x]$ where $R$ is a ring of some kind? – kodlu Aug 30 '16 at 4:05
• $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}$. – Leafar Aug 31 '16 at 18:27
• $N$ is fixed and $\circledast$ is the multiplication in $R$. All the information is here: assets.securityinnovation.com/static/downloads/NTRU/resources/… – Leafar Aug 31 '16 at 18:32