FIPS 204-Compatible Threshold ML-DSA via Masked Lagrange Reconstruction

2026

Read FIPS 204-Compatible Threshold ML-DSA via Masked Lagrange Reconstruction (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-20917.txt.

Introduction

Masked Lagrange reconstruction is presented in this 2026 paper as a way to split digital signing power among many parties. The target is ML-DSA, the standard signature scheme fixed by FIPS 204. A threshold version lets any T of the parties sign together. The signatures stay at the standard size and verify with unmodified FIPS 204 tools. Rival methods impose limits, such as honest-majority rules or many rounds of interaction.

The paper's technique aims to lift those limits while keeping standard output. That matters for shared custody of keys in finance and infrastructure. No verifier should need special software to trust the result. The work is a focused advance in applied cryptography. It shows that post-quantum signatures can be shared without breaking the standard.

Catalog record

YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE124 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-20917

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

FIPS 204-Compatible Threshold ML-DSA via Masked Lagrange Reconstruction Abstract We present masked Lagrange reconstruction , a technique that enables threshold ML-DSA (FIPS 204) with arbitrary thresholds T T while producing standard 3.3 KB signatures verifiable by unmodified FIPS 204 implementations. Concurrent approaches have limitations: Bienstock et al. (ePrint 2025/1163) achieve arbitrary T T but require honest-majority and 37–136 rounds; Celi et al. (ePrint 2026/013) achieve dishonest-majority but are limited to T ≤ 6 T\leq 6 . Our technique addresses the barrier that Lagrange coefficients grow as Θ ⁡ ( q ) \Theta(q) for moderate T T , making individual contributions too large for ML-DSA’s rejection sampling. Unlike ECDSA threshold schemes where pairwise masks suffice for correctness, ML-DSA requires solving three additional challenges absent in prior work: (1) rejection sampling on ‖ 𝐳 ‖ ∞ \|\mathbf{z}\|_{\infty} must still pass after masking, (2) the r0-check exposes c ​ 𝐬 2 c\mathbf{s}_{2} enabling key recovery if unprotected, and (3) the resulting Irwin-Hall nonce distribution must preserve EUF-CMA security. We solve all three. We instantiate this technique in three deployment profiles with full security proofs. Profile P1 (TEE-assisted) achieves 3-round signing with a trusted coordinator, with EUF-CMA security under Module-SIS (Theorem 4.2 ). Profile P2 (fully distributed) eliminates hardware trust via MPC in 8 rounds, achieving UC security against malicious adversaries corrupting up to n − 1 n-1 parties (Theorem 6.2 ). Profile P3 (2PC-assisted) uses lightweight 2PC for the r0-check in 3–5 rounds, achieving UC security under a 1-of-2 CP honest assumption (Theorem 6.5 ) with the best empirical performance (249ms). Our scheme requires | S | ≥ T + 1 |S|\geq T+1 signers and achieves success rates of 23–32%, matching single-signer ML-DSA. \addauthor [inst=1, [email protected], orcid=0009-0006-2592-1027 ]Leo Kao \addaffiliation [city=Taipei, country=Taiwan ]Codebat Technologies Inc. keywords threshold signatures, ML-DSA, post-quantum cryptography, lattice-based cryptography, FIPS 204 1 Introduction The imminent arrival of cryptographically relevant quantum computers poses an existential threat to currently deployed public-key cryptography. In response, the National Institute of Standards and Technology (NIST) has completed a multi-year standardization process, culminating in the release of FIPS 204 [ 32 ] , which specifies ML-DSA (Module-Lattice-Based Digital Signature Algorithm) as the primary post-quantum signature standard. As organizations worldwide begin transitioning to ML-DSA, there is an urgent need for threshold variants that enable distributed signing while maintaining compatibility with the standard. 1.1 Motivation: The Threshold Gap Threshold signatures allow a group of N parties to collectively sign messages such that any subset of T or more parties can produce a valid signature, while any coalition of fewer than T parties learns nothing about the secret key. This primitive is essential for protecting keys by distributing signing authority across multiple servers, enforcing multi-party authorization in financial systems, and building robust PKI infrastructure through distributed certificate authorities. For classical ECDSA and Schnorr signatures, efficient threshold protocols have been extensively studied and deployed [ 23 , 9 , 28 , 26 ] . However, the lattice-based structure of ML-DSA presents new challenges. The core difficulty lies in the Fiat-Shamir with Aborts paradigm: signatures are only valid when the response vector \mathbf{z}=\mathbf{y}+c\mathbf{s}_{1} satisfies \|\mathbf{z}\|_{\infty}<\gamma_{1}-\beta , where \mathbf{y} is a masking vector, c is a sparse challenge, and \mathbf{s}_{1} is the secret key. This rejection sampling step complicates the threshold setting. The State of Affairs. Current approaches to threshold ML-DSA can be categorized as follows: 1. Short-coefficient secret sharing [ 17 ] : Uses carefully constructed linear secret sharing schemes (LSSS) where reconstruction coefficients remain small. This approach produces standard-size signatures and has been demonstrated for T\leq 8 . The Ball-Çakan-Malkin bound [ 3 ] shows that \{0,1\} -LSSS for threshold T requires share size \Omega(T\log T) , which imposes practical limits on scaling this approach. 2. Noise flooding [ 6 ] : Masks the large Lagrange coefficients with overwhelming statistical noise. This works for arbitrary thresholds but produces signatures approximately 5\times larger than standard ML-DSA, breaking FIPS 204 compatibility. 3. Specialized constructions [ 8 ] : Ringtail and similar schemes modify the underlying signature algorithm to be threshold-friendly, achieving good efficiency but producing signatures incompatible with the FIPS 204 standard. This leaves a gap: for T\in[9,32] , there is no known scheme that simultaneously achieves standard signature size, practical success rates, and FIPS 204 compatibility. This range is precisely where many real-world applications fall—organizations typically require 16-of-32 or similar thresholds for robust multi-party control. 1.2 Our Contribution We present Masked Threshold ML-DSA , a threshold signature scheme for ML-DSA that supports arbitrary thresholds T\leq N while producing standard-size signatures ( \approx 3.3 KB for ML-DSA-65) identical to single-signer ML-DSA. Our scheme requires a two-honest requirement : signing sets must have size |S|\geq T+1 to ensure at least two honest parties for mask privacy. This addresses the threshold gap for T\in[9,32] while remaining practical—configurations like (3,5) , (11,15) , and (16,31) naturally satisfy N\geq T+1 . The scheme achieves practical success rates comparable to single-signer ML-DSA (theoretical baseline \approx 20\% , observed 23 – 32\% due to the more concentrated Irwin-Hall nonce distribution) and is fully verifier-compatible with FIPS 204: produced signatures are accepted by unmodified FIPS 204 verifiers. While our signer-side protocol is interactive and induces an Irwin-Hall nonce distribution rather than uniform, this affects only the signing process, not verification. Prior approaches attempt to ensure each party’s contribution is individually small, but this hits a barrier: Lagrange coefficients \lambda_{i}\approx 2^{T} grow exponentially, reaching \Theta(q) for T\geq 23 in ML-DSA. If party i naively computes \lambda_{i}\cdot\mathbf{z}_{i} where \|\mathbf{z}_{i}\|_{\infty}=O(\gamma_{1}) , the result exceeds the rejection threshold for any \lambda_{i}>1 . Our approach instead ensures that only the sum needs to be small, not individual contributions . While pairwise-canceling masks exist for ECDSA [ 9 ] , directly applying them to lattice signatures does not work because: (1) ML-DSA requires rejection sampling on \|\mathbf{z}\|_{\infty} , not just correctness; (2) the r0-check leaks c\mathbf{s}_{2} which enables key recovery; (3) the Irwin-Hall nonce distribution must preserve EUF-CMA security. Our masked Lagrange reconstruction addresses these challenges: 1. Each pair of parties (i,j) establishes a shared seed \mathsf{seed}_{i,j} (e.g., via ML-KEM). 2. During signing, party i computes a mask: \mathbf{m}_{i}=\sum_{j>i}\mathsf{PRF}(\mathsf{seed}_{i,j},\mathsf{nonce})-\sum_{j<i}\mathsf{PRF}(\mathsf{seed}_{j,i},\mathsf{nonce}) 3. By construction, \sum_{i\in S}\mathbf{m}_{i}=\mathbf{0} for any signing set S —the masks pairwise cancel. 4. Party i sends \mathbf{U}_{i}=\mathbf{y}_{i}+\lambda_{i}\cdot c\cdot\mathbf{s}_{1,i}+\mathbf{m}_{i} instead of the unmasked value. While each \mathbf{U}_{i} may have arbitrary norm in [0,q-1] , their sum is: \sum_{i\in S}\mathbf{U}_{i}=\sum_{i}\mathbf{y}_{i}+c\cdot\sum_{i}\lambda_{i}\mathbf{s}_{1,i}+\sum_{i}\mathbf{m}_{i}=\mathbf{y}+c\cdot\mathbf{s}_{1}+\mathbf{0}=\mathbf{z} which correctly reconstructs the signature vector \mathbf{z} and passes rejection sampling with probability matching single-signer ML-DSA (theoretical \approx 20\% , observed 23 – 32\% for ML-DSA-65). We note that while the aggregated nonce \mathbf{y}=\sum_{i}\mathbf{y}_{i} follows an Irwin-Hall distribution rather than uniform (see Definition O.5 ), this does not affect EUF-CMA security and only introduces a quantifiable statistical difference that we analyze in Section 3 . Performance. Our implementation achieves practical signing times: approximately 1 second average for (3,5) -threshold and 4 seconds for (16,31) -threshold on commodity hardware (including retries due to rejection sampling), using NTT-accelerated polynomial arithmetic. The communication cost is approximately 12.3 KB per party per signing attempt. Security. We prove security in the random oracle model. Unforgeability reduces to the Module-SIS problem, matching the security of single-signer ML-DSA, while privacy against coalitions of up to T-1 corrupted parties reduces to Module-LWE and

Read the complete text