In MITM attacks against the NTRU cryptosystem, we exploit the fact that in the ring of truncated polynomials of degree $n-1$ it holds that $$fg=h\mod q$$ for our secret and public keys $f,h$. The basic idea is splitting $f$ into $f_1,f_2$ such that $f_1+f_2=f$ and therefore considering $$f_1h=g-f_2h. $$This is almost like finding a collision in the function $f(x)=xh$, if it weren't for the presence of $g$. So we must introduce an auxiliary function $a(x)$, which according to the notes I'm reading is defined as follows:

To search for near-collisions an auxiliary function $a(x)$ is needed. This function takes a vector of length n and in each coordinate $x_i$ returns $\mathbb I (x_i > 0)$. If $g$ does not cause the coordinates of $−f_2 · h$ to change sign, i.e. $a(−f_2 · h) \ne a(−f_2 · h + g)$, we have that $a(f_1 h) = a(−f_2 h)$.

I don't quite understand what this function is supposed to do. Can anyone explain it to me in simple terms?


1 Answer 1


You should really give more context. Your quote is the same as in page 3 of https://eprint.iacr.org/2016/177.pdf.

The function detects positive coordinates.

So, if you apply $a$ to the vector $x$ via $$ (y_1,\ldots,y_n)=a(x_1,\ldots,x_n) $$ by definition we have $$ y_i=\mathbb I (x_i > 0)=\left\{ \begin{array}{ccr} 1,&\mathrm{ if} & x_i>0,\\ 0, &\mathrm{ if}& x_i\leq 0. \end{array}\right. $$ For example if $x=(-2,0,3)$ with $n=3,$ then $y=(0,0,1).$

I will expand the claim in the quote (which is a bit loosely phrased) as follows:

If adding $g$ does not cause the coordinates of $−f_2 · h$ to change sign, i.e. if we do not have $a(−f_2 · h) \ne a(−f_2 · h + g)$, we have that $a(f_1 h) = a(−f_2 h)$.

In page 2 of the paper, it is also stated that $g$ is chosen with coefficients zero and 1 only. Therefore the two quantities being unequal $a(−f_2 · h) \ne a(−f_2 · h + g)$ when $g$ is added is can just be detected by checking signs since the difference $g$ by design has only $0,1$ coefficients.

  • $\begingroup$ Could you elaborate a little on the last paragraph? I find it a bit confusing. I would also be very grateful if you could also explain a bit more why this whole method works; it's not so clear to me (following the same notes you link to) why we can 'almost' sure to have found the original key... $\endgroup$ Oct 16, 2022 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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