Join Log in
Score:3
Leafar avatar Crypto

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

ng flag
Leafar

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.

304
0 + 0
Score:5
Mark avatar Crypto
ng flag
Mark

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.

0 + 0
Leafar avatar
ng flag
Leafar
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?
0
Reply
Mark avatar
ng flag
Mark
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.
0
Reply
Leafar avatar
ng flag
Leafar
I can't because such polynomials are never invertible and this will mess with $f$, in your answer $s$, which needs to be invertible.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.