Alexander Karenin
Technology Innovation Institute

Elena Kirshanova
Technology Innovation Institute

Julian Nowakowski
Ruhr University Bochum

Eamonn W. Postlethwaite
King's College London

Ludo Pulles
Centrum Wiskunde & Informatica

Paul Vié
Télécom Paris

Fernando Virdia
University of Surrey, Guildford

Keywords: bounded distance decoding, sparse LWE, cryptanalysis, lattice cryptography, benchmarks

Abstract

The sparse secret Learning with Errors (LWE) problem is a widely used assumption in efficient fully homomorphic constructions. In [Wenger et al. IEEE S\&P 2025] two approaches, `Cool and Cruel’ (C+C) and the machine learning based `SALSA', were benchmarked against the well established primal attack on sparse secrets. The authors concluded that C+C outperforms SALSA and both outperform the primal attack.

In this work we show that the apparently novel C+C is an instantiation of a known dual attack [Albrecht, EUROCRYPT 2017]. To argue this we introduce a framework for dimension reduction in the bounded distance decoding problem that may be of independent interest. Furthermore we prove that the C+C `phenomenon' is an expression of the geometry of the well known Z-shape basis in $q$-ary lattices, despite claims to the contrary.

We also show that a correctly parametrised primal attack outperforms C+C both in parameter regimes studied by Wenger et al. and in new parameter regimes. To support this claim, we provide an open source implementation of two variants of the primal attack that are relevant for sparse secret LWE: Drop+Solve [May--Silverman, CaLC 2001] and Guess+Verify [Albrecht et al. SAC 2019].