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: Give the specific version of eprint reference [29]

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in PKC 2024
Keywords
Lattice-based CryptanalysisSecurity StrengthLWE estimatorTwo-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-03-09: last of 3 revisions
2024-01-16: received
See all versions
Short URL
https://ia.cr/2024/067
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2024/067}},
      url = {https://eprint.iacr.org/2024/067}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.