Welcome to the resource topic for 2022/1343
Title:
Improved Progressive BKZ with Lattice Sieving
Authors: Wenwen Xia, Leizhang Wang, Geng Wang, Dawu Gu, Baocang Wang, Leizhang Wang, GengWang, Dawu Gu, Baocang Wang
Abstract: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)\}.
ePrint: https://eprint.iacr.org/2022/1343
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .