nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Random Self-reducibility of Ideal-SVP via Arakelov Random Walks

verfasst von : Koen de Boer, Léo Ducas, Alice Pellet-Mary, Benjamin Wesolowski

Erschienen in: Advances in Cryptology – CRYPTO 2020

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

Fixing a number field, the space of all ideal lattices, up to isometry, is naturally an abelian group, called the Arakelov class group. This fact, well known to number theorists, has so far not been explicitly used in the literature on lattice-based cryptography. Remarkably, the Arakelov class group is a combination of two groups that have already led to significant cryptanalytic advances: the class group and the unit torus.

In the present article, we show that the Arakelov class group has more to offer. We start with the development of a new versatile tool: we prove that, subject to the Riemann Hypothesis for Hecke L-functions, certain random walks on the Arakelov class group have a rapid mixing property. We then exploit this result to relate the average-case and the worst-case of the Shortest Vector Problem in ideal lattices. Our reduction appears particularly sharp: for Hermite-SVP in ideal lattices of certain cyclotomic number fields, it loses no more than a \(\tilde{O}(\sqrt{n})\) factor on the Hermite approximation factor.

Furthermore, we suggest that this rapid-mixing theorem should find other applications in cryptography and in algorithmic number theory.

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 Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP

Nächstes Kapitel Slide Reduction, Revisited—Filling the Gaps in SVP Approximation

We here refer to the full fledge version of the scheme from Gentry’s PhD Thesis, which differs from the scheme in [18], the latter having been broken already [6, 10, 11, 16].

The measure on the Arakelov class group is unique up to scaling – it is the Haar measure. By fixing the volume of \({{\,\mathrm{{Pic}}\,}}_K^0\) as in Lemma 2.3, we fix this scaling as well. We use then this particular scaling of the Haar measure for the integrals over the Arakelov class group.

Hecke characters of K are characters on the idèle class group of K. As the Arakelov class group is a specific quotient of the idèle class group [37, Ch. VI, pp. 360], the characters on the Arakelov class group are essentially Hecke characters whose kernel contains the kernel of the quotient map sending the idèle class group to the Arakelov class group.

We use the bound \(\beta _{\alpha }^{(\ell )} \le e^{-\alpha ^2}\) for \(\alpha \ge \sqrt{\ell }\).

In this bound on B one would expect an additional \(\log (\log ({{\,\mathrm{Vol}\,}}({{\,\mathrm{{Pic}}\,}}_K^0))\). But as it is bounded by \(\log (\log (\varDelta ))\) (see Lemma 2.3), it can be put in the hidden polylogarithmic factors.

One can observe that this randomization process outputs an ideal lattice instead of a fractional ideal. This will be solved by rounding the ideal lattice to a fractional lattice with close geometry.

Observe that contrary to the high level overview, the center c of the Gaussian distribution has been randomized (but it still holds that the sampled element v will be balanced). This is needed in Lemma 4.2, to show that the \(\text {Extract}_{{\varsigma },M}(\cdot )\) distributions are identical when applied to K-isomorphic ideal lattices.

The function \(E_{\varepsilon _1}\) plays the role of the exponential function, rounded to a near element of K.

Ajtai, M.: Generating hard instances of the short basis problem. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 1–9. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48523-6_1CrossRef

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

Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(4), 625–636 (1993). https://doi.org/10.1007/BF01445125MathSciNetCrossRefMATH

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, Part I. LNCS, vol. 10210, pp. 60–88. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_3CrossRefMATH

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

Biasse, J.-F., Song, F.: A polynomial time quantum algorithm for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: SODA (2016)

de Boer, K., Ducas, L., Pellet-Mary, A., Wesolowski, B.: Random self-reducibility of ideal-SVP via Arakelov random walks. Cryptology ePrint Archive, report 2020/297 (2020). https://eprint.iacr.org/2020/297

de Boer, K., Pagano, C.: Calculating the power residue symbol and Ibeta. In: ISSAC, vol. 68, pp. 923–934 (2017)

Buhler, J., Pomerance, C., Robertson, L.: Heuristics for class numbers of prime-power real cyclotomic fields. In: High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams, Fields Institute Communications, pp. 149–157. American Mathematical Society (2004)

10.

Campbell, P., Groves, M., Shepherd, D.: Soliloquy: a cautionary tale. In: ETSI 2nd Quantum-Safe Crypto Workshop (2014)

11.

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, Part II. LNCS, vol. 9666, pp. 559–585. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_20CrossRefMATH

12.

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, Part I. LNCS, vol. 10210, pp. 324–348. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_12CrossRef

13.

Deitmar, A., Echterhoff, S.: Principles of Harmonic Analysis, 2nd edn. Springer, Cham (2016)MATH

14.

Dobrowolski, E.: On a question of Lehmer and the number of irreducible factors of a polynomial. Acta Arithmetica 34(4), 391–401 (1979)MathSciNetCrossRef

15.

Ducas, L., Plançon, M., Wesolowski, B.: On the shortness of vectors to be found by the ideal-SVP quantum algorithm. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part I. LNCS, vol. 11692, pp. 322–351. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_12CrossRef

16.

Eisenträger, K., Hallgren, S., Kitaev, A., Song, F.: A quantum algorithm for computing the unit group of an arbitrary degree number field. In: STOC, pp. 293–302. ACM (2014)

17.

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

18.

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

19.

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). https://doi.org/10.1007/978-3-642-14623-7_7CrossRef

