On the hardness of NTRU problems

摘要

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 = Õ(n5.5), average-case NTRU problem over arbitrary cyclotomic field K with [K: ℚ] = n is at least as hard as worst-case SIVPγ problems over K with ³ = Õ(n6).