nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

On the Shortness of Vectors to Be Found by the Ideal-SVP Quantum Algorithm

verfasst von : Léo Ducas, Maxime Plançon, Benjamin Wesolowski

Erschienen in: Advances in Cryptology – CRYPTO 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 hardness of finding short vectors in ideals of cyclotomic number fields (hereafter, Ideal-SVP) can serve as a worst-case assumption for numerous efficient cryptosystems, via the average-case problems Ring-SIS and Ring-LWE. For a while, it could be assumed the Ideal-SVP problem was as hard as the analog problem for general lattices (SVP), even when considering quantum algorithms.

But in the last few years, a series of works has lead to a quantum algorithm for Ideal-SVP that outperforms what can be done for general SVP in certain regimes. More precisely, it was demonstrated (under certain hypotheses) that one can find in quantum polynomial time a vector longer by a factor at most \(\alpha = \exp ({\widetilde{O}(n^{1/2})})\) than the shortest non-zero vector in a cyclotomic ideal lattice, where n is the dimension.

In this work, we explore the constants hidden behind this asymptotic claim. While these algorithms have quantum steps, the steps that impact the approximation factor \(\alpha \) are entirely classical, which allows us to estimate it experimentally using only classical computing. Moreover, we design heuristic improvements for those steps that significantly decrease the hidden factors in practice. Finally, we derive new provable effective lower bounds based on volumetric arguments.

This study allows to predict the crossover point with classical lattice reduction algorithms, and thereby determine the relevance of this quantum algorithm in any cryptanalytic context. For example we predict that this quantum algorithm provides shorter vectors than BKZ-300 (roughly the weakest security level of NIST lattice-based candidates) for cyclotomic rings of rank larger than about 24000.

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 Results on Modular Inversion Hidden Number Problem and Inversive Congruential Generator

Nächstes Kapitel Proofs of Replicated Storage Without Timing Assumptions

Nur mit Berechtigung zugänglich

For cyclotomic ideal lattices, approx-SVP and approx-SIVP are trivially equivalent.

In the rest of this work, we prefer to use the so called Hermite factor \(\eta \) instead of the approximation factor \(\alpha \); this is justified in Remark 1.

To verify that \(\Vert \cdot \Vert _{+\infty }\) is indeed an asymmetric norm over H, we recall that vector space H is \(\{x \in \mathbb {R}^d | \sum x_i = 0\}\): there is always one coordinate that is positive.

Unfortunately, while proved polynomial time, the algorithms of [EHKS14, BS16] have, to our knowledge not been the subject of refined complexity analysis. But already, one can note that the lower bound we suggest is far from tight, considering the overheads of running LLL quantumly rather than classically, and this, many times.

We recall that this bound is plausibly not tight, that is, even a perfect CVP oracle may not be able to reach it; see Remark 4.

The denominator \(2^{n/2-1}\) may not be standard in the litterature, and is due to our definition of the logarithmic embedding. Indeed since the field at hand is totally complex, we only use one embedding from each pair of conjugate embeddings.

[AC49]

Ankeny, N.C., Chowla, S.: The class number of the cyclotomic field. Proc. Natl. Acad. Sci. 35(9), 529–532 (1949)MathSciNetCrossRef

[ACD+18]

Albrecht, M.R., et al.: Estimate all the \(\{\)LWE, NTRU\(\}\) schemes! (2018). https://doi.org/10.1007/978-3-319-98113-0_19

[ADH+19]

Albrecht, M.R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E.W., Stevens, M.: The general sieve kernel and new records in lattice reduction. Cryptology ePrint Archive, Report 2019/089 (2019). https://eprint.iacr.org/2019/089, https://doi.org/10.1007/978-3-030-17656-3_25CrossRef

[Ajt99]

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

[Bab86]

Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986). Preliminary version in STACS 1985MathSciNetCrossRef

[BCLvV17]

Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C.: NTRU prime: reducing attack surface at low cost. In: Adams, C., Camenisch, J. (eds.) SAC 2017. LNCS, vol. 10719, pp. 235–260. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-72565-9_12CrossRef

