ML-DSA (formerlyCRYSTALS-Dilithium), the primary NIST post-quantum signature standard, relies on rejection sampling to ensure that released signatures are statistically independent of the secret key. Recent work by Liu et al. and Damm et al. showed that this protection breaks down as soon as an attacker obtains even a single bit of the generated masking randomness per signature, enabling key recovery via linear regression over the resulting noisy linear system. However, this regression approach requires the attacker to collect a large number of such leaky signatures—up to 2.4 million so-called informative relations for ML-DSA-65—thereby limiting the attack’s practical applicability. We dramatically reduce this cost by reformulating the key recovery as a constraint-satisfaction problem solvable by local optimization. Our approach rests on two contributions. First, we provide a verification routine that checks individual candidate subkeys only using the leakage relations collected. Second, building on theoretical insights from this verification method, we design a multi-tier hill-climbing algorithm that iteratively refines candidates by minimizing a scoring function. In the exact leakage setting, our attack recovers ML-DSA subkeys from as few as 1 500 to 35 000 informative relations across all parameter sets and tested leakage bit indices, constituting a reduction by a factor of 37–68×over the previous state of the art and allowing a recovery for leakage bit indices as low as 4 for ML-DSA-44 and ML-DSA-87 and 5 for ML-DSA-65. We further extend the attack to a noisy leakage model, where each leaked bit is flipped with some probability p. We demonstrate that key recovery even remains practical at noise rates as high as p= 45%, again with substantially less leakage information than prior work.