# Finally! A Compact Lattice-Based Threshold Signature

Rafael del Pino, Guilhem Niot

► To cite this version:

Rafael del Pino, Guilhem Niot. Finally! A Compact Lattice-Based Threshold Signature. PKC 2025 - International Conference on Practice and Theory in Public Key Cryptography, May 2025, Roros, Norway. pp.169-199, 10.1007/978-3-031-91826-1_6. hal-05230606

HAL Id: hal-05230606

https://hal.science/hal-05230606v1

Submitted on 30 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Finally! A Compact Lattice-Based Threshold Signature

Rafael del Pino¹ and Guilhem Niot¹,²

¹ PQShield

rafael.del.pino@pqshield.com, guilhem@gniot.fr

² Univ Rennes, CNRS, IRISA

**Abstract.** Threshold signatures improve upon digital signatures by splitting the trust and robustness among multiple parties. In a ($T, N$) threshold signature any set of $T$ parties can produce a signature but no set of less than $T$ users can do so. Many such constructions are now available in the pre-quantum setting but post-quantum threshold schemes are still running heavy, with the state-of-the-art boasting signature sizes that are still an order of magnitude larger than post-quantum digital signatures. We propose a novel very efficient threshold signature scheme, with a signature size close to that of a single Dilithium signature for any threshold $T$ of at most 8 users. Our construction reduces to well-studied problems (MLWE and SelfTargetMSIS) and does not need any heavy machinery, essentially consisting in just $T$ parallel executions of the Dilithium signature scheme. Though the resulting scheme is remarkably simple, many technical difficulties, such as sharing a secret in small shares, or simulating rejecting transcripts, have kept such an efficient threshold signature out of reach until now.

This is the full version of a paper appearing in the proceedings of PKC 2025. This version includes additional security proofs.
Table of Contents

<table><tr><td>Finally! A Compact Lattice-Based Threshold Signature</td><td>1</td></tr><tr><td>Rafael del Pino &amp; Guilhem Niot</td><td></td></tr><tr><td>1 Introduction</td><td>3</td></tr><tr><td>1.1 Related work</td><td>4</td></tr><tr><td>1.2 Our Contributions</td><td>5</td></tr><tr><td>1.3 Technical Overview</td><td>6</td></tr><tr><td>2 Preliminaries</td><td>8</td></tr><tr><td>2.1 General notations</td><td>8</td></tr><tr><td>2.2 Threshold signatures</td><td>9</td></tr><tr><td>2.3 Modulus Rounding</td><td>11</td></tr><tr><td>2.4 Hardness Assumptions</td><td>12</td></tr><tr><td>2.5 Rejection Sampling</td><td>13</td></tr><tr><td>2.6 Σ-protocols with Aborts</td><td>13</td></tr><tr><td>2.7 The Renyi divergence</td><td>14</td></tr><tr><td>3 Thresholdizing the Fiat-Shamir with Aborts Signature Scheme</td><td>15</td></tr><tr><td>3.1 Fiat-Shamir with Aborts (FSwA)</td><td>16</td></tr><tr><td>3.2 Threshold Fiat-Shamir with Aborts</td><td>20</td></tr><tr><td>3.3 Security analysis</td><td>20</td></tr><tr><td>4 Setting Parameters</td><td>27</td></tr><tr><td>4.1 Gaussians</td><td>28</td></tr><tr><td>4.2 Uniforms</td><td>28</td></tr><tr><td>A Omitted proof of unforgeability</td><td>33</td></tr><tr><td>B Omitted proof of unforgeability of non-threshold FSwA</td><td>46</td></tr></table>
# 1 Introduction

The Fiat-Shamir paradigm has proven crucial to building practical and easy-to-implement signature schemes. For lattice-based schemes, it is notably at the core of the NIST standardized scheme Dilithium [LDK+22], and was also leveraged for building practical lattice-based threshold signatures [DKM+24].

Let us first recall a short history of Fiat-Shamir schemes. In the classical setting, more precisely the Schnorr signature, signing works by sampling some randomness $r \stackrel{\$}{\leftarrow} \mathbb{Z}_q$ and computing a commitment $w = g^r$. Then the signer samples a challenge $c = H(w, \text{msg})$, and computes a response $z = c \cdot s + r$, where $s$ is the signer's secret. It finally outputs $(c, z)$ as signature.

This paradigm was applied to the lattice setting, where it is however crucial for security to produce short Fiat-Shamir responses, and $\mathbf{r}$ is thus sampled from a distribution of short vectors $\mathcal{P}_{\mathbf{r}}$. This introduces new challenges to ensure that responses do not leak the signer's secret. Several approaches have been developed to ensure the security of Fiat-Shamir schemes in the lattice setting:

- **Rejection sampling.** One way to ensure the independence of the signature distribution with the secret is to perform rejection sampling. Typically, schemes target an ideal distribution $\mathcal{P}_z$ for responses $\mathbf{z}$, and they obtain it using samples from $\mathcal{P}_r$ by accepting a given $\mathbf{z}$ only with probability $\frac{\mathcal{P}_z(\mathbf{z})}{M\mathcal{P}_r(\mathbf{r})}$ for some $M > 1$. This has been exploited in numerous schemes, with various choices for the distributions of its components: uniforms [LDK+22], unimodal (or bimodal) Gaussians and Hyperballs [Lyu12, BBD+23] providing different tradeoffs in terms of compactness and ease of implementation.

- **Trapdoor sampling.** While it was applied very early to the hash-and-sign paradigm [GPV08], trapdoor sampling was only recently shown to also apply to the Fiat-Shamir paradigm [DPS23]. It involves complex sampling techniques to choose internal distributions for $\mathbf{r}$ and $\mathbf{z}$ to ensure the correctness and independence of the output from the secret.

- **Noise flooding.** Another technique, called noise flooding, gives up on the perfect independence of $\mathbf{z}$ and $\mathbf{s}$ and accepts some leakage of the secret. By sampling $\mathbf{r}$ from a sufficiently wide distribution, they can prove that $\mathbf{s}$ preserves enough entropy to ensure security. Although this technique increases the signature size compared to earlier methods, it allows for the design of highly amenable threshold schemes and has produced the most practical lattice-based threshold signatures to date [DKM+24].

While it is notoriously difficult to share a trapdoor [BKP13], the other two approaches were applied to build threshold signatures.

*Rejection sampling* was leveraged in numerous works to build threshold signatures and multisignatures of a practical size. More recently, threshold signatures were also built based on *noise flooding*. While in a centralized setting, *noise flooding* constructions have larger sizes, they are the most compact in the threshold setting.
In this work, we will focus on threshold solutions that use rejection sampling as they appear like promising candidates to go below sizes provided by *noise flooding* techniques.

## 1.1 Related work

Threshold signatures have been the subject of extensive research in recent years, with various schemes proposed.

**Classical setting.** A large number of threshold signatures were designed in the classical setting based on RSA [Sho00, GHKR08], Schnorr signatures [KG20, CKM23], and ECDSA [CGG$^{+20}$, ANO$^{+22}$, CCL$^{+23}$]. Several threshold signatures were also designed from computational assumptions such as DDH [BLT$^{+24}$].

**Post-quantum setting.** In the post-quantum setting, the design of practical threshold signature schemes appeared much more challenging.

We have recently seen proposals for isogeny-based threshold schemes [DM20], hash-based threshold schemes [KCLM22], multivariate-based schemes [CEN24], and a line of works based on lattices. The focus of this work is on lattice-based threshold schemes.

Several lattice-based threshold signature schemes have been built with generic techniques like multi-party computation (MPC) [BKP13, CS19, TPCZ24] and fully homomorphic encryption [BGG$^{+18}$, ASY22]. These constructions however have limited practicality with inefficient signing procedures, high communication costs, and rather large signature sizes even for a small number of parties. Notably, [GKS24] achieves a signature size of 46.6kB in the 3-out-of-5 case for a communication cost of 3MB per user.

Another line of work explored tailored solutions. [CATZ24] built a lattice-based threshold Fiat-Shamir signature from the generalized secret sharing scheme from [BL90]. Lyubashevsky's Fiat-Shamir with Aborts (FSwA) signature scheme [Lyu09] was used to build many threshold signatures and multisignatures [DOTT22, BTT22, ADP24, Che23]. While many distributions were studied to implement FSwA signatures [Lyu09, DDLL13, DKL$^{+18}$, DFPS22, CCD$^{+23}$, BBRS24], unimodal distributions appear most suited to the threshold setting, as they verify by multiplying the FSwA response $z$ by a fixed matrix $A$ which allows for easy aggregation. However, these schemes are limited to the $N$-out-of-$N$ setting, and challenges in proving the security of FSwA in the threshold setting led to the introduction of additional mechanisms within these schemes, that aimed at hiding aborted transcripts that may leak secret information. For this reason, signature sizes following this approach remained large, with the state-of-the-art multisignature [Che23] generating signatures of 31kB for 1024 users.

