Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Key-Alternating Ciphers and Key-Length Extension: Exact Bounds and Multi-user Security Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

A Subfield Lattice Attack on Overstretched NTRU Assumptions

Cryptanalysis of Some FHE and Graded Encoding Schemes

verfasst von : Martin Albrecht, Shi Bai, Léo Ducas

Erschienen in: Advances in Cryptology – CRYPTO 2016

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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’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^{\varTheta (\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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel EWCDM: An Efficient, Beyond-Birthday Secure, Nonce-Misuse Resistant MAC
Nächstes Kapitel A Practical Cryptanalysis of the Algebraic Eraser
Fußnoten
1
Volume, dimension and length of unusually short vectors.
 
2
The NTRU problem has also been recently been referred to as DSPR (Decisional Small Polynomial Ratio), but we prefer its historical name for fair attribution of this invention.
 
3
A preliminary version of this work qualified the attack considered in this work as new. We are grateful to John Schanck for pointing us to this prior art.
 
4
It was recently shown that these attacks were in fact made possible by an improper choice of a very skewed error distributions leading to several noise-free linear equations [CIV16, Pei16].
 
5
For example, 7 is prime, so \(\mathbb Q(\omega _7)\) admits no cyclotomic number fields as proper subfields, yet it admits two proper subfields: \(\mathbb Q(\omega _7 + \bar{\omega }_7)\) of degree 3 and \(\mathbb Q(\omega _7 + \omega ^2_7 + \omega ^4_7)\) of degree 2.
 
6
Or equivalently, the size of a minimal sets of \(\mathbb Z\)-generators, since \(\mathbb Z\) is a principal ideal domain.
 
7
Non-principal ideals of \(\mathbb K\) being a counter-example.
 
8
The attack is attributed to Steven Galbraith in [ACLL15].
 
9
Note that the subfield lattice attack may be tweaked to obtain a triplet \(u (a_0, a_1 ,a_2)\) (or more) increasing the probability to recover \(\langle u\rangle \).
 
10
Asymptotically, the natural idea of replacing LLL by slightly stronger lattice reduction does not seems to help, but should help in practice. The quasi-polynomial factor relates to a number theoretic heuristic. See Sect. 7.6 of [GGH13a].
 
11
Multiplication of two small elements remains reasonably small.
 
12
A safe prime p is an odd prime such that \((p-1)/2 \) is also a prime. The terminology relates to weaknesses in RSA and Discrete Logarithm Problem introduced by the smoothness of \(p-1\) [Pol74].
 
Literatur
[ABC+]
[ACLL15]
Albrecht, M.R., Cocis, C., Laguillaumie, F., Langlois, A.: Implementing candidate graded encoding schemes from ideal lattices. In: Iwata, T., et al. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 752–775. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48800-3_​31 CrossRef
[BCLvV16]
[Ber14]
[BF14]
Biasse, J.-F., Fieker, C.: Subexponential class group, unit group computation in large degree number fields. LMS J. Comput. Math. 17(Suppl. A), 385–403 (2014)MathSciNetCrossRefMATH
[Bia14]
Biasse, J.-F.: Subexponential time relations in the class group of large degree number fields. Adv. Math. Commun. 8(4), 407–425 (2014)MathSciNetCrossRefMATH
[BLLN13]
Bos, J.W., Lauter, K., Loftus, J., Naehrig, M.: Improved security for a ring-based fully homomorphic encryption scheme. In: Stam, M. (ed.) IMACC 2013. LNCS, vol. 8308, pp. 45–64. Springer, Heidelberg (2013)CrossRef
[BS16]
Biasse, J.-F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) (2016)
[BV11]
Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky, R. (ed.) 52nd FOCS, pp. 97–106. IEEE Computer Society Press, October 2011
[CDPR16]
Cramer, R., Ducas, L., Peikert, C., Regev, O.: Recovering short generators of principal ideals in cyclotomic rings. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 559–585. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49896-5_​20 CrossRef
[CG13]
Canetti, R., Garay, J.A. (eds.): CRYPTO 2013. LNCS, vol. 8042. Springer, Heidelberg (2013)MATH
[CGS14]
[CIV16]
Castryck, W., Iliashenko, I., Vercauteren, F.: Provably weak instances of ring-LWE revisited. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 147–167. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49890-3_​6 CrossRef
[CJL16]
Cheon, J.H., Jeong, J., Lee, C.: An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without an encoding of zero. Cryptology ePrint Archive, Report 2016/139 (2016). http://​eprint.​iacr.​org/​
[CLS15]
[CLT13]
Coron, J.-S., Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Canetti, R., Garay, J.A. (eds.) [CG13], pp. 476–493
[CN11]
Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011)CrossRef
[CS97]
Coppersmith, D., Shamir, A.: Lattice attacks on NTRU. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 52–61. Springer, Heidelberg (1997)
[CS15]
[DDLL13]
Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal gaussians. In: Canetti, R., Garay, J.A. (eds.) [CG13], pp. 40–56
[Dev15]
[DHS15]
[EHKS14]
Eisenträger, K., Hallgren, S., Kitaev, A., Song, F.: A quantum algorithm for computing the unit group of an arbitrary degree number field. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 293–302. ACM (2014)
[EHL14]
Eisenträger, K., Hallgren, S., Lauter, K.: Weak instances of PLWE. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 183–194. Springer, Heidelberg (2014)CrossRef
[ELOS15]
Elias, Y., Lauter, K.E., Ozman, E., Stange, K.E.: Provably weak instances of ring-LWE. In: Gennaro, R., Robshaw, M. (eds.) [GR15], pp. 63–92
[FM14]
[Gen01]
Gentry, C.: Key recovery and message attacks on NTRU-composite. In: Pfitzmann, B. (ed.) [Pfi01], pp. 182–194
[GGH13a]
Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013)CrossRef
[GGH+13b]
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th FOCS, pp. 40–49. IEEE Computer Society Press, October 2013
[GN08]
Gama, N., Nguyen, P.Q.: Finding short lattice vectors within Mordell’s inequality. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 207–216. ACM Press, May 2008
[GR15]
Gennaro, R., Robshaw, M. (eds.): CRYPTO 2015. LNCS, vol. 9215. Springer, Heidelberg (2015)MATH
[GS02]
Gentry, C., Szydlo, M.: Cryptanalysis of the revised NTRU signature scheme. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 299–320. Springer, Heidelberg (2002)CrossRef
[HG07]
Howgrave-Graham, N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 150–169. Springer, Heidelberg (2007)CrossRef
[HHGP+03]
Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: NTRUSIGN: digital signatures using the NTRU lattice. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 122–140. Springer, Heidelberg (2003)CrossRef
[HJ15]
[HPS96]
[HPS98]
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)CrossRef
[HPS01]
Hoffstein, J., Pipher, J., Silverman, J.H.: NSS: an NTRU lattice-based signature scheme. In: Pfitzmann, B. (ed.) [Pfi01], pp. 211–228
[HPS11]
Hanrot, G., Pujol, X., Stehlé, D.: Analyzing blockwise lattice algorithms using dynamical systems. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 447–464. Springer, Heidelberg (2011)CrossRef
[HPS+15]
[HSW06]
Hoffstein, J., Silverman, J.H., Whyte, W.: Meet-in-the-middle attack on an ntru private key, 2006. Technical report, NTRU Cryptosystems, Report #04, July 2006. http://​www.​ntru.​com
[HT15]
Hauteville, A., Tillich, J.-P.: New algorithms for decoding in the rank metric and an attack on the LRPC cryptosystem. In: IEEE International Symposium on Information Theory, ISIT 2015, pp. 2747–2751 (2015)
[KF15]
Kirchner, P., Fouque, P.-A.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: Gennaro, R., Robshaw, M. (eds.) [GR15], pp. 43–62
[LJ14]
Löndahl, C., Johansson, T.: Improved algorithms for finding low-weight polynomial multiples in \(f_{2}[x]\) and some cryptographic applications. Des. Codes Crypt. 73(2), 625–640 (2014)CrossRefMATH
[LLL82]
Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982)MathSciNetCrossRefMATH
[LN14]
Lepoint, T., Naehrig, M.: A comparison of the homomorphic encryption schemes \(\sf {FV}\) and \(\sf {YASHE}\). In: Pointcheval, D., Vergnaud, D. (eds.) AFRICACRYPT. LNCS, vol. 8469, pp. 318–335. Springer, Heidelberg (2014)CrossRef
[Loi14]
Loidreau, P.: On cellular codes and their cryptographic applications. In: ACCT, Fourteenth International Workshop on Algebraic and Combinatorial Coding Theory, pp. 234–239 (2014)
[Lov87]
Lovasz, L.: An Algorithmic Theory of Numbers, Graphs and Convexity. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia (1987)MATH
[LPR10]
Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010)CrossRef
[LS14]
Lenstra, H.W., Silverberg, A.: Revisiting the Gentry-Szydlo algorithm. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 280–296. Springer, Heidelberg (2014)CrossRef
[LSS14]
Langlois, A., Stehlé, D., Steinfeld, R.: GGHLite: more efficient multilinear maps from ideal lattices. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 239–256. Springer, Heidelberg (2014)CrossRef
[LTV12]
López-Alt, A., Tromer, E., Vaikuntanathan, V.: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Karloff, H.J., Pitassi, T. (eds.) 44th ACM STOC, pp. 1219–1234. ACM Press, May 2012
[Mic02]
Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. In: 43rd FOCS, pp. 356–365. IEEE Computer Society Press, November 2002
[Pei16]
[Pfi01]
Pfitzmann, B. (ed.): EUROCRYPT 2001. LNCS, vol. 2045. Springer, Heidelberg (2001)MATH
[Pol74]
Pollard, J.M.: Theorems on factorization and primality testing. In: Math-ematical Proceedings of the Cambridge Philosophical Society, vol. 76, no. 03, pp. 521–528 (1974)
[Sam70]
Samuel, P.: Algebraic Theory of Numbers. Hermann, Paris (1970)MATH
[Sch87]
[Sit10]
Sittinger, B.D.: The probability that random algebraic integers are relatively r-prime. J. Number Theory 130(1), 164–171 (2010)MathSciNetCrossRefMATH
[SS11]
Stehlé, D., Steinfeld, R.: Making NTRU as secure as worst-case problems over ideal lattices. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 27–47. Springer, Heidelberg (2011)CrossRef
[SSTX09]
Stehlé, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 617–635. Springer, Heidelberg (2009)CrossRef
[Was97]
Washington, L.C.: Introduction to Cyclotomic Fields. Graduate Texts in Mathematics. Springer, New York (1997)CrossRefMATH
Metadaten
Titel
A Subfield Lattice Attack on Overstretched NTRU Assumptions
verfasst von
Martin Albrecht
Shi Bai
Léo Ducas
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – CRYPTO 2016

Print ISBN: 978-3-662-53017-7

Electronic ISBN: 978-3-662-53018-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53018-4_6

Premium Partner

    Bildnachweise