Projects per year
Abstract
The subfield attack exploits the presence of a subfield to solve overstretched versions of the NTRU assumption: norming the public key h down to a subfield may lead to an easier lattice problem and any sufficiently good solution may be lifted to a short vector in the full NTRUlattice. 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 subexponential time 2O(λ/log1/3λ)2O(λ/log1/3λ) invalidating the security claim of 2Θ(λ)2Θ(λ). The effect is more dramatic on GGHlike Multilinear Maps: this attack can run in polynomial time without encodings of zero nor the zerotesting 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 blocksize 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.
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 subexponential time 2O(λ/log1/3λ)2O(λ/log1/3λ) invalidating the security claim of 2Θ(λ)2Θ(λ). The effect is more dramatic on GGHlike Multilinear Maps: this attack can run in polynomial time without encodings of zero nor the zerotesting 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 blocksize 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.
Original language  English 

Title of host publication  Advances in Cryptology – CRYPTO 2016 
Subtitle of host publication  36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 1418, 2016, Proceedings, Part I 
Editors  Matthew Robshaw, Jonathan Katz 
Publisher  Springer 
Pages  153178 
Number of pages  26 
ISBN (Electronic)  9783662530184 
ISBN (Print)  9783662530177 
DOIs  
Publication status  Epub ahead of print  21 Jul 2016 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer Berlin Heidelberg 
Volume  9814 
ISSN (Print)  03029743 
Projects
 1 Finished

Multilinear Maps in Cryptography
Paterson, K.
Eng & Phys Sci Res Council EPSRC
31/01/14 → 30/01/17
Project: Research