针对NTRU算法的新型广播攻击

本文结合多次加密传送攻击和广播攻击的双重特征, 提出了一种针对NTRU算法的新型广播攻击, 并对该攻击进行了理论分析和实验验证. 攻击者首先在不稳定信道C中利用多次加密传送攻击的思想, 恢复噪声多项式ri的部分系数, 从而建立有关明文m的线性方程组. 然后在广播模型下获得足够多的线性方程组, 从而快速求解出明文m. 为充分挖掘噪声多项式的信息, 进一步减少攻击所需要的信道数量, 本文一方面利用噪声多项式之间发生的“伪碰撞”, 缩小未知系数的取值范围; 另一方面通过直接猜测ri中未知系数, 牺牲一定的正确率来获得更多信息. 通过这些方法能在有限的信道中, 建立更多关于m的方程. 理论分析表明新的...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Cryptologic Research 2016-12, Vol.3 (6), p.596
Main Authors: Zhi-Chao, YANG, Shao-Jing, FU, Long-Jiang, QU, LI, Chao, Duan-Qiang, XIE, 杨智超, 付绍静, 屈龙江, 李 超, 谢端强
Format: Article
Language:Chinese
Subjects:
Broadcasting
Channels
Coefficients
Linear equations
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:本文结合多次加密传送攻击和广播攻击的双重特征, 提出了一种针对NTRU算法的新型广播攻击, 并对该攻击进行了理论分析和实验验证. 攻击者首先在不稳定信道C中利用多次加密传送攻击的思想, 恢复噪声多项式ri的部分系数, 从而建立有关明文m的线性方程组. 然后在广播模型下获得足够多的线性方程组, 从而快速求解出明文m. 为充分挖掘噪声多项式的信息, 进一步减少攻击所需要的信道数量, 本文一方面利用噪声多项式之间发生的“伪碰撞”, 缩小未知系数的取值范围; 另一方面通过直接猜测ri中未知系数, 牺牲一定的正确率来获得更多信息. 通过这些方法能在有限的信道中, 建立更多关于m的方程. 理论分析表明新的攻击方法不仅将建立关于明文的方程所需引入的变量个数从原来的N+[N/2]降低到N. 而且完成一次攻击所需要的信道数也由原来的N+[N/2]-1+l减少到N/V(N,dr,k), 这里, 并且能够在O(N3)的时间复杂度下恢复明文. 实验结果表明, 新广播攻击比原有的多次加密传送攻击、广播攻击更加高效, 它对于更高安全等级的NTRU算法攻击仍然有效.
ISSN:2097-4116
DOI:10.13868/j.cnki.jcr.000155