Paper 2024/067
A Refined Hardness Estimation of LWE in Two-step Mode
, Xidian University, State Key Laboratory of Cryptology, P.O.Box 5159, Beijing, 100878, China, Xidian University, Shanghai Jiao Tong University, State Key Laboratory of Cryptology, P.O.Box 5159, Beijing, 100878, China, Xidian University, Shanghai Jiao Tong University, Xidian UniversityAbstract
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
-
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}
}
