×

zbMATH — the first resource for mathematics

Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes. (English) Zbl 1435.05015
Summary: M. Walter [Lect. Notes Comput. Sci. 9063, 269–282 (2015; Zbl 1359.94630)] studied the worst case computational cost to enumerate short lattice vectors on two well-known block reduced bases, i.e., BKZ reduced bases and slide reduced bases. Until then, existing works analyzed only extreme preprocessed bases, e.g., LLL reduced bases that are the weakest ones and quasi-HKZ reduced bases that are the strongest ones; hence, Walter tried to interpolate these results. For this purpose, Walter tried to calculate enumeration cost on block reduced bases of arbitrary blocksizes. The topic should be theoretically interesting since hardness of the lattice problem relates to the security of lattice-based cryptography. In this paper, we revisit the problem with refined analyses. For both BKZ and slide reduced bases, we show that the worst case enumeration costs are smaller than Walter’s analyses. In particular, we show that our results are the best possible ones when we follow Walter’s approach. Furthermore, we extend Walter’s result for slide reduced bases. Since Walter only studied the original slide reduced bases proposed by N. Gama and P. Q. Nguyen [in: Proceedings of the 40th annual ACM symposium on theory of computing, STOC 2008. Victoria, Canada, May 17–20, 2008. New York, NY: Association for Computing Machinery (ACM). 207–216 (2008; Zbl 1230.11153)], he did not analyze arbitrary blocksizes. To extend the analyses to arbitrary blocksizes, we use the generalized slide reduction that was defined by J. Li and W. Wei [Bull. Aust. Math. Soc. 88, No. 3, 390–406 (2013; Zbl 1283.11098)]. As a side contribution, we also show that the worst case behaviors of the generalized slide reduced bases are better than Li and Wei’s analyses. We obtain all these results by exploiting better geometric properties of block reduced bases.
MSC:
05A15 Exact enumeration problems, generating functions
05B05 Combinatorial aspects of block designs
94A60 Cryptography
11H06 Lattices and convex bodies (number-theoretic aspects)
Software:
BKZ
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ajtai, M., The shortest vector problem in L \({}_{\text{2}}\) is NP-hard for randomized reductions (extended abstract), (Vitter, J. S., Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (1998), ACM), 10-19 · Zbl 1027.68609
[2] Ajtai, M.; Kumar, R.; Sivakumar, D., A sieve algorithm for the shortest lattice vector problem, (Vitter, J. S.; Spirakis, P. G.; Yannakakis, M., Proceedings on 33rd Annual ACM Symposium on Theory of Computing (2001), ACM), 601-610 · Zbl 1323.68561
[3] Albrecht, M. R.; Ducas, L.; Herold, G.; Kirshanova, E.; Postlethwaite, E. W.; Stevens, M., The general sieve kernel and new records in lattice reduction, (Ishai, Y.; Rijmen, V., Advances in Cryptology - EUROCRYPT 2019-38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part II. Advances in Cryptology - EUROCRYPT 2019-38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part II, Lecture Notes in Computer Science, vol. 11477 (2019), Springer), 717-746 · Zbl 07164014
[4] Aono, Y.; Wang, Y.; Hayashi, T.; Takagi, T., Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator, (Fischlin, M.; Coron, J., Advances in Cryptology - EUROCRYPT 2016-35th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Advances in Cryptology - EUROCRYPT 2016-35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lecture Notes in Computer Science, vol. 9665 (2016), Springer), 789-819 · Zbl 1385.94007
[5] Chen, Y.; Nguyen, P. Q., BKZ 2.0: Better lattice security estimates, (Lee, D. H.; Wang, X., Advances in Cryptology - ASIACRYPT 2011-17th International Conference on the Theory and Application of Cryptology and Information Security. Advances in Cryptology - ASIACRYPT 2011-17th International Conference on the Theory and Application of Cryptology and Information Security, Lecture Notes in Computer Science, vol. 7073 (2011), Springer), 1-20 · Zbl 1227.94037
[6] Ducas, L., Shortest vector from lattice sieving: A few dimensions for free, (Nielsen, J. B.; Rijmen, V., Advances in Cryptology - EUROCRYPT 2018-37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2018 Proceedings, Part I. Advances in Cryptology - EUROCRYPT 2018-37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2018 Proceedings, Part I, Lecture Notes in Computer Science, vol. 10820 (2018), Springer), 125-145 · Zbl 1423.94069
[7] Fincke, U.; Pohst, M., Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp., 44, 170, 463-471 (1985) · Zbl 0556.10022
[8] Gama, N.; Howgrave-Graham, N.; Koy, H.; Nguyen, P. Q., Rankin’s constant and blockwise lattice reduction, (Dwork, C., Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference. Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Lecture Notes in Computer Science, vol. 4117 (2006), Springer), 112-130 · Zbl 1129.11058
[9] Gama, N.; Nguyen, P. Q., Finding short lattice vectors within mordell’s inequality, (Dwork, C., Proceedings of the 40th Annual ACM Symposium on Theory of Computing (2008), ACM), 207-216 · Zbl 1230.11153
[10] Gentry, C., Fully homomorphic encryption using ideal lattices, (Mitzenmacher, M., Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009 (2009), ACM), 169-178 · Zbl 1304.94059
[11] Gentry, C.; Peikert, C.; Vaikuntanathan, V., Trapdoors for hard lattices and new cryptographic constructions, (Dwork, C., Proceedings of the 40th Annual ACM Symposium on Theory of Computing (2008), ACM), 197-206 · Zbl 1231.68124
[12] Hanrot, G.; Pujol, X.; Stehlé, D., Analyzing blockwise lattice algorithms using dynamical systems, (Rogaway, P., Advances in Cryptology - CRYPTO 2011-31st Annual Cryptology Conference. Advances in Cryptology - CRYPTO 2011-31st Annual Cryptology Conference, Lecture Notes in Computer Science, vol. 6841 (2011), Springer), 447-464 · Zbl 1287.94072
[13] Hanrot, G.; Stehlé, D., Improved analysis of kannan’s shortest lattice vector algorithm, (Menezes, A., Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference. Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Lecture Notes in Computer Science, vol. 4622 (2007), Springer), 170-186 · Zbl 1215.94050
[14] Helfrich, B., Algorithms to construct minkowski reduced an hermite reduced lattice bases, Theoret. Comput. Sci., 41, 125-139 (1985) · Zbl 0601.68034
[15] Kannan, R., Improved algorithms for integer programming and related lattice problems, (Johnson, D. S.; Fagin, R.; Fredman, M. L.; Harel, D.; Karp, R. M.; Lynch, N. A.; Papadimitriou, C. H.; Rivest, R. L.; Ruzzo, W. L.; Seiferas, J. I., Proceedings of the 15th Annual ACM Symposium on Theory of Computing (1983), ACM), 193-206
[16] Laarhoven, T.; Mariano, A., Progressive lattice sieving, (Lange, T.; Steinwandt, R., Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings. Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings, Lecture Notes in Computer Science, vol. 10786 (2018), Springer), 292-311 · Zbl 1425.94066
[17] Lenstra, A.; Lenstra, H.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 515-534 (1982) · Zbl 0488.12001
[18] Li, J.; Wei, W., Slide reduction, successive minima and several applications, Bull. Aust. Math. Soc., 88, 3, 390-406 (2013) · Zbl 1283.11098
[19] Micciancio, D.; Peikert, C., Trapdoors for lattices: Simpler, tighter, faster, smaller, (Pointcheval, D.; Johansson, T., Advances in Cryptology - EUROCRYPT 2012-31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. Advances in Cryptology - EUROCRYPT 2012-31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lecture Notes in Computer Science, vol. 7237 (2012), Springer), 700-718 · Zbl 1297.94090
[20] Micciancio, D.; Voulgaris, P., A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations, (Schulman, L. J., Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 (2010), ACM), 351-358 · Zbl 1293.68172
[21] Micciancio, D.; Voulgaris, P., Faster exponential time algorithms for the shortest vector problem, (Charikar, M., Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010 (2010), SIAM), 1468-1480 · Zbl 1288.94076
[22] Micciancio, D.; Walter, M., Fast lattice point enumeration with minimal overhead, (Indyk, P., Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 (2015), SIAM), 276-294 · Zbl 1372.68140
[23] Micciancio, D.; Walter, M., Practical, predictable lattice basis reduction, (Fischlin, M.; Coron, J., Advances in Cryptology - EUROCRYPT 2016-35th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Advances in Cryptology - EUROCRYPT 2016-35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lecture Notes in Computer Science, vol. 9665 (2016), Springer), 820-849 · Zbl 1385.94062
[24] Mordell, L. J., Observation on the minimum of a positive quadratic form in eight variables, J. Lond. Math. Soc., 19, 73 Part 1, 3-6 (1944) · Zbl 0060.12009
[25] Nguyen, P. Q., Hermite’s constant and lattice algorithms, (Nguyen, P. Q.; Vallée, B., The LLL Algorithm - Survey and Applications, Information Security and Cryptography (2010), Springer), 19-69 · Zbl 1230.11155
[26] Nguyen, P. Q.; Stern, J., The two faces of lattices in cryptology, (Silverman, J. H., Cryptography and Lattices, International Conference, CaLC 2001. Cryptography and Lattices, International Conference, CaLC 2001, Lecture Notes in Computer Science, vol. 2146 (2001), Springer), 146-180 · Zbl 1006.94531
[27] Nguyen, P. Q.; Vidick, T., Sieve algorithms for the shortest vector problem are practical, J. Math. Cryptol., 2, 2, 181-207 (2008) · Zbl 1193.11117
[28] Regev, O., On lattices, learning with errors, random linear codes, and cryptography, (Gabow, H. N.; Fagin, R., Proceedings of the 37th Annual ACM Symposium on Theory of Computing (2005), ACM), 84-93 · Zbl 1192.94106
[29] Schnorr, C., A hierarchy of polynomial time lattice basis reduction algorithms, Theoret. Comput. Sci., 53, 201-224 (1987) · Zbl 0642.10030
[30] Schnorr, C., Block reduced lattice bases and successive minima, Comb. Probab. Comput., 3, 507-522 (1994) · Zbl 0845.11025
[31] Schnorr, C.; Euchner, M., Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Math. Program., 66, 181-199 (1994) · Zbl 0829.90099
[32] Walter, M., Lattice point enumeration on block reduced bases, (Lehmann, A.; Wolf, S., Information Theoretic Security - 8th International Conference, ICITS 2015. Information Theoretic Security - 8th International Conference, ICITS 2015, Lecture Notes in Computer Science, vol. 9063 (2015), Springer), 269-282 · Zbl 1359.94630
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.