Paper 2025/1002

Cool + Cruel = Dual, and New Benchmarks for Sparse LWE

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].