Paper 2025/820

One Bit to Rule Them All – Imperfect Randomness Harms Lattice Signatures

Abstract

The Fiat-Shamir transform is one of the most widely applied methods for secure signature construction. Fiat-Shamir starts with an interactive zero-knowledge identification protocol and transforms this via a hash function into a non-interactive signature. The protocol's zero-knowledge property ensures that a signature does not leak information on its secret key $\mathbf s$, which is achieved by blinding $\mathbf s$ via proper randomness $\mathbf y$. Most prominent Fiat-Shamir examples are DSA signatures and the new post-quantum standard Dilithium. In practice, DSA signatures have experienced fatal attacks via leakage of a few bits of the randomness $\mathbf y$ per signature. Similar attacks now emerge for lattice-based signatures, such as Dilithium. We build on, improve and generalize the pioneering leakage attack on Dilithium by Liu, Zhou, Sun, Wang, Zhang, and Ming. In theory, their original attack can recover a 256-dimensional subkey of Dilithium-II (aka ML-DSA-44) from leakage in a single bit of $\mathbf{y}$ per signature, in any bit position $j \geq 6$. However, the memory requirement of their attack grows exponentially in the bit position $j$ of the leak. As a consequence, if the bit leak is in a high-order position, then their attack is infeasible. In our improved attack, we introduce a novel transformation, that allows us to get rid of the exponential memory requirement. Thereby, we make the attack feasible for $all$ bit positions $j \geq 6$. Furthermore, our novel transformation significantly reduces the number of required signatures in the attack. The attack applies more generally to all Fiat-Shamir-type lattice-based signatures. For a signature scheme based on module LWE over an $\ell$-dimensional module, the attack uses a 1-bit leak per signature to efficiently recover a $\frac{1}{\ell}$-fraction of the secret key. In the ring LWE setting, which can be seen as module LWE with $\ell = 1$, the attack thus recovers the whole key. For Dilithium-II, which uses $\ell = 4$, knowledge of a $\frac{1}{4}$-fraction of the 1024-dimensional secret key lets its security estimate drop significantly from $128$ to $84$ bits.