Paper 2017/484

Cryptanalysis of Middle Lattice on the Overstretched NTRU Problem for General Modulus Polynomial

Jung Hee Cheon, 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 most important candidates for higher level cryptography. Unfortunately, Albrecht et al. in Crypto 2016 and Cheon et al. in ANTS 2016 proposed so-called subfield 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. Moreover, Kirchner and Fouque presented new cryptanalysis of the overstretched NTRU problem over general modulus in Eurocrypt 2017. They showed that a lattice basis reduction algorithm upon middle lattice, which is first presented by Howgrave-Graham in Crypto 2007, experimentally recover secret parameters of the overstretched NTRU problem. In this paper, we revisit the middle lattice technique on the overstretched NTRU problem. This analysis show that the optimized middle lattice technique has same complexity to subfield 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 new analysis implies that cryptosystem related to the overstretched NTRU problem cannot be secured by changing base ring. In addition, we present an extended (trace/norm) subfield attack for the power-of-two cyclotomic modulus, which is also one of the middle lattice technique. This extended subfield attack has a similar asymptotic complexity to the previous subfield attacks, but with smaller constant in the exponent term.