FlagThis

Abstract

ML-DSA is a representative lattice-based signature scheme in post-quantum cryptography 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 Integer Learning with Errors (ILWE)-type problems, resulting in secret key disclosure risks. Such randomness leakage attack can be formulated as a twostage key-recovery procedure, in which leaked partial information and public signatures are first transformed into an ILWEfamily 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 instancesolving 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. Specifically, the first class is the least-squares regression solvers using ordinary least squares (OLS) and likelihood-based estimators. The second class is the robust regression solvers with Huber regression and Cauchy regression. The last class is the prior-aware discrete-inference solvers by using belief propagation (BP), objective-induced greedy search, and bounded-error hillclimbing. 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: (i) compared with OLS, BP constitutes a reduction by a factor of 15 . 4 - 64 . 9 in noise-free settings, and by a factor of 10 . 5 - 73 . 9 in noisy settings. (ii) compared with hill-climbing, BP reduces the number of required relations by a factor of up to 7 . 6 . On CILWE, BP is more effective with the concealment rate lower than 0.9, while Cauchy regression is more stable for higher rates. of Overall, this work provides a systematic evaluation on different solvers in randomness leakage attacks, and presents new benchmarks for future analysis on ML-DSA.