NTRU公钥密码的量子算法攻击研究

• 作者: 董经 蔡彬彬 吴宇森 高飞 秦素娟 温巧燕
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: NTRU Claw-Finding算法 Grover算法
• 年，卷（期）: 2021,（6）
• 所属期刊栏目: 量子计算与密码分析专栏|Special Column:Quantum Computing and Cryptanalysis
• 页码范围: 948-959
• 页数: 12页
• 分类号: TP309.7
• 语种: 中文
• DOI: 10.13868/j.cnki.jcr.000489

摘要

NTRU作为近期NIST征集的后量子密码算法之一,分析其量子安全性具有重要意义.2015年,Fluhrer基于Grover搜索算法给出对NTRU公钥密码的量子攻击.在乘积多项式模式下,该攻击对小系数多项式私钥f1f2的搜索具有平方加速效果.然而,该攻击不仅需要一个强量子Oracle假设,且需要在Grover叠加查询过程中多次维护一个指数大的列表.针对此问题,本文发现Claw-Finding量子算法对NTRU密码具有同样的攻击效果.然而,原Claw-Finding算法中针对的函数输出值为单比特,不适用于分析NTRU.本文对原Claw-Finding算法进行修改,即当访问的两个函数输出为比特串时,算法依然可以找到Claw.基于此,本文给出在私钥搜索方面具有平方加速的量子攻击算法,避免了强量子Oracle的假设,且不需要维护指数大的列表.最后,本文给出所提量子攻击与Fluhrer攻击方法的比较.