Paper 2022/843

Predicting BKZ Z-Shapes on q-ary Lattices

Martin R. Albrecht, Information Security Group, Royal Holloway, University of London
Jianwei Li, Inria and DIENS, PSL

Primal attacks against the Learning With Errors (LWE) problem rely on reducing \(q\)-ary lattices. These reduced bases have been observed to exhibit a so-called ``Z-shape'' on their Gram--Schmidt vectors. We propose an efficient simulator to accurately predict this Z-shape behaviour, which we back up with extensive simulations and experiments. We also formalise (under standard heuristics) the intuition that the presence of a Z-shape makes enumeration-based primal lattice attacks faster. Furthermore, we upgrade the LWE or lattice estimator with our simulator to assess and then rule out the impact of the \(q\)-ary Z-shape on solving LWE instances derived from parameter sets for NIST PQC candidates. We consider this improved estimator to be of independent interest.

Available format(s)
-- withdrawn --
Public-key cryptography
Publication info
LWE q-ary lattices Z-shape BKZ simulator LWE estimator
Contact author(s)
martin albrecht @ royalholloway ac uk
lijianweisk @ sina com
2022-08-09: withdrawn
2022-06-26: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.