Skip to main content
Erschienen in:
Buchtitelbild

2018 | OriginalPaper | Buchkapitel

Second Order Statistical Behavior of LLL and BKZ

verfasst von : Yang Yu, Léo Ducas

Erschienen in: Selected Areas in Cryptography – SAC 2017

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

The LLL algorithm (from Lenstra, Lenstra and Lovász) and its generalization BKZ (from Schnorr and Euchner) are widely used in cryptanalysis, especially for lattice-based cryptography. Precisely understanding their behavior is crucial for deriving appropriate key-size for cryptographic schemes subject to lattice-reduction attacks. Current models, e.g.  the Geometric Series Assumption and Chen-Nguyen’s BKZ-simulator, have provided a decent first-order analysis of the behavior of LLL and BKZ. However, they only focused on the average behavior and were not perfectly accurate. In this work, we initiate a second order analysis of this behavior. We confirm and quantify discrepancies between models and experiments —in particular in the head and tail regions— and study their consequences. We also provide variations around the mean and correlations statistics, and study their impact. While mostly based on experiments, by pointing at and quantifying unaccounted phenomena, our study sets the ground for a theoretical and predictive understanding of LLL and BKZ performances at the second order.

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!

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!

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!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The variance statistics are not comparable to the simulator [5] whose results are “deterministic”, in the sense that the simulator’s result starting on the Hermite Normal Form of a lattice depends only on the parameters (dimension, volume) of the lattice, and not the randomness of the lattice itself.
 
3
Further improvements were recently put forward [2], but are beyond the scope of this paper.
 
4
For \(\text {BKZ}\) 2.0, the distributions of the \(r_i\)’s inside the body may not be identical, thus we just calculate the mean of those \(r_i\)’s as a measure of \(e(\beta )\).
 
5
Yet the quality of the basis does not decrease with \(\beta \) in this range, as the bump on \(e(\beta )\) is more than compensated by the decrease in \(d(\beta )\).
 
6
The impacts of the \(r_i\)’s inside the head and tail will still be significant when \(\beta = O(n)\).
 
7
We worked on an open-source \(\text {BKZ}\) simulator [30], with minor modifications.
 
8
In simulation, the initial profile sequence is set to \((10(n-1),-10,\cdots ,-10)\) and then we started from blocksize 6 and progressively ran simulator by step 2 (or 4 to simulate \(\text {BKZ}\) 2.0.). There seems to be something wrong when starting with \(\text {BKZ}_2\).
 
Literatur
1.
Zurück zum Zitat Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange—a new hope. In: USENIX Security 2016, 327–343 (2016) Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange—a new hope. In: USENIX Security 2016, 327–343 (2016)
4.
Zurück zum Zitat Chen, Y.: Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe. PhD thesis (2013) Chen, Y.: Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe. PhD thesis (2013)
8.
Zurück zum Zitat Gama, N., Nguyen, P.Q.: Finding short lattice vectors within mordell’s inequality. In: STOC 2008, pp. 207–216 (2008) Gama, N., Nguyen, P.Q.: Finding short lattice vectors within mordell’s inequality. In: STOC 2008, pp. 207–216 (2008)
15.
Zurück zum Zitat Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982)MathSciNetCrossRefMATH Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982)MathSciNetCrossRefMATH
17.
Zurück zum Zitat Massey, F.J.: The Kolmogorov-Smirnov test for goodness of fit. J. Am. Stat. Assoc. 46(253), 68–78 (1951)CrossRefMATH Massey, F.J.: The Kolmogorov-Smirnov test for goodness of fit. J. Am. Stat. Assoc. 46(253), 68–78 (1951)CrossRefMATH
23.
Zurück zum Zitat Schneider, M., Buchmann, J.A.: Extended lattice reduction experiments using the BKZ algorithm. In: Sicherheit 2010, 241–252 (2010) Schneider, M., Buchmann, J.A.: Extended lattice reduction experiments using the BKZ algorithm. In: Sicherheit 2010, 241–252 (2010)
26.
Zurück zum Zitat Schnorr, C.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53(2–3), 201–224 (1987)MathSciNetCrossRefMATH Schnorr, C.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53(2–3), 201–224 (1987)MathSciNetCrossRefMATH
Metadaten
Titel
Second Order Statistical Behavior of LLL and BKZ
verfasst von
Yang Yu
Léo Ducas
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-72565-9_1