Paper 2017/484

Cryptanalysis of the Overstretched NTRU Problem for General Modulus Polynomial

Jung Hee Cheon and Minki Hhan and Changmin Lee

Abstract

The overstretched NTRU problem, which is the NTRU problem with super-polynomial size q in n, is one of the important security foundation of cryptosystems which are recently suggested. Albrecht et al. in Crypto 2016 and Cheon et al. in ANTS 2016 proposed so-called subeld attacks which demonstrate that the overstretched NTRU problems with power-of-two cyclotomic modulus are not secure enough with given parameters in GGH multilinear map and YASHE/LTV fully homomorphic encryption. Unfortunately, they heavily depend on the algebraic structure of the base ring. On the other hand, Kirchner and Fouque presented new cryptanalysis of the overstretched NTRU problem over general modulus in Eurocrypt 2017. They achieve the similar performance compare to previous subeld attacks. In this paper, we present a new algorithm to the overstretched NTRU problem. This algorithm has same complexity to subeld attacks, but threaten more general base ring with poly(n) expansion factor as common in suggested schemes like original GGH, YASHE scheme and NTRU prime rings. Our algorithm implies that cryptosystem related to the overstretched NTRU problem cannot be secure by changing base ring. In addition, we present an extended (trace/norm) subeld attack for the power-of-two cyclotomic modulus. This extended subeld attack has a similar asymptotic complexity to the previous subeld attacks, but with smaller constant in the exponent term.