gholamreza moghissi

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.

Former studies on progressive-BKZ almost focus on increasing block sizes. Our work in IJCNIS 9.9, 2018, introduces a new version of progressive-BKZ based on increasing success probabilities, while its results are not sufficiently hopeful! This paper introduces two algorithms of “BKZ with optimal progressive block sizes” and “BKZ with optimal progressive success probabilities”, while their time-complexities are proved to be optimal. However these two proposed algorithms are designed to solve exact-SVP for an input basis, they can be used as an SVP-solver in the body of another BKZ algorithm for practical attacks! Also, our proposed algorithms can be used as reasonable representatives of two approaches of “increasing block sizes” and “increasing success probabilities” in the progressive-BKZ family to be compared with each other for the first time. For dimension n≥90, BKZ with optimal progressive success probabilities shows better runtime than corresponding instances of BKZ with optimal progressive block sizes, so that for Gentry-Halevi’s main lattice challenges, these speedups include: “2^14.1 times for Toy challenge of n=512”, “2^67.2 times for Small challenge of n=2048”, “2^235.5 times for Medium challenge of n=8192” and “2^1207.7 times for large challenge of n=32768”. Also, the time cost of BKZ with optimal progressive success probabilities and optimal progressive block sizes as two exact-SVP solvers are compared with some main claimants of exact-SVP solvers such as sieve algorithm, extreme-pruned enumeration, full-enumeration, and so on, for the dimensions of 100≤β≤240, and our results show hopeful time cost against these claimants. Moreover, two Cost-Models are approximated for these two optimal progressive BKZ.

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.

BKZ 2.0 algorithm is one of the claimant lattice reduction algorithms which incorporates extreme pruning as its main phase. The non-extreme pruning and extreme pruning in the original paper by Gamma-Nguyen-Regev (in 2010) respectively are claimed to reach the maximum speedup of 2^(β/4) and 2^(β/2) over full-enumeration. For 37≤β, this paper verifies the claimed speedup of 2^(β/4) by an optimal non-extreme pruned enumeration, while for a practical block size of 100≤β≤250, the upper-bound for speedup of extreme-pruned enumeration when blocks are preprocessed by BKZ with enumeration (as SVP-solver) is estimated from 2^(β/6.6) to 2^(β/4.4), and when blocks are preprocessed by BKZ with sieving is estimated from 2^(β/9.8) to 2^(β/3.4) ! By using these upper-bounds for speedup by extreme-pruning, all former security analyses which use the claimed speedup of 2^(β/2), should be revised  (or rejected). Also, this paper proposes a revised version of BKZ 2.0, so that for a practical block size of 100≤β≤250 and an infinite number of rounds N≈∞, the lower-bound of its speedup over BKZ 2.0 is estimated by a factor of ρ_0 in range of 2^12≤ρ_0≤2^15.5 when blocks are preprocessed by BKZ with enumeration, and also lower-bound of its speedup is estimated in the range of 0≤ρ_0≤2^20.5 when blocks are preprocessed by BKZ with sieving. Moreover, for a finite number of rounds N, speedup of our revised BKZ 2.0 over original BKZ 2.0 can be estimated by O(min⁡(N,ρ_0 ) ).