The cool and the cruel: separating hard parts of LWE secrets

arXiv:2403.10328v1 Announce Type: new
Abstract: Sparse binary LWE secrets are under consideration for standardization for Homomorphic Encryption and its applications to private computation. Known attacks on sparse binary LWE secrets include the sparse dual attack and the hybrid sparse dual-meet in the middle attack which requires significant memory. In this paper, we provide a new statistical attack with low memory requirement. The attack relies on some initial lattice reduction. The key observation is that, after lattice reduction is applied to …

applications arxiv attack attacks binary computation cs.cr encryption hard homomorphic encryption hybrid memory parts private secrets standardization under