nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Short Generators Without Quantum Computers: The Case of Multiquadratics

verfasst von : Jens Bauch, Daniel J. Bernstein, Henry de Valence, Tanja Lange, Christine van Vredendaal

Erschienen in: Advances in Cryptology – EUROCRYPT 2017

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Finding a short element g of a number field, given the ideal generated by g, is a classic problem in computational algebraic number theory. Solving this problem recovers the private key in cryptosystems introduced by Gentry, Smart–Vercauteren, Gentry–Halevi, Garg–Gentry–Halevi, et al. Work over the last few years has shown that for some number fields this problem has a surprisingly low post-quantum security level. This paper shows, and experimentally verifies, that for some number fields this problem has a surprisingly low pre-quantum security level.

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 Revisiting Lattice Attacks on Overstretched NTRU Parameters

Nächstes Kapitel Computing Generator in Cyclotomic Integer Rings

Nur mit Berechtigung zugänglich

We assume some familiarity with algebraic number theory, although we also review some background as appropriate.

Beware that the analysis in [17, p. 4] is incomplete: the analysis correctly states that the secret key is short, but fails to state that the textbook basis for the cyclotomic units is a very good basis; LLL would not be able to find the secret key starting from a bad basis. A detailed analysis of the basis appeared in a followup paper [22] by Cramer, Ducas, Peikert, and Regev.

The dimensions we used in these experiments are below the \(N=8192\) recommended by Smart and Vercauteren for \(2^{100}\) security against standard lattice-basis-reduction attacks, specifically BKZ. However, the Smart–Vercauteren analysis shows that BKZ scales quite poorly as N increases; see Appendix A. Our attack should still be feasible for \(N=8192\), and a back-of-the-envelope calculation suggests that \(N\approx 2^{20}\) is required for \(2^{100}\) security against our attack.

Abel, C.S.: Ein Algorithmus zur Berechnung der Klassenzahl und des Regulators reell-quadratischer Ordnungen. Ph.D. thesis, Universität des Saarlandes, Saarbrücken, Germany (1994)

Adleman, L.M.: Factoring numbers using singular integers. In: STOC 1991, pp. 64–71 (1991)

Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. USENIX Security 2016, pp. 327–343 (2016)

Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986)MathSciNetCrossRefMATH

Barbulescu, R., Gaudry, P., Joux, A., Thomé, E.: A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 1–16. Springer, Heidelberg (2014). doi:10.1007/978-3-642-55220-5_1 CrossRef

Belabas, K.: Topics in computational algebraic number theory. J. de Théorie des Nombres de Bordeaux 16(1), 19–63 (2004)MathSciNetCrossRefMATH

Biasse, J.-F., Fieker, C.: Improved techniques for computing the ideal class group and a system of fundamental units in number fields. In: ANTS-IX. Open Book Series, vol. 1, pp. 113–133. Mathematical Sciences Publishers (2012)

Biasse, J.-F., Jacobson Jr., M.J., Silvester, A.K.: Security estimates for quadratic field based cryptosystems. In: Steinfeld, R., Hawkes, P. (eds.) ACISP 2010. LNCS, vol. 6168, pp. 233–247. Springer, Heidelberg (2010). doi:10.1007/978-3-642-14081-5_15 CrossRef

Biasse, J.-F., Song, F.: On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in \(\mathbb{Q}(\zeta _{p^n})\) (2015). http://cacr.uwaterloo.ca/techreports/2015/cacr2015-12.pdf

10.

Biasse, J.-F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: SODA 2016, pp. 893–902 (2016)

11.

Biehl, I., Buchmann, J.: Algorithms for quadratic orders. In: Mathematics of Computation 1943–1993: A Half-century of Computational Mathematics, pp. 425–451. AMS (1994)

12.

Bos, J.W., Costello, C., Naehrig, M., Stebila, D.: Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In: IEEE S&P 2015, pp. 553–570 (2015)

13.

Buchmann, J., Maurer, M., Möller, B.: Cryptography based on number fields with large regulator. J. de Théorie des Nombres de Bordeaux 12(2), 293–307 (2000)MathSciNetCrossRefMATH

14.

Buchmann, J., Vollmer, U.: Binary Quadratic Forms: An Algorithmic Approach. Algorithms and Computation in Mathematics. Springer, Heidelberg (2007)CrossRefMATH

15.

Buchmann, J.A.: A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. In: Séminaire de Théorie des Nombres, Paris 1988–1989, pp. 27–41 (1990)

