nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

An LLL Algorithm for Module Lattices

verfasst von : Changmin Lee, Alice Pellet-Mary, Damien Stehlé, Alexandre Wallet

Erschienen in: Advances in Cryptology – ASIACRYPT 2019

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

The LLL algorithm takes as input a basis of a Euclidean lattice, and, within a polynomial number of operations, it outputs another basis of the same lattice but consisting of rather short vectors. We provide a generalization to R-modules contained in \(K^n\) for arbitrary number fields K and dimension n, with R denoting the ring of integers of K. Concretely, we introduce an algorithm that efficiently finds short vectors in rank-n modules when given access to an oracle that finds short vectors in rank-2 modules, and an algorithm that efficiently finds short vectors in rank-2 modules given access to a Closest Vector Problem oracle for a lattice that depends only on K. The second algorithm relies on quantum computations and its analysis is heuristic.

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 New Code-Based Privacy-Preserving Cryptographic Constructions

Nächstes Kapitel Order-LWE and the Hardness of Ring-LWE with Entropic Secrets

See https://csrc.nist.gov/projects/post-quantum-cryptography.

Observe that even if complex conjugation might not be well defined over K (i.e., the element \(\bar{x}\) might not be in K even if x is), it is however always defined over \(K_\mathbb {R}\). In this article, complex conjugation will only be used on elements of \(K_\mathbb {R}\), and we make no assumption that K should be stable by conjugation.

The vectors \(\mathbf {b}_j\)’s are said to be \(K_\mathbb {R}\)-linearly independent if and only if there is no non-trivial ways to write the zero vector as a \(K_\mathbb {R}\)-linear combination of the \(\mathbf {b}_j\)’s. Because \(K_\mathbb {R}\) is a ring and not a field, this definition is stronger than requiring that none of the \(\mathbf {b}_j\)’s is in the span of the others.

Note that ideal scaling and size-reduction have been suggested in [FS10, Se. 4.1], but without a complexity analysis (polynomial complexity was claimed but not proved).

[AD17]

Albrecht, M.R., Deo, A.: Large modulus Ring-LWE \(\ge \) Module-LWE. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 267–296. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_10CrossRef

[Ajt96]

Ajtai, M.: Generating hard instances of lattice problems. In: STOC (1996)

[Ajt98]

Ajtai, M.: The shortest vector problem in \(l_2\) is NP-hard for randomized reductions. In: STOC (1998)

[BEF+17]

Biasse, J.-F., Espitau, T., Fouque, P.-A., Gélin, A., Kirchner, P.: Computing generator in cyclotomic integer rings. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 60–88. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_3CrossRefMATH

[BF14]

Biasse, J.-F., Fieker, C.: Subexponential class group and unit group computation in large degree number fields. LMS J. Comput. Math. 17, 385–403 (2014)MathSciNetCrossRef

[BFH17]

Biasse, J.-F., Fieker, C., Hofmann, T.: On the computation of the HNF of a module over the ring of integers of a number field. J. Symb. Comput. 80, 581–615 (2017)MathSciNetCrossRef

[BGV14]

Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. ToCT 6, 13 (2014)MathSciNetCrossRef

[BP91]

Bosma, W., Pohst, M.: Computations with finitely generated modules over Dedekind domains. In: ISSAC (1991)

[BS96]

Bach, E., Shallit, J.O.: Algorithmic Number Theory: Efficient Algorithms. MIT Press, Cambridge (1996)MATH