A recent approach [DKM$^{+24}$] revisited lattice-based threshold signatures, and proposed to leverage noise-flooding to build Fiat-Shamir signatures. They achieve a signature size of 13kB for 1024 users. It was followed up in other works [EKT24, KRT24, BKL$^{+24}$, dPENP25] to provide different properties. It was also adapted to the hash-and-sign paradigm [ENP24]. These techniques allow
<table><caption>Table 1: Comparison with related works. As there are few lattice-based threshold signature schemes aimed at small groups we compare with other types of schemes ((T,N)=threshold, M=multisignature) and set sizes N. Dilithium is taken as a reference.</caption><thead><tr><th>Scheme</th><th>Ours</th><th>[GKS24]</th><th>[CATZ24]</th><th>[DKM<sup>+24</sup><br>[dPENP25]</th><th>[ENP24]</th><th>[ADP24]</th><th>[Che23]</th><th>[DKL<sup>+18</sup></th></tr></thead><tbody><tr><td>|sig| (kB)</td><td>2.7</td><td>47</td><td>219</td><td>12.7</td><td>12.3</td><td>12</td><td>20</td><td>2.4</td></tr><tr><td>|vk| (kB)</td><td>2.6</td><td>14</td><td>33</td><td>3.9</td><td>12.8</td><td>7</td><td>7</td><td>1.3</td></tr><tr><td>Type</td><td>(T,N)</td><td>(T,N)</td><td>(T,N)</td><td>(T,N)</td><td>(T,N)</td><td>(T,N) / M</td><td>M</td><td>-</td></tr><tr><td>N</td><td>8</td><td>5</td><td>5</td><td>1024</td><td>16</td><td>7</td><td>32</td><td>-</td></tr><tr><td>Technique</td><td>FSwA</td><td>Flooding</td><td>Flooding</td><td>Flooding</td><td>Flooding</td><td>FSwA</td><td>FSwA</td><td>FSwA</td></tr></tbody></table>

for large groups of signers thanks to their sublinear scaling, this lack of scaling however also means that restraining such schemes to small parameter sets would only give a marginal improvement in sizes.

At the crossing of the noise-flooding and FSwA approaches, [dPENP25] introduced novel secret-sharing techniques preserving the shortness of partial private keys. They showed that their techniques can be used in noise flooding schemes to provide identifiable aborts as well as smaller signatures.

## 1.2 Our Contributions

We present a scheme inspired by [dPENP25] that constructs smaller signatures through the use of rejection sampling. [dPENP25] introduced new secret sharing techniques with short shares and reconstruction coefficients and applied them to a *noise flooding*-based threshold construction to provide identifiable abort. We show in this work that this short secret sharing can be leveraged to implement a very efficient threshold signature based on rejection sampling. We avoid the advanced primitives that were previously needed by improving the analysis of the distribution of rejecting transcripts and prove its simulatability, thus improving the state-of-the-art proofs that were given in [BTT22, DFPS23]. By fine-tuning the analysis of our scheme and improving the bounds on the Renyi divergence of rejection sampling that were proposed in [DFPS22] we achieve signature size that are very close to a single Dilithium signature (2.7kB vs 2.42kB). When weakening requirements and supporting only $Q_s = 2^{40}$ signatures (instead of $2^{64}$), we can produce signatures as small as Dilithium.

We can summarize our contributions as follows.

1. **Compact Lattice-based Threshold Signatures.** We introduce a signature scheme for thresholds $T \le 8$ that achieves significantly smaller signatures than previous approaches by using rejection sampling. We compare it to previous works in Table 1.

2. **A versatile construction.** We present our construction as a blackbox transform of a Fiat-Shamir with Aborts scheme into a threshold signature
scheme. Meaning that different variants of the FSwA paradigm can be seamlessly adapted into threshold signatures.

3. **T-out-of-N threshold FSwA.** We leverage secret sharing techniques from [dPENP25] to introduce the first T-out-of-N threshold FSwA signature scheme without relying on heavy machinery such as multi-party computations (MPC), or fully homomorphic encryption (FHE).

4. **Novel proof techniques.**
    - We introduce novel proof techniques to tightly prove the simulatability of rejected transcripts in FSwA schemes improving the state-of-the-art proofs from [BTT22, DFPS23]. This result may be of independent interest for other lattice-based schemes relying on rejection sampling and allows tightly proving the Honest-Verifier Zero-Knowledge (HVZK) property for Σ-protocols with aborts, in place of the weaker no-abort Honest-Verifier Zero-Knowledge (naHVZK) property.

- We also introduce novel bookkeeping techniques to lift constructions based on [dPENP25] from the broadcast setting, to a setting where the communication channel is owned by the adversary.

## 1.3 Technical Overview

Our goal is to construct an efficient threshold signature for small parameters. To that end we chose to ignore the recent technique of Fiat-Shamir without abort developed in Raccoon [dPKPR24] and the subsequent threshold Raccoon [DKM+24] as it involves noise flooding which impacts the parameters adversely. We instead use the classic Fiat-Shamir with aborts scheme of [Lyu09, LDK+22], and find efficient ways to tackle the difficulties that arise when trying to transform these schemes into threshold signatures [DOTT22, BTT22, ADP24, Che23].

**Fiat-Shamir with Aborts** We start by describing the Fiat-Shamir with aborts technique to construct signatures. As our aim is to evaluate the efficiency of multiple instantiations we do not consider fixed distributions (e.g. uniform as in Dilithium, Gaussian as in [Lyu09], or spherical as in [DFPS22]) but rather give a scheme that can use any distribution and prove its security by reducing to hard problems (MLWE and MSIS) with said distributions.

Let $\chi_{sk}, \chi_r, \chi_z$ be three distribution over $\mathcal{R}^{k+\ell}$ for some ring $\mathcal{R}$. The secret key for our signature scheme will be $s \leftarrow \chi_{sk}$ and the corresponding public key will be the MLWE sample: $\mathbf{b} = \mathbf{As} = [\bar{\mathbf{A}} | \mathbf{I}]s$.

To sign a message $\mathbf{msg}$ the signer will proceed as follows:

- Sample $\mathbf{r} \leftarrow \chi_r$

- Set $c = H([\mathbf{A} \cdot \mathbf{r}]_{\nu_w}, \mathbf{msg})$

- Set $\mathbf{z} = c\mathbf{s} + \mathbf{r}$

- Output $\mathbf{z}$ with probability $\max(\chi_z(\mathbf{z})/(M\chi_r(\mathbf{r}), 1))$ (for some $M > 1$)

The last step of this algorithm is the so-called rejection sampling which guarantees that the distribution output by the signer will be close to the ideal distribution $\chi_z$, at the cost of rejecting with probability $1 - 1/M$.
Though the rejection sampling algorithm was thoroughly studied in [DFPS22], we provide tighter bounds on the Renyi divergence between the output of the rejection sampling algorithm and the ideal distribution $\chi_{sk}$.

**Threshold FSWA** We now would like to translate the Fiat-Shamir with Aborts construction to the threshold setting.

However, two challenges appear in the threshold setting: (a) how can we reject over $z$, while no single party can know the secret $s$, and (b) how to safely compute an aggregated commitment $w$ in case of aborts, as the distribution of $r$ then leaks some information on the secret.

To solve (a) we leverage the short replicated secret-sharing technique from [dPENP25] to sample short secret shares over which rejection sampling can be applied. In T-N replicated secret sharing the secret $s$ is shared as the sum of $M = \binom{N}{N-T+1}$ shares, this pool of shares $S = \{s_1, \cdots, s_M\}$ is then distributed among the $N$ users in such a way that for any set $\mathbf{a}$ct of $T$ users the union of all the shares known by the users in $\mathbf{a}$ct fully covers $S$ and, inversely, for any set $\mathbf{a}$ct of less than $T$ users there exists a share that is known by no one in $\mathbf{a}$ct. It is easy to see that by sampling the shares from a distribution of secrets that have a small norm we obtain a short replicated secret-sharing. The public key is finally set as the MLWE sample corresponding to the sum of the shares: $\mathbf{b} := \mathbf{A} \cdot \mathbf{s}$. Well-known secret sharing techniques for monotone access structures (see [ISN87]) can be used to construct such a secret-sharing. We present the algorithms RSS and Recover that respectively distribute the shares and (deterministically) decide a covering partition of the shares for any set of size $T$ in Section 3.2, Figs. 5 and 6.

*Remark 1.* We could also use the distributed key generation techniques from [dPENP25], or their ramp sharing to support higher thresholds. We note however that this would incur an increase in signature size, while our goal was to achieve very compact signatures in a reasonable setting.

As for (b), we decided to compute the commitment $w$ in a straightforward manner by having each party sample some randomness $r_i \leftarrow \chi_r$, and compute $w_i := \mathbf{A} \cdot r_i$. Finally, $\mathbf{w} := \sum_{i \in \mathbf{act}} w_i$ is computed after all the parties reveal their $w_i$ with a hash-and-reveal approach. This remains secure if $w_i$ looks uniform in case of aborts. This issue was tackled in [BTT22, DFPS23] but the solutions given do not apply to most of the schemes we consider, as notably observed in [CGL+24, Section 4.4]. These works give two orthogonal proofs that the distribution of $\mathbf{A} \cdot \mathbf{r}$ conditioned on the rejection sampling step aborting is close to uniform.

1. The first consists in using a leftover-hash-lemma or regularity lemma on $\mathbf{A} \cdot \mathbf{r}$. However, the leftover-hash lemma does not apply to polynomial rings, and regularity lemmas for polynomial rings only work for gaussian distributions with large standard deviations.

2. The second approach consists in reducing to the LWE hardness over $\chi_r$ assuming that the distribution of accepted $z_i$ is at a negligible statistical distance from the ideal distribution, however their proof relies on non-tight
search-to-decision and decision-to-search LWE reductions, and cannot be exploited for setting any parameter.

We present in Lemma 5 a new proof that is much simpler and directly relies on the hardness of MLWE for standard distributions, which can be applied to all the instantiations we consider. As an independent interest, this result can generically be applied to prove the Honest-Verifier Zero-Knowledge (HVZK) property for $\Sigma$-protocols with aborts, avoiding the use of more complex techniques to hide aborted transcripts. We notably refer to [BTT22, DFPS23] for motivations on achieving the HVZK property in other works.

As a last step, each party performs partial rejection-sampling signing using as partial key $\mathbf{s}_i^{\text{part}} := \sum_{I \in m_i} \mathbf{s}_I$, where $\mathbf{m} = \text{Recover}(\text{act})$:

1. computes $c = H_c(\mathbf{vk}, \mathbf{msg}, \mathbf{w})$.

2. computes $\mathbf{z}_i = \text{Rej}(c \cdot \mathbf{s}_i^{\text{part}}, \chi_z, \chi_r; \mathbf{r}_i)$, and reveals the result.

In our finalized scheme, we leverage standard rounding techniques to compress public keys and commitments by dropping $\nu_b$ (resp. $\nu_w$) bits of the public keys (resp. of the commitments). We describe the parameters of our scheme in Table 2 and formally describe its algorithms in Fig. 6, and Fig. 7.

We note that proving the security of this scheme also revealed novel challenges due to the fact that an adversary may provide two parties in the same signing session with different views and force them to use twice the same secret. This makes it non-trivial to program the random oracle in a way that protects a target non-corrupted secret as in [dPENP25], since they were relying on a broadcast channel for their proof. We note also that this issue was not present in other works as either (i) they are not replicating secrets like [DOTT22], or (ii) parties implicitly agree on a view before signing as in [KRT24]. This is tackled in our proof by deferring random oracle programmings until all the commitments $\mathbf{w}_i$ in a given session are defined. This requires a careful bookkeeping of all the interactions with signing oracles, and whenever a new $\mathbf{w}_i$ is sampled, the random oracle must be made consistent for the current session, as well as for previous sessions that implicitly relied on this commitment.

# 2 Preliminaries

## 2.1 General notations

**Sets, functions, and distributions.** For an integer $N > 0$, we note $[N] = \{1, \dots, N\}$. To denote the *assign* operation, we use $y := f(x)$ when $f$ is deterministic and $y \leftarrow f(x)$ when randomized.

**Linear algebra.** Throughout the work, for a fixed power-of-two $n$, we note $\mathcal{K} = \mathbb{Q}[x]/(x^n + 1)$ and $\mathcal{R} = \mathbb{Z}[x]/(x^n + 1)$ the associated cyclotomic field and cyclotomic ring. We also note $\mathcal{R}_q = \mathcal{R}/(q\mathcal{R})$. Given $\mathbf{x} \in \mathcal{K}^\ell$, we abusively note $\|\mathbf{x}\|_2$ the Euclidean norm (resp. $\|\mathbf{x}\|_\infty$ the infinite norm) of the $(n\ell)$-dimensional vector of the coefficients of $\mathbf{x}$. By default, vectors are treated as *column vectors* (unless specified otherwise).
**Distributions.** We also introduce useful distributions for this work.

**Definition 1 (Uniforms).** When $S$ is a finite set, we note $\mathcal{U}(S)$ the uniform distribution over $S$, and shorthand $x \stackrel{\$}{\leftarrow} S$ for $x \leftarrow \mathcal{U}(S)$.

**Definition 2 (Bernoulli).** Given a real $0 \le p \le 1$, we define the Bernoulli distribution $\mathcal{B}(p)$ that returns 1 with probability $p$, and 0 otherwise.

**Definition 3 (Discrete Gaussians).** Given a positive definite $\Sigma \in \mathbb{R}^{m \times m}$, we note $\rho_{\sqrt{\Sigma}}$ the Gaussian function defined over $\mathbb{R}^m$ as $\rho_{\sqrt{\Sigma}}(\mathbf{x}) = \exp\left(-\frac{\mathbf{x}^\mathrm{T}\cdot\Sigma^{-1}\cdot\mathbf{x}}{2}\right)$. The above definition may be extended to $(\Sigma, \mathbf{x}) \in \mathcal{K}^{m \times m} \times \mathcal{K}^m$ by treating $\Sigma$ as a block-circulant matrix in $\mathbb{R}^{nm \times nm}$ and $\mathbf{x}$ as a vector in $\mathbb{R}^nm$.

We may note $\rho_{\sqrt{\Sigma},c}(\mathbf{x}) = \rho_{\sqrt{\Sigma}}(\mathbf{x}-c)$. When $\Sigma$ is of the form $\sigma \cdot \mathbf{I}_m$, where $\sigma \in \mathbb{Q}^+$ a positive rational and $\mathbf{I}_m$ is the identity matrix, we note $\rho_{\sigma,c}$ as shorthand for $\rho_{\sqrt{\Sigma},c}$.

For any countable set $S \subset \mathcal{K}^m$, we note $\rho_{\sqrt{\Sigma},c}(S) = \sum_{\mathbf{x} \in \mathcal{K}^m} \rho_{\sqrt{\Sigma},c}(\mathbf{x})$ whenever this sum converges. Finally, when $\rho_{\sqrt{\Sigma},c}(S)$ converges, the discrete Gaussian distribution $D_{S,c,\sqrt{\Sigma}}$ is defined over $S$ by its probability distribution function
$$D_{S,\sqrt{\Sigma},c}(\mathbf{x}) = \frac{\rho_{\sqrt{\Sigma},c}(\mathbf{x})}{\rho_{\sqrt{\Sigma},c}(S)}.$$

**Security parameter.** We note $\kappa$ the security parameter.

## 2.2 Threshold signatures

We recall the definition of an $R$-round threshold signature from [KRT24]. It is defined as a tuple $\mathrm{TS} = (\mathrm{Setup}, \mathrm{Keygen}, (\mathrm{Sign}_i)_{i \in [R]}, \mathrm{Combine}, \mathrm{Verify})$. In particular, it does not make use of unique session identifiers as opposed to [DKM$^+$24].

We note $\mathrm{act} \subseteq [N]$ a set of $T$ parties used for signing. Each signer $i$ maintains a state $\mathrm{st}_i$ to retain short-lived session-specific information.

$\mathrm{Setup}(\kappa, N, T) \to \mathrm{pp}$. The setup algorithm takes as input a security parameter $\kappa$, the total number of parties $N$, the reconstruction threshold $T \le N$, and outputs a set of public parameters $\mathrm{pp}$.

$\mathrm{Keygen}(\mathrm{pp}) \to (\mathrm{vk}, (\mathrm{sk}_i)_{i \in [N]})$. The key generation algorithm takes as input the public parameters, and outputs a verification key $\mathrm{vk}$, and partial private keys $(\mathrm{sk}_i)_{i \in [N]}$.

$\mathrm{Sign}_r(\mathrm{vk}, \mathrm{act}, \mathrm{msg}, (\mathrm{pm}^j_{r-1})_{j \in \mathrm{act}}, i, \mathrm{sk}_i, \mathrm{st}_i) \to (\mathrm{pm}^i_r, \mathrm{st}_i)$ for $r = 1, \dots, R$. The signing algorithm for the $r$th-round takes as input the verification key $\mathrm{vk}$, the set of signers $\mathrm{act}$, a message $\mathrm{msg}$, the protocol messages exchanged during the previous round $(\mathrm{pm}^j_{r-1})_{j \in \mathrm{act}}$, as well as the partial private key $\mathrm{sk}_i$ and state $\mathrm{st}_i$ of user $i$, and it outputs a new message $\mathrm{pm}^i_r$ and updated state $\mathrm{st}_i$. We define $\mathrm{pm}^i_0 = \perp$. Note also that one may choose to delay passing $\mathrm{msg}$, $\mathrm{act}$ to a round later than the first.
Combine(vk, act, msg, $(pm_r^i)_{r \in [R], i \in \text{act}}$) → sig. The aggregation algorithm takes as input the verification key vk, the set of signers act, the message msg, and all the messages exchanges during the protocol $(pm_r^i)_{r \in [R], i \in \text{act}}$ and outputs a signature sig.

Verify(vk, msg, sig) → 0 or 1. The verification algorithm takes as input a verification key vk, a message msg, and a signature sig, and outputs 1 if sig is valid and 0 otherwise.

A key property of threshold signatures is unforgeability, which ensures that an adversary cannot produce valid signatures without the cooperation of honest parties. Several security models exist, differing in whether the adversary chooses corrupted users selectively [DKM+24] or adaptively [KRT24], and whether the communication channel is fully controlled by the adversary [DKM+24], or requires consensus properties [ENP24, dPENP25], and for which messages a forgery is accepted.

In this work, we consider the unforgeability notion from [DKM+24] adapted to remove the use of session identifiers. It ensures selective security – i.e. corrupted users are chosen before executing the protocol, a communication channel fully controlled by the adversary, and forgeries are accepted for messages for which no signing oracle was called. Although proving adaptive security would be preferable, it often requires heavier protocols for what appears to be proof artifacts. It is thus standard to prove only selective security.

**Definition 4 (Unforgeability of a threshold signature).** For a R round threshold signature scheme TS, the advantage of an adversary A (with oracle access to a random oracle H) against the unforgeability of TS is defined as

$$ \mathrm{Adv}_{\mathrm{TS},A}^{\mathrm{TS-UF}}(\kappa, N, T) := \Pr \left[ \mathrm{Game}_{\mathrm{TS},A}^{\mathrm{TS-UF}}(\kappa, N, T) = 1 \right] $$

where $\mathrm{Game}_{\mathrm{TS},A}^{\mathrm{TS-UF}}$ is described in Fig. 1. We say that TS is unforgeable in the random oracle model, if for all PPT adversary A, $\mathrm{Adv}_{\mathrm{TS},A}^{\mathrm{TS-UF}}(\kappa, N, T) \le \mathrm{negl}(\kappa)$.

We also wish to ensure correctness, i.e. that a valid signature is output when signers behave honestly. We however tolerate a probability of abort to support the Fiat-Shamir with Aborts paradigm.

**Definition 5 (Correctness of a threshold signature with aborts).** We say that a R round threshold signature with aborts is p-correct if for all but a negligible portion of keypairs V, we have for any message msg, set of signers act,

$$ \Pr \left[ \mathrm{Game}_{\mathrm{TS}}^{\mathrm{TS-corrr}}(\kappa, N, T, \mathrm{msg}, \mathrm{act}) \neq \perp \mid (\mathrm{vk}, (\mathrm{sk}_i)_{i \in [N]}) \notin V \right] \ge p $$

and

$$ \Pr \left[ \mathrm{Game}_{\mathrm{TS}}^{\mathrm{TS-corrr}}(\kappa, N, T, \mathrm{msg}, \mathrm{act}) = 0 \mid (\mathrm{vk}, (\mathrm{sk}_i)_{i \in [N]}) \notin V \right] = \mathrm{negl}(\kappa) $$

assuming $\Pr[\mathrm{Keygen}(\mathrm{pp}) \in V, \mathrm{pp} := \mathrm{Setup}(\kappa, N, T)] = \mathrm{negl}(\kappa)$, where $\mathrm{Game}_{\mathrm{TS}}^{\mathrm{TS-corrr}}$ is defined in Fig. 2.
<table><caption>Fig. 1: Unforgeability game for a threshold signature, where $H$ denotes the random oracle. We consider that the $OSign_r$ oracles return $⊥$ if the corresponding $ShareSign_r$ fails to output a protocol message. The game returns 0 if a requirement `req` fails. Finally, the adversary $\mathcal{A}$ wins if the game `TS-UF` returns 1, i.e. if it forged a new signature.</caption><thead><tr><th>Game<sup>TS-UF</sup><sub>TS,A</sub> (κ, N, T)</th><th>OSign<sub>r</sub> (act, msg, i, (pm<sup>j</sup><sub>r-1</sub>)<sub>j∈act</sub>)</th></tr></thead><tbody><tr><td>1: Q<sub>msg</sub> := ∅</td><td>1: req { i ∈ [N] ∧ i ∈ act ∩ honest }</td></tr><tr><td>2: pp ← Setup(κ, N, T)</td><td>2: Q<sub>msg</sub> := Q<sub>msg</sub> ∪ {msg}</td></tr><tr><td>3: corrupt, st<sub>A</sub> ← A(pp)</td><td>3: (pm<sup>i</sup><sub>r</sub>, st<sub>i</sub>) ← ShareSign<sub>r</sub>(vk, act, msg, (pm<sup>j</sup><sub>r-1</sub>)<sub>j∈act</sub>, i, sk<sub>i</sub>, st<sub>i</sub>)</td></tr><tr><td>4: assert{ corrupt ⊆ [N] }</td><td>4: return pm<sup>i</sup><sub>r</sub></td></tr><tr><td>5: assert{ |corrupt| &lt; T }</td><td></td></tr><tr><td>6: honest := [N]\corrupt</td><td></td></tr><tr><td>7: (vk, (sk<sub>i</sub>)<sub>i∈[N]</sub>) ← Sign.Keygen(pp)</td><td></td></tr><tr><td>8: for i ∈ honest do</td><td></td></tr><tr><td>9: st<sub>i</sub> := ∅</td><td></td></tr><tr><td>10: (msg, sig) ← A<sup>H</sup>(OSign<sub>i</sub>(·))<sub>i∈[R]</sub> (st<sub>A</sub>, vk, (sk<sub>i</sub>)<sub>i∈corrupt</sub>)</td><td></td></tr><tr><td>11: req { msg /∈ Q<sub>msg</sub> }</td><td></td></tr><tr><td>12: return Verify(vk, msg, sig)</td><td></td></tr></tbody></table>

<table><caption>Fig. 2: Correctness game for a threshold signature with aborts.</caption><thead><tr><th>Game<sup>TS-cor</sup><sub>TS</sub> (κ, N, T, msg, act)</th></tr></thead><tbody><tr><td>1: pp ← Setup(κ, N, T)</td></tr><tr><td>2: (vk, (sk<sub>i</sub>)<sub>i∈[N]</sub>) ← Sign.Keygen(pp)</td></tr><tr><td>3: for i ∈ [N] do</td></tr><tr><td>4: st<sub>i</sub> := ∅</td></tr><tr><td>5: for r ∈ [R] do</td></tr><tr><td>6: for i ∈ act do</td></tr><tr><td>7: (pm<sup>i</sup><sub>r</sub>, st<sub>i</sub>) ← ShareSign<sub>r</sub>(vk, act, msg, (pm<sup>j</sup><sub>r-1</sub>)<sub>j∈act</sub>, i, sk<sub>i</sub>, st<sub>i</sub>)</td></tr><tr><td>8: if ∃i ∈ act, pm<sup>i</sup><sub>R</sub> = abort then</td></tr><tr><td>9: return ⊥</td></tr><tr><td>10: sig := Combine(vk, act, (pm<sup>i</sup><sub>r</sub>)<sub>r∈[R],i∈act</sub>)</td></tr><tr><td>11: return Verify(vk, msg, sig)</td></tr></tbody></table>

## 2.3 Modulus Rounding

As previous works, we rely on rounding to reduce the size of public keys and signatures.

Let $\nu \in \mathbb{N}\{0\}$. Any integer $x \in \mathbb{Z}$ can be uniquely decomposed as:

$$x = 2^{\nu} \cdot x_{\perp} + x_{\perp}, \quad (x_{\perp}, x_{\perp}) \in \mathbb{Z} \times [-2^{\nu-1}, 2^{\nu-1} - 1], \quad (1)$$
which consists essentially in separating the lower-order bits from the higher-order ones. We define the function $[\cdot]_\nu : \mathbb{Z} \to \mathbb{Z}$ such that $[x]_\nu = [x/2^\nu] = x_\tau$, where $[\cdot] : \mathbb{R} \to \mathbb{Z}$ denotes the rounding operator. More precisely the “rounding half-up” method $[x] = [x + \frac{1}{2}]$ where half-way values are rounded up: e.g. $[2.5] = 3$ and $[-2.5] = -2$. With a slight overload of notation, when $q > 2^\nu$, we extend $[\cdot]_\nu$ to take inputs in $\mathbb{Z}_q$, in which case, we assume the output is an element in $\mathbb{Z}_{q_\nu}$ where $q_\nu = [q/2^\nu]$. Formally, we define:

$$[\cdot]_\nu : \mathbb{Z}_q \to \mathbb{Z}_{q_\nu} = \mathbb{Z}_{[q/2^\nu]} \quad \text{s.t.} \quad [x]_\nu = [x/2^\nu] \mod q_\nu = (x)_\tau \mod q_\nu$$

where $x \in \mathbb{Z}_q$ is assumed to have as representative an integer in $\{0, ..., q-1\}$. The function $[\cdot]_\nu$ naturally extends to vectors coefficient-wise.

We also recall a useful lemma from [DKM+24, EKT24] to bound the offset introduced by rounding.

**Lemma 1.** Let $\nu, q$ positive integers such that $q > 2^\nu, \nu \ge 4$, and set $q_\nu = [q/2^\nu]$. Moreover, assume that $q_\nu = [q/2^\nu]$, i.e. $q$ can be decomposed as $q = 2^\nu \cdot q_\nu + q_\perp$ with $q_\perp \in [0, 2^{\nu-1} - 1]$. Then, for any $x \in \mathbb{Z}_q$, we have

$$|x - 2^{\nu} \cdot [x]_{\nu}| \le 2^{\nu} - 1 \qquad (2)$$

Moreover, for any $\mathbf{x}, \delta \in \mathbb{Z}_q^n$, we have

$$\|2^{\nu} \cdot ([\mathbf{x} + \delta]_{\nu} - [\mathbf{x}]_{\nu})\| \le \|2^{\nu} \cdot [\delta]_{\nu} \mod q\| + \|\mathbf{1}\| \cdot 2^{\nu} \qquad (3)$$

## 2.4 Hardness Assumptions

We will rely on the SelfTargetMSIS problem [DKL+18, KLS18], in this variant of MSIS the problem is defined relative to some hash function. SelfTargetMSIS is shown to be as hard as MSIS in the random oracle model when the range of the hash function is exponentially large with a standard proof using the forking lemma [FS87, BN06]. We will directly work with SelfTargetMSIS, and will estimate its concrete security based on the best known attacks.

**Definition 6 (SelfTargetMSIS).** Let $k, \ell, q$ be integers, $B_{\text{stmsis}} > 0$ be a real number, and $\| \cdot \|$ be a norm. Let $C$ be a subset of $\mathcal{R}_q$, and let $G : \mathcal{R}_q^k \times \{0, 1\}^{2\kappa} \to C$ be a cryptographic hash function modeled as a random oracle. The advantage $\text{Adv}_A^{\text{SelfTargetMSIS}}(\kappa)$ of an adversary $\mathcal{A}$ against the Self Target MSIS problem $\text{SelfTargetMSIS}_{q, k, \ell, C, B_{\text{stmsis}}, \|\cdot\|}$ is defined as:

$$\text{Adv}_A^{\text{SelfTargetMSIS}}(\kappa) = \Pr\left[(\text{msg}, \mathbf{z}) \leftarrow \mathcal{A}^G(\mathbf{A}), (\text{msg}, \mathbf{z}) \in \{0, 1\}^{2\kappa} \times \mathcal{R}_q^{k+\ell} : \right. \\ \left. \left(\mathbf{z} = \begin{bmatrix} \mathbf{z}' \\ c \end{bmatrix}\right) \wedge (\|\mathbf{z}\| \le B_{\text{stmsis}}) \wedge G(\begin{bmatrix} \mathbf{I} & \mathbf{A} \end{bmatrix} \cdot \mathbf{z}, \text{msg}) = c\right]$$

where $\mathbf{A} \stackrel{\$}{\leftarrow} \mathcal{R}_q^{k \times \ell}$.

The SelfTargetMSIS$_{q, k, \ell, \beta}$ assumption states that any efficient adversary $\mathcal{A}$ has a negligible advantage $\text{Adv}_A^{\text{SelfTargetMSIS}}(\kappa)$.
We also rely on the MLWE assumption.

**Definition 7 (MLWE).** Let $k, \ell, q$ be integers, $\mathcal{D}_s$ be a probability distribution over $\mathcal{R}^{k+\ell}$. The advantage $\text{Adv}_A^{\text{MLWE}}(\kappa)$ of an adversary $\mathcal{A}$ against the Module Learning with Errors problem $\text{MLWE}_{q,k,\ell,\mathcal{D}_s}$ is defined as:

$$ \text{Adv}_A^{\text{MLWE}}_{q,k,\ell,\mathcal{D}_s}(\kappa) = \left| \Pr[1 \leftarrow \mathcal{A}(\mathbf{A}, [\mathbf{I}_k \mathbf{A}] \cdot \mathbf{s})] - \Pr[1 \leftarrow \mathcal{A}(\mathbf{A}, \mathbf{u})] \right|, $$

where $(\mathbf{A}, \mathbf{u}) \xleftarrow{\$} \mathcal{R}_q^{k \times \ell} \times \mathcal{R}_q^k, \mathbf{s} \leftarrow \mathcal{D}_s^{k+\ell}$. The MLWE$_{q,k,\ell,\mathcal{D}_s}$ assumption states that any efficient adversary $\mathcal{A}$ has a negligible advantage $\text{Adv}_A^{\text{MLWE}}_{q,k,\ell,\mathcal{D}_s}(\kappa)$.

## 2.5 Rejection Sampling

The Fiat-Shamir with aborts type of signatures heavily rely on the rejection sampling technique introduced in [Lyu09], which we recall with slightly different notations.

<table><caption>Fig. 3: Rejection algorithm and ideal algorithm.</caption><thead><tr><th>Rej(v, χ<sub>z</sub>, χ<sub>r</sub>, M) → z ∈ ℝ<sup>k+ℓ</sup> ∪ {⊥}</th><th>Ideal(χ<sub>z</sub>, M) → z ∈ ℝ<sup>k+ℓ</sup> ∪ {⊥}</th></tr></thead><tbody><tr><td>1: r ← χ<sub>r</sub></td><td>1: z ← χ<sub>z</sub></td></tr><tr><td>2: z := v + r</td><td>2: b ← B(1/M)</td></tr><tr><td>3: b ← B(min(χ<sub>z</sub>(z)/Mχ<sub>r</sub>(r), 1))</td><td>3: if b = 0 then</td></tr><tr><td>4: if b = 0 then</td><td>4: z = ⊥</td></tr><tr><td>5: z = ⊥</td><td>5: return z</td></tr><tr><td>6: return z</td><td></td></tr></tbody></table>

We will extend the algorithm Rej to Rej($v, \chi_z, \chi_r, M; r$) to parse the randomness $r \leftarrow \chi_r$ as an input. We will also write $(z|\text{acc})$ to denote the distribution of $z := v+r$ conditioned on $b=1$, and $(z|\text{rej})$ to denote the distribution of $z := v+r$ conditioned on $b=0$ (note that in that case $z = \perp$ but the distribution we are interested in is the one of $v+r$ so we abuse this notation).

The aim of rejection sampling is to map a distribution $v+\chi_r$ – that depends on the secret – to a distribution $\chi_z$ that doesn't. We prove in Lemma 4 that the algorithms Rej and Ideal are indistinguishable as well as other properties.

## 2.6 Σ-protocols with Aborts

We recall the notion of Σ-protocols with Aborts that are often used to model rejection sampling based protocols, and its associated zero-knowledge properties. Although we don't use them to formalize our threshold signature, these notions can provide a broader understanding of the potential applications of our simulation result Lemma 5.
**Definition 8 (Σ-protocol with Aborts).** Let $\mathcal{X}, \mathcal{Y}$ be two finite sets. A Σ-protocol for a relation $R \subset \mathcal{X} \times \mathcal{Y}$ with commitment set $W$, challenge set $C$ and response set $\mathcal{Z}$ is a 3-round interactive proof system between a prover written as $P = (P_1, P_2)$ and a verifier $V = (V_1, V_2)$ with the following specifications:

- $P_1: (x, y) \to (w, st)$ is a PPT algorithm that takes as input a pair of strings in $\mathcal{X} \times \mathcal{Y}$ and outputs a commitment $w \in W$ and a state $st \in \{0, 1\}^*$

- $V_1: (x, w) \to c$ is a PPT algorithm that takes as inputs a string $x \in \mathcal{X}$ and a commitment $w \in W$ and outputs a challenge $c \in C$

- $P_2: (x, y, w, c, st) \to z$ is a PPT algorithm that takes as inputs a pair of strings in $\mathcal{X} \times \mathcal{Y}$, a commitment $w \in W$, a challenge $c \in C$, and a state $st$ and outputs a response $z \in \mathcal{Z} \cup \{\perp\}$ (we say that $P_2$ aborts if it outputs $\perp$);

- $V_2: (x, w, c, z) \to b \in \{0, 1\}$ is a deterministic polynomial-time algorithm that takes as inputs a string $x \in \mathcal{X}$, a commitment $w \in W$, a challenge $c \in C$, and a response $z \in \mathcal{Z}$ and outputs a bit $b$ which represents acceptance or rejection; in the case that $z = \perp$, it returns 0.

The literature considers two different notions of zero-knowledge for Σ-protocols with aborts, depending on whether aborted transcripts need to be simulated: Honest-Verifier Zero-Knowledge (HVZK), and its counterpart no-abort Honest-Verifier Zero-Knowledge (naHVZK).

**Definition 9 (Computational Honest-Verifier Zero-Knowledge).** A Σ-protocol $((P_1, P_2), (V_1, V_2))$ for a relation $R$ is HVZK if there exists a PPT simulator $Sim$ such that for all PPT algorithm $\mathcal{A}$ and all $(x, y) \in R$, the following advantage is negligible:

$$ \text{Adv}(\mathcal{A}) := \left| \Pr \left[ \begin{array}{l} \mathcal{A}((w, c, z), y) = 1 \\ \quad (w, st) \leftarrow P_1(x, y) \\ \quad c \leftarrow V_1(x, w) \\ \quad z \leftarrow P_2(x, y, c, w, st) \end{array} \right] \\ - \Pr \left[ \mathcal{A}((w, c, z), y) = 1 \middle| (w, c, z) \leftarrow \text{Sim}(x) \right] \right| $$

**Definition 10 (Computational no-abort Honest-Verifier Zero-Knowledge).**

A Σ-protocol for a relation $R$ is naHVZK if there exists a PPT simulator $Sim$ such that for all PPT algorithm $\mathcal{A}$ and all $(x, y) \in R$, the distributions of simulated transcripts $(w, c, z)$ and $y$ are indistinguishable from the real distribution produced by Σ, conditioned on the event $z \neq \perp$.

## 2.7 The Renyi divergence

We will use the Renyi divergence throughout this work to measure the divergence of two distributions. We define it as in [BLL$^{+}$15].

Let $\mathcal{P}, \mathcal{Q}$ two discrete distributions such that $\text{Supp}(\mathcal{P}) \subseteq \text{Supp}(\mathcal{Q})$, and $\alpha \in (1, +\infty)$. The Renyi divergence of order $\alpha$ is defined as

$$ R_{\alpha}(\mathcal{P} || \mathcal{Q}) = \left( \sum_{x \in \text{Supp}(\mathcal{P})} \frac{\mathcal{P}(x)^{\alpha}}{\mathcal{Q}(x)^{\alpha-1}} \right)^{1/(\alpha-1)} $$
We also define $R_{\infty}(\mathcal{P}||\mathcal{Q}) = \max_{x \in \text{Supp}(\mathcal{P})} \frac{\mathcal{P}(x)}{\mathcal{Q}(x)}$.

The Renyi divergence provides very interesting properties for cryptographic purposes that can be found in [vEH14, BLL$^{+15}$]. We recall some important ones.

**Lemma 2 (Lemma 2.9, [BLL$^{+15}$]).** For two distributions $\mathcal{P}, \mathcal{Q}$, the Renyi divergence satisfies the following properties:

- **Data processing inequality.** For any function $f$, $R_{\alpha}(\mathcal{P}^f||\mathcal{Q}^f) \le R_{\alpha}(\mathcal{P}||\mathcal{Q})$, where $\mathcal{P}^f$ (resp. $\mathcal{Q}^f$) denotes the distribution of $f(y)$ induced by sampling $y \leftarrow \mathcal{P}$ (resp. $y \leftarrow \mathcal{Q}$).

- **Multiplicativity.** Assume that $\mathcal{P}$ and $\mathcal{Q}$ are the joint distributions of a tuple of random variables $(x_i)_i$. We note $(\mathcal{P}_i)_i, (\mathcal{Q}_i)_i$ the marginal distributions of the $(x_i)_i$. If the $(x_i)_i$ are independent under $\mathcal{P}$ and $\mathcal{Q}$, then $R_{\alpha}(\mathcal{P}||\mathcal{Q}) = \prod_i R_{\alpha}(\mathcal{P}_i||\mathcal{Q}_i)$.

- **Probability preservation.** For any event $E \subseteq \text{Supp}(\mathcal{Q})$, we have

$$ \mathcal{Q}(E) \ge \mathcal{P}(E)^{\alpha/(\alpha-1)}/R_{\alpha}(\mathcal{P}||\mathcal{Q}) $$

We can also get a form of multiplicativity for a distribution of tuples, even if the individual components are not independent. Typically, they would all depend on the value of a secret, and would become independent after conditioning on it. We recall a lemma covering this case from [HPRR20].

**Lemma 3 ([HPRR20], Proposition 4).** Let $\mathcal{P}, \mathcal{Q}$ the joint distributions of random variables $(x_i)_i$. Note $\mathcal{P}_{i,|x_{<i}=v}, \mathcal{Q}_{i,|x_{<i}=v}$, the conditional distributions of $x_i$ given $x_{<i} = v_{<i}$. Assume $R_{\alpha}(\mathcal{P}_{i,|x_{<i}=v_{<i}}||\mathcal{Q}_{i,|x_{<i}=v_{<i}}}) \le r_{\alpha,i}$ for any possible $v_{<i}$. Then,

$$ R_{\alpha}(\mathcal{P}||\mathcal{Q}) \le \prod_{i} r_{\alpha,i} $$

# 3 Thresholdizing the Fiat-Shamir with Aborts Signature Scheme

In this section, we show how we can construct a very compact and practical distributed signature scheme for small thresholds. At a high level, it builds on Lyubashevsky's Fiat-Shamir with Aborts signature scheme [Lyu09], and lifts it to the $T$-out-of-$N$ setting using the recent work [dPENP25] that introduced the possibility of sampling short secret sharings for use in lattice-based schemes. The threshold setting however introduces new forms of leakage incompatible with previous proof strategies for Fiat-Shamir with Abort. While this was overcome in [DOTT21, BTT22] by leveraging advanced primitives, this was at the cost of signature size and practicality. In this section, we will introduce new proof techniques to overcome these challenges and avoid a heavy increase in parameters in the threshold setting.
<table><caption>Table 2: Overview of parameters used in Fiat-Shamir with Aborts and its threshold variant.</caption><thead><tr><th>Parameter</th><th>Explanation</th></tr></thead><tbody><tr><td>R<sub>q</sub></td><td>Polynomial ring R<sub>q</sub> = Z[X]/(q, X<sup>n</sup> + 1)</td></tr><tr><td>(k, l)</td><td>Dimension of the public matrix A ∈ R<sub>q</sub><sup>k×l</sup></td></tr><tr><td>χ<sub>sk</sub></td><td>Distribution used for sampling secrets</td></tr><tr><td>χ<sub>r</sub></td><td>Distribution used for sampling randomness r<sub>i</sub></td></tr><tr><td>χ<sub>z</sub></td><td>Target distribution for the responses z<sub>i</sub></td></tr><tr><td>M</td><td>Rejection rate per party</td></tr><tr><td>ν<sub>b</sub></td><td>Amount of bit dropping performed on verification key</td></tr><tr><td>ν<sub>w</sub></td><td>Amount of bit dropping performed on (aggregated) commitment</td></tr><tr><td>(C ⊂ R<sub>q</sub>, ω)</td><td>Challenge set {c ∈ R<sub>q</sub> | ||c||<sub>∞</sub> = 1 ∧ ||c||<sub>1</sub> = ω} s.t. |C| ≥ 2<sup>κ</sup></td></tr><tr><td>B</td><td>Bound on the signature norm</td></tr><tr><td>p<sub>acc</sub></td><td>Total acceptance probability p<sub>acc</sub> = (1/M)<sup>T</sup></td></tr></tbody></table>

## 3.1 Fiat-Shamir with Aborts (FSwA)

We first present a slight generalization of the Lyubashevky’s Fiat-Shamir with Aborts scheme [Lyu09], in which we do not specify the distribution from which the secret and randomness are sampled, and where the distribution output by rejection sampling is not necessarily a shift of the one in input. We do so to be able to cover all subsequent works [DDLL13, DKL+18, DFPS22, BBRS24], which offer trade-offs between ease of implementation and compactness. This generalization is similar to the one of [DFPS22].

Before proving the correctness and unforgeability of the scheme in Fig. 4, we present some results on the rejection sampling algorithm. These results are similar to the ones given in [DFPS22] but we achieve tighter bounds in two ways. We first observe that we can replace the variable $\varepsilon(\mathbf{v}) = \sum_{\mathbf{x} \in S} \chi_{\mathbf{z}}(\mathbf{x})$ that was used in [DFPS22] with the strictly smaller $\varepsilon(\mathbf{v}) = \sum_{\mathbf{x} \in S} \chi_{\mathbf{z}}(\mathbf{x}) - M\chi_{\mathbf{r}}(\mathbf{x} - \mathbf{v})$. Second we use a finer-grained analysis of the Renyi divergence of order $\alpha$ to obtain a bound $1 + \varepsilon/M$ rather than $1 + \frac{\alpha}{\alpha-1}\varepsilon/M + O(\varepsilon^2)$ as in [DFPS22].

**Lemma 4.** Let any $M > 1$, $B > 0$, distributions $\chi_r$, $\chi_z$, and $T$ over $\mathcal{R}^{k+\ell}$ such that $\mathbf{v} \leftarrow T$ implies $\|\mathbf{v}\| \le B$ with overwhelming probability. Let $S = \{\mathbf{x} \in \mathcal{R}^{k+\ell} | \chi_z(\mathbf{x}) > M\chi_r(\mathbf{x} - \mathbf{v})\}$. For $\mathbf{v} \in \mathcal{R}^{k+\ell}$ let $\varepsilon(\mathbf{v}) = \sum_{\mathbf{x} \in S} \chi_z(\mathbf{x}) - M\chi_r(\mathbf{x} - \mathbf{v})$ and $\varepsilon$ be such that $\Pr_{\mathbf{v} \leftarrow T}[\varepsilon(\mathbf{v}) \ge \varepsilon] = \text{negl}(\kappa)$ and $\delta = \Delta(\mathbf{z}|\text{acc}, \chi_z)$. We have:

$$ \frac{1 - \varepsilon}{M} \le \Pr[\mathbf{z} \ne \perp] \le \frac{1}{M} \\ \delta \le \frac{2\varepsilon}{1 - \varepsilon} \\ R_{\infty}(\text{Rej}||\text{Ideal}) \le 1 + \frac{\varepsilon}{M-1} \\ R_{\alpha}(\text{Rej}||\text{Ideal}) \le 1 + \frac{\varepsilon}{M} $$
<figure><img src="image_2.png" /><figcaption>Fig. 4: Fiat-Shamir with aborts for key distribution $\chi_{sk}$, randomness distribution $\chi_r$, and rejection distribution $\chi_z$.</figcaption></figure>

*Proof.* We prove the first inequality:

$$
\begin{align*}
\Pr[\mathbf{z} \neq \perp] &= \sum_S \Pr[\text{acc}|\mathbf{z} = \mathbf{x}] \Pr[\mathbf{z} = \mathbf{x}] + \sum_{R^{k+\ell} \setminus S} \Pr[\text{acc}|\mathbf{z} = \mathbf{x}] \Pr[\mathbf{z} = \mathbf{x}] \\
&= \sum_S 1 \cdot \chi_r(\mathbf{x} - \mathbf{v}) + \sum_{R^{k+\ell} \setminus S} \frac{\chi_z(\mathbf{x})}{M\chi_r(\mathbf{x})} \chi_r(\mathbf{x} - \mathbf{v}) \\
&= \sum_S \chi_r(\mathbf{x} - \mathbf{v}) - \frac{\chi_z(\mathbf{x})}{M} + \sum_{\mathcal{R}^{k+\ell}} \frac{\chi_z(\mathbf{x})}{M} \\
&= \frac{1 - \varepsilon(\mathbf{v})}{M}
\end{align*}
$$

We make the distribution of $\mathbf{z}|\text{accept}$ explicit:

$$
\begin{align*}
\forall \mathbf{x} \notin S; \Pr[\mathbf{z} = \mathbf{x}|\text{acc}] &= \frac{\Pr[\text{acc}|\mathbf{z}=\mathbf{x}] \cdot \Pr[\mathbf{z}=\mathbf{x}]}{\Pr[\text{acc}]} \\
&= \frac{\chi_{\mathbf{z}}(\mathbf{x})}{M\chi_{\mathbf{r}}(\mathbf{x}-\mathbf{v})} \chi_{\mathbf{r}}(\mathbf{x}-\mathbf{v}) \cdot \frac{M}{1-\varepsilon(\mathbf{v})} \\
&= \frac{\chi_{\mathbf{z}}(\mathbf{x})}{1-\varepsilon(\mathbf{v})} \\
\forall \mathbf{x} \in S; \Pr[\mathbf{z} = \mathbf{x}|\text{acc}] &= \frac{\Pr[\text{acc}|\mathbf{z}=\mathbf{x}] \cdot \Pr[\mathbf{z}=\mathbf{x}]}{\Pr[\text{acc}]} \\
&= 1 \cdot \chi_{\mathbf{r}}(\mathbf{x}-\mathbf{v}) \cdot \frac{M}{1-\varepsilon(\mathbf{v})} \\
&= \frac{M\chi_{\mathbf{r}}(\mathbf{x}-\mathbf{v})}{1-\varepsilon(\mathbf{v})}
\end{align*}
$$
From this we can get the second inequality:

$$
\begin{align*}
\Delta((\mathbf{z}|\text{acc}), \chi_{\mathbf{z}}) &= \sum_{S} |\text{Pr}[\mathbf{z} = \mathbf{x}|\text{acc}] - \chi_{\mathbf{z}}(\mathbf{x})| + \sum_{\mathcal{R}^{k+\ell} \setminus S} |\text{Pr}[\mathbf{z} = \mathbf{x}|\text{acc}] - \chi_{\mathbf{z}}(\mathbf{x})| \\
&= \sum_{S} \left| \frac{M\chi_{\mathbf{r}}(\mathbf{x} - \mathbf{v})}{1 - \varepsilon(\mathbf{v})} - \chi_{\mathbf{z}}(\mathbf{x}) \right| + \sum_{\mathcal{R}^{k+\ell} \setminus S} \left| \frac{\chi_{\mathbf{z}}(\mathbf{x})}{1 - \varepsilon(\mathbf{v})} - \chi_{\mathbf{z}}(\mathbf{x}) \right| \\
&\le \frac{1}{1 - \varepsilon(\mathbf{v})} \cdot \left( \sum_{S} |M\chi_{\mathbf{r}}(\mathbf{x} - \mathbf{v}) - \chi_{\mathbf{z}}(\mathbf{x})| + \varepsilon(\mathbf{v}) \sum_{\mathcal{R}^{k+\ell}} |\chi_{\mathbf{z}}(\mathbf{x})| \right) \\
&\le \frac{2\varepsilon}{1 - \varepsilon}
\end{align*}
$$

Finally we prove the property on the Renyi divergence

$$
\begin{align*}
R_{\infty}(\text{Rej} || \text{Ideal}) &= \max_{\mathbf{x} \in \mathcal{R}^{k+\ell} \cup \{\perp\}} \frac{\Pr[\text{Rej} = \mathbf{x}]}{\Pr[\text{Ideal} = \mathbf{x}]} \\
&= \frac{\Pr[\text{Rej} = \perp]}{\Pr[\text{Ideal} = \perp]} \\
&\le 1 + \frac{\varepsilon(\mathbf{v})}{M-1}
\end{align*}
$$

Finally we consider the proof for the Renyi divergence of order α:

$$
\begin{align*}
R_{\alpha}(\text{Rej} || \text{Ideal})^{\alpha-1} &= \sum_{S} \frac{(\text{Pr}[\mathbf{z} = \mathbf{x}|\text{acc}] \cdot \text{Pr}[\text{acc}])^{\alpha}}{(\chi_{\mathbf{z}}(x)/M)^{\alpha-1}} \\
&\quad + \sum_{\mathcal{R}^{n+\ell} \setminus S} \frac{(\text{Pr}[\mathbf{z} = \mathbf{x}|\text{acc}] \cdot \text{Pr}[\text{acc}])^{\alpha}}{(\chi_{\mathbf{z}}(x)/M)^{\alpha-1}} + \left(1 - \frac{1-\varepsilon}{M}\right)^{\alpha} \cdot \left(1 - \frac{1}{M}\right)^{-\alpha+1} \\
&= \sum_{S} \frac{M^{\alpha-1} \chi_{\mathbf{r}}(\mathbf{x} - \mathbf{v})^{\alpha}}{\chi_{\mathbf{z}}(x)^{\alpha-1}} + \sum_{\mathcal{R}^{k+\ell} \setminus S} \frac{\chi_{\mathbf{z}}}{M} + \left(1 + \frac{\varepsilon}{M-1}\right)^{\alpha} \cdot \left(1 - \frac{1}{M}\right) \\
&\le \sum_{S} \frac{M \chi_{\mathbf{r}}(\mathbf{x} - \mathbf{v})}{M} + \frac{1}{M} \left(1 - \sum_{S} \chi_{\mathbf{z}}(\mathbf{x})\right) + \left(1 - \frac{\varepsilon}{M-1}\right)^{\alpha} \cdot \left(1 - \frac{1}{M}\right) \\
&\le \frac{1-\varepsilon}{M} + \left(1 + \frac{\alpha\varepsilon}{M-1}\right) \cdot \left(1 - \frac{1}{M}\right) \\
&= 1 + \frac{(\alpha-1)\varepsilon}{M}
\end{align*}
$$

which gives the desired result.

<figure><img src="image_3.png" /></figure>

We can now prove the correctness and unforgeability of our generic scheme.

**Theorem 1 (Correctness of FSwA).** Let $B_{sc}$ be an overwhelming bound on $||cs||$, and $B_{\mathbf{z}}$ be an overwhelming bound on $\mathbf{x} \leftarrow \chi_{\mathbf{z}}$. Let

$$
\varepsilon = \max_{||\mathbf{v}|| \le B_{sc}} \left( \sum_{\substack{\mathbf{x} \in \mathcal{R}^{k+\ell} \\ \chi_{\mathbf{z}}(\mathbf{x}) > M \cdot \chi_{\mathbf{r}}(\mathbf{x} - \mathbf{v})}} (\chi_{\mathbf{z}}(\mathbf{x}) - M \cdot \chi_{\mathbf{r}}(\mathbf{x} - \mathbf{v})) \right)
$$
If $B \ge B_z + \|1\| \cdot \omega \cdot 2^{\nu_b} + \|1\| \cdot 3 \cdot 2^{\nu_w-1}$ then the signing protocol of figure Fig. 4 outputs a signature with probability at least $(1-\varepsilon)/M$ and the verification algorithm succeeds with overwhelming probability.

**Proof.** First, the signature algorithm outputs a signature with probability at least $(1 - \varepsilon)/M$ by observing that $\text{Rej}(\mathbf{v}, \cdot)$ outputs $\mathbf{z} \ne \perp$ with probability $(1 - \varepsilon(\mathbf{v}))/M$ as proven in Lemma 4 and noting that $\varepsilon$ takes the maximum of $\varepsilon(\mathbf{v})$ for possible $\mathbf{v}$ with all but negligible probability.

Then, it remains to prove that the produced signature is valid. The check $H_c(\mathbf{vk}, \mathbf{msg}, \mathbf{w}) = c$ is straightforwardly verified, and we thus focus on bounding the norm of $(\mathbf{z}, 2^{\nu_w}\mathbf{h})$.

The bound analysis is analogous to the proof of [dPENP25, Theorem 7] (which fixed the proof of [DKM+24, Lemma C.1]), although we extend their result to the infinite norm.

Note $\hat{\mathbf{b}}$, and $\hat{\mathbf{w}} = \mathbf{A} \cdot \mathbf{z} - c \cdot \hat{\mathbf{b}}$, such that $\mathbf{b} = [\hat{\mathbf{b}}]_{\nu_b}$, $\mathbf{w} = [\hat{\mathbf{w}}]_{\nu_w}$.

Now, we bound the difference between the hint $\mathbf{h}$ and $\mathbf{z}_2$,

$$ \begin{aligned} \|2^{\nu_w} \cdot \mathbf{h} - \mathbf{z}_2\| &= \left\| 2^{\nu_w} \cdot \left( [\mathbf{w}]_{\nu_w} - \left[ \bar{\mathbf{A}} \sum \mathbf{z}_1 - 2^{\nu_b} \cdot c \cdot \mathbf{b} \right]_{\nu_w} \right) - \mathbf{z}_2 \right\| \\ &= \left\| 2^{\nu_w} \cdot \left( [\mathbf{w}]_{\nu_w} - \left[ \mathbf{z}_2 + c \cdot \hat{\mathbf{b}} + \mathbf{w} - 2^{\nu_b} \cdot c \cdot \mathbf{b} \right]_{\nu_w} \right) - \mathbf{z}_2 \right\| \\ &= \left\| 2^{\nu_w} \cdot \left( [\mathbf{w}]_{\nu_w} - \left[ \mathbf{w} + c(\hat{\mathbf{b}} - 2^{\nu_b} \cdot \mathbf{b}) + \mathbf{z}_2 \right]_{\nu_w} \right) - \mathbf{z}_2 \right\| \\ &\le 3 \cdot 2^{\nu_w-1} \|1\| + \omega \left\| \hat{\mathbf{b}} - 2^{\nu_b} \cdot \mathbf{b} \right\| \quad (\text{applying [dPENP25, Lemma 6]}) \\ &\le \|1\| \cdot (3 \cdot 2^{\nu_w-1} + \omega \cdot 2^{\nu_b}) \quad (\text{applying [DKM+24, Lemma 3.2]}) \end{aligned} $$

From this we have $\|(\mathbf{z}_1, 2^{\nu_w} \cdot \mathbf{h})\| \le \|(\mathbf{z}_1, \mathbf{z}_2)\| + \|1\| \cdot (3 \cdot 2^{\nu_w-1} + \omega \cdot 2^{\nu_b}) = TB_2^{\text{ind}} + \|1\| \cdot (3 \cdot 2^{\nu_w-1} + \omega \cdot 2^{\nu_b}) = B_2$.

Putting it all together, $\|(\mathbf{z}_1, 2^{\nu_w} \cdot \mathbf{h})\| \le \|\mathbf{z}\| + \underbrace{\|c\|_1}_{\le \omega} \cdot \|\mathbf{1}\| \cdot 2^{\nu_b} + \|\mathbf{1}\| \cdot 3 \cdot 2^{\nu_w-1}$.

The probability that $\mathbf{z}$ produced by Rej has a norm larger than $B_z$, is at most $R_\infty(\text{Rej}||\text{Ideal})$ times larger than for a $\mathbf{z}$ produced by Ideal, i.e. $1 + \frac{\varepsilon}{M-1}$ times larger, it thus remains negligible.

We deduce that $\|\mathbf{z}\| \le B_z$ with overwhelming probability when $\mathbf{z} \leftarrow \text{Rej}$ and we finally obtain the bound from the statement.

□

**Theorem 2 (Unforgeability of FSwA).** Let $B_{sc}$ be an overwhelming bound on $\|\mathbf{cs}\|$. Let

$$ \varepsilon = \max_{\|\mathbf{v}\| \le B_{sc}} \left( \sum_{\substack{\mathbf{x} \in \mathbb{R}^{k+\ell} \\ \chi_{\mathbf{z}}(\mathbf{x}) > M \cdot \chi_{\mathbf{r}}(\mathbf{x}-\mathbf{v})}} (\chi_{\mathbf{z}}(\mathbf{x}) - M \cdot \chi_{\mathbf{r}}(\mathbf{x}-\mathbf{v})) \right) $$
The Fiat-Shamir with aborts protocol of Fig. 4 is existentially unforgeable under the MLWE and SelfTargetMSIS assumptions with the following advantage:

$$ \text{Adv}_{A}^{\text{EUF-CMA}} \le Q_s \frac{3M-1}{M} \left( \text{Adv}_{A}^{\text{MLWE}_{q,k,l,\ell,\chi_r}} + \text{Adv}_{A}^{\text{MLWE}_{q,k,l,\ell,\chi_z}} + \frac{2\epsilon}{1-\epsilon} \right) + Q_{H_c} Q_s^2 \left( \frac{2^{\nu_w} + 1}{q} \right)^{kn} \\ + \left( 1 + \frac{\epsilon}{M-1} \right)^{Q_s} \left( \text{Adv}_{A}^{\text{MLWE}_{q,k,l,\ell,\chi_{sk}}} + \text{SelfTargetMSIS}_{A}^{\text{MSIS}} \right) + \text{negl}(\kappa) $$

$$ \text{where } B_{\text{stmsis}} := \begin{cases} B + \sqrt{\omega} + (\omega \cdot 2^{\nu_b} + 2^{\nu_w+1}) \cdot \sqrt{dk} & \text{if } \|\cdot\| = \|\cdot\|_2 \\ B + \omega \cdot 2^{\nu_b} + 2^{\nu_w+1} & \text{if } \|\cdot\| = \|\cdot\|_{\infty} \end{cases}, Q_s \text{ is} $$

the number of signing queries, and $Q_{H_c}$ is the number of queries to the random oracle.

*Proof.* As this proof is subsumed by the one of threshold Fiat Shamir with aborts we leave it to Section B. □

## 3.2 Threshold Fiat-Shamir with Aborts

We can now present the threshold version of the Fiat-Shamir with abort scheme of Section 3.1. Fig. 5 presents key generation. The secret sharing algorithm RSS samples $(N_{N-T+1})$ small shares $s_I$, one for each set $I \subset [N]$ of cardinal $N-T+1$, and distributes each one to all the users in the corresponding set $I$. In doing so we ensure that for each set $S$ of $T-1$ users, none of the parties know the secret $s_I$ for $I = [N] \setminus S$, and that any set $S$ of $T$ parties jointly knows all the secrets $s_I$ for all sets $I$ of size $N-T+1$. This algorithm then outputs all the partial secret keys $(sk_i)_{i \in [N]}$ (each containing $(N_{N-T}^{-1})$ shares) and the secret $s$ that is the sum of all the shares. Key generation then proceeds as in the standard Fiat-Shamir with abort scheme by setting the public key as (the rounding of) the MLWE sample $b := A \cdot s$.

Signature is presented in Fig. 6. Each party will first commit to a vector $w_i = A \cdot r_i$ and reveal it to avoid rushing adversaries. Once this is done the challenge is derived from $w = \sum w_i$. And, using the Recover each party can choose which secrets $s_I$ they will sum to construct the partial response $z_i := c \cdot \sum s_I + r_i$.

Finally, responses can be publicly recombined in a single $z$ to which one can apply bitdropping. This algorithm as well as verification are presented in Fig. 7.

## 3.3 Security analysis

We now would like to establish the correctness and unforgeability of our scheme. We will need to ensure that the constant $M$, and distributions $\chi_z, \chi_r$ are properly selected for both usability and security: the probability of aborts must not be too high for concrete usage, and for security, the distribution of accepted $z$ should be 'close' to some ideal distribution $\chi_z$ - which is independent of the secret. The former requirement was achieved in previous works either using the statistical distance [Lyu12], or the Renyi divergence [BBD+23] to obtain smaller parameters.
<figure><img src="image_4.png" /><figcaption>Fig. 5: Algorithms for key generation in threshold Fiat-Shamir with Aborts.</figcaption></figure>

We note that a critical challenge appears in proving the unforgeability of our scheme. As opposed to previous works, our scheme reveals vectors $w_i$ even in case of aborts. It was left as an open question whether they can be revealed without compromising the scheme's security. [Lyu12, BBD+23] circumvents this issue as aborting transcripts are never revealed for a centralized signature. In the threshold case, [DOTT21, BTT22] avoided revealing the $w_i$ at the cost of using trapdoor homomorphic commitment, largely increasing signature size. Intuitively, if the distribution of $r_i$ conditioned on the rejection of $z$ has enough entropy, the distribution of $w_i = A \cdot r_i$ should appear uniformly distributed, and not leak anything about the secret. Devevey et al [DFPS23] concretized this intuition for LWE samples, proposing one lemma relying on the Leftover Hash Lemma, and one lemma relying on generic (non-tight) reductions between search-LWE and LWE. Their reductions however appear impractical for setting any parameters. We will provide in the following paragraphs the first tight proof that the aborting $w_i$ appear uniform in the MLWE setting for typical secret distributions, reducing to computational assumptions.

**Correctness.** We now move on to proving the correctness of our scheme.

**Theorem 3 (Correctness of threshold FSwA).** Let $B_{sc}$ be an overwhelming bound on $||cs||$ where $s$ is any partial signing key used in our scheme, and
<figure><img src="image_5.png" /><figcaption>Fig. 6: Algorithms for threshold Fiat-Shamir with Aborts. When an assertion fails, the function returns $\perp$.</figcaption></figure>

$B_{z,T}$ be an overwhelming bound on the sum of up to $T$ secrets $x_i \leftarrow \chi_z$. Let

$$ \varepsilon = \max_{\|\mathbf{v}\| \le B_{sc}} \left( \sum_{\substack{\mathbf{x} \in \mathbb{R}^{k+\ell} \\ \chi_z(\mathbf{x}) > M \cdot \chi_r(\mathbf{x}-\mathbf{v})}} (\chi_z(\mathbf{x}) - M \cdot \chi_r(\mathbf{x}-\mathbf{v})) \right) $$

If $B \ge B_{z,T} + \|1\| \cdot \omega \cdot 2^{\nu_b} + \|1\| \cdot 3 \cdot 2^{\nu_w-1}$ then the signing protocol of figure Fig. 4 outputs a signature with probability at least $((1 - \varepsilon)/M)^T$ and the verification algorithm succeeds with overwhelming probability.

*Proof.* The proof goes as in Theorem 1 for the computation of the bound $B$, and the main challenge resides in determining the success probability of our algorithm.

The protocol succeeds in outputting a signature if all parties output a signature, which happens with probability at least $((1 - \varepsilon)/M)^T$. $\square$

**Unforgeability.** We now prove the unforgeability of our threshold scheme. We start by introducing a result of indistinguishability from random of commitments $\mathbf{w}_i$ that resulted in an aborted $\mathbf{z}_i$.
<figure><img src="image_6.png" /><figcaption>Fig. 7: Aggregation and verification of signatures</figcaption></figure>

Formally, given a secret **s** and a challenge **c**, we note $\mathcal{D}_{\mathbf{z},\text{accept}}^{(s,c)}$ the distribution of the accepted **z** conditioned on the values of **s** and **c**.

The main novelty of our proofs lies in the following lemma that allows us to
prove the pseudo-uniformity of the aborted $\mathbf{w}_i$.

**Lemma 5.** Given a secret **s**, and challenge **c**, note $\mathcal{D}_{\mathbf{r},\text{reject}}^{(s,c)}$ the distribution of rejected vectors $\mathbf{r}_i$ conditioned on $(\mathbf{s}, \mathbf{c})$. Let $\mathcal{A}$ be an adversary against the MLWE$_{q,k,l,\ell, \mathcal{D}_{\mathbf{r},\text{reject}}^{s,c}}$ problem. There exist adversaries $\mathcal{B}_1, \mathcal{B}_2$ respectively against the MLWE$_{q,k,l,\ell, \chi_r}$ and MLWE$_{q,k,l,\ell, \chi_z}$ problems, running in time $T_{\mathcal{B}_1} \approx T_{\mathcal{B}_2} \approx T_{\mathcal{A}}$ such that:

$$
\mathrm{Adv}_{\mathcal{A}}^{\mathrm{MLWE}_{q,k,l,\ell, \mathcal{D}_{\mathbf{r},\text{reject}}^{s,c}}} \le \frac{1}{p} \cdot \left( \mathrm{Adv}_{\mathcal{B}_1}^{\mathrm{MLWE}_{q,k,l,\ell, \chi_r}} + \mathrm{Adv}_{\mathcal{B}_2}^{\mathrm{MLWE}_{q,k,l,\ell, \chi_z}} + \delta \right)
$$

where $p = \Pr[\text{Rej}(\mathbf{cs}, \chi_r, \chi_{sk}, M; \mathbf{r} \leftarrow \chi_r) = \perp]$ is the probability of rejection of
$\mathbf{z}$ conditioned on $(\mathbf{s}, \mathbf{c})$ and $\delta$ is the statistical distance between $\mathcal{D}_{\mathbf{z},\text{accept}}^{(s,c)}$ and the
target distribution $\chi_{\mathbf{z}}$.

Remark 2. Although we don’t use this formalism here, the FSwA paradigm can be generically captured by the notion of Σ-protocol with aborts (Definition 8), see for instance [DFPS23, Fig. 3]. The above Lemma 5 allows to tightly prove the stronger notion of HVZK (Definition 9), instead of naHVZK (Definition 10), i.e. aborted transcripts can safely be revealed in this Σ-protocol with aborts.

This appears particularly useful in the threshold setting where it is difficult
to hide intermediate computations, and could have applications to other lattice-
based constructions relying on a rejection sampling identification protocol.
Proof. Let $\mathcal{A}$ be an adversary against the MLWE$_{q,k,\ell,\mathcal{D}_{\mathbf{r},\text{reject}}^{s,c}}$ problem.

In the rest of this proof, we will note $\delta_{\mathcal{A}}^{\mathcal{D}} := \Pr[1 \leftarrow \mathcal{A}(\bar{\mathbf{A}}, [\mathbf{I}_k \bar{\mathbf{A}}] \cdot \mathbf{r}) | \mathbf{r} \leftarrow \mathcal{D}]$ and $\gamma_{\mathcal{A}} := \Pr[1 \leftarrow \mathcal{A}(\bar{\mathbf{A}}, \mathbf{u}) | \mathbf{u} \leftarrow \mathcal{U}(\mathcal{R}_q^k)]$ for conciseness.

Let $\mathcal{B}_1 := \mathcal{A}$ an adversary against MLWE$_{q,k,\ell,\chi_r}$.

Recall the definition of the MLWE advantage of $\mathcal{B}_1$ for the distribution $\chi_r$ with the above notations:

$$ \mathrm{Adv}_{\mathcal{B}_1}^{\mathrm{MLWE}}_{q,k,\ell,\chi_r} = |\delta_{\mathcal{B}_1}^{\chi_r} - \gamma_{\mathcal{B}_1}| $$

Interestingly, we can equivalently express $\chi_r$ as a process involving $\mathcal{D}_{\mathbf{r},\text{reject}}^{(s,c)}$ and $\mathcal{D}_{\mathbf{z},\text{accept}}^{(s,c)}$. Noting $p$ the probability of rejection of $\mathbf{z}$ conditioned on $(\mathbf{s}, c)$, $\chi_r$ has the same distribution as:

- Sample $v$: 1 with probability $p$, 0 otherwise.

- If $v=1$, sample and return $\mathbf{r} \leftarrow \mathcal{D}_{\mathbf{r},\text{reject}}^{(s,c)}$.

- If $v=0$, sample $\mathbf{z} \leftarrow \mathcal{D}_{\mathbf{z},\text{accept}}^{(s,c)}$ and return $\mathbf{r} := \mathbf{z} - c \cdot \mathbf{s}$.

We can thus rewrite

$$ \delta_{\mathcal{B}_1}^{\chi_r} = p \cdot \delta_{\mathcal{B}_1}^{\mathcal{D}_{\mathbf{r},\text{reject}}^{(s,c)}} + (1-p) \cdot \delta_{\mathcal{B}_1}^{\mathcal{D}_{\mathbf{z},\text{accept}}^{(s,c)} - c \cdot \mathbf{s}} $$

At this point, we can define an adversary $\mathcal{B}_2$ that on inputs $(\bar{\mathbf{A}}, \mathbf{u})$ calls $\mathcal{B}_1$ with $(\bar{\mathbf{A}}, \mathbf{u} - [\bar{\mathbf{A}} \mathbf{I}] \cdot c \cdot \mathbf{s})$, and returns the response. Then,

$$ \delta_{\mathcal{B}_1}^{\chi_r} = p \cdot \delta_{\mathcal{B}_1}^{\mathcal{D}_{\mathbf{r},\text{reject}}^{(s,c)}} + (1-p) \cdot \delta_{\mathcal{B}_2}^{\mathcal{D}_{\mathbf{z},\text{accept}}^{(s,c)}} $$

We additionally have $\gamma_{\mathcal{B}_1} = \gamma_{\mathcal{B}_2}$, so we can finally rewrite:

$$
\begin{align*}
\mathrm{Adv}_{\mathcal{B}_1}^{\mathrm{MLWE}}_{q,k,\ell,\chi_r} &= \left| p \cdot \delta_{\mathcal{B}_1}^{\mathcal{D}_{\mathbf{r},\text{reject}}^{(s,c)}} + (1-p) \cdot \delta_{\mathcal{B}_2}^{\mathcal{D}_{\mathbf{z},\text{accept}}^{(s,c)}} - \gamma_{\mathcal{B}_1} \right| \\
&= \left| p \cdot (\delta_{\mathcal{B}_1}^{\mathcal{D}_{\mathbf{r},\text{reject}}^{(s,c)}} - \gamma_{\mathcal{B}_1}) + (1-p) \cdot (\delta_{\mathcal{B}_2}^{\mathcal{D}_{\mathbf{z},\text{accept}}^{(s,c)}} - \underbrace{\gamma_{\mathcal{B}_2}}_{\gamma_{\mathcal{B}_2}}) \right| \\
&\ge p \cdot \left| \delta_{\mathcal{B}_1}^{\mathcal{D}_{\mathbf{r},\text{reject}}^{(s,c)}} - \gamma_{\mathcal{B}_1} \right| - (1-p) \cdot \left| \delta_{\mathcal{B}_2}^{\mathcal{D}_{\mathbf{z},\text{accept}}^{(s,c)}} - \gamma_{\mathcal{B}_2} \right| \\
&\ge p \cdot \mathrm{Adv}_{\mathcal{B}_1}^{\mathrm{MLWE}}_{q,k,\ell,\mathcal{D}_{\mathbf{r},\text{reject}}^{(s,c)}} - \mathrm{Adv}_{\mathcal{B}_2}^{\mathrm{MLWE}}_{q,k,\ell,\mathcal{D}_{\mathbf{z},\text{accept}}^{(s,c)}}
\end{align*}
$$

By the properties of the statistical distance, we have,

$$ \mathrm{Adv}_{\mathcal{B}_2}^{\mathrm{MLWE}}_{q,k,\ell,\mathcal{D}_{\mathbf{z},\text{accept}}^{(s,c)}} \le \mathrm{Adv}_{\mathcal{B}_2}^{\mathrm{MLWE}}_{q,k,\ell,\chi_z} + \delta $$

with $\delta$ the statistical distance between $\mathcal{D}_{\mathbf{z},\text{accept}}^{(s,c)}$ and $\chi_z$.

As $\mathcal{B}_1 = \mathcal{A}$, we conclude the proof by reordering the terms. $\square$
We now rely on this lemma to formally prove the unforgeability of our scheme.

**Theorem 4 (Unforgeability of threshold FSwA).** Let $B_{cs}$ be an over-whelming bound on $\|c \cdot s_i^{\text{part}}\|$ for any $c \in C$ over the randomness of Keygen, and

$$ \varepsilon = \max_{\|\mathbf{v}\| \le B_{sc}} \left( \sum_{\substack{\mathbf{x} \in \mathcal{R}^{k+\ell} \\ \chi_{\mathbf{x}}(\mathbf{x}) > M \cdot \chi_{\mathbf{r}}(\mathbf{x}-\mathbf{v})}} (\chi_{\mathbf{z}}(\mathbf{x}) - M \cdot \chi_{\mathbf{r}}(\mathbf{x}-\mathbf{v})) \right). $$

$$ \text{Define } B_{\text{stmsis}} := \begin{cases} B + \sqrt{\omega} + (\omega \cdot 2^{\nu_b} + 2^{\nu_w+1}) \cdot \sqrt{dk} & \text{if } \|\cdot\| = \|\cdot\|_2 \\ B + \omega \cdot 2^{\nu_b} + 2^{\nu_w+1} & \text{if } \|\cdot\| = \|\cdot\|_{\infty} \end{cases}. $$

Our threshold signature scheme is TS-UF secure under the MLWE assumptions over the distributions $\chi_{sk}, \chi_{r}$ and $\chi_{z}$, and under the SelfTargetMSIS$_{q,k,l+1, B_{\text{stmsis}}, \|\cdot\|}$ assumption.

Formally, let $\mathcal{A}$ be an adversary against the TS-UF security of our threshold scheme making $Q_s$ call to signing oracles, and at most $Q_{H_{\text{cmt}}}, Q_{H_c}$ queries respectively to the random oracles $H_{\text{cmt}}, H_c$. There exist adversaries $\mathcal{B}_s$ against the MLWE$_{q,k,l,\chi_{sk}}, \mathcal{B}_r$ against the MLWE$_{q,k,l,\chi_{r}}$ game, $\mathcal{B}_z$ against the MLWE$_{q,k,l,\chi_{z}}$ game, and $\mathcal{B}_{\text{stmsis}}$ against SelfTargetMSIS$_{q,k,l+1, C, B_{\text{stmsis}}, \|\cdot\|}$ running in time $T_{\mathcal{B}_s} \approx T_{\mathcal{B}_r} \approx T_{\mathcal{B}_z} \approx T_{\mathcal{B}_{\text{stmsis}}} \approx T_{\mathcal{A}}$ such that:

$$ \begin{aligned} \text{Adv}_{\mathcal{A}}^{\text{TS-UF}} \le & \frac{Q_s Q_{H_{\text{cmt}}}}{q^{nk}} + Q_{H_c} Q_s^2 \cdot \left( \frac{2^{\nu_w} + 1}{q} \right)^{kn} + \frac{T \cdot Q_s Q_{H_{\text{cmt}}} + (Q_{H_{\text{cmt}} + Q_s)^2}{2^{2\kappa}} \\ & + \left(1 + \frac{2\varepsilon}{1-\varepsilon}\right)^{Q_s} \cdot \left( \text{Adv}_{\mathcal{B}_s}^{\text{MLWE}} + \text{Adv}_{\mathcal{B}_{\text{stmsis}}}^{\text{SelfTargetMSIS}} \right) \\ & + Q_s \cdot \frac{3M-2}{M-1} \cdot \left( \text{Adv}_{\mathcal{B}_r}^{\text{MLWE}} + \text{Adv}_{\mathcal{B}_z}^{\text{MLWE}} + \frac{2\varepsilon}{1-\varepsilon} \right) + \text{negl}(\kappa) \end{aligned} $$

*Proof.* Before diving into the full proof, we provide below a proof overview.

Our proof works with a series of hybrids, starting from the TS-UF game.

**Hybrid**_1. This is the TS-UF game.

**Hybrid**_2. In this hybrid, we defer the computation of $\mathbf{w}_i$ to the second round. This requires sampling a random $\text{cmt}_i$ in round 1, and then programming the random oracle in the second round for consistency. An adversary observes a difference if they called the random oracle on $\mathbf{w}_i$ before round 2, which can be bounded by the indistinguishability from uniform of $\mathbf{w}_i$, and the min-entropy of a uniform $\mathbf{w}_i$.

**Hybrid**_3. In this hybrid, we sample the challenges $c$ in advance and program the oracle $H_c$ for consistency in round 2 as soon as all the honest $(\mathbf{w}_i)_i$ are defined for the current session. Similarly, as for the previous hybrid, the adversary's view differs only if they queried the random oracle $H_c$ on the aggregated commitment $\mathbf{w} := \sum_i \mathbf{w}_i$ before it is programmed. We can bound the probability of this event by the indistinguishability from uniform of one $\mathbf{w}_i$, and the min-entropy of a rounded value $\mathbf{w} = |\mathbf{u}|_{\nu_w}$ where $\mathbf{u} \stackrel{\$}{\leftarrow} \mathcal{R}_q^k$.
**Hybrid$_4$.** This hybrid adds a check to make sure that the random oracle $H_{cmt}$ has no collisions, as well as that an adversary cannot find a pre-image for a $cmt_i$ after it is passed to the second signing oracle. We do so by introducing a table $Cmt$ that records all the images of $H_{cmt}$. The advantage loss of this hybrid is bounded by the collision and preimage resistance of $H_{cmt}$, which is provided by its large output space ${0, 1}^{2^κ}$.

**Hybrid$_5$.** In this hybrid, we compute the responses $z_i$ in advance in the second round, and return them in the third round. The previous hybrid ensures that the same challenge $c$ is used to compute a response in round 2, and in round 3, and this hybrid thus does not change the distribution of responses: there is no advantage loss.

**Hybrid$_6$.** In this hybrid, we remove the sampling of $r_i$ out of the rejection sampling function Rej. In the case of an accepted $z_i$, we recover $w_i$ as a function of $z_i$ and partial public keys $b_I$. In the case of an aborted $z_i$, we sample $r_i$ from the distribution $\chi_r$ conditioned on an abort, and evaluate $w_i = A \cdot r_i$. This is merely a syntactic change and does not change the adversary's advantage.

**Hybrid$_7$.** In this hybrid, we replace aborting commitments $w_i$ with uniformly distributed values by relying on Lemma 5. This makes sure that aborting transcripts no longer depend on secret values. This hybrid reduces to the MLWE assumption on distribution $\chi_r$ and $\chi_z$. Though the statistical distance between $\chi_z$ and the concrete distribution of accepted responses also appears in the proof, it is rather an artifact of the proof technique than a concrete mean of attack. In practice the distribution of accepted will have a very large standard deviation, ensuring that even without reducing to $\chi_z$ the corresponding MLWE instance will be hard.

**Hybrid$_8$.** In this hybrid, we replace the rejection sampling algorithm Rej by the ideal functionality Ideal, that is independent of the secrets. We rely on the Renyi divergence to show that this replacement does not increase much the probability of the adversary of winning the game.

**Hybrid$_9$.** We observe in this hybrid that at least one of the $s_I$ remains uncorrupted, and the adversary's view only depends on it through the partial public key $b_I$ that was used in Hybrid$_5$. We use the MLWE$_{q,k,\ell,\chi_{sk}}$ assumption to replace $b_I$ and $b$ by a uniform value.

**Conclusion.** Finally, we reduce the probability of forging a signature in Hybrid$_9$ to the SelfTargetMSIS assumption as in previous works [DKM$^{+24}$]. □

We defer the full proof to Section A.
## 4 Setting Parameters

In this section we present parameters based on two possible choices of distributions $(\chi_r, \chi_z)$: either $\chi_r = \chi_z = U(\gamma)$ or $\chi_r = \chi_z = D_\sigma$. We only consider these two parameter sets as they represent two extremes, on one side small uniform are the easiest to implement both for sampling and computing the rejection probability but give rather large signatures, on the other side discrete gaussians are harder to implement and need to evaluate a transcendental function for rejection but offer the best parameters.

A multitude of other distributions have been proposed in prior works such as rounded gaussians, or spherical distributions in [DFPS22], or intersections of polytopes in [BBRS24]. These distributions offer different trade-offs but are all covered by the framework and proofs of the previous sections.

Note that the distribution $\chi_{sk}$ of the secret is not as important. That is because all that matters for rejection sampling is the norm of $cs$ and the best known attacks on MLWE$^{q,k,l,\chi_{sk}}$ only rely on the norm of the secret $s$, hence for a fixed variance the actual distribution of $s$ does not matter much.

We will fix parameters according to Theorem 4, it is however worth noting that some terms in the corresponding equation can safely be ignored as they are either exponentially smaller than the final advantage or represent artefacts of the proof technique. We list them here:

- $(Q_s Q_{H_{\text{cmt}}} + Q_s^2 Q_{H_c} 2^{(\nu_w+1)nk}) \cdot q^{-nk}$: For all reasonable parameters $q^{nk}$ will be overwhelmingly larger than all the other terms.

- $Q_s \cdot \frac{3M-1}{M} \cdot (\text{Adv}_{B_r}^{\text{MLWE}} + \text{Adv}_{B_z}^{\text{MLWE}})$: Since the key $s \leftarrow \chi_{sk}$ is taken so that $\text{MLWE}_{q,k,l,\chi_{sk}}$ has more than $\kappa$ bits of security. The MLWE instances with secret $z$ or $r$, that are much larger than $s$, will have security much larger than $\kappa$ (in fact for our gaussian parameters these distributions are close to statistically uniform).

- $Q_s \cdot \frac{3M-1}{M} \cdot \frac{2\epsilon}{1-\epsilon}$: This term appears because we want to use MLWE on the ideal distribution $\chi_z$ rather than the actual distribution $z|\text{acc}$. As in the previous case, though it is slightly skewed, the variable $z|\text{acc}$ will have such a large variance that the corresponding MLWE will be close to statistically uniform and does not represent an attack surface in any way. We can thus forego the change from $z|\text{acc}$ to $\chi_z$.

Finally the only relevant terms are $(T \cdot Q_s Q_{H_{\text{cmt}}} + (Q_{H_{\text{cmt}}} + Q_s)^2) \cdot 2^{-2\kappa}$ and $(1 + \frac{2\epsilon}{1-\epsilon})^{Q_s} \cdot \text{Adv}_{B_s}^{\text{MLWE}}$. For the first since we consider the work needed by the adversary as $\text{Adv}_A^{\text{TS-UF}}/\mathcal{T}_A \le \text{Adv}_A^{\text{TS-UF}}/Q_s$, we will need $(T \cdot Q_s Q_{H_{\text{cmt}}} + (Q_{H_{\text{cmt}}} + Q_s)^2)/Q_s \le 2^\kappa$ and thus a number of queries $Q_s = O(2^\kappa)$. For the second if we set $\delta := \frac{2\epsilon}{1-\epsilon} \le 1/Q_s$ then $(1+\delta)^{Q_s} \le e$ and we can set the advantage against MLWE and MSIS to $\kappa + 3$ bits of security.

Additionally we have the following constraints for correctness:

- $B_{sc} \ge B_c B_s$, where
<table><caption>Table 3: Parameter sets for Gaussian distributions. The degree of the field is always chosen to be 256, and $\chi_{sk} = U(-1, 1)$. We consider $T \le N = 8$.</caption><thead><tr><th colspan="2">Security (bits)</th><th rowspan="2">Q<sub>s</sub></th><th rowspan="2">p<sub>acc</sub></th><th rowspan="2">[log q]</th><th rowspan="2">k</th><th rowspan="2">l</th><th rowspan="2">v<sub>b</sub></th><th rowspan="2">v<sub>w</sub></th><th rowspan="2">log(σ)</th><th rowspan="2">|sig| (kB)</th><th rowspan="2">|vk| (kB)</th></tr><tr><th>Classical</th><th>Quantum</th></tr></thead><tbody><tr><td>110</td><td>97</td><td>2<sup>64</sup></td><td>1/4</td><td>22</td><td>4</td><td>4</td><td>2</td><td>13</td><td>15.7</td><td>2.7</td><td>2.57</td></tr><tr><td>118</td><td>104</td><td>2<sup>40</sup></td><td>1/16</td><td>21</td><td>4</td><td>4</td><td>6</td><td>15</td><td>14.3</td><td>2.4</td><td>1.9</td></tr></tbody></table>

1. $B_s$ is an overwhelming bound on the norm of the partial secret $s_i^{\text{part}}$ used in ShareSign$_3$. With Recover described in Fig. 6, $s_i^{\text{part}}$ is the sum of up to $\binom{N}{T-1}$ secrets $s_i \leftarrow \chi_{sk}$, however we note that it is possible to implement a more balanced repartition of secrets ensuring each party sums at most $\lfloor \binom{N}{T-1} / T \rfloor$ secrets. We use the latter bound for our parameter selection.

2. $B_c$ is either the maximum of the operator norm of $c \leftarrow C$ or $B_c = \sqrt{\omega}$ if we consider a more heuristic bound. We will use the former when relying on uniform distributions, and the latter for Gaussian uniform.
$$ -B > B_{z,T} + \sqrt{kn \cdot \omega} \cdot 2^{\nu_b} + \sqrt{kn \cdot 3} \cdot 2^{\nu_w - 1} \quad \text{as in Theorem 3.} $$

Finally we need to consider the acceptance probability. Assuming an acceptance probability $p_i$ for each party, the overall success probability $p_{acc}$ scales in $p_i^T$. We will use a different probability $p_i = (p_{acc})^{1/T}$ for each threshold $T$ in order to guarantee the total acceptance probability. In doing so we are able to choose a smaller individual acceptance probability when $T = 5$ where the secret used by each party can be the sum of up to $\binom{8}{4}/8$ secrets, as opposed to $T = 8$ where each party uses only one secret. Typically, we can take $p = 1/4$, while this probability may seem low, the communication cost of the scheme is quite small and running it in parallel e.g. 10 times will be enough to guarantee a probability of failure of around 5%.

## 4.1 Gaussians

When considering $\chi_r = \chi_z = D_\sigma$, we will compute the explicit value of $\epsilon = \max_v \sum_{x \in S} \chi_z(x) - M\chi_r(x - v)$ using high precision numerical computation (for instance we used the mpmath python library to compute this distance with 200 bits of precision), and set it to $\epsilon \le 1/Q_s$. We do so because the impact of the rejection probability on the Renyi divergence is quite large and obtaining better bounds gives largely improved parameters. We provide two parameter sets in Table 3, one aiming for $Q_s = 2^{64}$, and one aiming for the same signature size as Dilithium but supporting only $Q_s = 2^{40}$.

## 4.2 Uniforms

We also consider uniform distributions to instantiate our threshold scheme. The main advantage over Gaussians is the simplicity of implementation, and of the rejection sampling.
<table><caption>Table 4: Parameter set for uniform distributions. The degree of the field is chosen to be 256, $Q_s = 2^{64}$, success probability $p_{acc} = 1/4$ and $\omega = 39$. We consider $T \le N = 8$.</caption><thead><tr><th colspan="2">Security (bits)</th><th rowspan="2">[log q]</th><th rowspan="2">k</th><th rowspan="2">l</th><th rowspan="2">η</th><th rowspan="2">γ</th><th rowspan="2">ν<sub>b</sub></th><th rowspan="2">ν<sub>w</sub></th><th rowspan="2">|sig| (kB)</th><th rowspan="2">|vk| (kB)</th></tr><tr><th>Classical</th><th>Quantum</th></tr></thead><tbody><tr><td>116</td><td>101</td><td>30</td><td>6</td><td>5</td><td>2</td><td>2<sup>24</sup></td><td>14</td><td>24</td><td>4.8</td><td>3.1</td></tr></tbody></table>

We define $\chi_{sk} = \mathcal{U}([-\eta, \eta])$, $\chi_r = \mathcal{U}([-\gamma, \gamma])$, $\chi_z = \mathcal{U}([-\gamma + \beta, \gamma - \beta])$, and $M = \left( \frac{2\gamma+1}{2\gamma-2\beta+1} \right)^{n(k+l)}$.

Taking $\beta = \omega \cdot \left[ \frac{N}{T-1} \right] / T \cdot \eta$ - a worse-case bound on $\|cs\|$, rejection sampling perfectly samples $\chi_z$ from $\chi_r$.

As for the first parameter set using Gaussians, we fix parameters that guarantee a total success probability 1/4, and we evaluate the security of MLWE with the lattice-estimator, and of SelfTargetMSIS with Dilithium's security estimator<fnref n="3" />, that tackles infinite norm.

We provide our parameter set in Table 4.

## References

ADP24. Nabil Alkeilani Alkadri, Nico Döttling, and Sihang Pu. Practical lattice-based distributed signatures for a small number of signers. In Christina Pöpper and Lejla Batina, editors, *ACNS 24 International Conference on Applied Cryptography and Network Security, Part I*, volume 14583 of LNCS, pages 376–402. Springer, Cham, March 2024.

ANO<sup>+</sup>22. Damiano Abram, Ariel Nof, Claudio Orlandi, Peter Scholl, and Omer Shlomovits. Low-bandwidth threshold ECDSA via pseudorandom correlation generators. In *2022 IEEE Symposium on Security and Privacy*, pages 2554–2572. IEEE Computer Society Press, May 2022.

ASY22. Shweta Agrawal, Damien Stehlé, and Anshu Yadav. Round-optimal lattice-based threshold signatures, revisited. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, *ICALP 2022*, volume 229 of LIPIcs, pages 8:1–8:20. Schloss Dagstuhl, July 2022.

BBD<sup>+</sup>23. Manuel Barbosa, Gilles Barthe, Christian Doczkal, Jelle Don, Serge Fehr, Benjamin Grégoire, Yu-Hsuan Huang, Andreas Hülsing, Yi Lee, and Xi-aodi Wu. Fixing and mechanizing the security proof of Fiat-Shamir with aborts and Dilithium. In Helena Handschuh and Anna Lysyanskaya, editors, *CRYPTO 2023, Part V*, volume 14085 of LNCS, pages 358–389. Springer, Cham, August 2023.

BBRS24. Henry Bambury, Hugo Beguinet, Thomas Ricosset, and Éric Sageloli. Polypopes in the fiat-shamir with aborts paradigm. In Leonid Reyzin and Douglas Stebila, editors, *CRYPTO 2024, Part I*, volume 14920 of LNCS, pages 339–372. Springer, Cham, August 2024.

<footnote n="3">³ https://github.com/pq-crystals/security-estimates</footnote>
BGG<sup>+</sup>18. Dan Boneh, Rosario Gennaro, Steven Goldfeder, Aayush Jain, Sam Kim, Peter M. R. Rasmussen, and Amit Sahai. Threshold cryptosystems from threshold fully homomorphic encryption. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part I, volume 10991 of LNCS, pages 565–596. Springer, Cham, August 2018.

BKL<sup>+</sup>24. Cecilia Boschini, Darya Kaviani, Russell W. F. Lai, Giulio Malavolta, Akira Takahashi, and Mehdi Tibouchi. Ringtail: Practical two-round threshold signatures from learning with errors. Cryptology ePrint Archive, Report 2024/1113, 2024.

BKP13. Rikke Bendlin, Sara Krehbiel, and Chris Peikert. How to share a lattice trapdoor: Threshold protocols for signatures and (H)IBE. In Michael J. Jacobson, Jr., Michael E. Locasto, Payman Mohassel, and Reihaneh Safavi-Naini, editors, ACNS 13International Conference on Applied Cryptography and Network Security, volume 7954 of LNCS, pages 218–236. Springer, Berlin, Heidelberg, June 2013.

BL90. Josh Cohen Benaloh and Jerry Leichter. Generalized secret sharing and monotone functions. In Shafi Goldwasser, editor, CRYPTO'88, volume 403 of LNCS, pages 27–35. Springer, New York, August 1990.

BLL<sup>+</sup>15. Shi Bai, Adeline Langlois, Tancrède Lepoint, Damien Stehlé, and Ron Steinfeld. Improved security proofs in lattice-based cryptography: Using the Rényi divergence rather than the statistical distance. In Tetsu Iwata and Jung Hee Cheon, editors, ASIACRYPT 2015, Part I, volume 9452 of LNCS, pages 3–24. Springer, Berlin, Heidelberg, November / December 2015.

BLT<sup>+</sup>24. Renas Bacho, Julian Loss, Stefano Tessaro, Benedikt Wagner, and Chenzhi Zhu. Twinkle: Threshold signatures from DDH with full adaptive security. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part I, volume 14651 of LNCS, pages 429–459. Springer, Cham, May 2024.

BN06. Mihir Bellare and Gregory Neven. Multi-signatures in the plain public-key model and a general forking lemma. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, ACM CCS 2006, pages 390–399. ACM Press, October / November 2006.

BTT22. Cecilia Boschini, Akira Takahashi, and Mehdi Tibouchi. MuSig-L: Lattice-based multi-signature with single-round online phase. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, pages 276–305. Springer, Cham, August 2022.

CATZ24. Rutchathon Chairattana-Apirom, Stefano Tessaro, and Chenzhi Zhu. Partially non-interactive two-round lattice-based threshold signatures. Cryptology ePrint Archive, Report 2024/467, 2024.

CCD<sup>+</sup>23. Jung Hee Cheon, Hyeongmin Choe, Julien Devevey, Tim Güneysu, Dongyeon Hong, Markus Krausz, Georg Land, Marc Möller, Damien Stehlé, and MinJune Yi. HAETAE: Shorter lattice-based fiat-shamir signatures. Cryptology ePrint Archive, Report 2023/624, 2023.

CCL<sup>+</sup>23. Guilhem Castagnos, Dario Catalano, Fabien Laguillaumie, Federico Savasta, and Ida Tucker. Bandwidth-efficient threshold EC-DSA revisited: Online/offline extensions, identifiable aborts proactive and adaptive security. Theor. Comput. Sci., 939:78–104, 2023.

CEN24. Sofia Celi, Daniel Escudero, and Guilhem Niot. Share the MAYO: thresholding MAYO. Cryptology ePrint Archive, Paper 2024/1960, 2024.
CGG$^{+20}$. Ran Canetti, Rosario Gennaro, Steven Goldfeder, Nikolaos Makriyannis, and Udi Peled. UC non-interactive, proactive, threshold ECDSA with identifiable aborts. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, *ACM CCS 2020*, pages 1769–1787. ACM Press, November 2020.

CGL$^{+24}$. Jean-Sébastien Coron, François Gérard, Tancrède Lepoint, Matthias Trannoy, and Rina Zeitoun. Improved high-order masked generation of masking vector and rejection sampling in dilithium. *IACR Transactions on Cryptographic Hardware and Embedded Systems*, 2024(4):335–354, Sep. 2024.

Che23. Yanbo Chen. DualMS: Efficient lattice-based two-round multi-signature with trapdoor-free simulation. In Helena Handschuh and Anna Lysanskaya, editors, *CRYPTO 2023, Part V*, volume 14085 of LNCS, pages 716–747. Springer, Cham, August 2023.

CKM23. Elizabeth C. Crites, Chelsea Komlo, and Mary Maller. Fully adaptive Schnorr threshold signatures. In Helena Handschuh and Anna Lysanskaya, editors, *CRYPTO 2023, Part I*, volume 14081 of LNCS, pages 678–709. Springer, Cham, August 2023.

CS19. Daniele Cozzo and Nigel P. Smart. Sharing the LUOV: Threshold post-quantum signatures. In Martin Albrecht, editor, *17th IMA International Conference on Cryptography and Coding*, volume 11929 of LNCS, pages 128–153. Springer, Cham, December 2019.

DLL13. Léo Ducas, Alain Durmus, Tancrède Lepoint, and Vadim Lyubashevsky. Lattice signatures and bimodal Gaussians. In Ran Canetti and Juan A. Garay, editors, *CRYPTO 2013, Part I*, volume 8042 of LNCS, pages 40–56. Springer, Berlin, Heidelberg, August 2013.

DFPS22. Julien Devevey, Omar Fawzi, Alain Passelègue, and Damien Stehlé. On rejection sampling in Lyubashevsky’s signature scheme. In Shweta Agrawal and Dongdai Lin, editors, *ASIACRYPT 2022, Part IV*, volume 13794 of LNCS, pages 34–64. Springer, Cham, December 2022.

DFPS23. Julien Devevey, Pouria Fallahpour, Alain Passelègue, and Damien Stehlé. A detailed analysis of Fiat-Shamir with aborts. In Helena Handschuh and Anna Lysyanskaya, editors, *CRYPTO 2023, Part V*, volume 14085 of LNCS, pages 327–357. Springer, Cham, August 2023.

DKL$^{+18}$. Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium: A lattice-based digital signature scheme. *IACR TCHES*, 2018(1):238–268, 2018.

DKM$^{+24}$. Rafaël Del Pino, Shuichi Katsumata, Mary Maller, Fabrice Mouhartem, Thomas Prest, and Markku-Juhani O. Saarinen. Threshold raccoon: Practical threshold signatures from standard lattice assumptions. In Marc Joye and Gregor Leander, editors, *EUROCRYPT 2024, Part II*, volume 14652 of LNCS, pages 219–248. Springer, Cham, May 2024.

DM20. Luca De Feo and Michael Meyer. Threshold schemes from isogeny assumptions. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, *PKC 2020, Part II*, volume 12111 of LNCS, pages 187–212. Springer, Cham, May 2020.

DOTT21. Ivan Damgård, Claudio Orlandi, Akira Takahashi, and Mehdi Tibouchi. Two-round n-out-of-n and multi-signatures and trapdoor commitment from lattices. In Juan Garay, editor, *PKC 2021, Part I*, volume 12710 of LNCS, pages 99–130. Springer, Cham, May 2021.
DOTT22. Ivan Damgård, Claudio Orlandi, Akira Takahashi, and Mehdi Tibouchi. Two-round n-out-of-n and multi-signatures and trapdoor commitment from lattices. *Journal of Cryptology*, 35(2):14, April 2022.

dPENP25. Rafael del Pino, Thomas Espitau, Guilhem Niot, and Thomas Prest. Simple and efficient lattice threshold signatures with identifiable aborts. 2025.

dPKPR24. Rafaël del Pino, Shuichi Katsumata, Thomas Prest, and Mélissa Rossi. Raccoon: A masking-friendly signature proven in the probing model. In Leonid Reyzin and Douglas Stebila, editors, *CRYPTO 2024, Part I*, volume 14920 of LNCS, pages 409–444. Springer, Cham, August 2024.

DPS23. Julien Devevey, Alain Passelègue, and Damien Stehlé. G+G: A fiat-shamir lattice signature based on convolved gaussians. In Jian Guo and Ron Steinfeld, editors, *ASIACRYPT 2023, Part VII*, volume 14444 of LNCS, pages 37–64. Springer, Singapore, December 2023.

EKT24. Thomas Espitau, Shuichi Katsumata, and Kaoru Takemure. Two-round threshold signature from algebraic one-more learning with errors. In Leonid Reyzin and Douglas Stebila, editors, *CRYPTO 2024, Part VII*, volume 14926 of LNCS, pages 387–424. Springer, Cham, August 2024.

ENP24. Thomas Espitau, Guilhem Niot, and Thomas Prest. Flood and submerse: Distributed key generation and robust threshold signature from lattices. In Leonid Reyzin and Douglas Stebila, editors, *CRYPTO 2024, Part VII*, volume 14926 of LNCS, pages 425–458. Springer, Cham, August 2024.

FS87. Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew M. Odlyzko, editor, *CRYPTO'86*, volume 263 of LNCS, pages 186–194. Springer, Berlin, Heidelberg, August 1987.

GHKR08. Rosario Gennaro, Shai Halevi, Hugo Krawczyk, and Tal Rabin. Threshold RSA for dynamic and ad-hoc groups. In Nigel P. Smart, editor, *EUROCRYPT 2008*, volume 4965 of LNCS, pages 88–107. Springer, Berlin, Heidelberg, April 2008.

GKS24. Kamil Doruk Gür, Jonathan Katz, and Tjerand Silde. Two-round threshold lattice-based signatures from threshold homomorphic encryption. In Markku-Juhani Saarinen and Daniel Smith-Tone, editors, *Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Part II*, pages 266–300. Springer, Cham, June 2024.

GPV08. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, *40th ACM STOC*, pages 197–206. ACM Press, May 2008.

HPRR20. James Howe, Thomas Prest, Thomas Ricosset, and Mélissa Rossi. Isochronous gaussian sampling: From inception to implementation. In Jintai Ding and Jean-Pierre Tillich, editors, *Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020*, pages 53–71. Springer, Cham, 2020.

ISN87. M. Ito, A. Saito, and Takao Nishizeki. Secret sharing schemes realizing general access structure. In Proc. *IEEE Global Telecommunication Conf. (Globecom'87)*, pages 99–102, 1987.

KCLM22. Irakliy Khaburzaniya, Konstantinos Chalkias, Kevin Lewi, and Harjasleen Malvai. Aggregating and thresholdizing hash-based signatures using STARKs. In Yuji Suga, Kouichi Sakurai, Xuhua Ding, and Kazue Sako, editors, *ASIACCS 22*, pages 393–407. ACM Press, May / June 2022.
KG20. Chelsea Komlo and Ian Goldberg. FROST: Flexible round-optimized Schnorr threshold signatures. In Orr Dunkelman, Michael J. Jacobson, Jr., and Colin O'Flynn, editors, *SAC 2020*, volume 12804 of LNCS, pages 34–65. Springer, Cham, October 2020.

KLS18. Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. In Jesper Buus Nielsen and Vincent Rijmen, editors, *EUROCRYPT 2018, Part III*, volume 10822 of LNCS, pages 552–586. Springer, Cham, April / May 2018.

KRT24. Shuichi Katsumata, Michael Reichle, and Kaoru Takemure. Adaptively secure 5 round threshold signatures from MLWE/MSIS and DL with rewinding. In Leonid Reyzin and Douglas Stebila, editors, *CRYPTO 2024, Part VII*, volume 14926 of LNCS, pages 459–491. Springer, Cham, August 2024.

LDK$^{+}$22. Vadim Lyubashevsky, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Peter Schwabe, Gregor Seiler, Damien Stehlé, and Shi Bai. CRYSTALS-DILITHIUM. Technical report, National Institute of Standards and Technology, 2022. available at https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022.

Lyu09. Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In Mitsuru Matsui, editor, *ASIACRYPT 2009*, volume 5912 of LNCS, pages 598–616. Springer, Berlin, Heidelberg, December 2009.

Lyu12. Vadim Lyubashevsky. Lattice signatures without trapdoors. In David Pointcheval and Thomas Johansson, editors, *EUROCRYPT 2012*, volume 7237 of LNCS, pages 738–755. Springer, Berlin, Heidelberg, April 2012.

Sho00. Victor Shoup. Practical threshold signatures. In Bart Preneel, editor, *EUROCRYPT 2000*, volume 1807 of LNCS, pages 207–220. Springer, Berlin, Heidelberg, May 2000.

TPCZ24. Guofeng Tang, Bo Pang, Long Chen, and Zhenfeng Zhang. Efficient lattice-based threshold signatures with functional interchangeability. Cryptology ePrint Archive, Report 2024/1067, 2024.

vEH14. Tim van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. *IEEE Transactions on Information Theory*, 60(7):3797–3820, 2014.

A Omitted proof of unforgeability

We now prove the unforgeability of our threshold scheme stated in Theorem 4.

*Proof.* We proceed with a series of hybrids starting from the TS-UF game. Throughout this proof, we denote the advantage of an adversary $\mathcal{A}$ against a search game $G$ by $\text{Adv}_{\mathcal{A}}^{G} := \text{Pr}[G(\mathcal{A}) \to 1]$ – in particular, we omit passing $\kappa$ as input.

**Hybrid**_1. This is the TS-UF game from Fig. 1.
**Hybrid<sub>2</sub>.** In this hybrid we defer the computation of the honest $w_i$ to the second round of the protocol, and program the random oracle to be consistent. We also introduce a flag $f_{fail}$ to explicitly mark additional cases where the adversary loses. Notably, $f_{fail}$ is set to $\top$ when the random oracle is programmed on a previously queried value. This is formalized in Fig. 8.

<figure><img src="image_7.png" /><figcaption>Fig. 8: Second hybrid of the unforgeability proof of our threshold signature scheme. If the random oracle is programmed on a previously queried index, consider that the adversary loses, i.e. $f_{fail}$ is set to $\top$. Difference with the previous hybrid are highlighted.</figcaption></figure>

The view of the adversary $\mathcal{A}$ differs if they called the random oracle of one of the $w_i$ before round 2 was executed, i.e.

$$|\text{Adv}_{\mathcal{A}}^{\text{Hybrid}_1} - \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_2}| \le \text{Pr}[\text{H}_{\text{cmt}} \text{ queried on } w_i \text{ before round 2 in Hybrid}_1]$$

By union-bound, we can reduce this to a single call to $\text{OSign}_1$.

$$|\text{Adv}_{\mathcal{A}}^{\text{Hybrid}_1} - \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_2}| \le \sum_{s=1}^{Q_s} \text{Pr}[w_i \text{ produced by } s\text{-th call to } \text{OSign}_1 \text{ is queried on } \text{H}_{\text{cmt}} \text{ before round 2 in Hybrid}_1] \quad (4)$$
We note the above individual probabilities $p_s$ for $s \in [Q_s]$. Formally, we introduce in Fig. 9 an intermediary game $\text{Int}_1^s$ in which $\mathcal{A}$ wins with probability exactly $p_s$. We also introduce a tweak of $\text{Int}_1^s$, named $\text{Int}_2^s$, where we replace the s-th commitment $\mathbf{w}_i$ by a uniform value in $\mathcal{R}_q^k$.

First, the difference in advantage between $\text{Int}_1^s$ and $\text{Int}_2^s$ reduces to $\text{MLWE}_{q,k,\ell,\chi_r}$. Formally, we can define an adversary $\mathcal{E}^s$ against the $\text{MLWE}_{q,k,\ell,\chi_r}$ problem such that:

$$ \left| \text{Adv}_{\mathcal{A}}^{\text{Int}_1^s} - \text{Adv}_{\mathcal{A}}^{\text{Int}_2^s} \right| = \left| p_s - \text{Adv}_{\mathcal{A}}^{\text{Int}_2^s} \right| \le \text{Adv}_{\mathcal{E}^s}^{\text{MLWE}_{q,k,\ell,\chi_r}} \quad (5) $$

Also, we note that in $\text{Int}_2^s$, the probability that one call of $\mathcal{A}$ to the random oracle queries the s-th $\mathbf{w}_i$ is bounded by the min-entropy of $\mathbf{w}_i \stackrel{\$}{\leftarrow} \mathcal{R}_q^k$, i.e. by $q^{-nk}$. By union bound, $\text{Adv}_{\mathcal{A}}^{\text{Int}_2^s} \le Q_{\text{H}_{\text{cnt}}} \cdot q^{-nk}$.

By combining the above inequality with Eq. (4) and Eq. (5), we conclude:

$$ \left| \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_1} - \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_2} \right| \le Q_s \cdot Q_{\text{H}_{\text{cnt}}} \cdot q^{-nk} + Q_s \cdot \text{Adv}_{B_1}^{\text{MLWE}_{q,k,\ell,\chi_r}} $$

where $B_1$ is the adversary $\mathcal{E}^s$ maximizing $\text{Adv}_{\mathcal{E}^s}^{\text{MLWE}_{q,k,\ell,\chi_r}}$.

*Remark 3.* As a useful remark for following hybrids, we note that a given $\mathbf{w}_i$ can't be used twice by the same party after $\text{Hybrid}_2$ as then the random oracle programming would fail, and the adversary loses.

**Hybrid$_3$.** In this hybrid, we sample a challenge $c$ in advance during round 2. When the last honest hash $\text{cmt}_i$ obtains a corresponding $\mathbf{w}_i$ programmed, we program the value $H_c(\text{vk}, |\sum_{i \in \text{act}} \mathbf{w}_i|_{\nu_w})$. This is formalized in Fig. 10.

The proof for this hybrid is analogous to the previous one. First, these changes do not bias $H_c$ as the sampled challenges $c$ are used at most once for programming $H_c$, and are not provided to the adversary before programming. The view of the adversary hence differs only if it queried the random oracle on some $\mathbf{w} = |\sum_{i \in \text{act}} \mathbf{w}_i|$ before it is programmed in round 2.

For each $s \in Q_s$, we reexpress as an advantage the probability $p_s$ that the s-th $\mathbf{w}_i$ produced during round 2 is used to compute a $\mathbf{w}$ that was previously queried on the random oracle $H_c$. Formally, we define the game $\text{Int}_3^s$ in Fig. 11, that verifies $p_s = \text{Adv}_{\mathcal{A}}^{\text{Int}_3^s}$. By union bound, we have $|\text{Adv}_{\mathcal{A}}^{\text{Hybrid}_2} - \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_3}| \le \sum_{s \in [Q_s]} p_s$.

