Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors.

*(English)*Zbl 1391.65099Summary: In 2015, M. Fukase and K. Kashiwabara [An accelerated algorithm for solving SVP based on statistical analysis, J. Inf. Process. 23, No. 1, 1–15 (2015; doi:10.2197/ipsjjip.23.67)] proposed an efficient method to find a very short lattice vector. Their method has been applied to solve Darmstadt shortest vector problems of dimensions 134 to 150. Their method is based on Schnorr’s random sampling, but their preprocessing is different from others. It aims to decrease the sum of the squared lengths of the Gram-Schmidt vectors of a lattice basis, before executing random sampling of short lattice vectors. The effect is substantiated from their statistical analysis, and it implies that the smaller the sum becomes, the shorter sampled vectors can be. However, no guarantee is known to strictly decrease the sum. In this paper, we study Fukase-Kashiwabara’s method in both theory and practice, and give a heuristic but practical condition that the sum is strictly decreased. We believe that our condition would enable one to monotonically decrease the sum and to find a very short lattice vector in fewer steps.

##### MSC:

65F20 | Numerical solutions to overdetermined systems, pseudoinverses |

68R01 | General topics of discrete mathematics in relation to computer science |

94A60 | Cryptography |

##### Software:

NTRU
PDF
BibTeX
Cite

\textit{M. Yasuda} et al., J. Math. Cryptol. 11, No. 1, 1--24 (2017; Zbl 1391.65099)

Full Text:
DOI

##### References:

[1] | Ajtai M., The shortest vector problem in \({L_{2}}\) is NP-hard for randomized reductions, Proceedings of the 30th Annual ACM Symposium on Theory of Computing - STOC 1998, ACM, New York (1998), 10-19. · Zbl 1027.68609 |

[2] | Ajtai M., Kumar R. and Sivakumar D., A sieve algorithm for the shortest lattice vector problem, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing - STOC 2001, ACM, New York (2001), 601-610. · Zbl 1323.68561 |

[3] | Bremner M. R., Lattice Basis Reduction: An Introduction to the LLL Algorithm and its Applications, CRC Press, Boca Raton, 2011. |

[4] | Buchmann J. and Ludwig C., Practical lattice basis sampling reduction, Algorithmic Number Theory - ANTS 2006, Lecture Notes in Comput. Sci. 4076, Springer, Berlin (2006), 222-237. · Zbl 1143.11336 |

[5] | Fukase M. and Kashiwabara K., An accelerated algorithm for solving SVP based on statistical analysis, J. Inform. Process. 23 (2015), no. 1, 1-15. |

[6] | Galbraith S. D., Mathematics of Public Key Cryptography, Cambridge University Press, Cambridge, 2012. · Zbl 1238.94027 |

[7] | Gama N. and Nguyen P. Q., Predicting lattice reduction, Advances in Cryptology - EUROCRYPT 2008, Lecture Notes in Computer Sci. 4965, Springer, Berlin (2008), 31-51. · Zbl 1149.94314 |

[8] | Gama N., Nguyen P. Q. and Regev O., Lattice enumeration using extreme pruning, Advances in Cryptology - EUROCRYPT 2010, Lecture Notes in Computer Sci. 6110, Springer, Berlin (2010), 257-278. · Zbl 1280.94056 |

[9] | Goldreich O., Goldwasser S. and Halevi S., Public-key cryptosystems from lattice reduction problems, Advances in Cryptology - CRYPTO 1997, Lecture Notes in Computer Sci. 1294, Springer, Berlin (1997), 112-131. · Zbl 0889.94011 |

[10] | Hoffstein J., Pipher J. and Silverman J. H., NTRU: A ring-based public key cryptosystem, Algorithmic Number Theory - ANTS III, Lecture Notes in Computer Sci. 1423, Springer, Berlin (1998), 267-288. · Zbl 1067.94538 |

[11] | Lenstra A. K., Lenstra H. W. and Lovász L., Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515-534. · Zbl 0488.12001 |

[12] | Ludwig C., Practical lattice basis sampling reduction, Ph.D thesis, Technische Universität Darmstadt, 2005. |

[13] | Micciancio D., The shortest vector in a lattice is hard to approximate to within some constant, SIAM J. Comput. 30 (2001), no. 6, 2008-2035. · Zbl 0980.68054 |

[14] | Micciancio D. and Michael W., Fast lattice point enumeration with minimal overhead, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms - SODA 2015, SIAM, Philadelphia (2015), 276-294. · Zbl 1372.68140 |

[15] | Nguyen P. Q. and Vallée B., The LLL algorithm, Inf. Secur. Cryptography, Springer, Berlin, 2010. · Zbl 1179.11003 |

[16] | Schneider M. and Göttert N., Random sampling for short lattice vectors on graphics cards, Cryptographic Hardware and Embedded Systems - CHES 2011, Lecture Notes in Computer Sci. 6917, Springer, Berlin (2011), 160-175. |

[17] | Schnorr C. P., Lattice reduction by random sampling and birthday methods, 20th Annual Symposium of Theoretical Aspects on Computer Science - STACS 2003, Lecture Notes in Computer Sci. 2606, Springer, Berlin (2003), 145-156. · Zbl 1035.68113 |

[18] | Schnorr C. P. and Euchner M., Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Math. Program. 66 (1994), 181-199. · Zbl 0829.90099 |

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.