The ISC International Journal of Information Security

Abstract The main role of BKZ simulations focuses on showing the behavior of BKZ algorithm for high block sizes, therefore current lattice security analysis (e.g., bit-security estimations and selection of efficient/secure parameter set for current LWE/NTRU-based schemes) needs to these simulations. This paper claims that current BKZ simulations are not necessarily accurate enough for exact lattice security analysis, so for first time, this study introduces two provable tools of “Emulation of updating GSO norms/coefficients” and “Emulation of LLL function” to be used in designing an accurate BKZ simulation. In fact, this paper proves that for a typical SVP solver “Z” (e.g., GNR-enumeration, Sieving, discrete pruning, etc.), if there is a simulation of “Z_emulate” which provably emulates the behaviour of practical running of “Z”, then Our BKZ Simulation by using “emulate_SVPSolver”=“Z_emulate” can provably emulates BKZ algorithm using SVP solver “Z”! Our BKZ Simulation solves different problems and weaknesses in former BKZ simulations. Our tests show that, altogether the shape of GSO norms ‖b_i^* ‖^2, root-Hermite factor of basis, estimated total cost and running time in “Experimental Running of Original BKZ algorithm” are more close to the corresponding test results in “Our BKZ Simulation”, than to the test results in “Chen-Nguyen’s BKZ-simulation”, “BKZ-Simulation by Shi Bai & et al” and some other BKZ models and approximations. Moreover, wrong strategy of updating GSO norms/coefficients in Chen-Nguyen’s BKZ-simulation leads to many GSO violation errors in lattice blocks, while our test results verify that whole these errors would be eliminated automatically in Our BKZ Simulation.

Abstract The exact manner of BKZ algorithm for higher block sizes cannot be studied by practical running, so simulation of BKZ can be used to predict the total cost and output quality of BKZ algorithm. Sampling method of enumeration solution vector v is one of the main components of designing BKZ-simulation and can be divided into two phases: sampling norm of solution vector v and sampling corresponding coefficient vectors. This paper introduces a simple and efficient idea for sampling the norm of enumeration solution v for any success probability of enumeration bounding functions, while to the best of our knowledge, no such sampling method for norm of enumeration solution is proposed in former studies. Next, this paper analyzes the structure and probability distribution of coefficient vectors (corresponding with enumeration solution v), and consequently introduces the sampling methods for these coefficient vectors which are verified by our test results, while no such a deep analysis for sampling coefficient vectors is considered in design of former BKZ-simulations. Moreover, this paper proposes an approximation for cost of enumerations pruned by optimal bounding functions.