[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: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 893–902. SIAM (2016)

[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). https://doi.org/10.1007/978-3-662-49896-5_20CrossRefMATH

[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

[CGS14]

Campbell, P., Groves, M., Shepherd, D.: Soliloquy: a cautionary tale. In: ETSI 2nd Quantum-Safe Crypto Workshop (2014). http://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves_Annex.pdf

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

[DB15]

Dadush, D., Bonifas, N.: Short paths on the Voronoi graph and closest vector problem with preprocessing. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 295–314. Society for Industrial and Applied Mathematics (2015)

[DLdW19]

Doulgerakis, E., Laarhoven, T., de Weger, B.: Finding closest lattice vectors using approximate Voronoi cells. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 3–22. Springer, Cham (2019). https://eprint.iacr.org/2016/888 CrossRef

[Duc17]

Ducas, L.: Advances on quantum cryptanalysis of ideal lattices. Nieuw Archief voor Wiskunde 5, 184–189 (2017)MathSciNetMATH

[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: STOC, pp. 293–302. ACM (2014)

[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

[HS15]

Halevi, S., Shoup, V.: Bootstrapping for HElib. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 641–670. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_25CrossRef

[JW18]

Jetchev, D., Wesolowski, B.P.C.: Horizontal isogeny graphs of ordinary abelian varieties and the discrete logarithm problem. Acta Arithmetica (2018, in press)

[Laa16]

Laarhoven, T.: Finding closest lattice vectors using approximate Voronoi cells. In: Published at SAC 2016 (2016). https://eprint.iacr.org/2016/888/20161219:141310

[Lan27]

Landau, E.: Über Dirichletsche Reihen mit komplexen Charakteren. Journal für die reine und angewandte Mathematik 157, 26–32 (1927)MathSciNetMATH

[Len75]

Lenstra Jr., H.W.: Euclid’s algorithm in cyclotomic fields. J. London Math. Soc. 10, 457–465 (1975)MathSciNetCrossRef

[Lep74]

Lepistö, T.: On the growth of the first factor of the class number of the prime cyclotomic field. Ann. Acad. Sci. Fenn. Ser. 577(Ser. A I), 1–21 (1974)MathSciNetMATH

[LLL82]

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

[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

[LPR13]

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

[Mic07]

Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Comput. Complex. 16(4), 365–411 (2007). Preliminary version in FOCS 2002MathSciNetCrossRef

[MV10]

Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: STOC, pp. 351–358 (2010)

[NS06]

Nguyen, P.Q., Stehlé, D.: LLL on the average. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 238–256. Springer, Heidelberg (2006). https://doi.org/10.1007/11792086_18CrossRef

[PMHS19]

Pellet-Mary, A., Hanrot, G., Stehlé, D.: Approx-SVP in ideal lattices with pre-processing. Cryptology ePrint Archive, Report 2019/215 (2019). https://eprint.iacr.org/2019/215. To appear at EUROCRYPT 2019. https://doi.org/10.1007/978-3-030-17656-3_24CrossRef

[Pom77]

Pomerance, C.: On the distribution of amicable numbers. J. Reine Angew. Math. 293(294), 217–222 (1977)MathSciNetMATH

[PRSD17]

Peikert, C., Regev, O., Stephens-Davidowitz, N.: Pseudorandomness of ring-LWE for any ring and modulus. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 461–473. ACM (2017)

[Reg09]

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

[Sch98]

Schoof, R.: Minus class groups of the fields of the l-th roots of unity. Math. Comput. Am. Math. Soc. 67(223), 1225–1245 (1998)MathSciNetCrossRef

[Sch03]

Schoof, R.: Class numbers of real cyclotomic fields of prime conductor. Math. Comput. 72(242), 913–937 (2003)MathSciNetCrossRef

[Sch10]

Schoof, R.: Catalan’s Conjecture. Springer, London (2010). https://doi.org/10.1007/978-1-84800-185-5CrossRefMATH

[SD19]

Stephens-Davidowitz, N.: A time-distance trade-off for GDD with preprocessing—instantiating the DLW heuristic. arXiv (2019). https://arxiv.org/abs/1902.08340

[SG10]

Schneider, M., Gama, N.: Darmstadt SVP challenges (2010). https://www.latticechallenge.org/svp-challenge/index.php. Accessed 02 Feb 2019

[Sin80]

Sinnott, W.: On the Stickelberger ideal and the circular units of an abelian field. Inventiones Math. 62, 181–234 (1980)MathSciNetCrossRef

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

[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

[SV10]

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

[Was12]

Washington, L.C.: Introduction to Cyclotomic Fields, vol. 83. Springer, New York (2012)MATH

[Wes18]

Wesolowski, B.P.C.: Arithmetic and geometric structures in cryptography. Ph.D. thesis, EPFL (2018)

Titel: On the Shortness of Vectors to Be Found by the Ideal-SVP Quantum Algorithm
verfasst von: Léo Ducas
Maxime Plançon
Benjamin Wesolowski
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2019
Print ISBN: 978-3-030-26947-0

Electronic ISBN: 978-3-030-26948-7

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-26948-7_12

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