Join Log in
Score:0
avatar Crypto

MITM against NTRU

jp flag
Creeptographer

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?

50
1 + 0
Score:2
kodlu avatar Crypto
sa flag
kodlu

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.

+ 1
jp flag
Creeptographer
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...
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.