Cryptology ePrint Archive: Report 2018/815

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

Yoshitatsu Matsuda and 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.

Category / Keywords: public-key cryptography / lattice techniques

Date: received 3 Sep 2018

Contact author: matsuda at graco c u-tokyo ac jp

Available format(s): PDF | BibTeX Citation

Version: 20180906:193041 (All versions of this report)

Short URL: ia.cr/2018/815


[ Cryptology ePrint archive ]