MITM对抗NTRU

Question

在针对NTRU密码体制的MITM攻击中，我们利用了一个事实，即在n-1度截短多项式环中，对于我们的秘密密钥和公钥f,h，它持有fg=h\mod q。基本思想是将f分解为f_1,f_2，这样f_1+f_2=f就可以考虑f_1h=g-f_2h. ，这几乎就像在函数f(x)=xh中找到冲突，如果没有g的存在的话。因此，我们必须引入一个辅助函数a(x)，根据我正在读的注释，它的定义如下：

为了搜索近碰撞，需要一个辅助函数a(x)。该函数采用长度为n的向量，在每个坐标中，x_i返回\mathbb I (x_i > 0)。如果g不使−f_2 · h的坐标改变符号，即a(−f_2 · h) \ne a(−f_2 · h + g)，我们就得到了a(f_1 h) = a(−f_2 h)。

我不太明白这个函数应该做什么。有人能简单地向我解释一下吗？

Answer 1

你真的应该给出更多的背景。您的报价与https://eprint.iacr.org/2016/177.pdf第3页相同。

该函数检测正坐标。

因此，如果您将a应用于向量x，则

(y_1,\ldots,y_n)=a(x_1,\ldots,x_n)

从定义上讲，我们

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.

例如，如果x=(-2,0,3)与n=3,一起使用，那么y=(0,0,1).

我将在引文(措辞有点松散)中扩大索赔，具体如下：

如果添加g不会导致−f_2 · h的坐标发生变化，也就是说，如果我们没有a(−f_2 · h) \ne a(−f_2 · h + g)，我们就有a(f_1 h) = a(−f_2 h)。

在本文的第2页中，我们还指出了g的选择是系数为0和1的。因此，当加入a(−f_2 · h) \ne a(−f_2 · h + g)时，两个不相等的g是可以通过检查符号来检测的，因为设计中的差分g只有0,1系数。