Estimation of the Success Probability of Random Sampling by the Gram-Charlier Approximation

Yoshitatsu Matsuda; Tadanori Teruya; Kenji Kasiwabara

Paper 2018/815

Estimation of the Success Probability of Random Sampling by the Gram-Charlier Approximation

Yoshitatsu Matsuda, Tadanori Teruya, and Kenji Kasiwabara

Abstract

The lattice basis reduction algorithm is a method for solving the Shortest Vector Problem (SVP) on lattices. There are many variants of the lattice basis reduction algorithm such as LLL, BKZ, and RSR. Though BKZ has been used most widely, it is shown recently that some variants of RSR are quite efficient for solving a high-dimensional SVP (they achieved many best scores in TU Darmstadt SVP challenge). RSR repeats alternately the generation of new very short lattice vectors from the current basis (we call this procedure ``random sampling'') and the improvement of the current basis by utilizing the generated very short lattice vectors. Therefore, it is important for investigating and ameliorating RSR to estimate the success probability of finding very short lattice vectors by combining the current basis. In this paper, we propose a new method for estimating the success probability by the Gram-Charlier approximation, which is a basic asymptotic expansion of any probability distribution by utilizing the higher order cumulants such as the skewness and the kurtosis. The proposed method uses a ``parametric'' model for estimating the probability, which gives a closed-form expression with a few parameters. Therefore, the proposed method is much more efficient than the previous methods using the non-parametric estimation. This enables us to investigate the lattice basis reduction algorithm intensively in various situations and clarify its properties. Numerical experiments verified that the Gram-Charlier approximation can estimate the actual distribution quite accurately. In addition, we investigated RSR and its variants by the proposed method. Consequently, the results showed that the weighted random sampling is useful for generating shorter lattice vectors. They also showed that it is crucial for solving the SVP to improve the current basis periodically.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: lattice techniques
Contact author(s): matsuda @ graco c u-tokyo ac jp
History: 2018-09-06: received
Short URL: https://ia.cr/2018/815
License: CC BY

BibTeX

@misc{cryptoeprint:2018/815,
      author = {Yoshitatsu Matsuda and Tadanori Teruya and Kenji Kasiwabara},
      title = {Estimation of the Success Probability of Random Sampling by the Gram-Charlier Approximation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/815},
      year = {2018},
      url = {https://eprint.iacr.org/2018/815}
}