Skip to main content

2017 | OriginalPaper | Buchkapitel

Random Sampling Revisited: Lattice Enumeration with Discrete Pruning

verfasst von : Yoshinori Aono, Phong Q. Nguyen

Erschienen in: Advances in Cryptology – EUROCRYPT 2017

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

In 2003, Schnorr introduced Random sampling to find very short lattice vectors, as an alternative to enumeration. An improved variant has been used in the past few years by Kashiwabara et al. to solve the largest Darmstadt SVP challenges. However, the behaviour of random sampling and its variants is not well-understood: all analyses so far rely on a questionable heuristic assumption, namely that the lattice vectors produced by some algorithm are uniformly distributed over certain parallelepipeds. In this paper, we introduce lattice enumeration with discrete pruning, which generalizes random sampling and its variants, and provides a novel geometric description based on partitions of the n-dimensional space. We obtain what is arguably the first sound analysis of random sampling, by showing how discrete pruning can be rigorously analyzed under the well-known Gaussian heuristic, in the same model as the Gama-Nguyen-Regev analysis of pruned enumeration from EUROCRYPT ’10, albeit using different tools: we show how to efficiently compute the volume of the intersection of a ball with a box, and to efficiently approximate a large sum of many such volumes, based on statistical inference. Furthermore, we show how to select good parameters for discrete pruning by enumerating integer points in an ellipsoid. Our analysis is backed up by experiments and allows for the first time to reasonably estimate the success probability of random sampling and its variants, and to make comparisons with previous forms of pruned enumeration. Our work unifies random sampling and pruned enumeration and show that they are complementary of each other: both have different characteristics and offer different trade-offs to speed up enumeration.

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!

