Halfspace Learning for Lattice Signature Key Recovery from Signs

Any signature scheme has to protect its secret key via some properly chosen, secret randomness. We show that, for the lattice signatures HAWK, Falcon and ML-DSA, even minimal leakage of this randomness suffices for secret key recovery.

In particular, leaking either the Hamming weight or a single bit of any randomness coordinate allows an attacker to infer the sign of that coordinate. This corresponds to learning $\textrm{sign}(\langle \mathbf b, \mathbf w \rangle)$, where $\mathbf b$ is the secret key and $\mathbf w$ is public. We model key recovery from such sign information as an instance of Learning a Halfspace. This well-studied problem from learning theory provides a rich solution machinery, which we adapt for the cryptanalysis of lattice-based signatures.

As a first main result, we resolve the open problem of recovering the secret key in HAWK from sign leakage. At the 128-bit security level and in the noise-free setting, we recover the secret key from only 30 signatures in 10 minutes.

As a second main result, we recover the secret key in Falcon via sign leakage from only 100 signatures in under a minute. In comparison to existing attacks, this reduces the number of required signatures by a factor of $250$.

As a third result, we show the first ML-DSA secret key recovery from sign leakage, which requires 190,000 signatures and completes within seconds. In comparison to existing ML-DSA attacks, we require a comparable amount of signatures, but utilize a less restrictive leakage model.

In addition, our attack is alarmingly noise-tolerant, succeeding with up to 35% noise for HAWK, 30% for Falcon, and 35% for ML-DSA, albeit requiring significantly more signatures in the noisy case.