Welcome to the resource topic for 2025/1002
Title:
Cool + Cruel = Dual
Authors: Alexandr Karenin, Elena Kirshanova, Julian Nowakowski, Eamonn W. Postlethwaite, Fernando Virdia
Abstract:Recently [Wenger et al.~IEEE S&P 2025] claimed that the `Cool and Cruel’ (C+C) approach to solving LWE with sparse secrets [Nolte et al.~AFRICACRYPT 2024] outperforms other approaches, in particular the well established primal attack.
In this work we show that
i.~C+C is an instantiation of a known dual attack [Albrecht, EUROCRYPT 2017], ii.~experimental evidence that the primal attack can outperform C+C in similar regimes to those studied by Wenger et al. and
iii.~both theoretical justification and experimental evidence that C+C is a consequence of a basis profile called the Z-shape.
To prove i.~we introduce a framework for dimension reduction in bounded distance decoding problems that may be of independent interest.
For ii.~we provide an open source implementation of the primal attack that is properly parametrised for short, sparse ternary secret LWE and guesses portions of the secret, along with an error analysis for a rounded variant of LWE that proves useful for practical cryptanalysis.
Given iii.~we falsify a claim of Nolte et al.
ePrint: https://eprint.iacr.org/2025/1002
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .