摘要
本文结合多次加密传送攻击和广播攻击的双重特征,提出了一种针对NTRU算法的新型广播攻击,并对该攻击进行了理论分析和实验验证.攻击者首先在不稳定信道(34)中利用多次加密传送攻击的思想,恢复噪声多项式ri的部分系数,从而建立有关明文m的线性方程组.然后在广播模型下获得足够多的线性方程组,从而快速求解出明文m.为充分挖掘噪声多项式的信息,进一步减少攻击所需要的信道数量,本文一方面利用噪声多项式之间发生的"伪碰撞",缩小未知系数的取值范围;另一方面通过直接猜测ri中未知系数,牺牲一定的正确率来获得更多信息.通过这些方法能在有限的信道中,建立更多关于m的方程.理论分析表明新的攻击方法不仅将建立关于明文的方程所需引入的变量个数从原来的N+[N/2]降低到N.而且完成一次攻击所需要的信道数也由原来的N+[N/2]-1+l减少到N/V(N,d/_r,k),这里V(N,d_r,k)=N(1-2(1-(d_r/N))~k+(1-(2d_r/N))~k),并且能够在O(N^3)的时间复杂度下恢复明文.实验结果表明,新广播攻击比原有的多次加密传送攻击、广播攻击更加高效,它对于更高安全等级的NTRU算法攻击仍然有效.
In this paper, a new broadcast attack against NTRU is proposed which is based on the combination of multiple transmission attack and classic broadcast attack. Theoretical analysis and experiments are conducted to determine the practicality of the new attack. Firstly, an attacker can recover some coefficients in random polynomials r_i with the idea of multiple transmission attack in channel(34). So linear equations about m can be established and the corresponding plaintext can be recovered quickly as long as those equations are solved. Moreover, two methods are used to further obtain more information about r_i and to reduce the number of channels in a whole attack. First, 'pseudo-collisions' between random polynomial are used to narrow down the range of unknown coefficients. Second, to guess the rest unknown coefficients is also a good approach. Those contributions result in reducing the needed channels and building more equations about m. Theoretical analysis indicates that the number of variables in the equations drops from N+[ N/ 2] to N, the needed channels also decreases from N+[n/2]-1+l to N/V(N,d_r,k) where V(N,d_r,k)=N(1-2(1-(d_r/N))~k+(1-(2d_r/N))~k),and an attack can be finished within O(N^3) computation. Finally, the experiment results show that the new attack is more efficient than the existing ones, and it also works in higher security levels.
出处
《密码学报》
CSCD
2016年第6期596-606,共11页
Journal of Cryptologic Research
基金
国家自然科学基金项目(61572026
11531002)
