This approach was originally sketched in a paper of Gentry and Szydlo at Eurocrypt'02 and there also attributed to Jonsson, Nguyen and Stern. However, because it does not apply for small moduli and hence NTRUEncrypt, it seems to have been forgotten. In this work, we resurrect this approach, fill some gaps, analyze and generalize it to any subfields and apply it to more recent schemes. We show that for significantly larger moduli ---a case we call overstretched--- the subfield attack is applicable and asymptotically outperforms other known attacks.
This directly affects the asymptotic security of the bootstrappable homomorphic encryption schemes LTV and YASHE which rely on a mildly overstretched NTRU assumption: the subfield lattice attack runs in sub-exponential time $2^{O(\lambda/\log^{1/3}\lambda)}$ invalidating the security claim of $2^{\Theta(\lambda)}$. The effect is more dramatic on GGH-like Multilinear Maps: this attack can run in polynomial time without *encodings of zero* nor the *zero-testing parameter*, yet requiring an additional quantum step to recover the secret parameters exactly.
We also report on practical experiments. Running LLL in dimension $512$ we obtain vectors that would have otherwise required running BKZ with block-size $130$ in dimension $8192$. Finally, we discuss concrete aspects of this attack, the condition on the modulus $q$ to guarantee full immunity, discuss countermeasures and propose open questions.
Category / Keywords: Subfield lattice attack, overstretched NTRU, FHE, Graded Encoding Schemes. Original Publication (with minor differences): IACR-CRYPTO-2016 Date: received 12 Feb 2016, last revised 4 Jul 2016 Contact author: ducas at cwi nl, shih bai@gmail com, martinralbrecht@googlemail com Available format(s): PDF | BibTeX Citation Version: 20160704:140228 (All versions of this report) Short URL: ia.cr/2016/127 Discussion forum: Show discussion | Start new discussion