Design of an Accurate BKZ Simulation

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^* ‖², 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.