A Refined Hardness Estimation of LWE in Two-step Mode

Wenwen Xia; Leizhang Wang; Geng Wang; Dawu Gu; Baocang Wang

Paper 2024/067

A Refined Hardness Estimation of LWE in Two-step Mode

Wenwen Xia

, Xidian University, State Key Laboratory of Cryptology, P.O.Box 5159, Beijing, 100878, China

Leizhang Wang

, Xidian University

Geng Wang

, Shanghai Jiao Tong University, State Key Laboratory of Cryptology, P.O.Box 5159, Beijing, 100878, China

Dawu Gu

, Xidian University, Shanghai Jiao Tong University

Baocang Wang

, Xidian University

Abstract

Recently, researchers have proposed many LWE estimators, such as lattice-estimator (Albrecht et al, Asiacrypt 2017) and leaky-LWE-Estimator (Dachman-Soled et al, Crypto 2020), while the latter has already been used in estimating the security level of Kyber and Dilithium using only BKZ. However, we prove in this paper that solving LWE by combining a lattice reduction step (by LLL or BKZ) and a target vector searching step (by enumeration or sieving), which we call a Two-step mode, is more efficient than using only BKZ. Moreover, we give a refined LWE estimator in Two-step mode by analyzing the relationship between the probability distribution of the target vector and the solving success rate in a Two-step mode LWE solving algorithm. While the latest Two-step estimator for LWE, which is the “primal-bdd” mode in lattice-estimator1, does not take into account some up-to-date results and lacks a thorough theoretical analysis. Under the same gate-count model, our estimation for NIST PQC standards drops by 2.1∼3.4 bits (2.2∼4.6 bits while considering more flexible blocksize and jump strategy) compared with leaky-LWE-Estimator. Furthermore, we also give a conservative estimation for LWE from the Two-step solving algorithm. Compared with the Core-SVP model, which is used in previous conservative estimations, our estimation relies on weaker assumptions and outputs higher evaluation results than the Core- SVP model. For NIST PQC standards, our conservative estimation is 4.17∼8.11 bits higher than the Core-SVP estimation. Hence our estimator can give a closer estimation for both upper bound and lower bound of LWE hardness.

Note: Correct 2 small editing mistakes in the article. One is line 9 in Algorithm 1, the other is line 4~5 in Algorithm 3.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in PKC 2024
Keywords: Lattice-based Cryptanalysis Security Strength LWE estimator Two-step mode
Contact author(s): xiawenwen @ stu xidian edu cn
lzwang_2 @ stu xidian edu cn
wanggx @ sjtu edu cn
dwgu @ sjtu edu cn
bcwang @ xidian edu cn
History: 2024-07-24: last of 5 revisions; 2024-01-16: received; See all versions
Short URL: https://ia.cr/2024/067
License: CC BY

BibTeX

@misc{cryptoeprint:2024/067,
      author = {Wenwen Xia and Leizhang Wang and Geng Wang and Dawu Gu and Baocang Wang},
      title = {A Refined Hardness Estimation of {LWE} in Two-step Mode},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/067},
      year = {2024},
      url = {https://eprint.iacr.org/2024/067}
}