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

Research on Quantum Algorithm Attack of NTRU Public Key Cryptography

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

NTRU is one of the candidates of post-quantum cryptography which is supported by NIST recently.It is important to analyze the security of NTRU in the quantum circumstance.In 2015,Fluhrer proposed a quantum attack on NTRU cryptosystem based on Grover search algorithm.In the product polynomial method,the attack can reach quadratic speedup on the search of small coefficient polynomial private key f_(1)f_(2)(IACR Cryptology ePrint Archive,2015/676,2015).However,there is a strong assumption of quantum oracle in this attack.Besides,the attack also needs to maintain a large exponential list during Grover superposition query.To solve this problem,it is found that NTRU cryptosystem can also be analyzed by Claw-Finding quantum algorithm.However,the original Claw-Finding algorithm aims at the functions with one-bit output.Hence,the original Claw-Finding algorithm cannot be used to analyze NTRU directly.This paper modifies the Claw-Finding algorithm,and the modified Claw-Finding algorithm can still find the claw even the output of the function is a bit-string.Based on this modified algorithm,the proposed quantum attack algorithm can achieve quadratic speedup in searching the private key.Moreover,the new attack does not need the assumption of strong quantum oracle and does not need to maintain the list of exponential size.Finally,a comparison of the proposed quantum attack and the attack presented by Fluhrer is given.