Paper 2026/2566

Fault-Induced Nonce Repetition in Threshold Lattice Signatures: A Reveal-Structure Criterion, Cross-Scheme Analysis, and Detection Boundaries

Abstract

Threshold ML-DSA is regarded as a deployment model that eliminates single-point key risk, and the NIST threshold call (IR 8214C) has likewise attracted many proposals. Existing security analyses, however, generally assume malicious or compromised protocol participants. For the threat of "physical faults in the devices of honest participants," single-party lattice signatures have been studied systematically for over a decade, whereas threshold schemes, to our knowledge, have not yet been systematically evaluated. We show that fault-induced cross-session sample replay by one party leaks that party's share, and that mechanisms such as RNG state rollback can trigger it. In a t-of-n deployment, the attacker need only fault t devices to recover the complete signing secret, while every signature is fully valid when examined individually; the hedged nonce, commitment/session binding, and fail-closed final verification all remain untriggered. We verify the attack end to end on Mithril (ePrint 2026/013, USENIX Security 2026): two implementation versions, six (t,n) configurations, and 96/96 statistical scan groups all achieve exact recovery, with residual error identically 0 and no lattice reduction. The secret recovered solely from the coordinator-visible transcript can be used to forge a signature on the spot that passes the implementation's FIPS 204 verifier. We further elevate the attack to a class-level criterion. The attack surface is determined by the reveal structure, that is, by whether the scheme reveals per-party responses to a party visible to the attacker, rather than by the distributional properties of the nonce. Quorus's structural immunity thus comes from non-reveal and is unrelated to uniformity. TALUS can be broken via a double-spend path in which "one-time consumption of preprocessing is skipped". Trilithium's signing algorithm hands the Server's response share to the Client in plaintext, and [TALUS] classifies it as internally uniform (\(I = 0\)), making it an instance of the "statistically immune and fault-fragile" quadrant; the attack requires only 1 device fault. The simulator message "(ss, sid, [z']_S)" in the original proof, together with [Jarv26]'s verbatim copy of this algorithm, is the evidence for this determination; see Appendix D for the evidence tier. This yields two independent evaluation dimensions: the statistical axis \(I\) and the reproducibility axis (reveal structure). Different design levers allow the two axes to take values independently. All three quadrants already have instances: (reveal, \(I > 0\)), (non-reveal, \(I = 0\)), and (reveal, \(I = 0\)). Two cases lie on the anti-diagonal, [Trilithium] and [Kao26]. We design detection as two layers of transcript-level checks. The early-warning surface alarms on reveal-hash liveness and achieves 305/305 exact hits over the full corpus with zero false positives. The full-coverage surface runs the identification computation shared with the attack; within the feasible range of identification, there is no window in which the attack is usable but undetectable. §6.1 explains the difference in alarm timing. For imperfect faults, we prove the threshold law for full-key recovery \(m^* = (\ell-1)N+\lceil N/K \rceil\) and verify it coordinate by coordinate; for ML-DSA-44 the law gives \(768+\lceil 256/K \rceil\), namely 896 at K=2 and 787 at K=14. This reveals the trade-off nature of K. All claims have undergone a tool-assisted verification workflow with three analysis paths that are independent of one another. The authors direct the workflow; §8.2 describes its execution mode and artifact disclosure.