A Subfield Lattice Attack on Overstretched NTRU Assumptions : Cryptanalysis of Some FHE and Graded Encoding Schemes. / Albrecht, Martin; Bai, Shi; Ducas, Leo.

Advances in Cryptology – CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I. ed. / Matthew Robshaw; Jonathan Katz. Springer, 2016. p. 153-178 (Lecture Notes in Computer Science; Vol. 9814).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

E-pub ahead of print

Standard

A Subfield Lattice Attack on Overstretched NTRU Assumptions : Cryptanalysis of Some FHE and Graded Encoding Schemes. / Albrecht, Martin; Bai, Shi; Ducas, Leo.

Advances in Cryptology – CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I. ed. / Matthew Robshaw; Jonathan Katz. Springer, 2016. p. 153-178 (Lecture Notes in Computer Science; Vol. 9814).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Albrecht, M, Bai, S & Ducas, L 2016, A Subfield Lattice Attack on Overstretched NTRU Assumptions: Cryptanalysis of Some FHE and Graded Encoding Schemes. in M Robshaw & J Katz (eds), Advances in Cryptology – CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9814, Springer, pp. 153-178. https://doi.org/10.1007/978-3-662-53018-4_6

APA

Albrecht, M., Bai, S., & Ducas, L. (2016). A Subfield Lattice Attack on Overstretched NTRU Assumptions: Cryptanalysis of Some FHE and Graded Encoding Schemes. In M. Robshaw, & J. Katz (Eds.), Advances in Cryptology – CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I (pp. 153-178). (Lecture Notes in Computer Science; Vol. 9814). Springer. https://doi.org/10.1007/978-3-662-53018-4_6

Vancouver

Albrecht M, Bai S, Ducas L. A Subfield Lattice Attack on Overstretched NTRU Assumptions: Cryptanalysis of Some FHE and Graded Encoding Schemes. In Robshaw M, Katz J, editors, Advances in Cryptology – CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I. Springer. 2016. p. 153-178. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-662-53018-4_6

Author

Albrecht, Martin ; Bai, Shi ; Ducas, Leo. / A Subfield Lattice Attack on Overstretched NTRU Assumptions : Cryptanalysis of Some FHE and Graded Encoding Schemes. Advances in Cryptology – CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I. editor / Matthew Robshaw ; Jonathan Katz. Springer, 2016. pp. 153-178 (Lecture Notes in Computer Science).

BibTeX

@inproceedings{82c46e02d7a7441e8fdeaabf7a8995a4,
title = "A Subfield Lattice Attack on Overstretched NTRU Assumptions: Cryptanalysis of Some FHE and Graded Encoding Schemes",
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 NTRU-lattice. This approach was originally sketched in a paper of Gentry and Szydlo at Eurocrypt{\textquoteright}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 2O(λ/log1/3λ)2O(λ/log1/3⁡λ) invalidating the security claim of 2Θ(λ)2Θ(λ). 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.",
author = "Martin Albrecht and Shi Bai and Leo Ducas",
year = "2016",
month = jul,
day = "21",
doi = "10.1007/978-3-662-53018-4_6",
language = "English",
isbn = "978-3-662-53017-7",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "153--178",
editor = "Matthew Robshaw and Jonathan Katz",
booktitle = "Advances in Cryptology – CRYPTO 2016",

}

RIS

TY - GEN

T1 - A Subfield Lattice Attack on Overstretched NTRU Assumptions

T2 - Cryptanalysis of Some FHE and Graded Encoding Schemes

AU - Albrecht, Martin

AU - Bai, Shi

AU - Ducas, Leo

PY - 2016/7/21

Y1 - 2016/7/21

N2 - 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 NTRU-lattice. 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 2O(λ/log1/3λ)2O(λ/log1/3⁡λ) invalidating the security claim of 2Θ(λ)2Θ(λ). 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.

AB - 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 NTRU-lattice. 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 2O(λ/log1/3λ)2O(λ/log1/3⁡λ) invalidating the security claim of 2Θ(λ)2Θ(λ). 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.

U2 - 10.1007/978-3-662-53018-4_6

DO - 10.1007/978-3-662-53018-4_6

M3 - Conference contribution

SN - 978-3-662-53017-7

T3 - Lecture Notes in Computer Science

SP - 153

EP - 178

BT - Advances in Cryptology – CRYPTO 2016

A2 - Robshaw, Matthew

A2 - Katz, Jonathan

PB - Springer

ER -