Research on Quantum Algorithm Attack of NTRU Public Key Cryptography

• 1、State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, BeiJing 100876

Abstract：NTRU is one of 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, Scott 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 (IACR Cryptology ePrint Archive, 2015:676, 2015). However, there exist a strong assumption of quantum oracle in this attack.，but also needs to maintain a large exponential list many times during Grover overlay query. To solve this problem, we find that the claw finding quantum algorithm has the same attack effect on NTRU cryptosystem, and can effectively avoid the above problems. However, the original Claw-Finding algorithm aims at the functions whose output is one bit. Hence, the original Claw-Finding algorithm cannot be used to analyze NTRU directly. Therefore, we need to modify the Claw-Finding algorithm here. The modified Claw-Finding algorithm can still find the claw even the output of function is bit-serial. Finally, this paper presents a quantum attack algorithm with quadratic speedup for NTRU cryptosystem in private key search, avoids the assumption of strong quantum Oracle, and does not need to maintain the list of exponential size. Then, we give the comparison of the proposed quantum attack and the attack presented by Scott.

Keywords： NTRU Claw-Finding Algorithm Grover Algorithm