We additionally define the game $\text{Int}_4^s$ in Fig. 11, where we replace the s-th $\mathbf{w}_i$ by a uniform value in $\mathcal{R}_q^k$. The advantage difference between $\text{Int}_3^s$ and $\text{Int}_4^s$ again reduces to $\text{MLWE}_{q,k,\ell,\chi_r}$: $|\text{Adv}_{\mathcal{A}}^{\text{Int}_3^s} - \text{Adv}_{\mathcal{A}}^{\text{Int}_4^s}| \le \text{Adv}_{\mathcal{E}^s}^{\text{MLWE}_{q,k,\ell,\chi_r}}$ for an adversary $\mathcal{E}^s$ against the $\text{MLWE}_{q,k,\ell,\chi_r}$ problem.

Then, we can see that the probability that $\mathcal{A}$ wins in $\text{Int}_4^s$ can be bounded using the min-entropy of $|\mathcal{U}(\mathcal{R}_q^k)|_{\nu_w}$. Indeed, the s-th $\mathbf{w}_i$ is sampled uniformly from $\mathcal{R}_q^k$ and ensures that each $\mathbf{w}$ that needs to be programmed follows the distribution $|\mathcal{U}(\mathcal{R}_q^k)|_{\nu_w}$. As there are at most $Q_s$ $\mathbf{w}$ to check, we obtain the bound $\text{Adv}_{\mathcal{A}}^{\text{Int}_4^s} \le Q_{\text{H}_c} Q_s \cdot \left(\frac{2^{\nu_w+1}}{q}\right)^{kn}$.
<figure><img src="image_8.png" /><figcaption>Fig. 9: Intermediary games for the second hybrid of the unforgeability proof of our threshold signature scheme. Difference with Hybrid<sub>1</sub> are highlighted.</figcaption></figure>
Hybrid<sub>3</sub>