Literatur
1.
Zurück zum Zitat Agrell, E., Eriksson, T., Vardy, A., Zeger, K.: Closest point search in lattices. IEEE Trans. Info. Theory 48(8), 2201–2214 (2002)MathSciNetCrossRefMATH Agrell, E., Eriksson, T., Vardy, A., Zeger, K.: Closest point search in lattices. IEEE Trans. Info. Theory 48(8), 2201–2214 (2002)MathSciNetCrossRefMATH
2.
Zurück zum Zitat 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). doi:10.1007/978-3-662-49890-3_30 CrossRef 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). doi:10.​1007/​978-3-662-49890-3_​30 CrossRef
3.
Zurück zum Zitat Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. In: Mehlhorn, K. (ed.) STACS 1985. LNCS, vol. 182, pp. 13–20. Springer, Heidelberg (1985). doi:10.1007/BFb0023990 CrossRef Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. In: Mehlhorn, K. (ed.) STACS 1985. LNCS, vol. 182, pp. 13–20. Springer, Heidelberg (1985). doi:10.​1007/​BFb0023990 CrossRef
4.
Zurück zum Zitat Buchmann, J., Ludwig, C.: Practical lattice basis sampling reduction. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 222–237. Springer, Heidelberg (2006). doi:10.1007/11792086_17 CrossRef Buchmann, J., Ludwig, C.: Practical lattice basis sampling reduction. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 222–237. Springer, Heidelberg (2006). doi:10.​1007/​11792086_​17 CrossRef
6.
Zurück zum Zitat Ding, D., Zhu, G., Wang, X.: A genetic algorithm for searching the shortest lattice vector of SVP challenge. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2015, pp. 823–830 (2015) Ding, D., Zhu, G., Wang, X.: A genetic algorithm for searching the shortest lattice vector of SVP challenge. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2015, pp. 823–830 (2015)
7.
Zurück zum Zitat Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comput. 44(170), 463–471 (1985)MathSciNetCrossRefMATH Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comput. 44(170), 463–471 (1985)MathSciNetCrossRefMATH
8.
Zurück zum Zitat Fukase, M., Kashiwabara, K.: An accelerated algorithm for solving SVP based on statistical analysis. JIP 23(1), 67–80 (2015) Fukase, M., Kashiwabara, K.: An accelerated algorithm for solving SVP based on statistical analysis. JIP 23(1), 67–80 (2015)
9.
Zurück zum Zitat Fukase, M., Yamaguchi, K.: Analysis of the extended search space for the shortest vector in lattice. J. Syst. Cybern. Inf. 9(6), 42–46 (2011) Fukase, M., Yamaguchi, K.: Analysis of the extended search space for the shortest vector in lattice. J. Syst. Cybern. Inf. 9(6), 42–46 (2011)
12.
13.
Zurück zum Zitat Håstad, J., Just, B., Lagarias, J.C., Schnorr, C.-P.: Polynomial time algorithms for finding integer relations among real numbers. SIAM J. Comput. 18(5), 859–881 (1989)MathSciNetCrossRefMATH Håstad, J., Just, B., Lagarias, J.C., Schnorr, C.-P.: Polynomial time algorithms for finding integer relations among real numbers. SIAM J. Comput. 18(5), 859–881 (1989)MathSciNetCrossRefMATH
14.
Zurück zum Zitat Hosono, T.: Numerical inversion of laplace transform and some applications to wave optics. Radio Sci. 16(6), 1015–1019 (1981)CrossRef Hosono, T.: Numerical inversion of laplace transform and some applications to wave optics. Radio Sci. 16(6), 1015–1019 (1981)CrossRef
15.
Zurück zum Zitat Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), pp. 193–206 (1983) Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), pp. 193–206 (1983)
16.
Zurück zum Zitat Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 513–534 (1982)MathSciNetCrossRefMATH Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 513–534 (1982)MathSciNetCrossRefMATH
20.
Zurück zum Zitat Ludwig, C.: Practical Lattice Basis Sampling Reduction. Ph.D. thesis, Technische Universität Darmstadt (2005) Ludwig, C.: Practical Lattice Basis Sampling Reduction. Ph.D. thesis, Technische Universität Darmstadt (2005)
22.
Zurück zum Zitat Nguyen, P.Q.: Public-key cryptanalysis. In: Luengo, I. (ed.) Recent Trends in Cryptography. Contemporary Mathematics, vol. 477. AMS-RSME (2009) Nguyen, P.Q.: Public-key cryptanalysis. In: Luengo, I. (ed.) Recent Trends in Cryptography. Contemporary Mathematics, vol. 477. AMS-RSME (2009)
23.
Zurück zum Zitat 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). doi:10.1007/11792086_18 CrossRef 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). doi:10.​1007/​11792086_​18 CrossRef
24.
Zurück zum Zitat Nguyen, P.Q., Vallée, B. (eds.): The LLL Algorithm: Survey and Applications. Information Security and Cryptography. Springer, Heidelberg (2009) Nguyen, P.Q., Vallée, B. (eds.): The LLL Algorithm: Survey and Applications. Information Security and Cryptography. Springer, Heidelberg (2009)
25.
Zurück zum Zitat Pohst, M.: On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. SIGSAM Bull. 15(1), 37–44 (1981)CrossRefMATH Pohst, M.: On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. SIGSAM Bull. 15(1), 37–44 (1981)CrossRefMATH
27.
Zurück zum Zitat Rousseau, C.C., Ruehr, O.G.: Problems and solutions. SIAM Review 39(4), 779–786 (1997). Subsection: The Volume of the Intersection of a Cube and a Ball in \(N\)-space. Two solutions by Bernd Tibken and Denis ConstalesCrossRef Rousseau, C.C., Ruehr, O.G.: Problems and solutions. SIAM Review 39(4), 779–786 (1997). Subsection: The Volume of the Intersection of a Cube and a Ball in \(N\)-space. Two solutions by Bernd Tibken and Denis ConstalesCrossRef
29.
Zurück zum Zitat Schneider, M., Göttert, N.: Random sampling for short lattice vectors on graphics cards. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 160–175. Springer, Heidelberg (2011). doi:10.1007/978-3-642-23951-9_11 CrossRef Schneider, M., Göttert, N.: Random sampling for short lattice vectors on graphics cards. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 160–175. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-23951-9_​11 CrossRef
30.
31.
Zurück zum Zitat Schnorr, C.-P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181–199 (1994)MathSciNetCrossRefMATH Schnorr, C.-P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181–199 (1994)MathSciNetCrossRefMATH
32.
Zurück zum Zitat Schnorr, C.P., Hörner, H.H.: Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 1–12. Springer, Heidelberg (1995). doi:10.1007/3-540-49264-X_1 CrossRef Schnorr, C.P., Hörner, H.H.: Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 1–12. Springer, Heidelberg (1995). doi:10.​1007/​3-540-49264-X_​1 CrossRef
35.
Metadaten
Titel
Random Sampling Revisited: Lattice Enumeration with Discrete Pruning
verfasst von
Yoshinori Aono
Phong Q. Nguyen
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-56614-6_3