-
题名NTRU公钥密码的量子算法攻击研究
- 1
-
-
作者
董经
蔡彬彬
吴宇森
高飞
秦素娟
温巧燕
-
机构
北京邮电大学网络与交换技术国家重点实验室
密码科学技术国家重点实验室
-
出处
《密码学报》
CSCD
2021年第6期948-959,共12页
-
基金
中央高校基本科研业务费专项资金(2019XD-A01)
国家自然科学基金(61972048,61976024)。
-
文摘
NTRU作为近期NIST征集的后量子密码算法之一,分析其量子安全性具有重要意义.2015年,Fluhrer基于Grover搜索算法给出对NTRU公钥密码的量子攻击.在乘积多项式模式下,该攻击对小系数多项式私钥f_(1)f_(2)的搜索具有平方加速效果.然而,该攻击不仅需要一个强量子Oracle假设,且需要在Grover叠加查询过程中多次维护一个指数大的列表.针对此问题,本文发现Claw-Finding量子算法对NTRU密码具有同样的攻击效果.然而,原Claw-Finding算法中针对的函数输出值为单比特,不适用于分析NTRU.本文对原Claw-Finding算法进行修改,即当访问的两个函数输出为比特串时,算法依然可以找到Claw.基于此,本文给出在私钥搜索方面具有平方加速的量子攻击算法,避免了强量子Oracle的假设,且不需要维护指数大的列表.最后,本文给出所提量子攻击与Fluhrer攻击方法的比较.
-
关键词
NTRU
Claw-Finding算法
GROVER算法
-
Keywords
NTRU
Claw-Finding algorithm
Grover algorithm
-
分类号
TP309.7
[自动化与计算机技术—计算机系统结构]
-
