# How to decide if an element is a public key in NTRU encryption scheme?

First, I'm using the settings of https://en.wikipedia.org/wiki/NTRUEncrypt, with $$L_f$$ set of polynomials with $$d_f+1$$ coefficients equal to 1, $$d_f$$ equal to $$-1$$ and the remaining $$N-2d_f-1$$ equal to 0; and $$L_g$$ the set of polynomials with $$d_g$$ coefficients equal to 1, $$d_g$$ equal to $$-1$$ and the remaining $$N-2d_g$$ equal to 0. The natural numbers $$d_f$$ and $$d_g$$ are just fixed parameters of the scheme.

Suppose one receives a polynomial $$h$$ in the ring $$R_{N,q}=\mathbb{Z}_q[X]/\langle X^N-1 \rangle$$.

Question: Is it possible to determine if $$h$$ is a public-key, that is, is it possible to determine if $$h$$ is of the form $$pf_q \cdot g \pmod{q}$$?

My attempt: The NTRU hardness assumption says that from $$h$$ one cannot determine $$f$$ or $$g$$, otherwise the scheme would be useless. Although I couldn't answer my question, I came up with a test. Since $$g(1)=0$$, we must have $$h(1)=0$$. Hence if $$h(1) \neq 0$$ then $$h$$ is not a public-key. What can we test more?

PS: No zero-knowledge proof or similar things from the source of $$h$$ are given.

You can't under a standard assumption known as the "Decisional NTRU Assumption". This is essentially the statement that NTRU public keys are pseudorandom. The following is definition 4.4.4 of A Decade of Lattice Cryptography.

NTRU Learning Problem: For an invertible $$s\in R_q^*$$, and distribution $$\chi$$ on $$R$$, define $$N_{s, \chi}$$ to be the distribution that outputs $$e/s\in R_q$$ where $$e\gets\chi$$. The NTRU Learning Problem is: Given independent samples $$a_i\in R_q$$, where each sample is distributed according to either

1. $$N_{s,\chi}$$, for some randomly chosen $$s\in R_q^*$$ (fixed for all samples), or
2. the uniform distribution, distinguish which is the case (with non-negligible advantage).

Note that this problem essentially states that you cannot do what you are asking, i.e. states that NTRU keys are computationally indistinguishable from random.

• Thanks a lot! I understand more now, but here in this definition the uniform distribution is defined over all $R_{N,q}$, which is against the test I provided. Moreover, $\chi$ is a distribution over $L(d_g,d_g)$. Can I define point 2 as uniform distribution over $R_{N,q}$ except for all polynomials which evaluated at 1 give 0? Will this definition / hardness assumption be enough? Oct 4, 2021 at 23:27
• You can probably just define the ring $R$ to have polynomials that evaluate to 0 at 1, e.g. set $R = \mathbb{Z}[x] / (x^n-1)$. You can't just change point 2 unilaterally though, as then the distinguishing problem becomes a different distinguishing problem.
– Mark
Oct 5, 2021 at 1:51
• I can't because such polynomials are never invertible and this will mess with $f$, in your answer $s$, which needs to be invertible. Oct 5, 2021 at 20:46