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

摘要

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