Revised Method for Sampling Coefficient Vector of GNR-enumeration Solution

For selecting security parameters in lattice-based cryptographic primitives, the exact manner of BKZ algorithm (as total cost and specification of output basis) should be estimated in high block sizes. The simulations of BKZ are used to predict (estimate) the exact manner of BKZ algorithm which cannot be studied by practical running of BKZ algorithm for higher block sizes. Sampling method of GNR (Gamma-Nguyen-Regev) enumeration solution vector v is one of the main components of designing BKZ-simulation and it includes two phases: sampling the norm of solution vector v and sampling corresponding coefficient vectors. Our work, by Moghissi and Payandeh in 2021, entitled as “Better Sampling Method of Enumeration Solution for BKZ-Simulation”, introduces a simple and efficient idea for sampling the norm and coefficient vectors of GNR enumeration solution v. This paper proposes much better analysis for approximating the expected value and variance of the entries of these coefficient vectors. By this analysis, our previous idea for sampling the coefficient vectors is revised, which means that the expected value and variance of every entry in these coefficient vectors sampled by our new sampling method, are more close to the expected value and variance of corresponding entries in original sampling method, while these new sampled coefficient vectors include no violation from main condition of GNR bounding function (i.e., our new sampling method is not a rejection sampling).