Pebble: Threshold ML-DSA Signing with Discrete Gaussians

Decentralization is a standard layer of defense in modern security stacks. Secure Multiparty Computation (MPC) is a broad term for technologies that operate on virtually combined secrets without physical co-location; in the context of decentralized key management MPC is manifested in Threshold Signature Schemes. Simply put, a threshold signing entails the collaborative generation of a signature by devices that each hold a share of the signing key.

It is standard practice today to protect digital assets with threshold signatures. Under the hood, the threshold signature scheme is closely tied to the exact signing algorithm used in the transaction infrastructure. For instance, managing assets on an ECDSA-driven ledger like Bitcoin entails using a threshold ECDSA scheme. As the industry at large begins its migration towards quantum-safe cryptography, such ledgers will no longer be driven by quantum-vulnerable signatures like ECDSA alone, but instead be augmented by a quantum-safe layer.

As of writing, there are three quantum-safe signing algorithms standardized by NIST—XMSS, SLH-DSA, and ML-DSA—with a third (FN-DSA) currently at the draft stage. Of these, only ML-DSA is known to support threshold signing with deployment-ready efficiency at present, in particular the Mithril scheme of Celi et al. (Usenix '26).

At Silence Laboratories, we are bringing quantum-safe threshold signing closer to practice, by pushing the state of the art in protocol design and engineering. Practicality of a threshold signature scheme is determined by several dimensions, and in Pebble, our new threshold ML-DSA protocol, we make the following improvements towards it:

• More Conservative Design. While Mithril does achieve efficiency suitable for many deployments, it does so at the expense of a few assumptions and heuristics in its security proof. In Pebble, we revive a more traditional approach from the literature—namely Dilithium signing with Gaussian nonces—in order to achieve comparable efficiency while eliminating dependence on these heuristics.

• Support for Advanced Features. Using the Gaussian distribution unlocks a larger toolkit from the literature, and as a demonstration of this principle we show that Pebble supports the advanced feature of Associated Data Authentication (ADA). In brief, ADA enables provable signing quorum identification, which provides elegant solutions to incentivize and audit nodes that jointly hold custody of digital assets.

In the rest of this blog post, we begin with an analogy from the classical setting, describe the technical challenges of ML-DSA, and then provide a sketch of our solution and its novelty relative to prior work.

A Recap of Schnorr

Schnorr’s signature scheme provides a simple method to derive signatures from the hardness of the discrete logarithm problem. This is the scheme that underlies modern standards like EdDSA. Schnorr’s signatures are known for their simple linear structure, which from the MPC perspective has been conducive to a clean threshold signing protocol.

Each signature \(\sigma = (R,s)\) consists of two components: a random elliptic curve point \(r \cdot G = R\), and a scalar \(z = x \cdot e + r\), where \(e = H(\mathrm{pk}, R, \mathrm{msg})\) is the public “Fiat–Shamir” challenge. This structure permits a threshold signing scheme wherein parties simply aggregate their individual \(\sigma_i = (R_i,z_i)\) contributions. These contributions—partial signatures—are essentially identical to full Schnorr signatures, with the one change that the challenge \(e = H(\mathrm{pk}, R, \mathrm{msg})\) is synchronized across the partial signatures rather than being purely local. Threshold signing is a matter of interactively sampling \(R = \sum_i R_i\) in order to plug it into this computation.

ML-DSA: A Lattice Based Analogue of Schnorr

At a high level, ML-DSA (the single signer version) follows a template similar to Schnorr. A signer holds a long-term secret key \(\mathbf{s}\), and to sign a message \(\mathrm{msg}\), it selects a random nonce \(\mathbf{w} = \mathbf{A} \cdot \mathbf{y}\), derives a public challenge \(c\) by hashing \(\mathrm{msg}\) and (part of) \(\mathbf{w}\), and produces a response of the form \(\mathbf{z} = c \cdot \mathbf{s} + \mathbf{y}\). The overall signature is then \((c,\mathbf{z})\), omitting some details that are not necessary to demonstrate the basic mechanics. Because this signature is linear in both the secret and the nonce in a manner similar to Schnorr, it is natural to attempt applying the same techniques that underlie Threshold Schnorr signing. In particular, one might hope that each party is able to produce a partial signature \((c,\mathbf{z}_i)\) that upon simple aggregation yields a full signature, in the style of Schnorr.

This method unfortunately does not work out of the box, because Dilithium (the algorithm that underlies ML-DSA) differs from Schnorr in one crucial respect. In Schnorr, the scalar response \(z\) resides in a finite set, where masking a secret with a uniform random value hides it perfectly. In Dilithium, the corresponding response \(\mathbf{z}\) is a vector of integers that must be short: verification explicitly enforces an upper bound on its size. This shortness requirement complicates Schnorr-style uniform masking.

Rejection sampling and the choice of target distribution

In Lyubashevsky’s “Fiat-Shamir with Aborts” technique as used by Dilithium/ML-DSA, the signer fixes an ideal distribution for the response in advance and then rejection-samples the signature to match this distribution. At a high level, this implies trying different putative nonce vectors y until one that hides the secret appropriately is found.

The geometry of the target distribution is consequential. The ML-DSA standard employs a hypercube, chosen originally for ease of implementation. More spherical targets, however, are more efficient in that they yield more compact signatures. This was already known to some extent at the time that Dilithium (the basis for ML-DSA) was formulated—the original Dilithium paper initially proposed a Gaussian variant called “Dilithium-G” as a more efficient alternative to the hypercube one. However, the Gaussian variant was dropped without consideration for the ML-DSA standard, possibly due to it being too complex and delicate for a standard that is meant to be implementable by the average developer.

Following the original Dilithium paper, subsequent work established that sampling from either a hyperball or a discrete Gaussian is essentially optimal, yielding signatures approximately 20% smaller than the hypercube variant.

The smaller signatures achieved by more spherical target distributions has an interesting side effect. Simple aggregation of a handful of such signatures supplied by different parties à la Schnorr, yields a combined signature that fits within the hypercube enforced by ML-DSA—i.e. an aggregated signature will be compatible with standardized ML-DSA verification.

Prior work and Pebble’s premise

Celi et al. instantiated the above idea in the Mithril scheme with a hyperball-based target distribution. More concretely, each party samples its partial signature from a hyperball, and the aggregate falls within the Dilithium bound with high probability. The construction is efficient and exhibits a profile reminiscent of Schnorr signing.

We observe that the original alternative considered in the Dilithium paper—the discrete Gaussian—had not been examined in this setting, despite the fact that Gaussians are accompanied by an extensive and well-developed mathematical toolkit that the uniform in ball distribution does not offer. This led us to a natural question: what advantages follow from constructing the entire threshold signing protocol on discrete Gaussians?

In our paper, we construct a new threshold ML-DSA signing scheme—Pebble—where each party samples its partial signature from a discrete Gaussian instead, much like the original Dilithium-G signature scheme.

The principal benefit: a cleaner and more conservative proof

The advantages prove substantial. Gaussians behave predictably under the linear operations from which these protocols are composed—the sum of two Gaussians is itself a Gaussian—which makes the intermediate quantities easier to analyze. We also know how they behave under leakage and modulo ideals of the ring. The hyperball approach, by contrast, requires nested reduction arguments and depends on several heuristics and simplifying assumptions in order to formulate a security argument.

The technical core of our improved proof lies in the analysis of entropy over rings. ML-DSA operates over a ring that decomposes into many small components (ideals), which makes it difficult to prove that expressions such as \(\mathbf{A} \cdot \mathbf{y}\) or \([\mathbf{A}\ \mathbf{I}] \cdot \mathbf{y}\) appear uniform. Discrete Gaussians are distinctive in this regard: they admit fine-grained, provable lower bounds on their entropy modulo every ideal of the ring. Building on this property, one can refine a classical result—the Leftover Hash Lemma—for the specific matrix structure that arises here and demonstrate that the relevant values are close to uniform in a strong, quantitative sense. Hence, the contribution of our paper is a cleaner, more conservative proof for threshold ML-DSA together with more fundamental contributions to lattice-based cryptography.

An additional capability: Associated Data Authentication

The Gaussian toolkit also enables features that are not straightforward to realize with the hyperball approach. We demonstrate one such feature—Associated Data Authentication (ADA)—in a variant of Pebble that we name Pebble-ADA. Intuitively, ADA allows a signature to serve simultaneously as a commitment to supplementary data that may be revealed separately, without altering the signature’s format. A representative application is proving the identity of the quorum of nodes that participated in a given threshold signing operation, enabling participants to claim rewards for their contribution.

Supporting this capability entailed a new analysis. Essentially, a portion of the nonce is disclosed when the associated data is opened, and so the scheme’s unforgeability had to be reduced to a leaky variant of ML-DSA in which the adversary is allowed to learn a noisy linear function of the nonce. We prove security for this leaky variant, again relying on the statistical control that the Gaussian distribution uniquely provides. This demonstrates that the Gaussian tools contribute not only to a more rigorous proof but also to expanded functionality.

The cost: comparable to the hyperball approach

We show empirically that the benefits of Gaussian nonces do not come at substantial overhead—Pebble occupies roughly the same performance envelope as Mithril. Its per-attempt success probability falls in the 30–50% range, against approximately 50% for Mithril, meaning it requires a comparable number of parallel signing sessions to achieve a given reliability target. In concrete terms, to reach a 99% overall success rate, Pebble requires at most 35% additional communication, which is unlikely to make the difference in practical viability. For sampling, we employ a Karney exact discrete-Gaussian sampler, which keeps the supporting machinery modest. The sampling and efficiency profile is therefore broadly on par with the hyperball approach, and in many settings the overhead is a reasonable price for the stronger security analysis.

Takeaways

Pebble illustrates that by using discrete Gaussian nonces, we can obtain practical threshold ML-DSA for the small quorums that custody applications depend on, while gaining a cleaner proof, a richer analytical toolkit, and sufficient flexibility to incorporate new capabilities such as proof of quorum identity. We believe that as the post-quantum migration advances, this combination of conservatism and extensibility is well suited to the requirements of production systems.