16.

Buhler, J.P., Lenstra Jr., H.W., Pomerance, C.: Factoring integers with the number field sieve. In: Lenstra, A.K., Lenstra, H.W. (eds.) Algorithms and Computation in Mathematics. Springer, Heidelberg (2007)

17.

Campbell, P., Groves, M., Shepherd, D.: Soliloquy: a cautionary tale (2014). http://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves_Annex.pdf

18.

Cheon, J.H., Han, K., Lee, C., Ryu, H., Stehlé, D.: Cryptanalysis of the multilinear map over the integers. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 3–12. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46800-5_1

19.

Cohen, H.: A Course in Computational Algebraic Number Theory. Springer, Heidelberg (1993)CrossRefMATH

20.

Cohen, H.: Advanced Topics in Computational Number Theory. Springer, New York (1999)

21.

Coron, J.-S., Lepoint, T., Tibouchi, M.: New multilinear maps over the integers. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 267–286. Springer, Heidelberg (2015). doi:10.1007/978-3-662-47989-6_13 CrossRef

22.

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

23.

The Sage Developers: SageMath, the Sage Mathematics Software System (Version 7.5.1) (2017). http://www.sagemath.org

24.

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, Cham (2014). doi:10.1007/978-3-319-13051-4_11 CrossRef

25.

Galbraith, S.D.: Mathematics of Public Key Cryptography. Cambridge University Press, Cambridge (2012)CrossRefMATH

26.

Galbraith, S.D., Gaudry, P.: Recent progress on the elliptic curve discrete logarithm problem. Des. Codes Cryptogr. 78(1), 51–72 (2016)MathSciNetCrossRefMATH

27.

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). doi:10.1007/978-3-642-38348-9_1 CrossRef

28.

Gentry, C.: A fully homomorphic encryption scheme. Ph.D. thesis, Stanford University (2009). https://crypto.stanford.edu/craig

29.

C. Gentry.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169–178 (2009)

30.

Gentry, C.: Toward basing fully homomorphic encryption on worst-case hardness. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 116–137. Springer, Heidelberg (2010). doi:10.1007/978-3-642-14623-7_7 CrossRef

31.

Gentry, C., Halevi, S.: Implementing Gentry’s fully-homomorphic encryption scheme. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 129–148. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20465-4_9 CrossRef

32.

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). doi:10.1007/BFb0054868 CrossRef

33.

Kim, T., Barbulescu, R.: Extended tower number field sieve: a new complexity for the medium prime case. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 543–571. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53018-4_20 CrossRef

34.

Kubota, T.: Über den bizyklischen biquadratischen Zahlkörper. Nagoya Math. J. 10, 65–85 (1956)MathSciNetCrossRefMATH

35.

Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)MathSciNetCrossRefMATH

36.

Lenstra, H.W.: Solving the Pell equation. Notices Amer. Math. Soc. 49, 182–192 (2002)MathSciNetMATH

37.

Pohst, M.: A modification of the LLL reduction algorithm. J. Symb. Comput. 4, 123–127 (1987)MathSciNetCrossRefMATH

38.

Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420–443. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13013-7_25 CrossRef

39.

van der Kallen, W.: Complexity of an extended lattice reduction algorithm (1998). http://www.staff.science.uu.nl/~kalle101/complexity.pdf

40.

Vollmer, U.: Asymptotically fast discrete logarithms in quadratic number fields. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 581–594. Springer, Heidelberg (2000). doi:10.1007/10722028_39 CrossRef

41.

Vollmer, U.: Rigorously analyzed algorithms for the discrete logarithm problem in quadratic number fields. Ph.D. thesis, Technische Universität, Darmstadt (2004)

42.

Wada, H.: On the class number and the unit group of certain algebraic number fields. J. Fac. Sci. Univ. Tokyo Sect. I 13(13), 201–209 (1966)MathSciNetMATH

43.

Williams, H.C.: Solving the Pell equation. In: Number theory for the millennium III, pp. 397–435. A K Peters (2002)

Titel: Short Generators Without Quantum Computers: The Case of Multiquadratics
verfasst von: Jens Bauch
Daniel J. Bernstein
Henry de Valence
Tanja Lange
Christine van Vredendaal
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2017
Print ISBN: 978-3-319-56619-1

Electronic ISBN: 978-3-319-56620-7

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-56620-7_2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"