Cryptology ePrint Archive: Report 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 sub eld 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 sub eld attacks. In this paper, we present a new algorithm to the overstretched NTRU problem. This algorithm has same complexity to sub eld 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) sub eld attack for the power-of-two cyclotomic modulus. This extended sub eld attack has a similar asymptotic complexity to the previous sub eld attacks, but with smaller constant in the exponent term.

Category / Keywords: NTRU, Ideal Lattice, sub eld attack

Date: received 29 May 2017, last revised 29 May 2017

Contact author: cocomi11 at snu ac kr

Available format(s): PDF | BibTeX Citation

Version: 20170531:180742 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]