Paper 2026/1448

Improving Skipping Fault Correction Attacks on Randomized Dilithium via MILP

Abstract

Dilithium, as a quantum-secure digital signature standard in FIPS 204, has received widespread attention for its physical implementation security. NIST selected Dilithium's randomized signing mode as the default, which can mitigate the severe physical attacks that exploit the deterministic signing mode. However, the physical attack resilience of randomized signing mode is currently an open question. In 2024, Krahmer et al. demonstrated a key-recovery attack against randomized Dilithium by exploiting fault injection. The skipping fault correction attack in Krahmer et al.'s work benefits from operational simplicity in practical settings. Nevertheless, it uses a full-rank collection strategy, requiring several effective faults equal to the number of key coefficients. By developing an optimized skipping fault correction attack, we prove the non-necessity of the full-rank collection strategy. Theoretically, we derive the minimum number of faults M_min and a key-dependent trend for reliable key recovery. For the M_min, we obtain it by analyzing secret coefficient coverage and unique bounded solution probability under the random-row model. Lemma~1 guarantees high-probability coverage of all coefficient positions, while Lemmas~2--~4 and Theorem~1 prove sufficient uniqueness conditions. Furthermore, we instantiate M_min of Dilithium for security levels L2, L3, and L5 with a high key recovery probability. For the key-dependent trend, Remark~2 reveals that the secret key with a larger number of $\pm \eta$ in the coefficients (denoted as $\mathrm{abs_\eta}$) tends to be easier to recover, offering a feature-based insight into recovery efficiency. We formulate the key recovery of Dilithium as an MILP problem and propose an MILP model. Based on the MILP model, we design algorithms of adaptive skipping fault correction attacks for plain and shuffling settings to recover the key with fewer faults. In our experiments, we explored factors influencing key recovery success, confirming theoretical predictions that success rates increase with more faults and larger $\mathrm{abs_\eta}$. Compared to Krahmer et al.'s work, our improved attack reduces the required number of faults for recovering the private key. Specifically, for the plain setting, fault reductions were 25.9% (L2), 16.2% (L3), and 25.6% (L5). Similarly, for the shuffling setting, reductions were 25.6% (L2), 13.5% (L3), and 26.3% (L5).