At CCS 2017, Espitau et al. described a side-channel attack against the
rejection sampling step in BLISS signatures, and mentioned that the
attack could be greatly improved and simplified for *uncompressed* BLISS
signatures, as one could target the part of rejection sampling depending
linearly on the secret key, as opposed to quadratically. In actual,
compressed BLISS signatures, though, one only gets noisy linear relations
on the secret, so key recovery amounts to solving a high-dimensional
LWE-type problem. As a result, Espitau et al. dimissed this approach as
infeasible.
However, the LWE problem that arises in this way does not involve any
modular reduction: it is defined over Z. With that motivation in mind, we
study the hardness of LWE over the integers, and find that the problem
(with polynomial size errors) can heuristically always be solved given
sufficiently many samples. We also present provable results in that
direction, and show that we can in fact mount the side-channel attack on
BLISS, against 100% of secret keys (as opposed to ~7% in the CCS paper).
This is joint work with J. Bootle (University College London).
