On the hardness of NTRU problems
作者机构：School of MathematicsShandong UniversityJinan250100China Key Laboratory of Cryptologic Technology and Information SecurityShandong UniversityJinan250100China
出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)
年 卷 期：2022年第16卷第6期
页 面：135-144页
核心收录：
基 金：supported by the National Key Research and Development Program of China (2018YFA0704702) the National Natural Science Foundation of China (Grant No.61832012).
主 题：lattice-based cryptography algebraic nmber fields NTRU Problems Ring-LWE computational compleity
摘 要：The hardness of NTRU problem affects heavily on the securities of the cryptosystems based on it.However,we could only estimate the hardness of the specific parameterized NTRU problems from the perspective of actual attacks,and whether there are worst-case to average-case reductions for NTRU problems like other lattice-based problems(e.g.,the Ring-LWE problem)is still an open problem.In this paper,we show that for any algebraic number field K,the NTRU problem with suitable parameters defined over the ring of integers R is at least as hard as the corresponding Ring-LWE problem.Hence,combining known reductions of the Ring-LWE problem,we could reduce worst-case basic ideal lattice problems,e.g.,SIVPγproblem,to average-case NTRU problems.Our results also mean that solving a kind of average-case SVPγproblem over highly structured NTRU lattice is at least as hard as worst-case basic ideal lattice problems in K.As an important corollary,we could prove that for modulus q=Õ(n^(5.5)),average-case NTRU problem over arbitrary cyclotomic field K with[K:Q]=n is at least as hard as worst-case SIVP_(γ)problems over K with γ=Õ(n^(6)).
维普期刊数据库