20.

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206 (2008)

21.

Iwaniec, H., Kowalski, E.: Analytic Number Theory. American Mathematical Society, Providence (2004)MATH

22.

Jao, D., Miller, S.D., Venkatesan, R.: Expander graphs based on GRH with an application to elliptic curve cryptography. J. Number Theory 129, 1491–1504 (2009)MathSciNetCrossRef

23.

Jetchev, D., Wesolowski, B.: On graphs of isogenies of principally polarizable abelian surfaces and the discrete logarithm problem. CoRR, abs/1506.00522 (2015)

24.

Kessler, V.: On the minimum of the unit lattice. Séminaire de Théorie des Nombres de Bordeaux 3(2), 377–380 (1991)MathSciNetCrossRef

25.

Klein, P.N.: Finding the closest lattice vector when it’s unusually close. In: SODA, pp. 937–941 (2000)

26.

Lee, C., Pellet-Mary, A., Stehlé, D., Wallet, A.: An LLL algorithm for module lattices. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part II. LNCS, vol. 11922, pp. 59–90. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34621-8_3CrossRef

27.

Louboutin, S.: Explicit bounds for residues of Dedekind zeta functions, values of l-functions at s=1, and relative class numbers. J. Number Theory 85, 263–282 (2000)MathSciNetCrossRef

28.

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

29.

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. J. ACM 60(6), 43:1–43:35 (2013). Preliminary version in Eurocrypt 2010MathSciNetCrossRef

30.

Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Comput. Complex. 16(4), 365–411 (2007). https://doi.org/10.1007/s00037-007-0234-9. Preliminary version in FOCS 2002MathSciNetCrossRefMATH

31.

Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007)MathSciNetCrossRef

32.

Miller, J.C.: Real cyclotomic fields of prime conductor and their class numbers. Math. Comput. 84(295), 2459–2469 (2015)MathSciNetCrossRef

33.

Miller, S.D., Stephens-Davidowitz, N.: Generalizations of Banaszczyk’s transference theorems and tail bound. arXiv preprint arXiv:1802.05708 (2018)

34.

Minkowski, H.: Gesammelte Abhandlungen. Chelsea, New York (1967)

35.

Miyake, T.: Modular Forms. Springer Monographs in Mathematics. Springer, Heidelberg (1989). https://doi.org/10.1007/3-540-29593-3CrossRefMATH

36.

Neukirch, J.: Algebraic Number Theory, vol. 322. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-662-03983-0dCrossRefMATH

37.

Neukirch, J., Schappacher, N.: Algebraic Number Theory. Grundlehren der mathematischen Wissenschaften. Springer, Heidelberg (2013)

38.

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

39.

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

40.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 1–40 (2009). Preliminary version in STOC 2005MathSciNetCrossRef

41.

Schoof, R.: Computing Arakelov class groups. In: Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, pp. 447–495. Cambridge University Press (2008)

42.

Shoup, V.: A new polynomial factorization algorithm and its implementation. J. Symb. Comput. 20(4), 363–397 (1995)MathSciNetCrossRef

43.

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

44.

von zur Gathen, J., Panario, D.: Factoring polynomials over finite fields: a survey. J. Symb. Comput. 31(1), 3–17 (2001)MathSciNetCrossRef

Titel: Random Self-reducibility of Ideal-SVP via Arakelov Random Walks
verfasst von: Koen de Boer
Léo Ducas
Alice Pellet-Mary
Benjamin Wesolowski
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2020
Print ISBN: 978-3-030-56879-5

Electronic ISBN: 978-3-030-56880-1

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-56880-1_9

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