Paper 2025/820

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

Simon Damm, Ruhr University Bochum
Nicolai Kraus, Ruhr University Bochum
Alexander May, Ruhr University Bochum
Julian Nowakowski, Ruhr University Bochum
Jonas Thietke, Ruhr University Bochum
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 , which is achieved by blinding via proper randomness . 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 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 per signature, in any bit position . However, the memory requirement of their attack grows exponentially in the bit position 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 bit positions . 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 -dimensional module, the attack uses a 1-bit leak per signature to efficiently recover a -fraction of the secret key. In the ring LWE setting, which can be seen as module LWE with , the attack thus recovers the whole key. For Dilithium-II, which uses , knowledge of a -fraction of the 1024-dimensional secret key lets its security estimate drop significantly from to bits.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in PKC 2025
DOI
10.1007/978-3-031-91820-9_10
Keywords
ML-DSADilithiumRandomness LeakageKey RecoverySide-Channel
Contact author(s)
simon damm @ rub de
nicolai kraus @ rub de
alex may @ rub de
julian nowakowski @ rub de
jonas thietke @ rub de
History
2025-05-09: approved
2025-05-08: received
See all versions
Short URL
https://ia.cr/2025/820
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/820,
      author = {Simon Damm and Nicolai Kraus and Alexander May and Julian Nowakowski and Jonas Thietke},
      title = {One Bit to Rule Them All – Imperfect Randomness Harms Lattice Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/820},
      year = {2025},
      doi = {10.1007/978-3-031-91820-9_10},
      url = {https://eprint.iacr.org/2025/820}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.