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.
Category / Keywords: NTRU, Ideal Lattice, subfield attack Date: received 29 May 2017, last revised 29 Jun 2017 Contact author: cocomi11 at snu ac kr Available format(s): PDF | BibTeX Citation Version: 20170629:124619 (All versions of this report) Short URL: ia.cr/2017/484 Discussion forum: Show discussion | Start new discussion