Better Sampling Method of Enumeration Solution for BKZ-Simulation

Message:
Article Type:
Research/Original Article (دارای رتبه معتبر)
Abstract:

The Blockwise-Korkine-Zolotarev (BKZ) algorithm has the main role in most lattice-based attacks, so the total cost and output quality of this algorithm should be computed exactly and used in parameter selection of lattice-based cryptographic primitives. Since the exact manner of BKZ for higher block sizes cannot be studied by practical running, simulation of BKZ is needed. In this paper, we introduce all necessary building-blocks of designing BKZ-simulation so much exactly. The main superiority of these building-blocks is that, either these components provably returned to their counterparts in BKZ algorithm, or proved/verified by long-studied heuristics or facts in lattice theory. Also, independency of these components makes them easy to use in design of any form of BKZ-simulation or any specific tester related to BKZ algorithm. More precisely, this paper includes following contributions: introducing a sampling method for norm of enumeration solution; introducing an exact definition of optimal enumeration radii; use of GSO coefficients besides the GSO norms as input/output parameters; design of a precise sampling methods for coefficient vectors related to enumeration solution; design of a proved process of updating GSO norm/coefficient together with a proved process of LLL reduction; defining so exact estimation of success probability and enumeration cost for GNR-pruning; introducing a mapping technique for GNR-pruned bounding function to avoid some wrong results in former studies and complexities in design of simulation.

Language:
English
Published:
International Journal of Information Security, Volume:13 Issue: 2, Jul 2021
Pages:
3 to 32
https://www.magiran.com/p2302724