Lattice Enumeration with Discrete Pruning: Improvements, Cost Estimation and Optimal Parameters

Luan Luan, Chunxiang Gu, Yonghui Zheng () and Yanan Shi
Additional contact information
Luan Luan: Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China
Chunxiang Gu: Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China
Yonghui Zheng: Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China
Yanan Shi: Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China

Mathematics, 2023, vol. 11, issue 3, 1-33

Abstract: Lattice enumeration is a linear-space algorithm for solving the shortest lattice vector problem (SVP). Extreme pruning is a practical technique for accelerating lattice enumeration, which has a mature theoretical analysis and practical implementation. However, these works have yet to be applied to discrete pruning. In this paper, we improve the discrete pruned enumeration (DP enumeration) and provide a solution to the problem proposed by Léo Ducas and Damien Stehlé regarding the cost estimation of discrete pruning. We first rectify the randomness assumption to more precisely describe the lattice point distribution of DP enumeration. Then, we propose a series of improvements, including a new polynomial-time binary search algorithm for cell enumeration radius, a refined cell-decoding algorithm and a rerandomization and reprocessing strategy, all aiming to lift the efficiency and build a more precise cost-estimation model for DP enumeration. Based on these theoretical and practical improvements, we build a precise cost-estimation model for DP enumeration by simulation, which has good accuracy in experiments. This DP simulator enables us to propose an optimization method of calculating the optimal parameters of DP enumeration to minimize the running time. The experimental results and asymptotic analysis both show that the discrete pruning method could outperform extreme pruning, which means that our optimized DP enumeration might become the most efficient polynomial-space SVP solver to date. An open-source implementation of DP enumeration with its simulator is also provided.

Keywords: lattice-based cryptanalysis; SVP; enumeration; discrete pruning (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/3/766/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/3/766/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:3:p:766-:d:1056437

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().