Search papers, labs, and topics across Lattice.
This paper addresses the vulnerability of the ML-DSA lattice-based signature scheme to randomness leakage attacks, which can compromise secret keys by transforming public signatures into ILWE-type problems. The authors introduce a unified framework to evaluate various recovery solvers, revealing that the choice of solver significantly influences the efficiency of secret key recovery. Notably, their prior-aware discrete-inference method demonstrates a substantial reduction in the number of informative relations needed for recovery, outperforming traditional methods by factors of up to 73.9x in various settings.
Secret key recovery from randomness leakage in ML-DSA can be improved by up to 73.9x with the right solver, reshaping our understanding of security in lattice-based cryptography.
ML-DSA is a representative lattice-based signature scheme standardized by NIST. It relies on signing randomness and rejection sampling to ensure that released signatures are statistically independent of the secret key. Practical implementations, however, may leak partial information about this randomness, and such leakage can transform public signatures into ILWE-type problems, resulting in secret key disclosure risks. Such randomness leakage attack can be formulated as a two-stage key-recovery procedure, in which leaked partial information and public signatures are first transformed into an ILWE-family instance, and then a recovery solver is applied to recover the secret key. Existing work has mainly focused on the first stage by constructing such instances under different leakage models. By contrast, the role of solver in the subsequent instance-solving stage remains under-explored, and existing attacks often rely on ad-hoc model-specific solvers. To address this gap, we propose a unified framework to systematically evaluate different recovery solvers on leakage-derived ILWE-family instances. The framework covers three ILWE instances, including the ordinary ILWE, Fiat-Shamir ILWE (FS-ILWE) and Concealed ILWE (CILWE) under different scenarios. Within our framework, we explore three classes of solvers. Our experiments show that the solver has a significant impact on the secret-key recovery efficiency. In particular, on FS-ILWE, prior-aware discrete-inference reduces the number of informative relations by one to two orders of magnitude compared to the baselines: Compared with OLS, BP constitutes a reduction by a factor of 15.4x-64.9x in noise-free settings, and by a factor of 10.5x-73.9x in noisy settings. Overall, this work provides a systematic evaluation on different solvers in randomness leakage attacks, and presents new benchmarks for future analysis on ML-DSA.
