An efficient quantum meet-in-the-middle attack against NTRU-2005

作     者：WANG Hong MA Zhi MA ChuanGui 

作者机构：State Key Laboratory of Mathematical Engineering and Advanced Computing 

出 版 物：《Chinese Science Bulletin》 (Chinese Science Bulletin)

年 卷 期：2013年第58卷第28期

页      面：3514-3518页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：supported by the National High Technology Research and Development Program of China(2011AA010803) the National Natural Science Foundation of China(U1204602) the Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing(2013A14) 

主　　题：中间人攻击 量子算法 NTRU 空间复杂度 公钥密码 安全性 私钥 搜索 

摘      要：NTRU is one of the most widely used public-key cryptosystems and its security has been an active research topic.This paper proposes a new way to find NTRU-2005 private key.The algorithm is based on meet-in-the-middle attack and a quantum algorithm for searching the fixed weight target.Compared with the current classical and quantum meet-in-the-middle attacks,our algorithm has lower time and space complexity.Moreover,this attack can also be applied against different versions of NTRU.The result can help to understand the security of NTRU better.