Paper 2022/1343

Improved Progressive BKZ with Lattice Sieving

Wenwen Xia, Xidian University
Leizhang Wang, Xidian University
GengWang, Shanghai Jiao Tong University
Dawu Gu, Xidian University, Shanghai Jiao Tong University
Baocang Wang, Xidian University

BKZ is currently the most efficient algorithm in solving the approximate shortest vector problem (SVP$_\gamma$). One of the most important parameter choice in BKZ is the blocksize $\beta$, which greatly affects its efficiency. In 2016, Aono \textit{et al.} presented \textit{Improved Progressive BKZ} (pro-BKZ). Their work designed a blocksize strategy selection algorithm so that pro-BKZ runs faster than BKZ 2.0 which has a fixed blocksize. However, pro-BKZ only considers enumeration as its subroutine, without using the more efficient lattice sieving algorithm. Besides, their blocksize strategy selection is not optimal, so the strategy selection algorithm could further be improved. In this paper, we present a new lattice solving algorithm called Improved Progressive pnj-BKZ (pro-pnj-BKZ) mainly based on an optimal blocksize strategy selection algorithm for BKZ with sieving, which relies on accurate time cost models and simulating algorithms. We propose the following approaches: - New simulators and time cost models for sieving and BKZ with sieving. A simulator is used for simulating lattice reduction process without running the lattice reduction algorithm itself. We give new simulators for sieving and BKZ, to simulate the cases where blocks in BKZ with sieve oracle jump by more than one dimension. We also give more accurate time cost models for both sieving and BKZ with sieving by experiments. Specifically, we discover new relationships among time cost, blocksize and lattice dimension, which cannot be explained by the existing theoretical results, and discuss the reason. - New two-step mode for solving SVP$_\gamma$ problem with BKZ and sieving. Other than a subroutine of BKZ, sieving can also be combined with BKZ to get a more efficient lattice solving algorithm, but the best way of combination is currently unknown. We show that to solve SVP$_\gamma$ problem more efficiently, one should first repeatedly run BKZ to reduce the lattice basis and finally run lattice sieving once, since BKZ performs better in lattice basis reduction, while sieving performs better in finding short vectors. By our simulator, we can properly choose the timing where the algorithm ends the BKZ routine and begins sieving. - New blocksize strategy selection algorithm for BKZ with sieving. Since the blocksize strategy selection algorithm in pro-BKZ is not optimal, we design a new blocksize strategy selection algorithm to ensure an optimal strategy output. We implement both blocksize strategy selection algorithms in pro-BKZ and ours, along with our new BKZ simulator and two-step mode to generate the blocksize strategies. Simulation results show that the strategy generated by our new algorithm are more efficient in solving SVP$_\gamma$ problem. By generated strategy, we improve the efficiency nearly $24.6$ times compared with heuristic blocksize strategy in G6K. We test the efficiency of the pro-pnj-BKZ with the TU Darmstadt LWE challenge and break the LWE challenges with $(n,\alpha)\in\{(40,0.035),(50,0.025),(55,0.020),(90,0.005)\}$.

Available format(s)
Public-key cryptography
Publication info
cryptanalysis lattice reduction SVPγ progressive BKZ optimal blocksize selection
Contact author(s)
xiawenwen @ stu xidian edu cn
lzwang_2 @ stu xidian edu cn
wanggxx @ sjtu edu cn
dwgu @ sjtu edu cn
bcwang @ xidian edu cn
2022-10-11: last of 2 revisions
2022-10-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Wenwen Xia and Leizhang Wang and GengWang and Dawu Gu and Baocang Wang},
      title = {Improved Progressive BKZ with Lattice Sieving},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1343},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.