1: $Q_{\text{msg}}$, UnopenedCmt[·] := ∅

2: **ToProgram**, Programmed[·] := ∅

▷▷▷ Other lines are identical to Hybrid<sub>2</sub> ▷▷▷

ShareSign<sub>2</sub>(vk, act, msg, pm<sub>1</sub>, i, sk<sub>i</sub>, st<sub>i</sub>)

1: assert{ act ⊆ [N] ∧ i ∈ act }

2: assert{ UnopenedCmt[(i, pm<sub>1</sub><sup>i</sup>)] = ⊤ }

3: UnopenedCmt[(i, pm<sub>1</sub><sup>i</sup>)] := ⊥

4: if (act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg, ·) /∈ ToProgram then

5: c ← C

6: ToProgram := ToProgram ∪ {(act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg, c)}

7: Pick (a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, c) from ToProgram s.t. (a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>) = (act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg)

8: r<sub>i</sub> ← χ<sub>r</sub><sup>l+k</sup>

9: w<sub>i</sub> := A · r<sub>i</sub>

10: $H_{\text{cmt}}(vk, w_i) := pm_1^i$

11: **for** (act', (cmt'<sub>j</sub>)<sub>j∈act'</sub>, msg', c') ∈ ToProgram **do**

12: if (i ∈ act') ∧ (cmt'<sub>i</sub> = pm<sub>1</sub><sup>i</sup>) ∧ (∀j ∈ act'\{i}, ∃w<sub>j</sub>, cmt<sub>j</sub> = $H_{\text{cmt}}(vk, j, w_j)$) then

▷ Find all the new programmable challenges

13: ToProgram := ToProgram\{(act', (cmt'<sub>j</sub>)<sub>j∈act'</sub>, msg', c')}

14: $w := \left[ \sum_{j \in \text{act}'} w_j \right]_{\nu_w}$

15: $H_c(vk, msg', w) := c'$

▷ Program random oracle

16: $st_i := st_i \cup \{(\text{act}, \text{msg}, pm_1, w_i, r_i)\}$

17: return (pm<sub>2</sub><sup>i</sup> := w<sub>i</sub>, st<sub>i</sub>)

Fig. 10: Third hybrid of the unforgeability proof of our threshold signature scheme. If the random oracle is programmed on a previously queried index, consider that the adversary loses, i.e. $f_{\text{fail}}$ is set to $\top$. Difference with the previous hybrid are highlighted.

Putting together the different inequalities obtained, we finally deduce the existence of an adversary $\mathcal{B}_2$ against the $\text{MLWE}_{q,k,\ell,\chi_r}$ such that:

$$ \left| \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_2} - \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_3} \right| \le Q_{H_c} Q_s^2 \cdot \left( \frac{2^{\nu_w} + 1}{q} \right)^{kn} + Q_s \cdot \text{Adv}_{\mathcal{B}_2}^{\text{MLWE}_{q,k,\ell,\chi_r}} $$

**Hybrid<sub>4</sub>.** In this hybrid, we ensure that $H_{\text{cmt}}$ has no collisions and that the adversary cannot find preimages of hashes $cmt_i$ after passing them to the second signing oracle. We introduce a table Cmt that records every $cmt$ sampled in $H_{\text{cmt}}$ or in $\text{OSign}_1$, as well as those passed to the second signing oracle. Whenever a new hash $cmt$ is sampled, we ensure that it was not previously added to Cmt,
<figure><img src="image_9.png" /><figcaption>Fig. 11: Intermediary games for the third hybrid of the unforgeability proof of our threshold signature scheme. Difference with Hybrid₂ are highlighted.</figcaption></figure>
or the challenger sets the flag $f_{fail}$ to $\top$ in order to abort the game. This is formalized in Fig. 12.

<figure><img src="image_10.png" /><figcaption>Fig. 12: Fourth hybrid of the unforgeability proof of our threshold signature scheme. Difference with the previous hybrid are highlighted.</figcaption></figure>

The view of the adversary differs in $Hybrid_4$ if it was previously able to (i) find a pre-image of a $cmt_i$ after passing it to $OSign_2$, or (ii) if a given $cmt$ was sampled twice.

We can bound the probability of (i) due to the pre-image resistance of the hash function $H_{cmt}$, and with an union bound over all the commits passed by the adversary to $OSign_2$ which gives a bound $Q_{H_{cmt}} \cdot T \cdot Q_s \cdot 2^{-2\kappa}$.

As for (ii), we rely on the collision resistance of $H_{cmt}$. Since the commitments are sampled uniformly from $\{0,1\}^{2\kappa}$, we can bound the probability of (ii) by $\frac{(Q_{H_{cmt}}+Q_s)^2}{2^{2\kappa}}$.
We conclude that,

$$ \left| \mathrm{Adv}_A^{\mathrm{Hybrid}_3} - \mathrm{Adv}_A^{\mathrm{Hybrid}_4} \right| \le \frac{Q_{\mathrm{Hcmt}} \cdot T \cdot Q_s + (Q_{\mathrm{Hcmt}} + Q_s)^2}{2^{2\kappa}} $$

**Hybrid<sub>5</sub>.** In this hybrid, we ensure that the challenge used in round 3 is the same as the one sampled in round 2, and we precompute the responses $z_i$ in advance. This is formalized in Fig. 13.

<figure><img src="image_11.png" /><figcaption>Fig. 13: Fifth hybrid of the unforgeability proof of our threshold signature scheme. Difference with the previous hybrid are highlighted.</figcaption></figure>
We want to show that responses are identically distributed in $\text{Hybrid}_5$. This is the case if programmed responses use the same $c$ in both round 2 and round 3, and if they are used at most once.

Now, we can first observe that if the hash checks in round 3 pass, then all the $cmt_i := H_{cmt}(vk, w_i)$ are correctly defined. Recall that $\text{Hybrid}_4$ ensured that $H_{cmt}$ has no collisions, and that pre-images cannot be found after round 2 is called. Hence, if these checks pass, then it means that in round 2, all the hashes $cmt_i$ either: (i) already had pre-images, or (ii) were produced by an honest party in $\text{OSign}_1$ and were waiting for programming. Eventually, all the missing $cmt_i$ from (ii) must thus have been programmed in $\text{OSign}_2$ and as the challenger programs $H_c$ as soon as all the $w_i$ are defined, then it ensures that the same $c$ is used in round 2 and in round 3.

Additionally, responses are used at most once by a given party due to the collision resistance of $H_{cmt}$ and Remark 3 which ensures that party $i$ will accept $cmt_i$ at most once.

All in all, we conclude that the adversary's view is identically distributed in $\text{Hybrid}_4$ and $\text{Hybrid}_5$ so,

$$ \mathrm{Adv}_{\mathcal{A}}^{\text{Hybrid}_5} = \mathrm{Adv}_{\mathcal{A}}^{\text{Hybrid}_4} $$

**Hybrid**_6. In this hybrid, we no longer sample $\mathbf{r}_i$ out of the rejection sampling, and instead (i) in case of success, we compute $\mathbf{w} = \mathbf{A} \cdot \mathbf{z} - \mathbf{b}_i^{\text{part}}$, and (ii) in case of abort, we sample a $\mathbf{r}_i$ from the aborting distribution $\mathcal{D}_{\mathbf{r}, \text{reject}}^{(\mathbf{s}_i^{\text{part}}, c)}$. This is formalized in Fig. 14.

We can see that the view of the adversary is identically distributed. Indeed, in $\text{Hybrid}_5$ we have $\mathbf{A} \cdot \mathbf{z}_i = c \cdot \underbrace{\mathbf{A} \cdot \mathbf{s}_i^{\text{part}}}_{\mathbf{b}_i^{\text{part}}} + \underbrace{\mathbf{A} \cdot \mathbf{r}_i}_{\mathbf{w}_i}$. We can thus equivalently write $\mathbf{w}_i = \mathbf{A} \cdot \mathbf{z}_i - c \cdot \mathbf{b}_i^{\text{part}}$ and sample $\mathbf{z}_i$ first.

So,

$$ \mathrm{Adv}_{\mathcal{A}}^{\text{Hybrid}_6} = \mathrm{Adv}_{\mathcal{A}}^{\text{Hybrid}_5} $$

**Hybrid**_7. In this hybrid, we replace the aborting $\mathbf{w}_i$ by a uniform value in $\mathcal{R}_q^k$. This is formalized in Fig. 15.

There are up to $Q_s$ $\mathbf{w}_i$ to replace. We define a family of games $G^p$ for $p \in [Q_s + 1]$, replacing one by one the $\mathbf{w}_i$ by a uniform vector, which verifies:

$$ |\mathrm{Adv}_{\mathcal{A}}^{\text{Hybrid}_6} - \mathrm{Adv}_{\mathcal{A}}^{\text{Hybrid}_7}| \le \sum_{s \in [Q_s]} |\mathrm{Adv}_{\mathcal{A}}^{G^{p+1}} - \mathrm{Adv}_{\mathcal{A}}^{G^p}| $$

$$ \text{Let } p \in [Q_s + 1]. \text{ We want to bound } |\mathrm{Adv}_{\mathcal{A}}^{G^{p+1}} - \mathrm{Adv}_{\mathcal{A}}^{G^p}|. $$

The core idea is to condition on the value of $v := (\text{act}, i, \mathbf{s}_i^{\text{part}}, c)$ used to define the distribution $\mathcal{D}_{\mathbf{r}, \text{reject}}^{(\mathbf{s}_i^{\text{part}}, c)}$:

$$ |\mathrm{Adv}_{\mathcal{A}}^{G^{p+1}} - \mathrm{Adv}_{\mathcal{A}}^{G^p}| \le \sum_{\mathbf{s}, c} |\mathrm{Adv}_{\mathcal{A}}^{F^{\prime v}} - \mathrm{Adv}_{\mathcal{A}}^{F^v}| \cdot \Pr[v = (\text{act}, i, \mathbf{s}_i^{\text{part}}, c) \text{ used by } G^s] \quad (6) $$
Hybrid<sub>6</sub>

▷▷▷ Identical to Hybrid<sub>5</sub> ▷▷▷

ShareSign<sub>2</sub>(vk, act, msg, pm<sub>1</sub>, i, sk<sub>i</sub>, st<sub>i</sub>)

1: assert{ act ⊆ [N] ∧ i ∈ act }

2: assert{ UnopenedCmt[(i, pm<sub>i</sub><sup>1</sup>)] = ⊥ }

3: UnopenedCmt[(i, pm<sub>i</sub><sup>1</sup>)] := ⊥

4: if (act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg, ·) ∉ ToProgram then

5: c ← C

6: ToProgram := ToProgram ∪ {(act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg, c)}

7: Pick (a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, c) from ToProgram s.t. (a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>) = (act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg)

8: m := RecoverPERT

9: s<sub>i</sub><sup>part</sup> := Σ<sub>I∈m<sub>i</sub></sub> s<sub>I</sub>

10: z<sub>i</sub> ← Rej(c · s<sub>i</sub><sup>part</sup>, χz, χr, M)

11: if z<sub>i</sub> = ⊥ then

12: r<sub>i</sub> ← D<sub>r, reject</sub>(s<sub>i</sub><sup>part, c</sup>)

13: w<sub>i</sub> := [A I] · r<sub>i</sub>

14: else

15: b<sub>i</sub><sup>part</sup> := Σ<sub>I∈m<sub>i</sub></sub> b<sub>I</sub>

16: w<sub>i</sub> := A · z<sub>i</sub> - c · b<sub>i</sub><sup>part</sup>

17: Responses[(act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg, i)] := z<sub>i</sub>

▷ if reject

▷▷▷ Rest is identical ▷▷▷

<caption>Fig. 14: Sixth hybrid of the unforgeability proof of our threshold signature scheme. Difference with the previous hybrid are highlighted.</caption>

where $F^{\prime v}$ and $F^v$ are respectively the games $G^{p+1}$ and $G^p$ where we impose the set of signers act, signer $i$, and challenge $c$ for the $p$-th $w_i$ to replace, and sample the secrets $s_I$ to be consistent with the value $s_i^{\text{part}}$.

We can then define adversaries $\mathcal{E}^v$ against the MLWE
$q, k, \ell, \mathcal{D}_{r, \text{reject}}^{s_i^{\text{part}}, c}$ such that

$$
| \mathrm{Adv}_{\mathcal{A}}^{F^{\prime v}} - \mathrm{Adv}_{\mathcal{A}}^{F^v} | = \mathrm{Adv}_{\mathcal{E}^v}^{\mathrm{MLWE}_{q, k, \ell, \mathcal{D}_{r, \mathrm{reject}}^{s_i^{\mathrm{part}}, c}}} \quad (7)
$$

Applying Lemma 5, there exists adversaries $\mathcal{E}^{\prime v}$ and $\mathcal{E}^{\prime \prime v}$ such that

$$
\text{Adv}_{\mathcal{E}^v}^{\text{MLWE}}_{q, k, \ell, \mathcal{D}_{r, \text{reject}}^{s_i^{\text{part}}, c}} \le \frac{1}{\text{Pr}[\mathbf{z} = \perp | (s_i^{\text{part}}, c)]} \cdot (\text{Adv}_{\mathcal{E}^{\prime v}}^{\text{MLWE}}_{q, k, \ell, \chi_r} + \text{Adv}_{\mathcal{E}^{\prime \prime v}}^{\text{MLWE}}_{q, k, \ell, \chi_z} + \delta^v) \quad (8)
$$

where $\delta^v$ is the statistical distance between $\chi_z$ and $\mathcal{D}_{z, \text{accept}}^{(s_i^{\text{part}}, c)}$.
Hybrid<sub>7</sub>

▷▷▷ Identical to Hybrid<sub>6</sub> ▷▷▷

ShareSign<sub>2</sub>(vk, act, msg, pm<sub>1</sub>, i, sk<sub>i</sub>, st<sub>i</sub>)

1: assert{ act ⊆ [N] ∧ i ∈ act }

2: assert{ UnopenedCmt[(i, pm<sub>i</sub><sup>1</sup>)] = ⊥ }

3: UnopenedCmt[(i, pm<sub>i</sub><sup>1</sup>)] := ⊥

4: if (act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg, ·) ∉ ToProgram then

5: c ← C

6: ToProgram := ToProgram ∪ {(act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg, c)}

7: Pick (a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, c) from ToProgram s.t. (a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>) = (act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg)

8: m := RecoverPERT

9: s<sub>i</sub><sup>part</sup> := Σ<sub>I∈m<sub>i</sub></sub> s<sub>I</sub>

10: z<sub>i</sub> ← Rej(c · s<sub>i</sub><sup>part</sup>, χ<sub>z</sub>, χ<sub>r</sub>, M)

11: if z<sub>i</sub> = ⊥ then

12: w<sub>i</sub> $\leftarrow$ R<sub>q</sub><sup>k</sup>

13: else

14: b<sub>i</sub><sup>part</sup> := Σ<sub>I∈m<sub>i</sub></sub> b<sub>I</sub>

15: w<sub>i</sub> := A · z<sub>i</sub> − c · b<sub>i</sub><sup>part</sup>

16: Responses[(act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg, i)] := z<sub>i</sub>

▷▷▷ Rest is identical ▷▷▷

Fig. 15: Seventh hybrid of the unforgeability proof of our threshold signature scheme. Difference with the previous hybrid are highlighted.

As $(N_T) = \text{poly}(\kappa)$, we have by assumption for any $(\text{act}, i) \|c \cdot s_i^{\text{part}}\| \le B_{cs}$ with overwhelming probability, and we can apply Lemma 4 to bound $\delta(s_i^{\text{part}}, c) \le \frac{2\epsilon}{1-\epsilon}$ and $\Pr[z = \bot | (s_i^{\text{part}}, c)] \ge 1 - \frac{1}{M}$.

By combining Equations 6, 7, and 8, we obtain:

$$ \left| \text{Adv}_{\mathcal{A}}^{G^{p+1}} - \text{Adv}_{\mathcal{A}}^{G^p} \right| \le \frac{M}{M-1} \left( \max_{\text{act}, i, \|cs\| \le B_{cs}} \left( \text{Adv}_{\mathcal{E}^{\text{IL}}(s,c)}^{\text{MLWE}}_{q,k,l,\chi_r} + \text{Adv}_{\mathcal{E}^{\text{IL}}(s,c)}^{\text{MLWE}}_{q,k,l,\chi_z} \right) + \frac{2\epsilon}{1-\epsilon} \right) + \text{negl}(\kappa) $$

Finally, by summing all the above inequalities, we obtain:

$$ \left| \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_6} - \text{Adv}_{\mathcal{A}}^{\text{Hybrid}_7} \right| \le Q_s \frac{M}{M-1} \left( \text{Adv}_{\mathcal{B}_3}^{\text{MLWE}}_{q,k,l,\chi_r} + \text{Adv}_{\mathcal{B}_4}^{\text{MLWE}}_{q,k,l,\chi_z} + \frac{2\epsilon}{1-\epsilon} \right) + \text{negl}(\kappa) $$

where $\mathcal{B}_3$ is an adversary against the $\text{MLWE}_{q,k,l,\chi_r}$ problem, $\mathcal{B}_4$ is an adversary against the $\text{MLWE}_{q,k,l,\chi_z}$ problem.

**Hybrid<sub>8</sub>**. In this hybrid, we replace the real rejection sampling algorithm $\text{Rej}(c \cdot s_i^{\text{part}}, \chi_z, \chi_r, M; r_i)$ by an ideal functionality $\text{Ideal}(\chi_z, M)$ which is independent of the secret. This is formalized in Fig. 16.

We rely on the Renyi divergence to prove that this only slightly increases the probability that $\mathcal{A}$ wins the game. For conciseness, we will abuse Renyi
Hybrid<sub>8</sub>

▷▷▷ Identical to Hybrid<sub>6</sub> ▷▷▷

ShareSign<sub>2</sub>(vk, act, msg, pm<sub>1</sub>, i, sk<sub>i</sub>, st<sub>i</sub>)

1: assert{ act ⊆ [N] ∧ i ∈ act }

2: assert{ UnopenedCmt[(i, pm<sub>i</sub>)] = ⊥ }

3: UnopenedCmt[(i, pm<sub>i</sub>)] := ⊥

4: if (act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg, ·) ∉ ToProgram then

5: c ← C

6: ToProgram := ToProgram ∪ {(act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg, c)}

7: Pick (a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, c) from ToProgram s.t. (a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>) = (act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg)

8: m := RecoverPERTEST

9: z<sub>i</sub> ← Ideal(χ<sub>z</sub>, M)

10: if z<sub>i</sub> = ⊥ then

11: w<sub>i</sub> ← R<sub>q</sub><sup>k</sup>

12: else

13: b<sub>i</sub><sup>part</sup> := Σ<sub>I∈m<sub>i</sub></sub> b<sub>I</sub>

14: w<sub>i</sub> := A · z<sub>i</sub> − c · b<sub>i</sub><sup>part</sup>

15: Responses[(act, (cmt<sub>j</sub>)<sub>j∈act</sub>, msg, i)] := z<sub>i</sub>

▷▷▷ Rest is identical ▷▷▷

<caption>Fig. 16: Eighth hybrid of the unforgeability proof of our threshold signature scheme. Difference with the previous hybrid are highlighted.</caption>

divergence notations to take a random variable as input, implicitly corresponding
to the divergence between the marginal distributions from **Hybrid**<sub>7</sub> and **Hybrid**<sub>8</sub>.

Note $x_j := ((\mathbf{s}_j, c_j), \mathbf{z}_j)_{j \in [Q_s]}$ the successive random variables in the games
$\text{Hybrid}_7(\mathcal{A})$ and $\text{Hybrid}_8(\mathcal{A})$ respectively corresponding to the partial secret $\mathbf{s}$ and
challenge $c$ then used by the signing oracle, and the rejection sampling output
$\mathbf{z}_j$. First, we can condition on the event $E = \{\forall j, \|c_j \cdot \mathbf{s}_j\| \le B_{cs}\}$. $E$ occurs
with overwhelming probability as for any $c$, and over the randomness of the
partial private keys we have $\|c_j \cdot \mathbf{s}_j\|$. We further assumed $Q_s = \text{poly}(\kappa)$ and
$(N_T) = \text{poly}(\kappa)$. Thus, $\text{Adv}_{\mathcal{A}}^{\text{Hybrid}_7} \le \text{Pr}[\text{Hybrid}_7(\mathcal{A}) \to 1 | E] + \text{negl}(\kappa)$.

By the data processing inequality of the Renyi divergence, since we can see
Hybrid<sub>7</sub> and Hybrid<sub>8</sub> as functions of the (x<sub>j</sub>)<sub>j</sub>, their Renyi divergence is bounded
by the Renyi divergence of the (x<sub>j</sub>)<sub>j</sub>.

We then apply Lemma 3:

$$
R_{\infty}(\text{Hybrid}_7 | E \parallel \text{Hybrid}_8 | E) \le \prod_j r_j
$$

where $r_j = \max_{v<j} R_\infty(x_j | x_{<j} = v_{<j} \wedge E) = \max_{v_{j-1}} R_\infty(x_j | x_{j-1} = v_{j-1} \wedge E)$.
We can apply again Lemma 3 to get:

$$R_{\infty}(x_j | x_{j-1} = v_{j-1} \land E) \le R_{\infty}((s_j, c_j) | x_{j-1} \land E) \cdot \max_{\|c^* \cdot s^*\| \le B_{cs}} R_{\infty}(z_j | (s_j, c_j) = (s^*, c^*))$$

as $z_j$ only depends on $(s_j, c_j)$.

Since $R_{\infty}((s_j, c_j) | x_{j-1} \land E) = 1$, we finally apply Lemma 4 to deduce that,

$$R_{\infty}(\text{Hybrid}_7 | E \mid \text{Hybrid}_8 | E) \le \left(1 + \frac{\varepsilon}{M-1}\right)^{Q_s}$$

Applying the probability preservation of the Renyi divergence, we get:

$$\mathrm{Adv}_{A}^{\mathrm{Hybrid}_7} \le \left(1 + \frac{\varepsilon}{M-1}\right)^{Q_s} \cdot \mathrm{Adv}_{A}^{\mathrm{Hybrid}_8} + \mathrm{negl}(\kappa)$$

**Hybrid**_9. In this hybrid, we replace the public key by $[\hat{\mathbf{b}}]_{\nu_b}$ where $\hat{\mathbf{b}} \stackrel{\$}{\leftarrow} \mathcal{R}_q^k$. To preserve consistency, we fix a secret index $I$ such that $I_0 \subseteq \text{honest}$, i.e. $s_{I_0}$ is not given to the adversary, and we replace $\mathbf{b}_{I_0}$ with $\mathbf{b}_{I_0} := \hat{\mathbf{b}} - \sum_{I \ne I_0} \mathbf{b}_I$. This is formalized in Fig. 17.

As secrets are no longer used by honest parties in the scheme at this stage, we can replace $\mathbf{b}_{I_0}$ by a uniform value by the MLWE$_{q,k,l,\chi_{sk}}$ assumption. Equiv- alently, we can then sample $\hat{\mathbf{b}}$ uniformly at random and define $\mathbf{b} := [\hat{\mathbf{b}}]_{\nu_b}$ and $\mathbf{b}_{I_0} := \hat{\mathbf{b}} - \sum_{I \ne I_0} \mathbf{b}_I$.

Formally, there exists an adversary $\mathcal{B}_5$ against the MLWE$_{q,k,l,\chi_{sk}}$ problem such that:

$$|\mathrm{Adv}_{A}^{\mathrm{Hybrid}_8} - \mathrm{Adv}_{A}^{\mathrm{Hybrid}_9}| \le \mathrm{Adv}_{\mathcal{B}_5}^{\mathrm{MLWE}_{q,k,l,\chi_{sk}}}$$

**Conclusion.** Finally, we reduce Hybrid_9 to the SelfTargetMSIS assumption. The proof goes as in [DKM+24, Lemma C.4], except that we may also consider the infinite norm.

At a high level, it defines a challenger $\mathcal{B}_6$ against the SelfTargetMSIS problem that takes as input a $\mathbf{M} \in \mathcal{R}_q^{k \times (l+1)}$. It sets $\hat{\mathbf{b}}$ as the first column of $\mathbf{M}$, and $\mathbf{A}$ as the $\ell$ remaining columns.

Then, $\mathcal{B}_6$ simulates Hybrid_9 except for one difference: whenever $H_c$ is queried on $(\mathbf{vk}, \mathbf{msg}, \mathbf{w})$, $\mathcal{B}_6$ queries $(2^{\nu_w} \cdot \mathbf{w} \mod q, \mathbf{msg})$ to the SelfTargetMSIS random oracle $\mathcal{G}$ and uses that as the output instead.

Given a valid forgery $\mathbf{sig}^* = (c^*, \mathbf{z}^*, \mathbf{h}^*)$, the adversary $\mathcal{B}_6$ builds a SelfTargetMSIS solution for $c^*$:

$$\mathbf{z}_{\text{sol}} := \begin{bmatrix} c^* \\ \mathbf{z}^* \\ -c^* \cdot \delta_{\mathbf{b}} + 2^{\nu_w} \cdot (\mathbf{h}^* - |q|_{\nu_w} \cdot \delta_1) + \delta_2 \end{bmatrix}$$

$$\text{with } \|\delta_{\mathbf{b}}\|_{\infty} \le 2^{\nu_b} - 1, \quad \|\delta_1\|_{\infty} \le 1, \quad \|\delta_2\|_{\infty} \le 2^{\nu_w} - 1.$$
<figure><img src="image_12.png" /><figcaption>Fig. 17: Nineth hybrid of the unforgeability proof of our threshold signature scheme. Difference with the previous hybrid are highlighted.</figcaption></figure>

And $\mathbf{z}_{\text{sol}}$ verifies:

$$ \|\mathbf{z}_{\text{sol}}\| \le B_{\text{stmsis}} := \begin{cases} B + \sqrt{\omega} + (\omega \cdot 2^{\nu_b} + 2^{\nu_w+1}) \cdot \sqrt{dk} & \text{if } \|\cdot\| = \|\cdot\|_2 \\ B + \omega \cdot 2^{\nu_b} + 2^{\nu_w+1} & \text{if } \|\cdot\| = \|\cdot\|_\infty \end{cases} $$

Hence,

$$ \mathrm{Adv}_{A}^{\text{Hybrid}_9} \le \mathrm{Adv}_{B_6}^{\text{SelfTargetMSIS}} $$

We finally collect all the bounds to obtain the theorem statement, noting that all the intermediary adversaries have an execution time roughly equal to $T(A)$. □

## B Omitted proof of unforgeability of non-threshold FSwA

Numerous proofs exist for the unforgeability of the Fiat-Shamir with Aborts scheme in the non-threshold setting. However, they do not extend to the threshold setting. Our proof tackles this by showing that aborting transcripts $\mathbf{w}_i$ are indistinguishable from uniform, and thus do not leak the secret.
While most interesting for the threshold setting, this also provides a new
proof strategy to prove the security of the Fiat-Shamir with Aborts signature in
the random oracle model that is generic and easily extends to many distributions.

*Proof (of Theorem 2).* Let $\mathcal{A}$ be an adversary against the EUF-CMA security of the signature scheme from Fig. 4.

The proof of Theorem 2 is easily implied by Theorem 4 by defining an ad-
versary $\mathcal{B}$ against the security of our threshold scheme with $N = 1, T = 0$.

$\mathcal{B}$ simulates $\mathcal{A}$, and whenever $\mathcal{A}$ calls the signing oracle, $\mathcal{B}$ honestly execute
the threshold signing protocol and provides the output to $\mathcal{A}$.

Noting that $\mathcal{A}$ does not need access to $H_{\text{cmt}}$, we bound the advantage of $\mathcal{B}$
with Theorem 4 by taking $Q_{H_{\text{cmt}}} = 0$. $\square$

<figure><img src="image_13.png" /></figure>