[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: SODA (2016)

[CDW17]

Cramer, R., Ducas, L., Wesolowski, B.: Short stickelberger class relations and application to ideal-SVP. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 324–348. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_12CrossRef

[Cer05]

Cerri, J.-P.: Spectres euclidiens et inhomogènes des corps de nombres. Ph.D. thesis, Université Henri Poincaré, Nancy (2005)

[Coh96]

Cohen, H.: Hermite and Smith normal form algorithms over Dedekind domains. Math. Comput. 65, 1681–1699 (1996)MathSciNetCrossRef

[Fie97]

Fieker, C.: Über relative Normgleichungen in älgebraischen Zahlkörpern. Ph.D. thesis, TU Berlin (1997)

[FP96]

Fieker, C., Pohst, M.E.: On lattices over number fields. In: Cohen, H. (ed.) ANTS 1996. LNCS, vol. 1122, pp. 133–139. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61581-4_48CrossRefMATH

[FP06]

Fieker, C., Pohst, M.E.: Dependency of units in number fields. Math. Comput. 75, 1507–1518 (2006)MathSciNetCrossRef

[FS10]

Fieker, C., Stehlé, D.: Short bases of lattices over number fields. In: Hanrot, G., Morain, F., Thomé, E. (eds.) ANTS 2010. LNCS, vol. 6197, pp. 157–173. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14518-6_15CrossRefMATH

[GLM09]

Gan, Y.H., Ling, C., Mow, W.H.: Complex lattice reduction algorithm for low-complexity full-diversity MIMO detection. IEEE Trans. Signal Process. 57, 2701–2710 (2009)MathSciNetCrossRef

[Hop98]

Hoppe, A.: Normal forms over Dedekind domains, efficient implementation in the computer algebra system KANT. Ph.D. thesis, TU Berlin (1998)

[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). https://doi.org/10.1007/BFb0054868CrossRef

[Kan87]

Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12, 415–440 (1987)MathSciNetCrossRef

[KL17]

Kim, Taechan, Lee, Changmin: Lattice reductions over Euclidean rings with applications to cryptanalysis. In: O’Neill, Máire (ed.) IMACC 2017. LNCS, vol. 10655, pp. 371–391. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71045-7_19CrossRef

[Laa16]

Laarhoven, T.: Sieving for closest lattice vectors (with preprocessing). In: Avanzi, R., Heys, H. (eds.) SAC 2016. LNCS, vol. 10532, pp. 523–542. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69453-5_28CrossRef

[Lez14]

Lezowski, P.: Computation of the euclidean minimum of algebraic number fields. Math. Comput. 83(287), 1397–1426 (2014)MathSciNetCrossRef

[LLL82]

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

[LM06]

Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 144–155. Springer, Heidelberg (2006). https://doi.org/10.1007/11787006_13CrossRef

[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). https://doi.org/10.1007/978-3-642-13190-5_1CrossRef

[LPSW19]

Lee, C., Pellet-Mary, A., Stehlé, D., Wallet, A.: An LLL algorithm for module lattices (full version). Cryptology ePrint Archive (2019)

[LS15]

Langlois, A., Stehlé, D.: Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr. 75, 565–599 (2015)MathSciNetCrossRef

[MG02]

Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: A Cryptographic Perspective. Kluwer Academic Press, Dordrecht (2002)CrossRef

[Mic01]

Micciancio, D.: The hardness of the closest vector problem with preprocessing. Trans. Inf. Theory 47, 1212–1215 (2001)MathSciNetCrossRef

[Nap96]

Napias, H.: A generalization of the LLL-algorithm over Euclidean rings or orders. J. théorie des nombres de Bordeaux 8, 387–396 (1996)MathSciNetCrossRef

[Neu99]

Neukirch, J.: Algebraic number theory. In: Grundlehren der Mathematischen Wissenschaften, vol. 322. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-662-03983-0CrossRef

[O’M63]

O’Meara, O.T.: Introduction to Quadratic Forms. Springer, Heidelberg (1963). https://doi.org/10.1007/978-3-642-62031-7CrossRefMATH

[PHS19]

Pellet-Mary, A., Hanrot, G., Stehlé, D.: Approx-SVP in ideal lattices with pre-processing. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 685–716. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_24CrossRef

[PR06]

Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 145–166. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_8CrossRef

[Reg09]

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56, 34 (2009)MathSciNetCrossRef

[RSW18]

Rosca, M., Stehlé, D., Wallet, A.: On the Ring-LWE and Polynomial-LWE problems. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 146–173. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_6CrossRef

[SE94]

Schnorr, C.-P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181–199 (1994)MathSciNetCrossRef

[SMSV14]

Morel, I., Stehlé, D., Villard, G.: LLL Reducing with the most significant bits. In: ISSAC (2014)

[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). https://doi.org/10.1007/978-3-642-10366-7_36CrossRef

Titel: An LLL Algorithm for Module Lattices
verfasst von: Changmin Lee
Alice Pellet-Mary
Damien Stehlé
Alexandre Wallet
Verlag: Springer International Publishing
Buch: Advances in Cryptology – ASIACRYPT 2019
Print ISBN: 978-3-030-34620-1

Electronic ISBN: 978-3-030-34621-8

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-34621-8_3

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"

Premium Partner