### Predicting BKZ Z-Shapes on q-ary Lattices

##### Abstract

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 --
Category
Public-key cryptography
Publication info
Preprint.
Keywords
LWE q-ary lattices Z-shape BKZ simulator LWE estimator
Contact author(s)
martin albrecht @ royalholloway ac uk
lijianweisk @ sina com
History
2022-08-09: withdrawn