**Comparison between Subfield and Straightforward Attacks on NTRU**

*Paul Kirchner and Pierre-Alain Fouque*

**Abstract: **Recently in two independent papers, Albrecht, Bai and Ducas and Cheon, Jeong and Lee presented two
very similar attacks, that allow to break NTRU with larger parameters and GGH Multinear Map without
zero encodings. They proposed an algorithm for recovering the NTRU secret key given the public key
which apply for large NTRU modulus, in particular to Fully Homomorphic Encryption schemes based on
NTRU. Hopefully, these attacks do not endanger the security of the NTRUE NCRYPT scheme, but shed new
light on the hardness of this problem. The basic idea of both attacks relies on decreasing the dimension
of the NTRU lattice using the multiplication matrix by the norm (resp. trace) of the public key in some
subfield instead of the public key itself. Since the dimension of the subfield is smaller, the dimension of
the lattice decreases, and lattice reduction algorithm will perform better.
Here, we revisit the attacks on NTRU and propose another variant that is simpler and outperforms both
of these attacks in practice. It allows to break several concrete instances of YASHE, a NTRU-based FHE
scheme, but it is not as efficient as the hybrid method of Howgrave-Graham on concrete parameters of
NTRU. Instead of using the norm and trace, we propose to use the multiplication by the public key in
some subring and show that this choice leads to better attacks. We
√ can then show that for power of two
cyclotomic fields, the time complexity is polynomialFinally, we show that, under
heuristics, straightforward lattice reduction is even more efficient, allowing to extend this result to fields
without non-trivial subfields, such as NTRU Prime. We insist that the improvement on the analysis applies
even for relatively small modulus ; though if the secret is sparse, it may not be the fastest attack. We also
derive a tight estimation of security for (Ring-)LWE and NTRU assumptions. when $q=2^{\Omega(\sqrt{n \log \log n})}$.

**Category / Keywords: **public-key cryptography / cryptanalysis,lattice techniques,number theory ,post quantum cryptography,NTRU

**Date: **received 19 Jul 2016

**Contact author: **paul kirchner at ens fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20160721:150011 (All versions of this report)

**Short URL: **ia.cr/2016/717

[ Cryptology ePrint archive ]