Design of an Accurate BKZ Simulation

Q: How can I download an article?

To download an article from SID, first log in to the site, search for the article title, and click on the 'Download Article' option.

Q: How can I download an ISI article?

To download an ISI article on SID, enter the keyword or article title in the search bar, view the relevant results, click on the desired article, and select the 'Download Article' option.

Q: How can I access the SID database?

To access the SID database, visit SID.ir, create an account, and log in to access scientific resources.

Q: Is downloading articles from SID free?

Some articles on SID are available for free, while others require payment. Details are specified on the article's page.

Moghissi Gholam Reza; Ali Payandeh Ali

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Journal Paper

Paper Information

Journal: THE ISC INTERNATIONAL JOURNAL OF INFORMATION SECURITY Year:2025 | Volume:17 | Issue:1 Page(s): 75-106

Download Full-Text

View:

Download:

Cites:

Information Journal Paper

Title

Design of an Accurate BKZ Simulation

Author(s)

Moghissi Gholam Reza | Ali Payandeh Ali | Issue Writer Certificate

Keywords

Provable Emulation

Gram-Schmidt Orthogonalization (GSO)

Updating GSO Norms

Updating GSO Coefficients

LLL function

GNR

enumeration

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.

Multimedia

No record.

Cites

No record.

References

No record.

Cite

Related Journal Papers

No record.

Related Seminar Papers

No record.

Related Plans