The lattice-based cryptography is one of the most promising candidates in the era of post-quantum cryptography. It is necessary to precisely choose the practical parameters by evaluating the hardness of the underlying hard mathematical problems, such as the shortest vector problem (SVP). Currently, there are two state-of-the-art strategies for solving (approximate) SVP. One is the SVP-solving strategy proposed in G6K[5], which has the least solving time cost but high memory cost requirements; another is to execute progressive BKZ (pBKZ)[8] for pre-processing at first and call the high-dimensional SVP-oracle to find the short vector on the original lattice. Due to the strong pre-processing on the lattice basis, the memory cost of the latter strategy is usually smaller than that of the former strategy, while the time cost of pre-processing is relatively costly. In this paper, we first optimize the pnj-BKZ simulator when the jump value is quite large by giving a refined dimension for free (d4f) estimation. Then, based on our optimized pnj-BKZ simulator, we show a more accurate hardness estimation of LWE by considering technologies such as progressive BKZ pre-processing technology, jump strategy, and d4f technology. Furthermore, based on the sharper pnj-BKZ simulator, we propose an SVP-solving strategy trade-off between G6K and pBKZ, which derives less time cost than pBKZ within less memory compared with G6K. Experimental results show that when solving the TU Darmstadt SVP challenge, our algorithm can save 50%-66% of memory compared with G6K’s default SVP-solving strategy. Moreover, our algorithm speeds up the pre-processing stage by 7-30 times, saving the time cost by 4-6 times compared with the pBKZ default SVP-solving strategy. Using our proposed strategy, we solved the 170-dimensional TU Darmstadt SVP challenge and up to the 176-dimensional ideal lattice challenge.

Abstract The security of lattice‐based cryptosystems is generally based on the hardness of the Shortest Vector Problem (SVP). The original enumeration (ENUM) algorithm solving SVP runs in exponential time due to the exhaustive search, which is used as a subroutine for the block Korkin–Zolotarev (BKZ) algorithm. It is a critical issue to reduce the computational complexity of ENUM. In this paper, first, we improve the reordering method proposed by Wang et al. in ACISP 2018. We call our proposed method DPR, which permutates the projected dual lattice vectors by decreasing norms. Preliminary experimental results show that the proposed reordering methods can reduce the ENUM complexity compared to the predecessor; for instance, DPR reduces around 32.8% on average in 45‐dimensional lattices. Moreover, the authors’ simulation shows that the higher the lattice dimension, the more DPR can reduce the ENUM complexity. In addition, we study a condition for deciding when the reordering method shall be executed or not. Finally, we improve the BKZ algorithm with DPR methods and the proposed condition.