nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

The Convergence of Slide-Type Reductions

verfasst von : Michael Walter

Erschienen in: Public-Key Cryptography – PKC 2021

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

In this work, we apply the dynamical systems analysis of Hanrot et al. (CRYPTO’11) to a class of lattice block reduction algorithms that includes (natural variants of) slide reduction and block-Rankin reduction. This implies sharper bounds on the polynomial running times (in the query model) for these algorithms and opens the door to faster practical variants of slide reduction. We give heuristic arguments showing that such variants can indeed speed up slide reduction significantly in practice. This is confirmed by experimental evidence, which also shows that our variants are competitive with state-of-the-art reduction algorithms.

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 An Alternative Approach for SIDH Arithmetic

Nächstes Kapitel On the Success Probability of Solving Unique SVP via BKZ

The restriction that \(d \mid n\) is lifted in [ALNS20] by combining it with the algorithm of [MW16].

Technically, LLL reduction also requires size-reduction and usually contains a slack factor in the inequality to guarantee termination in polynomial time. Neither of these additional requirements are important for this work, so we ignore it here for simplicity.

Code available at: http://pub.ist.ac.at/~mwalter/publication/hkz_slide/hkz_slide.zip.

[ABF+20]

Albrecht, M.R., Bai, S., Fouque, P.-A., Kirchner, P., Stehlé, D., Wen, W.: Faster enumeration-based lattice reduction: root hermite factor \(k^{1/(2k)}\) Time \(k^{k/8+o(k)}\). In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 186–212. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_7CrossRef

[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. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 717–746. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_25CrossRefMATH

[ALNS20]

Aggarwal, D., Li, J., Nguyen, P.Q., Stephens-Davidowitz, N.: Slide reduction, revisited—filling the gaps in SVP approximation. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 274–295. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_10CrossRef

[AWHT16]

Aono, Y., Wang, Y., Hayashi, T., Takagi, T.: Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 789–819. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_30CrossRef

[BLR08]

Buchmann, J., Lindner, R., Rückert, M.: Explicit hard instances of the shortest vector problem. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 79–94. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88403-3_6CrossRefMATH

[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

[DM13]

Dadush, D., Micciancio, D.: Algorithms for the densest sub-lattice problem. In: Khanna, S., (ed.) 24th SODA, pp. 1103–1122. ACM-SIAM, January 2013

[dt16]

The FPLLL development team. fplll, a lattice reduction library (2016). https://github.com/fplll/fplll

[GN08a]

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

[GN08b]

Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_3CrossRef

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

[HS07]

Hanrot, G., Stehlé, D.: Improved analysis of Kannan’s shortest lattice vector algorithm. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 170–186. Springer, Heidelberg (2007)CrossRef

[LLL82]

Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 513–534 (1982)

[LN14]

Li, J., Nguyen, P.: Approximating the densest sublattice from rankin’s inequality. LMS J. Comput. Math. [electronic only], 17, 08 (2014)

[LN20]

Li, J., Nguyen, P.Q.: A complete analysis of the bkz lattice reduction algorithm. Cryptology ePrint Archive, Report 2020/1237 (2020). https://eprint.iacr.org/2020/1237

[Lov86]

Lovász, L.: An algorithmic theory of numbers, graphs and convexity, vol. 50. CBMS. SIAM (1986)

[MW16]

Micciancio, D., Walter, M.: Practical, predictable lattice basis reduction. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 820–849. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_31CrossRef

[Neu17]

Neumaier, A.: Bounding basis reduction properties. Des. Codes Cryptogr., 84(1-2), 237–259 (2017)

[PT09]

Pataki, G., Tural, M.: Unifying lll inequalities (2009)

[Sch87]

Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53(2–3), 201–224 (1987)MathSciNetCrossRef

[SE94]

Schnorr, C.-P., Euchner, M.: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical Programm. 66(1–3), 181–199, August 1994. Preliminary version in FCT 1991

[Wal15]

Walter, M.: Lattice point enumeration on block reduced bases. In: Lehmann, A., Wolf, S. (eds.) ICITS 2015. LNCS, vol. 9063, pp. 269–282. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-17470-9_16CrossRef

Titel: The Convergence of Slide-Type Reductions
verfasst von: Michael Walter
Verlag: Springer International Publishing
Buch: Public-Key Cryptography – PKC 2021
Print ISBN: 978-3-030-75244-6

Electronic ISBN: 978-3-030-75245-3

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-75245-3_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"