Accelerating the Primal Hybrid Attack against Sparse LWE using GPUs

Ludo N. Pulles; Paul Vié

Paper 2025/1990

Accelerating the Primal Hybrid Attack against Sparse LWE using GPUs

Ludo N. Pulles

, Centrum Wiskunde & Informatica

Paul Vié

, Télécom Paris

Abstract

Although the lattice-estimator predicts that Learning with Errors instances having small and very sparse secrets can be broken by hybrid attacks with modest computational resources, no efficient open-source implementation of these attacks exists. This work implements the so-called Guess + Verify attack (G+V) analysed by Albrecht et al. (SAC'19), containing three improvements: (1) cuBLASter, a GPU-based implementation of the lattice basis reduction software BLASter by Ducas et al. (ASIACRYPT'25); (2) a dimension reduction technique for the BDD instance; and (3) a batched variant of Babai’s Nearest Plane algorithm. On bases of dimension 512 and above, cuBLASter outperforms BLASter. We also integrate the GPU implementation of the General Sieve Kernel by Ducas et al. (EUROCRYPT'21) into cuBLASter’s BKZ framework. Running G+V on the benchmark instances by Wenger et al. (IEEE SP'25), we show that G+V achieves significantly higher success rates than the Cool&Cruel attack (C+C) by Nolte et al. (AFRICACRYPT'24) on almost all instances, and G+V's average CPU and GPU utilization is substantially lower than the minimum reported by C+C.

Note: Acknowledgments updated

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: Bounded Distance Decoding Learning with Errors Hybrid Attack Lattice Reduction Graphics Processing Unit
Contact author(s): lnp @ cwi nl
paul vie @ telecom-paris fr
History: 2025-10-30: revised; 2025-10-24: received; See all versions
Short URL: https://ia.cr/2025/1990
License: CC0

BibTeX

@misc{cryptoeprint:2025/1990,
      author = {Ludo N. Pulles and Paul Vié},
      title = {Accelerating the Primal Hybrid Attack against Sparse {LWE} using {GPUs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1990},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1990}
}