MITM against NTRU

Question

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?

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.