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.

  • $\begingroup$ 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? $\endgroup$
    – Leafar
    Oct 4 '21 at 23:27
  • $\begingroup$ 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. $\endgroup$
    – Mark
    Oct 5 '21 at 1:51
  • $\begingroup$ I can't because such polynomials are never invertible and this will mess with $f$, in your answer $s$, which needs to be invertible. $\endgroup$
    – Leafar
    Oct 5 '21 at 20:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.