  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 the rows of a q-ary-like embedded
random matrix $\mathbf A$, the entries with high variance are concentrated in
the early columns of the extracted matrix. This allows us to separate out the
"hard part" of the LWE secret. We can first solve the sub-problem of finding
the "cruel" bits of the secret in the early columns, and then find the
remaining "cool" bits in linear time. We use statistical techniques to
distinguish distributions to identify both the cruel and the cool bits of the
secret. We provide concrete attack timings for recovering secrets in dimensions
$n=256$, $512$, and $768$. For the lattice reduction stage, we leverage recent
improvements in lattice reduction (e.g. flatter) applied in parallel. We also
apply our new attack in the RLWE setting for $2$-power cyclotomic rings,
showing that these RLWE instances are much more vulnerable to this attack than
LWE.
