From TS-SUF-2 to TS-SUF-4: Practical Security Enhancements for FROST2 Threshold Signatures

From TS-SUF-2 to TS-SUF-4: Practical Security Enhancements for FROST2 Threshold Signatures Will Wang, Syh-Yuan Tan, Ryan Chow, Chanson Chan, and Martin Zhao

arXiv:2610.02805v1 [cs.CR] 2 Oct 2026

Solv Protocol, Singapore {will,sytan,ryan,chanson,martin}@solv.finance

Abstract. Threshold signature schemes play a vital role in securing digital assets within blockchain and distributed systems. FROST2 stands out as a practical threshold Schnorr signature scheme, noted for its efficiency and compatibility with standard verification processes. However, under the one-more discrete logarithm assumption, with static corruption and centralized key generation settings, FROST2 has been shown by Bellare et al. (in CRYPTO 2022) to achieve only TS-SUF-2 security, which is a consequence of its vulnerability to TS-UF-3 attacks. In this paper, we address this security limitation by presenting an enhanced variant of FROST2, namely, FROST2+ which achieves the TSSUF-4 security level under the same computational assumptions as the original FROST2. FROST2+ strengthens FROST2 by integrating additional pre-processing token verifications that help mitigate TS-UF-3 and TS-UF-4 vulnerabilities while maintaining practical efficiency. We show that FROST2+ can achieve TS-SUF-4 security not only under the same conditions as the original FROST2 analysis, but also when initialized with a distributed key generation protocol such as PedPoP. Our benchmark using ZCash’s FROST library shows that the performance of FROST2+ is comparable to FROST2 and about 64 − 79% faster than FROST when precomputation is enabled. Keywords: Schnorr · Threshold Signature · FROST · TS-SUF · Provable Security

1

Introduction

The Schnorr signature scheme [28] has emerged as a cornerstone for blockchain applications due to its efficient signing and verification processes, compact signatures, and support for aggregation. In this context, Schnorr-based threshold signatures are particularly critical for threshold signing in blockchain systems [24,20,1,27], with FROST [22] establishing itself as a benchmark and currently undergoing IETF standardization [12]. Furthermore, NIST’s recent call for contributions on threshold multi-party schemes [9] has intensified research interest in FROST. Research related to FROST can be categorized into two main areas: the development of new schemes that offer enhanced efficiency [15,8,6,23], and improvements in security [26,11,2,10,3,25,4]. The latter category can be further divided

2

Will et al.

into specific areas of security analysis focused on distributed key generation [11,15,6] and adaptive security [16,14,10,18,2,25,17,4]. Several works [8,6,13,14,18] delve deeper into the security notions relevant to threshold signature schemes. The TS-(S)UF-i security framework [8,6] represents a recent effort to rigorously formalize the security of threshold signature schemes. This framework groups a message M along with its auxiliary signing information as a leader request (lr) and classifies unforgeability levels according to adversarial capabilities, ranging from the weakest (TS-UF-0, which resists less capable attackers) to the strongest (TS-UF-4, which resists more capable attackers). While the framework typically describes forgeries in terms of triviality, let c < t denotes the number of corrupted signers, we outline the attackers’ abilities at each level for clarity: 1. TS-UF-0: The threshold scheme can withstand an attacker who cannot obtain any partial signatures from honest signers for the target message M . 2. TS-UF-1: The threshold scheme can withstand an attacker at TS-UF-0 who also queries at most t − c − 1 partial signatures on M from honest signers. 3. TS-UF-2: The threshold scheme can withstand an attacker at TS-UF-1 who also queries leader requests (lr) on M and obtain at most t − c − 1 honest partial signatures per lr. 4. TS-UF-3: The threshold scheme can resist an attacker at TS-UF-2 who also corrupts pre-processing tokens (ppi ) for honest signers idi ∈ lr.S in the signing set, but not for all non-responding honest signers in the same set. 5. TS-UF-4: The threshold scheme can resist an attacker at TS-UF-3 who corrupts pre-processing tokens (ppi ) for all honest signers idi ∈ lr.S in the signing set, though it cannot obtain partial signatures from every honest signer in lr.S. where the descriptions of TS-UF-3 and TS-UF-4 refer to the adversary capabilities in echo schemes [6,8,13] like FROST. In such schemes, an honest signer idi only produces a partial signature if the leader request (lr) contains idi ’s honestly generated pre-processing token ppi ∈ lr.PP(idi ). The framework also introduces the concepts of strong unforgeability (TS-SUF-i), which ties a request lr to each unique signature, beyond just the message M . Moreover, the framework provides valuable insights into the relationships among security levels. For instance, it demonstrates that achieving TS-UF-0
n security implies TS-UF-1 security, risking a security loss of t−1 for number of signers n and threshold t. Additionally, it shows that combining a threshold scheme achieving TS-UF-3 security with a standard digital signature scheme with strong existential unforgeability under chosen-message attacks (SUF-CMA) results in a threshold scheme with TS-UF-4 security. Within this security framework, both FROST and FROST2 achieve TS-UF-0 (and thereby TS-UF-1) security in the distributed key generation (DKG) settings [22,15,6], which represents the baseline security level within the TS-UF-i hierarchy. Under the centralized key generation (CKG) setting, FROST achieves TSSUF-3 security and can be further improved to attain the highest TS-SUF-4 security level by incorporating an additional digital signature scheme for each signer

Title Suppressed Due to Excessive Length

3

[8,6,13]. However, this approach introduces additional computational overhead and implementation complexity. More critically for our work, FROST2 [15,8,6] has been shown to achieve only TS-SUF-2 security and is not qualified for this security upgrade. The limitation of FROST2 to TS-SUF-2 security arises from a fundamental vulnerability to TS-UF-3 attacks, as demonstrated by Bellare et al. [8,6]. This attack is reminiscent of the rogue public key attack in multi-signature schemes, exploiting a weakness in FROST2’s pre-processing token mechanism to forge a Schnorr signature. Consequently, this enables a forgery under an unauthorized signer set without needing to know the partial signatures of all honest signers, thereby compromising TS-UF-3 security (see Appendix A.2). Enhancements to FROST2 have been proposed, but none have achieved TSSUF-3 security or higher. For instance, ROAST [26] introduces token aggregation and signature share verification, improving robustness while acknowledging security reduction to the original FROST2. Its successor, Olaf [11], combines ROAST with a simplified DKG protocol (SimplPedPoP) from FROST’s PedPoP, proving its TS-SUF-2 security. Recent theoretical results [14,17] indicate that FROST, FROST2, and FROST3 (or ROAST) are either unforgeable with full adaptive security in the algebraic group model (AGM), under the assumptions of Algebraic One-More Discrete Logarithm (AOMDL) and Low-Dimensional Vector Representation (LDVR); or adaptively secure with a maximum of t/2 corruptions, assuming AOMDL in the random oracle model (ROM). FROST-Mask [10], which can be viewed as an extension of FROST2 with masking mechanisms applied to the pre-processing tokens and partial signatures, has been proven unforgeable with adaptive security under the ROM. Conversely, ms-FROST [2] and FaFROST [4] apply masking solely to the partial signature, proving to achieve TS-UF-4 and adp-TS-UF, respectively, with adaptive security under the weaker AGM. The security notions TS-SUF-3 and TS-SUF-4 are important in practice. The TS-SUF-3 security protects against premature leakage of a pre-processing token, and the TS-SUF-4 security prevents an honest signer from being wrongfully framed for a forgery. In this work, we investigate whether FROST2, which improves efficiency over FROST and reduces communication rounds compared to several later three-round variants [15,3,25], can achieve the same TS-SUF-3 and TS-SUF-4 security levels as FROST in the ROM. 1.1

Our Contributions

We proposed an improved variant of FROST2 that achieve TS-SUF-4 security, the highest tier in Bellare et al.’s hierarchical framework, while maintaining the protocol’s efficiency and its two-round structure. The proposed FROST2+ addresses the TS-UF-3 vulnerability of FROST2 by introducing a lightweight token authentication mechanism for pre-processing tokens. In contrast to Bellare et al.’s ATS[TS, DS] transformation [8,6], which requires each signer to generate and manage an additional digital signature keypair, our approach authenticates the tokens using only the signing key share

4

Will et al.

and the secret exponents already presented in the pre-processing tokens (R, S). We establish the TS-SUF-4 security of FROST2+ under the one-more discrete logarithm (OMDL) assumption within the ROM, in the static corruption and centralized key generation (CKG) settings. Subsequently, we show that our proposed schemes maintain their security levels when transitioning from the CKG setting to a distributed key generation (DKG) setting, specifically using PedPoP DKG as an instantiation. We also explain how to speed up the partial signing algorithm by pre-verifying the preprocessing tokens, which is not bind to the signing message. Moreover, similar to FROST’s offline pre-processing, our token verification mechanism facilitates per-signer batching across multiple signing sessions. This design choice preserves the efficiency of FROST-style pre-processing, making our schemes particularly advantageous for high-throughput, leaderless environments where offline token preparation is critical. Finally, we show that the proposed FROST2+, while offering stronger security, achieves better efficiency than FROST and matches the performance of FROST2, as detailed in our performance evaluation (Section 5). Organization. This paper is structured as follows. In Section 2, we present the necessary mathematical tools. We then outline the proposed FROST2+ scheme in Section 3, followed by the security analysis in Section 4. Next, we present the performance evaluation in Section 5 and conclude the paper in Section 6.

2

Preliminaries

We briefly recall the required mathematical tools in this section.

2.1

One-More Discrete Logarithm (OMDL) Assumption

Definition 1. Let G be a cyclic group of prime order p with generator g, and let Chall and Dlog be oracles such that: $

– Chall() returns a random challenge A = g a for a ← − Z∗p ∗ b – Dlog(B) returns b ∈ Zp such that B = g for any B ∈ G The OMDL assumption states that for any probabilistic polynomial-time adversary C making at most q − 1 queries to Dlog, the advantage 

 (A1 , . . . , Aq ) ← Chall(), Chall,Dlog   (g) Advomdl G (C) = Pr (a1 , . . . , aq ) ← C ∀i : g ai = Ai ∧ C never queried Dlog(Ai ) is negligible.

Title Suppressed Due to Excessive Length

2.2

5

Lagrange Coefficient

Let f (·) be a random (t − 1)-degree polynomial such that f (xi ) = si . The polynomial f (·) can be reconstructed by having the knowledge of t-pair values of (xi , si ): X f (·) = si ∆xi ,S (·) xi ∈S

where S = {x1 , x2 , . . . , xt }. Definition 2. The Lagrange coefficient ∆xi ,S is defined as: Y

∆xi ,S (Z) =

xj ∈S,j̸=i

Z − xj xi − x j

where xi and xj are elements in the set S. 2.3

Threshold Signature Scheme

To synchronize with Bellare et al.’s TS-(S)UF-i security framework [8,6], we adopt their scheme definition while making some adjustments, which includes the addition of a Setup algorithm and modifications to certain inputs for each algorithm. We define a non-interactive threshold signature scheme as TS={Setup, Kg, SPP, LPP, LR, PS, Agg, Vf, SVf}, characterized as follows: Setup(1λ ) → par: The setup algorithm takes in a security parameter 1λ and produces public parameters par, which are implicitly provided to all other algorithms. Kg(par, t, ns) → {sti = (X̃, aux, sk)}ns i=1 : The key generation algorithm takes in threshold t and number of signers ns such that t ≤ ns, initializes the state sti for every signer idi ∈ {id1 , . . . , idns } with joint public key X̃, public auxiliary information aux, and a signing key share sk. SPP(sti ) → (pp, sti ): The signing pre-processing algorithm takes as input the state sti of signer idi . It outputs a pre-processing token pp and updates the signer’s state. LPP(idi , pp, st0 ) → st0 : The leader pre-processing algorithm takes the pre-processing token pp from signer idi and the leader’s state st0 , updating st0 to incorporate the token. LR(M, S, st0 ) → (lr, st0 ): This leader signing-request algorithm generates a leader request lr based on a message M , a signing set S with at least t signers, and the leader’s state st0 .

6

Will et al.

PS(lr, sti ) → (psigi , sti ): The signer partial-signing algorithm takes the leader request lr, the state sti of a signer idi , generating a partial signature psigi and updating state sti . Agg(lr, {psigi }idi ∈lr.S , st0 ) → (σ, st0 ): The leader partial-signature aggregation algorithm aggregates the partial signatures received from the signing set S into a final signature σ for the message M while updating the leader’s state st0 . Vf(X̃, M, σ) → 0 or 1: The verification algorithm checks the validity of the signature σ for the message M using the public key X̃, returning 1 if valid and 0 otherwise. SVf(X̃, lr, σ) → 0 or 1: The strong verification algorithm checks the validity of the signature σ for the leader request lr using the public key X̃, returning 1 if valid and 0 otherwise. 2.4

Security Model

Table 1. Trivial forgery predicates for TS-(S)UF-i [8,6] with Cremers et al.’s recommendation [13]. Predicate Definition tf0 (M ) tf1 (M ) tf2 (lr) tf3 (lr) tf4 (lr)

S1 (M ) = ∅ |S1 (M )| ≥ t − |CS| |S2 (lr)| ≥ t − |CS| tf2 (lr) ∧ S2 (lr) = S3 (lr) tf2 (lr) ∧ S2 (lr) = S3 (lr) = S4 (lr)

tsf2 (lr, X̃, σ) tf2 (lr) ∧ SVf(X̃, lr, σ) tsf3 (lr, X̃, σ) tf3 (lr) ∧ SVf(X̃, lr, σ) tsf4 (lr, X̃, σ) tf4 (lr) ∧ SVf(X̃, lr, σ)

To address a shortcoming in the original hierarchy of Bellare et al.’s hierarchy framework [6], where TS-(S)UF-4 does not imply TS-(S)UF-3, and vice versa, due to incomparable trivial forgery conditions, we adopt the strengthened trivial forgery condition in Table 1 for tf4 as recommended by Cremers et al. [13]. Specifically, this strengthens tf4 from requiring S2 (lr) = S4 (lr) to S2 (lr) = S3 (lr) = S4 (lr), ensuring that all honest signers in lr.S responded with honestly generated pre-processing tokens. The modification is purely definitional such that for echo schemes satisfying the standard pre-processing token check, it does not change the set of trivial forgeries. In particular, this holds for the ATS[TS,DS] transformation [8,6] whose partial signing only accepts signed pre-processing tokens, so the original and the strengthened tf 4 coincide and the existing TSSUF-4 security proof for ATS[TS,DS] remains valid.

Title Suppressed Due to Excessive Length

7

Games Gts-uf-i (i = 0, 1, 2, 3, 4) and Gts-suf-i (i = 2, 3, 4) TS TS Init(CS): 1: Require: CS ⊆ {id1 , . . . , idns } and |CS| < t $

$

2: h ← − TS.HF; (X̃, aux, sk1 , . . . , skns ) ← − Kg 3: HS ← {id1 , . . . , idns } \ CS 4: for idi ∈ HS do 5: sti .sk ← xi ; sti .X̃ ← X̃; sti .aux ← aux 6: end for 7: return X̃, aux, {xi }idi ∈CS

▷ Set of corrupted signers ▷ Set of hash functions TS.HF ▷ Set of honest signers

PPO(idi ): 8: Require: idi ∈ HS $ 9: (pp, sti ) ← − SPP(sti ); P P L ← P P L ∪ {(idi , pp)} 10: return pp PSignO(idi , lr): 11: Require: lr.S ⊆ {id1 , . . . , idns }, M = lr.msg ∈ {0, 1}∗ and idi ∈ HS $

12: (psig, sti ) ← − PS(lr, sti ); L ← L ∪ {lr} 13: if psig ̸= ⊥ then 14: S1 (M ) ← S1 (M ) ∪ {idi }; S2 (lr) ← S2 (lr) ∪ {idi } 15: end if 16: return psig RO[h](x) : 17: return h(x) Fin(M, σ): 18: for all lr ∈ L do 19: S3 (lr) ← {idi ∈ HS ∩ lr.S : lr.PP(idi ) ∈ P P L}; S4 (lr) ← HS ∩ lr.S 20: end for 21: if ¬Vf(X̃, M, σ) then 22: return false; 23: end if for i = 0, 1 then 24: if Game Gts-uf-i TS 25: return ¬tfi (M ) 26: end if 27: if Game Gts-uf-i for i = 2, 3, 4 then TS 28: return ¬∃lr(lr.msg = M ∧ tfi (lr)) 29: end if 30: if Game Gts-suf-i then TS 31: return ¬∃lr(lr.msg = M ∧ tsfi (lr, X̃, σ)) 32: end if Fig. 1. Security games defining TS-(S)UF-i [6,8,13].

This strengthening approach, corresponds to Cremers et al.’s SiGu-4:aLRhPP level, restores linear downward implications across the hierarchy (e.g., TS-(S)UF-

8

Will et al.

4 implies TS-(S)UF-3) without weakening the lower levels as done in the revised version [8]. We prefer this strengthened TS-(S)UF-i model as shown in Figure 1 over Cremers et al.’s full framework [13] because it provides a standard comparison to FROST and its related variants. Definition 3. Let X ∈ {suf, uf} and i ∈ {0, 1, 2, 3, 4}. A TS scheme is secure if there is no polynomial time algorithm F that can win the game Gts-X-i in time TS T (F) with non-negligible advantage: ts-X-i Advts-X-i (F) = true]. TS (F) = Pr[GTS

2.5

Generalized Forking Lemma Extension

This lemma is proposed by Bellare et al. [8,6] in proving the TS-SUF-2 security of FROST2. It extends the generalized Forking Lemma [7] where if A can only output index I within a given set SS ⊆ [1..q], then the final bound on acc(ForkA ) depends only on |S| instead of q. This reduces the security loss from 1/q to 1/|SS|. Lemma 1. Let q ≥ 1 be an integer, SS ⊆ [1..q] be a set, and H be a set. Let A be a randomized algorithm that on input x, h1 , . . . , hq outputs a pair (isig , Out), where isig ∈ {⊥} ∪ SS and Out is a side output. Let GrGen be a randomized algorithm that generates as acc(A) =  x. The accepting probability of A is defined  Prx←GrGen, h1 ,...,hq ←H (isig , Out) ← A(x, h1 , . . . , hq ) : isig ̸=⊥ . The accepting probability of ForkA is defined as   acc(ForkA ) = Pr α ← ForkA (x) : α ̸=⊥ . x←GrGen

Then acc(ForkA ) ≥ acc(A)2 /|SS|. 2.6

Generalized Multi-Instance Multi-Forking Lemma

We extend the generalized multi-instance forking lemma of Bagherzandi et al. [5] to allow multiple forks per instance. The statement is average-case over parameters generated by GrGen, in the same style as the original lemma. In essence, we modify the success count of each local instance from 1 to n, analogous to Gennaro et al.’s multi-reset lemma [19] built upon Bellare and Neven’s generalized reset lemma [7]. Let H be a finite set and let q, N, n be positive integers. Consider an algorithm A that, on input par, internal coins ρ, and a random-oracle tape h = (h1 , . . . , hq ) ∈ Hq , outputs an index set I and side outputs ({outi }i∈I , θ). If A fails, it outputs (I, {outi }i∈I , θ) with I = ∅. Otherwise we assume |I| = N , treating I as a multiset and allowing repetitions, and we assume that if I = {i1 , . . . , iN } then i1 ≤ · · · ≤ iN . Note that we adopt the simplified output notations [11] that has an extra θ, which can be viewed as a suffix in every outi .

Title Suppressed Due to Excessive Length

9

Let Ω = {(ρ, h1 , . . . , hq ) | ρ ∈ {0, 1}∗ , hj ∈ H} be the set of all possible random tapes. For a fixed par, let S(par) = {f ∈ Ω | A(par, f ) succeeds}. Define ε(par) = Prf ←Ω [A(par, f ) succeeds] and let ε̂ = Prpar←GrGen(1λ ), f ←Ω [A(par, f ) succeeds]. Let O = {(him , outim )}N m=1 be the side outputs from the initial execution, and let O′ = ∅ initially. The forking algorithm MIMForkA N,n (par) performs N local rewinding processes, one for each occurrence im in the ordered multiset I. For each target occurrence im , it resamples the random-oracle suffix starting at im until it collects n additional side outputs whose random-oracle responses at im are pairwise distinct and also distinct from the original response him .

Algorithm 1 MIMForkA N,n (par)

Generalized

Multi-Instance

Multi-Forking

Algorithm

1: Pick internal coins ρ for A at random $ 2: (h1 , . . . , hq ) ← − Hq 3: (I, {outi }i∈I , θ) ← A(par, (h1 , . . . , hq ); ρ) 4: if I = ∅ then 5: return ⊥ 6: end if 7: Parse I as a multiset {i1 , i2 , . . . , iN } suchthat i1 ≤ i2
 ≤ · · · ≤ iN 8N q ′ 8N n ln ; Tmax ← nL 8: O ← {(him , outim )}N m=1 ; O ← ∅ ; L ← ε̂ ε̂ 9: for m = 1 to N do ′ 10: Om ← ∅ ; cm ← 0 ′ 11: while |Om | < n and cm < Tmax do (m,c

)

(m,c

)

$

− Hq−im +1 12: cm ← cm + 1 ; him m , . . . , hq m ← (m,cm ) (m,c )
(m,cm ) 13: Q ← h1 , . . . , him −1 , him , . . . , hq m 14: (I ′ , {out′i }i∈I ′ , θ′ ) ← A(par, Q(m,cm ) ; ρ) 15: if im ∈ I ′ then (m,c ) ′ } then / {him } ∪ {h′ | (h′ , ·) ∈ Om 16: if him m ∈ (m,cm ) ′ ′ ′ , outim )} 17: Om ← Om ∪ {(him 18: end if 19: end if 20: end while ′ 21: if |Om | < n then 22: return ⊥ 23: end if ′ 24: O ′ ← O ′ ∪ Om 25: end for 26: return (O, O′ )

Lemma 2 (Generalized Multi-Instance Multi-Forking Lemma). Let H be a finite set and let q, N, n ∈ N with N, n ≥ 1. Let A be a randomized algorithm that, on input par and a vector h ∈ Hq , returns an index set I and side outputs ({outi }i∈I , θ). Define ε̂ as above. Assume |H| > 16Nε̂ nq . Then the

10

Will et al.

accepting probability of MIMForkA N,n is  h i ε̂  A acc MIMForkA N,n = Pr MIMForkN,n (par) ̸= ⊥ ≥ , 8 where the probability is over par ← GrGen(1λ ) and the coins of MIMForkA N,n . Moreover, whenever the algorithm returns (O, O′ ), for every occurrence im the ′ collection Om contains n pairs whose first components are pairwise distinct and distinct from him . Proof. For a fixed par, let ε = ε(par) and S = S(par) where Pr[S] = ε by definition. For every f ∈ S, let I(f ) = {i1 (f ), . . . , iN (f )}, where i1 (f ) ≤ · · · ≤ iN (f ). For j ∈ {1, . . . , q}, let fj = (ρ, h1 , . . . , hj−1 ) denote the prefix before the j-th random-oracle response, and let sj = (hj , . . . , hq ) denote the corresponding suffix. For every n m ∈ {1, . . . , N } and j ∈ {1, . . . , q}, define Ajm = {f ∈ S | im (f ) = o   Sq j j ). = f ∈ Ω Prsj (fj ∥sj ) ∈ Ajm ≥ 2Nε q . Let Em = j=1 (Ajm ∩Bm j} and Bm By part (3) of the Splitting Lemma [5, Lemma 2], for every m, Pr[Em | S] =

q X

j Pr[Ajm ∩ Bm | S] ≥

j=1

 q  X ε/(2N q) 1 Pr[Ajm | S] − . =1− Pr[S] 2N j=1 (1)

Hence, by the union bound, it gives " Pr S ∩

N \ m=1

# Em ≥ ε 1 −

N X m=1

! Pr[Em | S]

≥

ε . 2

(2)

TN Condition on S ∩ m=1 Em . Fix an occurrence m and suppose that fewer than n distinct forks have been collected. Since the original tape belongs to Em , im , and hence a fresh suffix yields an execution in Aimm with we have f ∈ Bm ′ probability at least ε/(2N q). Let Hforbid = {him } ∪ {h′ | (h′ , ·) ∈ Om }. Since ′ |Om | < n, we have |Hforbid | ≤ n, and conditioned on the current state of the local rewinding process, the probability that a fresh trial produces an execution n ε̂ ε in Aimm and yields a new response is at least p ≥ 2Nε q − |H| > 2Nε q − 16N q > 4N q , where the second inequality uses |H| > 16N nq/ε̂, and the last uses ε > ε̂/2 for the good parameters. Thus, as long as fewer than n forks have been collected, every rewinding trial has conditional probability at least lε/(4N q) of producing a new valid fork.
m 8N q 8N n Recall that Tmax = nL, where now L = ε̂ ln ε̂ . Partition the nL trials into n consecutive blocks of L trials. Since each trial has conditional success probability at least p > ε/(4N q) > ε̂/(8N q), the probability that a fixed block produces no new fork is at most (1 − p)L ≤ exp(−pL) ≤ 8Nε̂ n . Therefore, let Failm be the event that the m-th occurrence fails to collect n distinct forks. By the union bound over the n blocks and then over the N

Title Suppressed Due to Excessive Length

11

occurrences, " Pr Failany S ∩

N \

# Em ≤ N · n ·

m=1

ε̂ ε̂ = , 8N n 8

(3)

SN where Failany = m=1 Failm . Since we are conditioning on a good parameter with ε > ε̂/2, we have ε̂/8 < ε/4. Combining (2) and (3), for every par with ε(par) > ε̂/2, we have frk(par) ≥ 2ε − 4ε = 4ε . Finally, average over par ← GrGen(1λ ). Let P ′ = {par | ε(par) > ε̂/2}. For par ∈ P ′ , we have frk(par) ≥ ε(par) while for par ∈ / P ′ , we use the trivial bound 4 frk(par) ≥ 0. Therefore,   1 X ε(par) acc MIMForkA N,n ≥ |P | 4 par∈P ′     1 1 X 1 ε̂ ε̂  = ε̂ − ε(par) ≥ ε̂ − = . 4 |P | 4 2 8 ′

⊔ ⊓

par∈P /

3

Our Constructions

In this section we present FROST2+ (shown in Figure 2) as a TS-SUF-4 variant of FROST2 from Bellare et al. [6]. Different from Bellare et al.’s ATS[TS, DS] transformation [6], which requires each signer to manage an extra digital signature key-pair to authenticate the pre-processing token (R = g r , S = g s ), ours reuses only the existing signing key share and the secret exponents already presented in the token. That said, FROST2+ has the same construction as FROST2 except in the SPP and PS algorithms. The SPP now broadcast not only the pre-processing token (R, S) but also a short authentication transcript (u, V = g v ) with: u = v + sti .sk · e + re2 + se3 which is to be verified during PS. A signer aborts PS whenever a peer’s (u, V ) verification fails. The correctness follows directly from the equations such that if all parties are honest, then for each authentication transcript (u, V ), we have 2 3 g u = V Xie Re S e . In the signing phase, Pthe partial signatures satisfy zi = ri + dsi + c∆idi ,S (0)sti .sk. Aggregating z = idi ∈S zi gives g z = R̃X̃ c and Vf returns 1. Moreover, as discussed in the subsequent sections, when considering a batch verification of k tokens (R1 , S1 , . . . , Rk , Sk ), the transcript size remains constant. 3.1

Pre-Computations

Although the TS-SUF-i notions of Bellare et al. [6] assume a designated leader for collecting and distributing pre-processing tokens and signing requests to simplify security analysis, they explicitly cover scenarios in which corrupted signers take turns acting as the leader. Consequently, a leaderless design introduces no

12

Will et al.

Setup(1λ ) (G, p, g) ← GrGen(1λ ) Hpp , Hnon , Hsig : {0, 1}∗ → Z∗p par ← ((G, p, g), Hpp , Hnon , Hsig ) return par Kg(par, t, ns) : For i = 0 to t − 1, do ai ∈ Z∗p For i = 1 to ns, do P j ski ski ← t−1 j=0 aj × idi ; Xi ← g X̃ = g a0 ; aux ← ({Xi }1≤i≤ns ) For i = 1 to ns, do sti ← (X̃, aux, ski ) return {sti }1≤i≤ns

CompPar(X̃, lr) M ← lr.msg d ← Hnon (X̃, lr) (Ri , Si ) ← lr.PP(idi ) Q Q R̃ ← idi ∈lr.S Ri ( idi ∈lr.S Si )d c ← Hsig (X̃, M, R̃) return (R̃, c, d) PS(lr, sti ) ppi ← lr.PP(idi ) If sti .mapPP(ppi ) =⊥, return (⊥, sti ) X̃, aux ← sti For idi ∈ lr.S, do (Ri , Si , ui , Vi ) ← lr.PP(idi )

SPP(sti ) $

r, s , v ← − Z∗p e = Hpp (X̃, Xi , R = g r , S = g s , V = g v ) u = v + sti .sk · e + re2 + se3 pp ← (R, S , u, V ) sti .mapPP(pp) ← (r, s , v ) return (pp, sti ) LPP(idi , pp, st0 ): st0 .currPPi ← st0 .currPPi ∪ {pp} return st0 LR(M, S, st0 ) If ∃idi ∈ S : st0 .curPP(idi ) = ∅, return (⊥, st0 ) lr.msg ← M ; lr.S ← S For idi ∈ S, do Pick ppi from st0 .curPP(idi ) lr.PP(idi ) ← ppi st0 .curPP(idi ) ← st0 .curPP(idi ) \ {ppi } return (lr, st0 ) Vf(X̃, M, σ) (R̃, z) ← σ ; c ← Hsig (X̃, M, R̃) return (g z = R̃X̃ c )

e′ = Hpp (X̃, Xi , Ri , Si , Vi ) ′

′2

′3

If g ui ̸= Vi Xie Rie Sie , return ⊥ Else lr.PP(idi ) ← (Ri , Si ) (ri , si ) ← sti .mapPP(ppi ) sti .mapPP(ppi ) ←⊥ (R̃, c, d) ← CompPar(sti .X̃, lr) zi ← ri + d · si + c · ∆idi ,S (0) · sti .sk psigi ← (R̃, zi ) return (psigi , sti ) Agg({psigi }idi ∈lr.S , st0 ) R̃ ←⊥; z ← 0 For idi ∈ S, do If R̃ =⊥, R̃ ← psigi .R̃ If R̃ ̸= psigi .R̃, return (⊥, st0 ) z ← z + psigi .z σ ← (R̃, z) return (σ, st0 ) SVf(X̃, lr, σ) (R̃, z) ← σ (R̃′ , c′ , d) ← CompPar(X̃, lr) ′ return (R̃ = R̃′ ) ∧ (g z = R̃X̃ c )

Fig. 2. The FROST2 and FROST2+ signature schemes where FROST2 contains all but the solid box. GrGen generates cyclic group parameter in which the discrete logarithm assumption holds, st is state, ns < p − 1 is the number of signers, and t is the signing threshold. The function mapPP records dlogs of tokens pp, and currPP is the current pp collection.

Title Suppressed Due to Excessive Length

13

unmodeled attack vectors. In particular, attacks captured by TS-UF-3 and TSUF-4, where a corrupted leader forging tokens or requests, are already included in the TS-SUF-i adversary model. When an honest signer initiates the protocol, the same corruption bounds apply, preserving the original security guarantees. If our proposed FROST2+ adopts this leaderless approach, signers can collect and verify pre-processing tokens as in the original FROST [22] prior to the partial signing (PS) phase. This pre-verification step improves runtime performance, as shown in Table 2, without compromising security. 3.2

Batch Verification

Similar to ATS[FROST,DS] [8,6] which can generate an offline signature on multiple tokens for batch verification, our FROST2+ generates an offline authentication transcript on multiple tokens for the same purpose. Specifically, when a signer idi has n(≥ 2) tokens to be verified, during SPP, the signer computes: $

{ri,j , si,j }nj=1 , v ← − Z∗p , e = Hpp (X̃, Xi , {Ri,j , Si,j }nj=1 , V = g v ) n n X X si,j ej+1+n , pp ← ({Ri,j , Si,j }nj=1 , u, V ) ri,j ej+1 + u = v + sti .sk · e + j=1

j=1

where the transcript size (u, V ) remains constant. Subsequently, the verification is done by checking whether: g

u

′ = V Xie

n Y j=1

e′j+1 Ri,j

n Y

′j+1+n

e Si,j

j=1

holds where e′ = Hpp (X̃, Xi , {Ri,j , Si,j }nj=1 , V ). Enabling this batch verification feature does not affect the TS-SUF-4 security level, but the reduction loss because the run time of reduction is linear to n as shown in Section 4. If a tighter reduction is desirable, then one may need to explore the Multi-Instance Reset Lemma [21].

4

Security Analysis

We prove the TS-SUF-4 security of FROST2+ under the OMDL assumption in the random oracle model. Our proving strategy is to separate the security analysis into three parts which handle the events 1. E1 : Vf(X̃, M ∗ , σ ∗ ) ∧ (lr∗ =⊥ ∨ |S2 (lr∗ )| < t − |CS|), 2. E2 : Vf(X̃, M ∗ , σ ∗ ) ∧ lr∗ ̸=⊥ ∧ S2 (lr∗ ) ̸= S3 (lr∗ ), 3. E3 : Vf(X̃, M ∗ , σ ∗ ) ∧ lr∗ ̸=⊥ ∧ ¬(S2 (lr∗ ) = S3 (lr∗ ) = S4 (lr∗ )), respectively. We first present the security proofs in the centralized key generation setting to ease exposition, and show how to extend them to the decentralized key generation setting in Section 4.1.

14

Will et al.

Theorem 1. Let F be a TS-SUF-4 forger against FROST2+ making at most q queries to the random oracle. Suppose the success probability of F is bounded by Advts-suf-4 FROST2+ (F) ≤ Pr[E1 ] + Pr[E2 ] + Pr[E3 ]. Then, there exist three OMDL adversaries B1 , B2 and B3 such that: q omdl omdl q · Advomdl Advts-suf-4 (F) ≤ G (B1 ) + 8AdvG (B2 ) + 8AdvG (B3 ) + negl FROST2+ where B1 and B3 issue at most 2qs + t queries to the Chall oracle, while B2 issues at most 2qs queries. Moreover, their running times are bounded above by T (B1 ) ≤ 2T (F ) + T (q), 16ns2 q ln(16ns/ Pr[E2 ]) T (F) + T (q), and Pr[E2 ] 24q ln(24/ Pr[E3 ]) · T (F) + T (q), T (B3 ) ≤ Pr[E3 ] T (B2 ) ≤

respectively, where t ≤ ns, and T (q) denotes the time required for the relevant group operations and exponentiations. Proof. The proof follows from Lemmas 3, 4 and 7.

⊓ ⊔

Lemma 3 is intended for the event E1 , where the forgery must contain at least one forged psigi . The proof is similar to the TS-SUF-2 proof of FROST2 [8, Lemma 5.2], except that we add an additional RO[Hpp ] to handle the authentication transcript (u, V ) and adjust the sequence of hash queries accordingly. Lemma 3. There exists an OMDL adversary B1 making at most 2qs + t queries to the Chall oracle and q queries to the random oracle such that q Pr[E1 ] ≤ q · Advomdl G (B1 ) + negl. Moreover, B1 runs in time roughly twice that of F, plus the time T (q) required to perform exponentiations and group operations. Proof. Let F be an adversary as described in the theorem. Denote the output message-signature pair of F as (M ∗ , sig ∗ = (R̃∗ , z ∗ )). Without loss of generality, we assume F always queries RO on Hsig (X̃, M ∗ , R̃∗ ) before F returns and always queries RO on Hpp (X̃, Xi , R, S, V ) and Hnon (X̃, lr) prior to the query PSignO(idi , lr) for some idi and lr. This adds up to 2qs additional RO queries, and we let q = qh + 2qs + 1 where qh = qpp + qnon + qsig . Let lr∗ be the leader query whose nonce query Hnon (X̃, lr∗ ) is the last such query before the signature hash query Hsig (X̃, M ∗ , R̃∗ ) and which satisfies SVf(X̃, lr∗ , σ ∗ ) = true (if none exist, lr∗ =⊥). Denote the event E1 as Vf(X̃, M ∗ , σ ∗ ) ∧ (lr∗ =⊥ ∨ |S2 (lr∗ )| < t − |CS|). We first construct an algorithm C compatible with the syntax in Lemma 1. The input of C consists of 2qs + t uniformly random group elements A =

Title Suppressed Due to Excessive Length

15

{A0 , . . . , At−1 }, R = {R1 , . . . , Rqs }, S = {S1 , . . . , Sqs } ∈ G and uniformly random integers h1 , . . . , h2(q−qpp ) , h2(q−qpp )+1 , . . . , h2q ∈ Zp . Also, C can access an oracle Dlog, which on input X ∈ G outputs DLG,g (X). To start with, C initializes all the states st0 , . . . , stns . In addition, it initializes counters ctrs , ctrh to 0, ctrpp to 2(q − qpp ) and a function dt to an empty table, which are used to record the Dlog query related to each (Rj , Sj ). C also initializes curLR ← ∅ to record all leader requests that appear during the game and initializes ctrPP to an empty table, which are used to record the counter corresponding to each token generated by honest signers. We also use a flag BadPPO to denote whether a bad event occurs, which is initially set to false. Then, C runs F with access to g PPO, g which are simulated as follows. ] PSignO, ^ RO, the oracles Init, Qt−1 id j g Init(CS): C initializes H to an empty table and sets X̃ ← A0 , Xi = j=0 Aj i for i ∈ [1..ns], and sti .sk = Dlog(Xi ) for idi ∈ CS. Finally, C returns X̃, aux = (X1 , . . . , Xns ), {sti .sk}idi ∈CS . g pp ](x): If Hpp (x) ̸=⊥, C returns Hpp (x). Otherwise, C parses x as (X̃, Xi , R, S, V ). RO[H $

If the parsing fails or X̃ ̸= A0 , C sets Hpp (x) ← − Z∗p and returns Hpp (x). Otherwise, C sets ctrpp ← ctrpp + 1 and Hpp (x) ← hctrpp then returns Hpp (x). g non ](x): If Hnon (x) ̸=⊥, C returns Hnon (x). Otherwise, C parses x as (X̃, lr). RO[H If the parsing fails or X̃ ̸= A0 , C sets Hnon (x) ← Z∗p and returns Hnon (x). Else, C sets ctrh ← ctrh + 1 and Hnon (x) ← h2ctrh −1 . It then computes R̃ ← Q h2ctrh −1 , where (Ri , Si , ui , Vi ) ← lr.PP(idi ). If Hsig (X̃, lr.msg, R̃) =⊥, idi ∈lr.S Ri Si C sets Hsig (X̃, lr.msg, R̃) = h2ctrh . In addition, C defines mapLR(ctrh ) = lr and sets curLR ← curLR ∪ {lr}. Finally, C returns Hnon (x). g sig ](x): If Hsig (x) ̸=⊥, C returns Hsig (x). Otherwise, C parses x as (X, e M, R̃). RO[H $ e ̸= X, C sets Hsig (x) ← If the parsing fails or X − Z∗p and returns Hsig (x). Else, C sets ctrh ← ctrh + 1 and Hsig (x) ← h2ctrh . Finally, C returns Hsig (x). ] i ) query: Same as in the game Gts-suf-3 , except that, in the simulation PPO(id FROST2+ $

of SPP, C increments ctrs and ctrpp by 1, chooses uctrpp ← − Z∗p and computes hctr

h2ctrpp

h3ctrpp

Vctrpp = g uctrpp /Xi pp Rctrs Sctrs . If Hpp (X̃, Xi , Rctrs , Sctrs , Vctrh ) =⊥, C sets Hpp (X̃, Xi , Rctrs , Sctrs , Vctrh ) ← hctrpp , pp ← (Rctrs , Sctrs , uctrh , Vctrh ), sti .mapPP(pp) ← (0, 0, 0, 0), and ctrPP(idi , pp) ← ctrs . Else if Hpp (X̃, Xi , Rctrs , Sctrs , Vctrpp ) ̸=⊥, ′ BadPPO is set to true. If there exists lr ∈ curLR such that lr.PP(idi ) = (Rctrs , Sctrs , u′ctrpp , Vctr ) pp ′ ′ for some valid (uctrpp ̸= uctrpp , Vctrpp ̸= Vctrpp ), then BadPPO is also set to true. ts-suf-3 ^ PSignO(id i , lr) query: Same as in the game GFROST2+ , except that, in the simuc∆id ,lr.S (0)
lation of PS, if sti .mapPP(pp) ̸=⊥, C sets zi ← Dlog Rj Sjdi Xi i , where j ← ctrPP(idi , lr.PP(idi )). In addition, C sets dt(j) ← (idi , k, di , c∆idi ,lr.S (0), zi ), where k denotes the index such that Hnon (X̃, lr) is set to h2k−1 during the simulation.

16

Will et al.

After receiving the output (lr∗ = {M ∗ , S, PP}, σ ∗ = (R̃∗ , z ∗ )) from F, C returns ⊥ if BadPPO = true, or E1 does not occur. Else, C finds the index isig such that Hsig (X̃, M ∗ , R̃∗ ) is set to hisig during the simulation. By our assumption on F, we know such isig must exist. Then, C returns (isig , Out), where Out consists of all variables received or generated by C. Analysis of C. To apply Lemma 1, we define SS := {2k}k∈[1..q−qpp ] and let GrGen be the algorithm that samples 2qs + t group elements uniformly from G and outputs them. From the simulation, the output index isig of C is always in SS. Moreover, it is clear that C simulates the game Gts-suf-4 FROST2+ perfectly when all the inputs to C are uniformly sampled from their domain, which implies acc(C) ≥ Pr[E1 ] − Pr[BadPPO], where Pr[E1 ] denotes the probability in the original Gts-suf-3 FROST2+ game with F as in Lemma 1, and Pr[BadPPO] denotes the probability that BadPPO = true at the end of C’s execution. Since each pair (Rj , Sj ) is sampled uniformly from G and the corresponding authentication transcript (u, V ) is generated by programming RO[Hpp ], for each PPO(idi ) query, the probability BadPPO is set to true is negligible and at most qh /p + |curLR|/p = 2qh /p. Therefore, we have Pr[BadPPO] ≤ 2qs qh /p. By Lemma 1, acc(ForkC ) ≥

4 Pr[E1 ]qs qh Pr[E1 ]2 2qh Pr[E1 ]2 (Pr[E1 ] − 2qs qh /p)2 − ≥ − . ≥ q − qpp q p·q q p

Construct B1 from ForkC . We now construct the OMDL adversary B1 using ForkC and the available Dlog oracle. To begin, B1 queries Init and then queries Chall oracle 2qs +t times to generate the three lists of group elements (A, R, S) as the input to run ForkC . Without loss of generality, we can assume all the OMDL challenges are distinct, since otherwise B1 can solve them trivially. All Dlog queries from ForkC are forwarded by B1 to the Dlog oracle in the game ′ ′ Gomdl G . Denote by BadHash the event that any two of the scalars h1 , h1 , . . . , hq , hq C generated in the execution of Fork are equal. Since these scalars are sampled uniformly from Z∗p , we have Pr[BadHash] ≤ 2q 2 /p. It remains to show that if ForkC returns (isig , Out, Out′ ) and BadHash does not occur, B1 wins the game Gomdl G . Absorbing all strictly negligible terms into a function negl, we have C Advomdl G (B1 ) ≥ acc(Fork ) − Pr[BadHash] ≥

Pr[E1 ]2 3q 2 Pr[E1 ]2 − = − negl. q p q

We use the notations introduced in the description of C to denote the variables in Out and append a prime (·)′ to denote the variables in Out′ . By the execution ′ ′ of ForkC , we have (X̃, M ∗ , R̃∗ ) = (X̃ ′ , M ∗ , R̃∗ ) and X̃ = A0 . Since isig ∈ SS, let k ∗ = isig /2 where mapLR(k ∗ ) = lr∗ . Furthermore, if mapLR(k ∗ ) =⊥, then lr∗ =⊥ as well. We first show how to compute the discrete logarithm of A0 , . . . ,P At−1 . Det−1 i note these discrete logarithms by a0 , . . . , at−1 and define f (x) := i=0 ai x . ∗ ∗ ′ Since BadHash does not occur, we have Hsig (X̃, M , R̃ ) = hisig ̸= hisig =

Title Suppressed Due to Excessive Length

Hsig ′ (X̃, M ∗ , R̃∗ ). As g z ∗

∗′

f (0) = a0 = hi z −z −h′ sig

∗

isig

= R̃∗ g a0 hisig and g z

∗′

17

a h′

= R̃∗ g 0 isig , B1 computes

. Define Tdt := {j : (i, k, d, c, z) ← dt(j), k = k ∗ }.

For each j ∈ Tdt ∩ Tdt′ , let (i, k, d, c, z) ← dt(j) and (i′ , k ′ , d′ , c′ , z ′ ) ← dt′ (j), ′ ′ ′ then g z = Rj Sjd Xic and g z = Rj Sjd Xic . Since BadPPO = false during both executions of C, we know that (Rj , Sj , uj , Vj ) was returned by a query PPO(idi ) prior to the query Hsig (X̃, M ∗ , R̃∗ ) in the first execution of C. Because the two executions of C are identical up to the query Hsig (X̃, M ∗ , R̃∗ ), we have id′i = idi . Moreover, we know d = hk = hk∗ = hk′ = d′ . ′ Therefore, B1 can compute f (idi ) = DLG,g (Xi ) = z−z c−c′ . Let D := {idi }j∈Tdt ∩Tdt′ , (i,k,d,c,z)←dt(j) . If S2 (lr∗ ) < t − |CS| occurs in the first execution of C, then |Tdt | = |S2 (lr∗ )| < t − |CS|. Therefore, we have |D| = |Tdt ∩Tdt′ | < t−|CS|. Consequently, B1 can pick an arbitrary set D′ ⊆ HS \D of size (t − |CS| − |Tdt ∩ Tdt′ | − 1) and for each idi ∈ D′ , B1 queries the Dlog oracle on Xi . Thus B1 knows the value of f (idi ) for every idi ∈ CS ∪ D ∪ D′ ∪ {0}. Since |CS ∪ D ∪ D′ ∪ {0}| = t, B1 can recover a0 , . . . , at−1 by Lagrange interpolation. We now show how to compute the discrete log of R1 , S1 , . . . , Rqs , Sqs . Denote these discrete logarithms by r1 , s1 , . . . , rqs , sqs . From the execution of C, we know dt(j) = (i, k, d, c, z) ̸=⊥ if and only if C queries Dlog on Rj Sjd Xic . Therefore, we denote the Dlog query on Rj Sjd Xic as the Dlog query associated with dt(j). For each j ∈ [1..qs ], there are the following cases. Case 0: Both dt(j) and dt′ (j) are ⊥. In this case, B1 queries rj ← Dlog(Rj ) and sj ← Dlog(Sj ). Case 1: Exactly one of dt(j) and dt′ (j) is not ⊥. Without loss of generality, assume dt(j) = (i, k, d, c, z), which implies g z = Rj Sjd Xic . B1 queries sj ← Dlog(Sj ) and computes rj = z − d · sj − c · f (idi ). For all the following cases, both dt(j) and dt′ (j) are not ⊥ and we denote (i, k, d, c, z) ← dt(j) and (i′ , k ′ , d′ , c′ , z ′ ) ← dt′ (j). Case 2: k ̸= k ′ or k = k ′ > k ∗ . In this case, we have d = hk ̸= h′k′ = d′ and ′ ′ ′ ′ +c′ f (idi ) g z = Rj Sjd Xic , g z = Rj Sjd Xic . Therefore, B1 computes sj = z−cf (idi )−z d−d′ and rj = z − d · sj − c · f (idi ). Case 3: k = k ′ = k ∗ . In this case, B1 computes rj , sj the same as Case 1. Case 4: k = k ′ < k ∗ . B1 computes rj , sj the same as Case 1. Also, in this case we have d = d′ and c = c′ . Therefore, B1 queries the Dlog oracle once in order to simulate the Dlog queries associated with dt(j) and dt′ (j). We now count the number of Dlog queries made by B1 . B1 queries the Dlog oracle |CS| times to simulate the queries Dlog(Xi ) made by C for each i ∈ CS. If S2 (lr∗ ) < t − |CS| occurs, B1 queries the Dlog oracle |D′ | times to compute a0 , . . . , at−1 . For each j ∈ [1..qs ], B1 queries Dlog twice to simulate the queries associated with dt(j) and dt′ (j) and to compute rj , sj in cases 0, 1, 2, 4, and three times in Case 3. Since the condition of Case 3 is equivalent to j ∈ Tdt ∩ Tdt′ , the total Dlog queries made by B1 is 2qs + |Tdt ∩ Tdt′ | + |CS| + |D′ | = 2qs + t − 1. Therefore, B1 breaks the OMDL assumption. ⊔ ⊓

18

Will et al.

Lemma 4 below is devoted to the event E2 , which captures forgeries under the condition S2 (lr) ̸= S3 (lr). Since st.mapPP(ppi ) ̸=⊥ is enforced in the partialsigning algorithm PS, an honest signer generates a ppi (and S3 (lr) grows) whenever a psigi is requested (and S2 (lr) grows), so forgeries with S3 (lr) ⊂ S2 (lr) will not occur. Therefore, we only consider the case S2 (lr) ⊂ S3 (lr). In other words, E2 captures the attack in which at least one ppi is honestly generated but the corresponding psigi is forged. Our proof idea is to embed OMDL challenges into the honest signer’s ppi , which would fall in S3 (lr) \ S2 (lr) when E2 occurs. We show that by using the Lemma 2 with an approach inspired by the mix forking technique [11], all secret exponents in the forger’s token authentication transcripts (u, V ) (i.e., those belonging to lr∗ .S \ S3 (lr∗ )) can be recovered, and an OMDL challenge in S3 (lr∗ ) \ S2 (lr∗ ) can be solved without querying the Dlog oracle. Lemma 4. There exists an OMDL adversary B2 issuing at most 2qs queries to the Chall oracle and q queries to random oracle such that Pr[E2 ] ≤ 8Advomdl G (B2 ) + negl. 2

Pr[E2 ]) · T (F) + T (q) where ns is Moreover, B2 runs in time T (B2 ) ≤ 16ns q ln(16ns/ Pr[E2 ] the number of signers, and T (q) is the time required to perform exponentiations and group operations.

Proof. Let F be an adversary as described in the theorem. Denote the output message-signature pair of F as (M ∗ , sig ∗ = (R̃∗ , z ∗ )). Without loss of generality, we assume F always queries RO on Hsig (X̃, M ∗ , R̃∗ ) before F returns and always queries RO on Hpp (X̃, Xi , R, S, V ) and Hnon (X̃, lr) prior to the query PSignO(idi , lr) for some idi and lr. This adds up to 2qs additional RO queries, and we let q = qh + 2qs + 1 where qh = qpp + qnon + qsig . Let lr∗ be the leader query whose nonce query Hnon (X̃, lr∗ ) is the last such query before the signature hash query Hsig (X̃, M ∗ , R̃∗ ) and which satisfies SVf(X̃, lr∗ , σ ∗ ) = true. Denote the event E2 as E2 : Vf(vk, M ∗ , σ ∗ ) ∧ lr∗ ̸=⊥ ∧ S2 (lr∗ ) ⊂ S3 (lr∗ ). To begin, we construct an algorithm C which is compatible with the syntax in Lemma 2. The input of C consists of 2qs random elements R = {R1 , . . . , Rqs }, S = {S1 , . . . , Sqs } from G, and uniformly random integers h1 , . . . , hq ∈ Z∗p . Also, C has access to an oracle Dlog, which on input X ∈ G outputs DLG,g (X). C initializes the signers’ states st0 , . . . , stns , counters ctrh = 0 and ctrs = 0. It then runs F, answering its oracle queries as follows. Pt−1 $ i g – Init(CS): C picks a0 , . . . , at−1 ← − Zp , sets f (x) = i=0 ai x , and defines f (0) f (idi ) X̃ = g , Xi = g for i ∈ [1..ns]. For idi ∈ CS it stores sti .sk = f (idi ). It returns (X̃, (X1 , . . . , Xns ), {sti .sk}idi ∈CS ). g pp ](x): If Hpp (x) ̸=⊥, C returns Hpp (x). Otherwise, increments ctrh to – RO[H set Hpp (x) ← hctrh and returns Hpp (x).

Title Suppressed Due to Excessive Length

19

g non ](x): If Hnon (x) ̸=⊥, C returns Hnon (x). Otherwise, increments ctrh – RO[H to set Hnon (x) ← hctrh and returns Hnon (x). g sig ](x): If Hsig (x) ̸=⊥, C returns Hsig (x). Otherwise, increments ctrh to – RO[H set Hnon (x) ← hctrh and returns Hnon (x). ] i ): Same as in the game Gts-suf-3 , except that, in the simulation – PPO(id FROST2+ $

of SPP, C selects u ← − Zp , increments ctrh and ctrs to set e = hctrh , and 3 e2 computes V = g u /Xie Rctr S e . C sets Hpp (X̃, Xi , Rctrs , Sctrs , V ) ← e and s ctrs adds ppi ← (Rctrs , Sctrs , u, V ) to sti .curPP. ts-suf-3 ^ – PSignO(id i , lr): Same as in the game GFROST2+ , except that, in the simulation of PS, if sti .mapPP(ppidi ) ̸=⊥ and all ppj ∈ lr.PP pass the verifications, C retrieves (R, S) ← ppidi and other (Rj , Sj ) ∈ lr.PP to compute Q Q R̃ = i∈lr.S Ri ( i∈lr.S Si )d where d ← Hnon (
X̃, lr). C then removes ppidi from sti .curPP and returns zi ← Dlog RS d + c∆idi ,lr.S (0) f (idi ) where c ← Hsig (X̃, lr.msg, R̃). Finally, F outputs its forgery (lr∗ = {M ∗ , S, PP}, σ ∗ = (R̃∗ , z ∗ )) and wins the game Gts-suf-4 FROST2+ . C returns (I, {outi }i∈I , θ) where I are the set of random oracle indices such that outi contains hi ← Hpp (X̃, Xi , Ri , Si , Vi ) for idi ∈ lr∗ .S \ S3 (lr∗ ) and θ = (lr∗ , σ ∗ ). Analysis of C. There are two possible forging cases under the condition S2 (lr∗ ) ⊂ S3 (lr∗ ): (1) lr∗ .S \ S3 (lr∗ ) = ∅; and (2) lr∗ .S \ S3 (lr∗ ) ̸= ∅. We first present the analysis for case (1) and subsequently explain how to extend it to handle case (2). Case (1): When lr∗ .S \ S3 (lr∗ ) = ∅, F forges without generating any preprocessing tokens such that S3 (lr∗ ) = S4 (lr∗ ) = lr∗ .S. We show that there is an OMDL adversary B2 which uses C as the helper algorithm to compute the discrete logarithms of (R∗ , S ∗ ) for an id∗ ∈ S3 (lr∗ ) \ S2 (lr∗ ). B2 queries 2qs challenges R = {R1 , . . . , Rqs }, S = {S1 , . . . , Sqs } from Chall and selects random h1 , . . . , hq ∈ Z∗p as the input to C. The Dlog queries from C are relayed by B2 to its Dlog of Gomdl G Q. From (I, {out Q i }i∈I , θ) ←∗ C, B2 needs only θ to obtain ((z ∗ , c∗ , f (0)), R̃∗ = idj ∈lr∗ .S Rj ( idj ∈lr∗ .S Sj )d ) and compute the sum P α = idj ∈lr∗ .S rj + d∗ · sj = z ∗ − c∗ f (0). Subsequently, for all (Rj , Sj ) belong to the set D = S3 (lr∗ ) \ S2 (lr∗ ), B2 queries {rj ← Dlog(Rj )}idj ∈D and {sj ← Dlog(Sj )}idj ∈D\{id∗ } where id∗ ∈ D is the targeted identity who owns (R∗ , S ∗ ). For those (Rj , Sj ) belong to idj ∈ S2 (lr∗ ), they have been queried to PSignO and B2 knows zj = rj + d∗ · sj + c∗ ∆idj ,lr∗ .S (0)f (idj ) in which B2 can query sj ← Dlog(Sj ) and computes rj = zj − c∗ ∆idj ,lr∗ .S (0)f (idj ) − d∗ · sj . Therefore, lr∗ .S = D ∪ S2 (lr∗ ) and B2 can extract s∗ ← DLG,g (S ∗ ) by computing: P P α − idj ∈lr∗ .S rj − d∗ idj ∈lr∗ .S\{id∗ } sj ∗ . s = d∗ For the OMDL challenges not involved in the forgery (Rj , Sj ) ̸∈ lr∗ .PP(idj ) where idj ∈ HS, they are either queried or have not queried to PSignO. If

20

Will et al.

queried, B2 knows the corresponding partial signature zj in which it can query sj ← Dlog(Sj ) and compute rj = zj − f (idj )cj ∆idj ,lr.S (0) − dj sj . Else, B2 queries rj ← Dlog(Rj ) and sj ← Dlog(Sj ). We now count the number of Dlog queries made by B2 . For each chals , B2 queries Dlog twice except the lenge pair in {Rj = g rj , Sj = g sj }qj=1 ∗ ∗ s ← DLG,g (S ) used by the targeted honest signer id∗ ∈ S3 (lr∗ ) \ S2 (lr∗ ). Hence the total Dlog queries made by B2 equals 2qs − 1, breaking the OMDL assumption. Denote BadHash as the event of hi = hj for some i ̸= j ≤ q. Since every hash value is selected independently, it is Pr[BadHash] = 1/p. Absorbing all strictly negligible terms into a function negl, we have: ts-suf-3 Advomdl G (B2 ) ≥ Pr[GFROST2+ (F) = true] − Pr[BadHash] ≥ Pr[E2 ] − negl,

and T (B2 ) ≈ T (F) + T (q). Case (2): Now, we consider the case where F forges with at least one preprocessing token in lr∗ .PP generated by itself, i.e., lr∗ .S \ S3 (lr∗ ) ̸= ∅. In this case, the output of C’s single run is not sufficient for solving the OMDL problem. This is because C does not know the discrete logarithms of {Ri , Si }idi ∈lr∗ .S\S3 (lr∗ ) generated by F. To overcome this obstacle, we need a helper algorithm C ′ . Construct C ′ from MIMForkCN,2 . We now construct the helper algorithm C ′ , which is a syntactically valid OMDL adversary, using MIMForkCN,2 with N = |I| = |lr∗ .S \ S3 (lr∗ )|. C ′ initiates C the same as B2 did in the previous case. Similar to the proof in case (1), from (O, O′ ) ← MIMForkCN,2 , C ′ also computes the values (α, {rj ← Dlog(Rj )}idj ∈S3 (lr∗ ) , {sj ← Dlog(Rj )}idj ∈S3 (lr∗ )\{id∗ } ) but now C ′ needs to additionally extract (ri ← DLG,g (Ri ), si ← DLG,g (Si )) from {(ei,j = hi,j , ri e2i,j + si e3i,j = ui,j − f (idi )ei,j , Vi ) ← ppi,j }2j=0 for idi ∈ D where D = lr∗ .S \ S3 (lr∗ ). As lr∗ .S = D ∪ S3 (lr∗ ), C ′ can compute P P α − idi ∈lr∗ .S ri − d∗ idi ∈lr∗ .S\{id∗ } si ∗ ∗ . DLG,g (S ) → s = d∗ C ′ then solves those OMDL challenges not involved in the forgery by querying the Dlog oracle. Since a hash collision occurs with a negligible probability only, by Lemma 2, we have: acc(C ′ ) ≥ acc(MIMForkCN,2 ) − negl ≥ Pr[E2 ]/8 − negl. However, after broadcasting a ppi in any of the |I| · Tmax rewinds in MIMForkCN,2 , F still can issue PSignO queries till it forges a signature. So, C ′ does not solve OMDL because the |I|·Tmax rewinds make C issues more than 2qs Dlog queries to answer these additional PSignO queries. Construct B2 from C ′ . We now construct an OMDL adversary B2 which is defined the same as C ′ except that, starting from the first rewind of each instance i ∈ I, B2 aborts any executions of C after it has obtained the ppi . This avoids B2

Title Suppressed Due to Excessive Length

21

from issuing too many Dlog queries as done by C ′ . Moreover, B2 has the same success probability as C ′ because the θ required to compute α is available after the first run ended completely, that is, before a rewind begins. Since N = |I| = |lr∗ .S \ S3 (lr∗ )| ≤ ns − 1, and every i ∈ I collected n = 2 forks, B2 uses time: T (B2 ) ≤ T (C ′ ) ≤ |I| · Tmax · T (C) + T (q) ≤ |I| · Tmax · T (F) + T (q) 8 · ns · 2q ln(8 · ns · 2/ Pr[E2 ]) · T (F) + T (q) Pr[E2 ] 16ns2 q ln(16ns/ Pr[E2 ]) · T (F) + T (q). ≤ Pr[E2 ] ≤ ns ·

This completes the proof.

⊔ ⊓

Up to this point, FROST2+ has achieved the TS-SUF-3 security whose forgeries are covered by the events E1 and E2 . If we apply the ATS[TS,DS] transformation framework as in FROST [8,6], we obtain an ATS[FROST2+, DS] scheme that achieves TS-SUF-4 security. However, the transformation comes with the cost of managing an extra DS key pair, longer ppi and slower signing time. To avoid these, we give a direct proof instead, which is the proof for event E3 . As S4 (lr) = HS ∩ lr∗ .S and the event E2 has covered S2 (lr) ̸= S3 (lr), we only need to deal with the forgeries under S2 (lr) = S3 (lr) ⊂ S4 (lr) in E3 . Before presenting the direct proof, we would like to introduce a leader request forger Flr of FROST2+ which possesses the same ability as that of a normal TS-SUF-4 forger F, but instead of producing a valid signature (σ ∗ , lr∗ ) as the output, Flr produces a valid leader request lr∗ as the output. Denote A =⇒ B as A implies B, that is, B is reducible to A. Below, we show that Flr ⇐⇒ F when a forgery falls under S3 (lr) ⊂ S4 (lr), that is, when at least a pre-processing token is forged. Theorem 2 (Flr ⇐⇒ F). For FROST2+, a TS-SUF-4 forger F which output a forgery that falls under the event E : Vf(X̃, M ∗ , σ ∗ ) ∧ lr∗ ̸=⊥ ∧ S3 (lr) ⊂ S4 (lr). is equivalent to a leader request forger Flr . Proof. The proof follows from Lemmas 5 and 6 which show that F and Flr are equivalent under E such that they are reducible to each other. ⊔ ⊓ Lemma 5 (Flr =⇒ F). Let F be a TS-SUF-4 forger for FROST2+, and Flr be a leader request forger in FROST2+. There exists an Flr which wins Gts-lr FROST2+ such that ts-lr Advts-suf-4 FROST2+ (F) = AdvFROST2+ (Flr ) where the running time of Flr is at most that of F. Proof. It is straight forward to see that Flr can simulate the environment perfectly for F by acting as the middle-man in between its underlying FROST2+

22

Will et al.

oracles and F. When F outputs a valid TS-SUF-4 forgery (σ ∗ , lr∗ ), Flr uses lr∗ as its output. In fact, Flr can return lr∗ before answering the PSignO query on lr∗ , that is, whenever it sees that a valid lr∗ contains ppi such that S3 (lr∗ ) ⊂ S4 (lr∗ ). Therefore, Flr runs in time at most that of F. ⊔ ⊓ Lemma 6 (F =⇒ Flr ). Let F be a TS-SUF-4 forger for FROST2+, and Flr be a leader request forger in FROST2+. There exists an F which wins Gts-suf-4 FROST2+ such that ts-suf-4 Advts-lr FROST2+ (Flr ) ≤ Pr[E] ≤ 8 · AdvFROST2+ (F). 24q ln(24/Advts-lr

(F ))

lr FROST2+ · T (Flr ) + T (q) where Moreover, F runs in time T (F) ≤ Advts-lr FROST2+ (Flr ) q is the number of hash queries issued and T (q) is the time required to perform exponentiations and group operations. The number of F’s queries to each oracle is at most that of Flr .

Proof. We show that if there exists a leader request forger Flr , then we can construct a TS-SUF-4 forger F to win in Gts-suf-4 FROST2+ such that the output forgery (lr∗ , σ ∗ ) falls under the event: E : Vf(X̃, M ∗ , σ ∗ ) ∧ lr∗ ̸=⊥ ∧ S3 (lr) ⊂ S4 (lr). F constructs a wrapper C whose task is only to relay all oracle queries from Flr to F, which then replies by querying its own oracles. To begin, F forwards the g Init(CS) query from C to its underlying Init oracle and returns the required parameter (X̃, aux, {xi }idi ∈CS ). Without loss of generality, we assume |CS| = t − 1. If |CS| < t − 1, F fills it with random idi ∈ HS to make sure |CS| = t − 1 before querying Init but does not return the signing key share of the fillers to C. When Flr returns a valid lr∗ = (M, S, {ppi = (Ri , Si , ui , Vi )}idi ∈S ) during the first run, C knows (I, outi∗ , θ =⊥) with I = {i∗ } = S4 (lr∗ ) \ S3 (lr∗ ) corresponds to a query ei∗ = Hpp (X̃, Xi∗ , Ri∗ , Si∗ , Vi∗ ) such that ppi∗ ∈ lr∗ . If 1 < |I| ≤ ns, C selects a random index i∗ from the |I| indices. Then C returns (ei∗ , outi∗ ). F executed (O, O′ ) ← MIMForkC1,3 to get four transcripts (X̃, Xi∗ , Ri∗ , Si∗ , Vi∗ , ui∗ , ei∗ ) ← O, ({ui∗ ,j , ei∗ ,j }3j=1 ) ← O′ which yields a solvable system of linear equations and allows F to extract sti∗ .sk = xi∗ ← DLG,g (Xi∗ ), ri∗ ← DLG,g (Ri ), si∗ ← DLG,g (Si∗ ). Thus, F knows |CS| + 1 = t pairs of (idi , sti .sk = xi = f (idi )) and can extract the shared signing key f (0) through Lagrange interpolation. F then utilizes f (0) to generate a signature σ ∗ on lr∗ and output (σ ∗ , lr∗ ) to win its Gts-suf-4 FROST2+ game. Throughout the game, all q hash values are produced by F’s hash oracles and we assume hash collision does not occur, or F can win without Flr . Since F simulates the environment perfectly, by Lemma 2, we have: C Advts-suf-4 FROST2+ (F) = acc(MIMFork1,3 ) ≥

and F runs in time T (F) ≤

Advts-lr Pr[E] FROST2+ (Flr ) = 8 8

24q ln(24/Advts-lr FROST2+ (Flr )) · T (Flr ) + T (q). Advts-lr FROST2+ (Flr )

⊔ ⊓

Title Suppressed Due to Excessive Length

23

Now we are ready to prove the security under the event E3 , by constructing an OMDL challenger B3 that uses the forger Flr , which is equivalent to the TS-SUF-4 forger F. Lemma 7. There exists an OMDL adversary B3 issuing at most 2qs + t queries to the Chall oracle and q queries to random oracle such Pr[E3 ] ≤ 8Advomdl G (B3 ) + negl. Pr[E3 ]) · T (F) + T (q) where ns is the Moreover, B3 runs in time T (B3 ) ≤ 24q ln(24/ Pr[E3 ] number of signers, and T (q) is the time required to perform exponentiations and group operations.

Proof. The proof setup is similar to that of Lemma 3 but considering the event E3 : Vf(X̃, M ∗ , σ ∗ ) ∧ lr∗ ̸=⊥ ∧ ¬(S2 (lr) = S3 (lr) = S4 (lr)). As event E2 has covered S2 (lr) ̸= S3 (lr), we only need to deal with the forgeries under S2 (lr) = S3 (lr) ⊂ S4 (lr) in event E3 and this is a subset of event E in Theorem 2. The simulation of algorithm C is the same as that of Lemma 3 but here, C runs Flr instead of F, and takes in h1 , . . . , hq only as the hash values. By Theorem 2, the TS-SUF-4 forger F and the leader request forger Flr are equivalent. Unlike F which issues a PSignO query for lr∗ to generate partial signatures before forging, Flr outputs lr∗ directly without issuing this specific query in its winning condition. After receiving the output (lr∗ = {M ∗ , S, PP = {ppi = (Ri , Si , ui , Vi )}idi ∈S }) from Flr , C returns ⊥ if BadPPO = true, or E3 does not occur. Else, denote I = S4 (lr) \ S3 (lr) and assume N = |I| = 1, C knows (I, outi∗ , θ =⊥) with I = {i∗ } corresponds to a query ei∗ = Hpp (X̃, Xi∗ , Ri∗ , Si∗ , Vi∗ ) such that ppi∗ ∈ lr∗ . If 1 < |I| < ns, C selects a random index i∗ from the |I| indices. Then, C returns (ei∗ , outi∗ ) ← O. Construct B3 from MIMForkC1,3 . We can construct the OMDL adversary B3 using MIMForkC1,3 and the available Dlog oracle. To begin, B3 queries Init and then queries Chall oracle 2qs + t times to generate the three lists of group elements (A, R, S) as the input to run MIMForkC1,3 . All Dlog queries from MIMForkC1,3 are forwarded by B3 to the Dlog oracle in the game Gomdl G . We first show how to compute the discrete logarithm of A0 , . . . , At−1 . From (O, O′ ) ← MIMForkC1,3 , B3 obtains {ei∗ , ppi∗ = (Ri∗ , Si∗ , ui∗ , Vi∗ ) ← outi∗ } ← O and {ei∗ ,j , ppi∗ = (Ri∗ , Si∗ , ui∗ ,j , Vi∗ )}1≤j≤3 ← O′ . This yields a solvable system of linear equations, allowing B3 to extract the discrete logarithms f (idi∗ ) = xi ← DL(Xi∗ ), ri∗ ← DL(Ri∗ ) and si∗ ← DL(Si∗ ). So, B3 knows |CS| + 1 = t pairs of (idi , f (idi )) and can interpolate the key generation polynomial f (·) to extract all a0 ← DL(A0 ), . . . , at−1 ← DL(At−1 ). Since lr∗ have not been queried to PSignO, for the OMDL challenges used as tokens (Ri , Si ) ∈ lr∗ , B3 simply queries the Dlog oracle to solve them. For those (Ri , Si ) ̸∈ lr∗ generated through

24

Will et al.

the PPO queries, they are either not queried, or queried once to PSignO before Flr returns lr∗ . B3 queries Dlog oracle to solve them as explained in Lemma 3. Absorbing all strictly negligible terms such as Pr[BadPPO] and hash collision into a function negl, we have C Advomdl G (B3 ) ≥ acc(MIMFork1,3 ) − negl

Advts-lr FROST2+ (Flr ) − negl 8 Advts-suf-4 FROST2+ (F) ≥ − negl 8 Pr[E3 ] ≥ − negl, 8 ≥

//by Theorem 2

and the running time is: T (B3 ) ≤ |I| · Tmax · T (Flr ) + T (q) ≤

N · n · 8 · N · q ln(8 · N · n/Advts−lr FROST2+ (Flr )) Advts−lr FROST2+ (Flr ) 24q ln(24/Advts-suf-4 FROST2+ (F))

· T (F) + T (q) Advts-suf-4 FROST2+ (F) 24q ln(24/ Pr[E3 ]) ≤ · T (F) + T (q). Pr[E3 ]

≤

· T (Flr ) + T (q) //by Theorem 2

⊔ ⊓ 4.1

Security with Distributed Key Generation

Our amendments on the pre-processing token generation and verification mechanism are orthogonal to key generation, allowing seamless integration with FROST2 when instantiated with secure distributed key generation (DKG) protocols such as PedPoP [22,6]. This follows because SPP/PS only use the existing key share sti .sk and token exponents (r, s), and do not involve the DKG commitment/PoP messages. To ensure completeness, we demonstrate that our proposed scheme maintain TS-SUF-3 security in the ROM when it is instantiated in the DKG setting using PedPoP (in Appendix B). Essentially, the oracle simulations are similar to that in Theorem 1, except for the key generation. We first show how to build an OMDL adversary B1′ for a forgery under event E1 in the DKG setting. Intuitively, we construct the OMDL adversary B1′ using the mix forking technique [11] as follows. First, we g simulates the define a wrapper C that is same as that in Lemma 3 but its Init PedPoP protocol. Then, an algorithm D runs ForkC to extract the signing key f (0). Next, we define D′ which is syntactically a valid OMDL adversary but does not break the OMDL assumption. D′ runs MIMForkD |CS|,1 and solves all the OMDL challenges. Finally, we present B1′ , which uses D′ as a helper to break the OMDL assumption.

Title Suppressed Due to Excessive Length

25

We do not discuss the DKG-counterpart B2′ for the B2 in Lemma 4 which knows the signing key shares of every honest signer and it can run the PedPoP protocol honestly. Since B1 in Lemma 3 and B3 in Lemma 7 share the same game simulation strategy, the DKG-counterpart B3′ adopts the same key generation simulation as B1′ but perform a double forkings, that is, double layers of MIMFork, instead of a mix forking. Specifically, an algorithm D runs the first MIMForkC1,3 as in Lemma 7 to extract f (0), followed by an algorithm D′ which runs MIMForkD |CS|,1 to fork the |CS| < t PoPs generated by the forger in PedPoP. Finally, B3′ runs D′ and halts C right after PedPoP is completed to solve an extra OMDL challenges and break the OMDL assumption — exactly the same proving steps of B1′ as shown below. Theorem 3. Let F be a TS-SUF-4 forger against FROST2+ with PedPoP making at most q queries to the random oracle. Suppose the success probability of F is bounded by Advts-suf-4 FROST2+ (F) ≤ Pr[E1 ] + Pr[E2 ] + Pr[E3 ]. Then, there exist three OMDL adversaries B1′ , B2′ and B3′ such that: Advts-suf-4 FROST2+ (F) ≤

q

omdl omdl ′ ′ ′ 8q · Advomdl G (B1 ) + 8AdvG (B2 ) + 64AdvG (B3 ) + negl

where B1′ and B3′ makes at most 2qs + t queries to the Chall oracle, and B2′ makes at most 2qs queries. Moreover, the running times of B1′ , B2′ and B3′ are bounded above by 128t2 q 2 ln(64tq/ Pr[E1 ]2 ) · T (F) + T (q), Pr[E1 ]2 16ns2 q ln(16ns/ Pr[E2 ]) T (B2′ ) ≤ · T (F) + T (q), and Pr[E2 ] 12288t2 q 2 ln(512t/ Pr[E3 ]) ln(24/ Pr[E3 ]) T (B3′ ) ≤ · T (F) + T (q), Pr[E3 ]2 T (B1′ ) ≤

respectively, where t ≤ ns, and T (q) denotes the time required for the relevant group operations and exponentiations. Proof. We show how to construct the B1′ OMDL adversary before showing the B3′ OMDL adversary which shares the same proving strategy. The B1′ Adversary. We define an algorithm D which can be viewed as the DKG-counterpart of B1 in Lemma 3. It constructs a wrapper C and simulates the oracles in a similar way. However, C now defines fi (Z) for every honest signer instead of querying the OMDL oracles to implicitly define f (Z). C also defines an additional RO[Hkg ] oracle to handle the hash queries incurred by PedPoP: RO[Hkg ](x) : If Hkg (x) ̸=⊥, return Hkg (x). Else, C sets ctrpp ← ctrpp + 1 and Hkg (x) ← hctrpp then returns Hkg (x).

26

Will et al.

g Particularly, in Init(CS), let honest signers be the set HS = {idi , . . . , idns } \ CS and k = |CS| < t, C queries A0 = g a0 , {Aℓ = g aℓ }kℓ=1 ← Chall and $

$

samples {aℓ }t−1 − Z∗p . C selects {yi }idi ∈HS ← − Z∗p to implicitly define the ℓ=k+1 ← Pt−1 random polynomials fi (Z) = yi ( ℓ=0 aℓ Z ℓ ) for every honest signer idi ∈ HS. $

Firstly, for every idi ∈ HS, C increments ctrpp and chooses z̄i ← − Z∗p to comyi hctr

pute R̄i = g z̄i /A0 pp and set Hkg (Ai,0 = Ay0i , Ai,0 , R̄i ) ← hctrpp . C broadcasts i )) as the proof of possession (PoP). ((R̄i , z̄i ), C = (Ai,0 = Ay0i , . . . , Ai,t−1 = Ayt−1 ℓ Q t−1 id Secondly, C queries f ′ (idj ) ← Dlog(A0 ℓ=1 Aℓ j ) and sends xi,j = yi f ′ (idj ) from every honest signer idi ∈ HS to every corrupted signer idj ∈ CS. In return, C receives xj,i = fj (idi ) from idj ∈ CS for every idi ∈ HS. So far, C issued |CS| + 1 Chall queries and |CS| Dlog queries. As C simulates the DKG perfectly, all PoP broadcast by HS are verified and every P corrupted signer j ∈ CS obtains their signing key share xj = Pid ns ns f (idj ) =P i=1 fi (id ) = j i=1 xi,j as expected, and the joint public key is P Q Q a0 id ∈HS yi + id ∈CS aj,0 j i = idi ∈HS Ai,0 idj ∈CS Aj,0 . Furthermore, from X̃ = g F’s view, each signer’s state st is indistinguishable from that generated in the CKG setting, so the oracle simulations by D after the key generation stage are identical to that by B1 in Lemma 3. C Therefore, from P P (isig , Out) ← Fork , D can extract the signing key f (0) = a0 idi ∈HS yi + idj ∈CS aj,0 . However, D does not proceed to interpolate f (·) because it is not helpful in solving its OMDL challenges. Specifically, the discrete logarithms required here are no longer the f (·) coefficients (the OMDL challenges of B1 in Lemma 3), but the values {aj,0 = fj (0)}idj ∈CS which are not known to D. Construct helper D′ from MIMForkD |CS|,1 . Denote the output of D as (I, {outi }i∈I , θ) where outi is the internal state of D up to the i-th random oracle response such that I = (i1 , . . . , i|CS| ) are the set of random oracle indices for hi ← g and θ = f (0). We now construct a helper algoHkg (idi , Ai,0 , Ai,0 , R̄i ) during Init ′ rithm D which is a syntactically valid OMDL adversary and it runs MIMForkD |CS|,1 . D′ generates uniformly random h1 , . . . , h2q ∈ Z∗p and queries the 2qs + t challenges (A, R, S) ← Chall to initiate MIMForkD |CS|,1 . All Dlog queries from D are relayed to D′ . ′ Therefore, from (O, O′ ) ← MIMForkD |CS|,1 , D obtains f (0) from the first run of D, and extracts the {fj (0) = aj,0 }idj ∈CS from corrupted signers’ PoPs ((R̄j , z̄j = r̄j + hj aj,0 ) ← O, (R̄j , z̄j′ = r̄j + h′j aj,0 ) ← O′ ). Now, D′ can com  P P pute f ′ (0) = a0 = f (0) − idj ∈CS fj (0) / idi ∈HS yi . With the knowledge ′ ′ of (f ′ (0), {f ′ (idj )}idj ∈CS , {aℓ }t−1 ℓ=|CS|+1 ), D can recover f (·) and then {aℓ ← |CS|

DLG,g (Aℓ )}ℓ=1 through Lagrange interpolation. Hence, D′ solved all |CS| + 1 |CS| g and it can also solve the 2qs challenges {aℓ ← DL(Aℓ )}ℓ=0 used during Init s challenges {rℓ ← DL(Rℓ ), sℓ ← DL(Sℓ )}qℓ=1 used in PPO queries as B1 done in Lemma 3. Since the BadPPO and hash collision happen with a negligible

Title Suppressed Due to Excessive Length

27

probability, the success probability of D′ is: C 2 acc(D′ ) ≥ acc(MIMForkD |CS|,1 ) − negl ≥ acc(Fork )/8 − negl ≥ Pr[E1 ] /8q − negl

However, rewinding D for at most |I| · Tmax times making D′ issued more than 2qs Dlog queries to answer PSignO queries and so D′ does not solve OMDL. Construct B1′ from D′ . We now construct an OMDL adversary B1′ which is defined the same as D′ except that B1′ aborts any executions of C after it obtains g query. This makes sure D′ ’s all PoPs (R̄j , z̄j ) which F sent during the Init internal state recorded the required (θ, {(R̄j , z̄j , z̄j′ )}idj ∈CS ), yet not issuing any additional Dlog query during the rewinds as D′ suffered from. Therefore, B1′ has the same success probability as D′ and it runs in time: T (B1′ ) ≤ T (D′ ) ≤ |I| · Tmax · T (D) + T (q) ≤ t · Tmax · 2T (F) + T (q) 8t2 q ln(8t/acc(D′ )) · 2T (F) + T (q) acc(D′ ) 128t2 q 2 ln(64tq/ Pr[E1 ]2 ) ≤ · T (F) + T (q) Pr[E1 ]2

≤

′ 2 such that Advomdl G (B1 ) ≥ Pr[E1 ] /8q − negl.

The B3′ Adversary. As explained previously, B3′ which handles forgery under event E3 follows the same proving steps of B1′ although B3′ executes double MIMFork but not performing a mix forking. Therefore, for B3′ , the success probability of D′ is: C acc(D′ ) ≥ acc(MIMForkD |CS|,1 ) − negl ≥ acc(MIMFork1,3 )/8 − negl ≥ Pr[E3 ]/64 − negl

and B3′ runs in time: T (B3′ ) ≤ T (D′ ) ≤ |I| · Tmax · T (D) + T (q) 24q ln(24/ Pr[E3 ]) · T (F) + T (q) Pr[E3 ] 8t2 q ln(8t/acc(D′ )) 24q ln(24/ Pr[E3 ]) ≤ · T (F) + T (q) acc(D′ ) Pr[E3 ] 512t2 q ln(512t/ Pr[E3 ]) 24q ln(24/ Pr[E3 ]) ≤ · T (F) + T (q) Pr[E3 ] Pr[E3 ] 12288t2 q 2 ln(512t/ Pr[E3 ]) ln(24/ Pr[E3 ]) ≤ · T (F) + T (q) Pr[E3 ]2 ≤ t · Tmax ·

′ such that Advomdl G (B3 ) ≥ Pr[E3 ]/64 − negl.

⊔ ⊓

28

5

Will et al.

Performance Evaluations

We benchmark the proposed FROST2+ against ZCash’s FROST implementation (GitHub commit 3ffc19d) [29] on a laptop with an Intel i9-14900HX (2.20 GHz), 32 GB RAM, running Windows 11 Home Single Edition. To support our (and FROST2’s) CompPar algorithm, which differs from the original FROST design, we modified the functions binding_factor_preimages and compute_group_commitment in frost-core/src/lib.rs. We benchmark the related schemes by measuring only their signing throughput. Variants such as ROAST [26] and Olaf [11] build on FROST2 and add robustness mechanisms. When those mechanisms are not invoked, their signing cost is essentially that of FROST2. Similarly, ATS[FROST,DS] is FROST plus an additional (Schnorr) signature per pre-processing token, so it is dominated by the measured FROST cost. We therefore benchmark FROST, FROST2, msFROST2 and FROST2+, which represent the main computational differences in Table 2, using the Ed25519 curve across various predefined (t = 0.7n, n) parameter sets. For each configuration, we executed 100 rounds and recorded the average time per signature generation. Each timing experiment was conducted twice: once with pre-computations enabled and once with them disabled. When pre-computations were enabled, the timings for token verification and the preprocessing round were excluded from the signature generation time; when disabled, they were included. The full numerical results are provided in Table 3 (Appendix C), and Figure 3 visualizes the signatures-per-second for the four schemes. We also present a comparison of the algorithmic complexity which focuses on scalar multiplications, and security of our schemes against FROST and its two-round variants in Table 2. This analysis highlights the core computational differences in scalar operations, with pre-processing contributions denoted in parentheses. When pre-computations are enabled, FROST2+ achieves throughput nearly identical (within -2.3% to 1.8%) to FROST2 across all group sizes, demonstrating that its additional features come with negligible overhead. Besides, FROST2+ is × 100 (at n = 50) to 79% = 1267−708 × 100 (at always 64.7% = 3333−2024 2024 708 n = 150) faster than FROST with pre-computations, confirming the better scalability of the underlying algorithms in FROST2 and FROST2+. Specifically, at n = 200 signers, FROST2+ reaches 913 signatures/sec, marginally surpassing FROST2 (897 sig/s) and outperforming FROST (544 sig/s). ms-FROST shows a similar performance to FROST, suggesting that the hashing operation is also an important factor for signing speed. When pre-computations are disabled, FROST2+ exhibits a noticeable performance degradation compared to FROST2 (e.g., 2160 vs. 3012 sig/s at n = 50). This suggests that the optimizations in FROST2+ rely heavily on the precomputations to achieve competitive throughput, and without it the additional operations from authenticating tokens impose a measurable cost. Nonetheless, even without pre-computations, FROST2+ outperforms FROST for all tested n, demonstrating the efficiency gained from the lighter-weight CompPar algorithm.

Title Suppressed Due to Excessive Length

Signature Throughput Comparison

4000

FROST FROST2 ms-FROST FROST2+ with precomp no precomp

3500 3000

Throughput (signatures/sec)

29

2500 2000 1500 1000 500 0

50

100

Total Signers (n)

150

200

Fig. 3. Signatures generated per seconds for FROST, FROST2, ms-FROST, FROST2+. Table 2. Comparison of complexity andsecurity for the proposed FROST+ against FROST and its variants with two signing rounds. Scheme

Sign Round |pp|

FROST [22] FROST [6] FROST∗∗ [14,17] ATS[TS, DS]∗ [6] FROST2 [15] FROST2 [6] ROAST [26] Olaf [11] Arctic [23] ms-FROST [2] FaFROST [4] FROST-Mask [10] FROST2∗∗ [17] FROST3∗∗ [17] FROST2+ FROST2+$

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

2 2 2 4 2 2 2 2 1 2 2 2 2 2 4 4

smul

Agg Vf G Zp smul smul

(2) + t 2 (2) + t 3 (2) + t 2 (3) + 3t 4 (2)+1 2 (2)+1 3 (2)+1 2 (2)+1 2 (1) + t2 + t 1 (2)+1 3 (2)+1 3 (2)+1 3 (2) + 1 3 (2) + 1 2 (3) + 4t + 1 4 (3 + 4t) + 1 4

1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 2

t 0 t 0 1 0 1 1 t 0 0 1 0 1 0 0

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Security Notion

Model Corrupt

Kg

TS-UF-1 ROM Static TS-SUF-3 ROM Static adp-TS-UF AGM Adaptive TS-SUF-4 ROM Static TS-UF-1 ROM Static TS-SUF-2 ROM Static TS-SUF-2 ROM Static TS-SUF-2 ROM Static UF ROM Static adp-TS-UF-4 AGM Adaptive adp-TS-UF AGM Adaptive adp-UF ROM Adaptive adp-TS-UF AGM Adaptive adp-TS-UF AGM Adaptive TS-SUF-4 ROM Static TS-SUF-4 ROM Static

D C C C D C C D C,D C C C C C C,D C,D

Assume DS is the Schnorr signature scheme. $ with pre-computations. Maximum of t/2 adaptive corruptions if in ROM. Note: smul : scalar multiplication, G, Zp : numbers of group and field element sent per signer, Kg: key generation, C: centralized, D: decentralized, t : threshold, (num) : op. in pre-proc. round

∗

∗∗

30

Will et al.

6

Conclusion

We presented an enhanced FROST2 scheme, namely, FROST2+ with proven TSSUF-4 security under OMDL assumption in the ROM with static corruption and (de)centralized key generation settings. FROST2+ is the only ROM-based TS-SUF-4 scheme to date apart from Bellare et al.’s ATS[FROST,DS] where the primitive FROST used there is at least 64% slower than FROST2+ for a signing group with threshold t = 0.7n.

References 1. Arch Network: Arch’s signature scheme model (frost + roast). https://docs.arch. network/learn/fundamentals/arch-signature-scheme-model-frost-roast (2024), documentation page, last updated 2024; accessed Nov 18, 2025 2. Bacho, R., Chen, Y., Loss, J., Tessaro, S., Zhu, C.: Adaptively secure partially noninteractive threshold schnorr signatures in the AGM. Cryptology ePrint Archive, Paper 2025/1953 (2025), https://eprint.iacr.org/2025/1953 3. Bacho, R., Das, S., Loss, J., Ren, L.: Adaptively secure three-round threshold schnorr signatures from ddh. In: Advances in Cryptology – CRYPTO 2025: 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17–21, 2025, Proceedings, Part VI. p. 390–422. Springer-Verlag, Berlin, Heidelberg (2025). https://doi.org/10.1007/978-3-032-01887-8_13, https://doi.org/10.1007/ 978-3-032-01887-8_13 4. Baecker, R., Gerhart, P., Calsi, D.L., Russo, L., Schröder, D., Yerukhimovich, A.: Fully adaptive FROST in the algebraic group model from falsifiable assumptions. Cryptology ePrint Archive, Paper 2025/1950 (2025), https://eprint.iacr.org/2025/ 1950 5. Bagherzandi, A., Cheon, J.H., Jarecki, S.: Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma. In: Proceedings of the 15th ACM Conference on Computer and Communications Security. p. 449–458. CCS ’08, Association for Computing Machinery, New York, NY, USA (2008). https: //doi.org/10.1145/1455770.1455827, https://doi.org/10.1145/1455770.1455827 6. Bellare, M., Crites, E., Komlo, C., Maller, M., Tessaro, S., Zhu, C.: Better than advertised security for non-interactive threshold signatures. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology – CRYPTO 2022. pp. 517–550. Springer Nature Switzerland, Cham (2022) 7. Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: Proceedings of the 13th ACM Conference on Computer and Communications Security. p. 390–399. CCS ’06, Association for Computing Machinery, New York, NY, USA (2006). https://doi.org/10.1145/1180405.1180453, https://doi.org/10.1145/1180405.1180453 8. Bellare, M., Tessaro, S., Zhu, C.: Stronger security for non-interactive threshold signatures: BLS and FROST. Cryptology ePrint Archive, Paper 2022/833 (2022), https://eprint.iacr.org/2022/833 9. Brandão, L.T.A.N., Peralta, R.: NIST First Call for Multi-Party Threshold Schemes (NISTIR 8214C, draft). NIST Interagency Report (NISTIR) – Draft 8214C, National Institute of Standards and Technology (NIST) (2023), https: //csrc.nist.gov/publications/detail/nistir/8214c/draft

Title Suppressed Due to Excessive Length

31

10. Chen, Y.: Round-efficient adaptively secure threshold signatures with rewinding. IACR Communications in Cryptology 2(2) (2025). https://doi.org/10.62056/ ah893z10k 11. Chu, H., Gerhart, P., Ruffing, T., Schröder, D.: Practical schnorr threshold signatures without the algebraic group model. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology – CRYPTO 2023. pp. 743–773. Springer Nature Switzerland, Cham (2023) 12. Connolly, D., Komlo, C., Goldberg, I., Wood, C.A.: Rfc 9591 the flexible roundoptimized schnorr threshold (frost) protocol for two-round schnorr signatures (2024) 13. Cremers, C., Peltonen, A., Zhao, M.: An extended hierarchy of security notions for threshold signature schemes and automated analysis of protocols that use them. Cryptology ePrint Archive, Paper 2024/1920 (2024), https://eprint.iacr.org/2024/ 1920 14. Crites, E., Katz, J., Komlo, C., Tessaro, S., Zhu, C.: On the adaptive security of frost. In: Tauman Kalai, Y., Kamara, S.F. (eds.) Advances in Cryptology – CRYPTO 2025. pp. 480–511. Springer Nature Switzerland, Cham (2025) 15. Crites, E., Komlo, C., Maller, M.: How to prove schnorr assuming schnorr: Security of multi- and threshold signatures. Cryptology ePrint Archive, Paper 2021/1375 (2021), https://eprint.iacr.org/2021/1375 16. Crites, E., Komlo, C., Maller, M.: Fully adaptive schnorr threshold signatures. In: Advances in Cryptology – CRYPTO 2023: 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20–24, 2023, Proceedings, Part I. p. 678–709. Springer-Verlag, Berlin, Heidelberg (2023). https://doi.org/10.1007/978-3-031-38557-5_22, https://doi.org/10.1007/ 978-3-031-38557-5_22 17. Crites, E., Komlo, C., Maller, M.: On the adaptive security of key-unique threshold signatures. Cryptology ePrint Archive, Paper 2025/943 (2025), https://eprint.iacr. org/2025/943 18. Crites, E., Stewart, A.: A plausible attack on the adaptive security of threshold schnorr signatures. In: Tauman Kalai, Y., Kamara, S.F. (eds.) Advances in Cryptology – CRYPTO 2025. pp. 457–479. Springer Nature Switzerland, Cham (2025) 19. Gennaro, R., Leigh, D., Sundaram, R., Yerazunis, W.: Batching schnorr identification scheme with applications to privacy-preserving authorization and lowbandwidth communication devices. In: Lee, P.J. (ed.) Advances in Cryptology – ASIACRYPT 2004 (Lecture Notes in Computer Science, vol. 3329). Springer, Berlin, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30539-2_20 20. Harman, S., Shishmarev, M., Nash, T., Lennon, D., Janse van Vuuren, S.: Chainflip protocol whitepaper. Tech. rep., Auxilio Ventures (2022), https://www.auxilioventures.com/wp-content/uploads/2022/08/ Chainflip-Whitepaper-May-2020.pdf 21. Kiltz, E., Masny, D., Pan, J.: Optimal security proofs for signatures from identification schemes. In: Robshaw, M., Katz, J. (eds.) Advances in Cryptology – CRYPTO 2016. pp. 33–61. Springer Berlin Heidelberg, Berlin, Heidelberg (2016) 22. Komlo, C., Goldberg, I.: Frost: Flexible round-optimized schnorr threshold signatures. In: Dunkelman, O., Jacobson, Jr., M.J., O’Flynn, C. (eds.) Selected Areas in Cryptography. pp. 34–65. Springer International Publishing, Cham (2021) 23. Komlo, C., Goldberg, I.: Arctic: Lightweight and stateless threshold schnorr signatures. In: Jager, T., Pan, J. (eds.) Public-Key Cryptography – PKC 2025. pp. 234–267. Springer Nature Switzerland, Cham (2025)

32

Will et al.

24. Mccorry, P., Bakshi, S., Dembo, A., Miller, A.: sbtc: Design of a trustless twoway peg for bitcoin. Tech. rep., Trustless Computing Foundation (2023), https: //sbtc.tech/sbtc.pdf 25. Niot, G., Reichle, M., Takemure, K.: Adaptively-secure three-round threshold schnorr from DL. Cryptology ePrint Archive, Paper 2025/1941 (2025), https: //eprint.iacr.org/2025/1941 26. Ruffing, T., Ronge, V., Jin, E., Schneider-Bensch, J., Schröder, D.: Roast: Robust asynchronous schnorr threshold signatures. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. p. 2551–2564. CCS ’22, Association for Computing Machinery, New York, NY, USA (2022). https: //doi.org/10.1145/3548606.3560583, https://doi.org/10.1145/3548606.3560583 27. Safe Research: safe-frost. https://github.com/safe-research/safe-frost (2024), gitHub repository; accessed Nov 18, 2025 28. Schnorr, C.P.: Efficient signature generation by smart cards. Journal of Cryptology 4, 161–174 (1991). https://doi.org/10.1007/BF00196725 29. Zcash Foundation: Speeding up frost with multi-scalar multiplication, https://zfnd. org/speeding-up-frost-with-multi-scalar-multiplication/

A

Attacks on FROST2

A.1

Types of Forgeries

Referring to the security model in Section 2.4, we recall the conditions under which a (strong) forgery can be achieved in a threshold signature scheme that is also an echo scheme [8,6] (e.g., FROST2) in Figure 4. A.2

TS-UF-3 Attack

In Bellare et al.’s work [8,6], they provide a security proof of TS-SUF-2 and also a TS-UF-3 attack for FROST2. This indicates that the best possible security level FROST2 can achieve is only TS-SUF-2. We recall Bellare et al.’s TS-UF-3 attack in the setting below: – Total signers are {P1 , P2 , P3 , P4 }. – Signers {P3 , P4 } corrupted. – A signing request on signer set lr.S = {1, 2, 3} for a message lr.msg = M . – The pre-processing token (R1 , S1 ), (R2 , S2 ) are known to the corrupted signers before they generate theirs. – First signer’s partial signature z1 = r1 + ds1 + c∆1,S (0)x1 can be obtained. P – Expected combined signature is z = dlog(R̃)+cx = i∈S ri +dsi +c∆i,S (0)xi The attack procedure is as follows: 1. P3 generates its pre-processing token as ∆ (0) 1,S ′ −1 ∆ (0)

R3 = R1 1,S

∆ (0) 1,S ′ −1 ∆ (0)

R2−1 , S3 = S1 1,S

S2−1 .

Title Suppressed Due to Excessive Length

33

SVf(X̃, lr, σ) = true

|S2 (lr)| < t − |CS| (TS-SUF-2)

|S2 (lr)| ≥ t − |CS|

S2 (lr) = S4 (lr)

S3 (lr) ⊂ S4 (lr) = S2 (lr) (TS-SUF-3)

S2 (lr) ⊂ S4 (lr)

S3 (lr) ⊂ S2 (lr)

S2 (lr) = S3 (lr)

S2 (lr) ⊂ S3 (lr)

S3 (lr) ⊂ S2 (lr) ⊂ S4 (lr) (TS-SUF-3)

S2 (lr) = S3 (lr) ⊂ S4 (lr) (TS-SUF-4)

S2 (lr) ⊂ S3 (lr) = S4 (lr) (TS-SUF-3)

Fig. 4. Decision tree for queries comparisons and forgery outcomes.

marks the

algorithmically prohibited forgery types (i.e., st.mapPP(ppi ) ̸=⊥ enforced in PS) while marks the possible forgery types.

where S ′ = {1, 3, 4}. The resulting group pre-processing token will be: ∆

(0) 1,S ′ ∆ (0)

R̃ = R1 1,S

∆

′ (0)

d ∆1,S (0)

S1

1,S

=

Y

Ri Sid

i∈S ∆

′ (0)

∆

′ (0)

+ ds1 ∆1,S and d = Hnon (X̃, lr). where dlog(R̃) = r1 ∆1,S 1,S (0) 1,S (0) ∆

′ (0)

∆

′ (0)

∆

′ (0)

+ ds1 ∆1,S + c∆1,S ′ (0)x1 = ∆1,S z1 2. P3 computes z1′ = r1 ∆1,S 1,S (0) 1,S (0) 1,S (0) 3. P3 and P4 forge a valid combined signature for M under lr.S as z ′ = dlog(R̃) + cx = z1′ + c∆3,S ′ (0)x3 + c∆4,S ′ (0)x4 . This is a valid TS-UF-3 attack because S2 = {1} but unequal to S3 = {1, 2}, i.e., S2 (lr) ⊂ S3 (lr) = S4 (lr) in Figure 4. We note that this attack does not work on our schemes because the attacker’s pre-processing token (R3 , S3 ) is a combination of the honest signers’ pre-processing token whose discrete logarithms are not known. Consequently, a valid authentication transcript (u, V ) for (R3 , S3 ) cannot be generated and the honest signers abort during PSignO.

S2 (lr) ⊂ S3 (lr) ⊂ S4 (lr) (TS-SUF-3)

34

Will et al.

A.3

TS-UF-4 Attack

In Bellare et al.’s work [8,6], they demonstrate a TS-UF-4 attack for FROST but not FROST2. Here, we mount the attack on FROST2 as follows: – Total signers are {P5 , P10 , P11 , P15 , P20 }. – Signers {P5 , P10 } corrupted. – A signing request on signer set lr.S = {11, 15, 20} for a message lr.msg = M . – The pre-processing token lr.PP = {(R11 , S11 ), (R15 = g r15 , S15 = g s15 ), (R20 = g r20 , S20 = g s20 )}) and r15 , s15 , r20 , s20 ∈ Z∗p are known to the corrupted signers before they generate theirs. – First signer’s partial signature z11 = r11 + d11 s11 + c∆11,S (0)x11 can be obtained. P – Expected combined signature is z = dlog(R̃)+cx = i∈S ri +dsi +c∆i,S (0)xi The attack procedure is as follows: 1. Let S ′ = {5, 10, 11}, the Lagrange coefficients are the same for: ∆11,lr.S =

25 5 · 10 15 · 20 = = = ∆11,S ′ . (15 − 11)(20 − 11) 3 (5 − 11)(10 − 11)

The resulting group pre-processing token will be: d r15 +ds15 +r20 +ds20 R̃ = R11 S11 g =

Y

Ri Sid

i∈S

where dlog(R̃) = r11 + ds11 + r15 + ds15 + r20 + ds20 and d = Hnon (X̃, lr). 2. P5 and P10 forge a valid combined signature for M under lr.S as z ′ = dlog(R̃)+cx = z11 +r15 +ds15 +r20 +ds20 +c∆5,S ′ (0)x5 +c∆10,S ′ (0)x10 . This is a valid TS-UF-4 attack because S2 = {11} = S3 but unequal to S4 = {11, 15, 20}, i.e., S2 (lr) = S3 (lr) ⊂ S4 (lr) in Figure 4. We note that this attack does not work on our schemes for the similar reason in Section A.2. Although the attacker knows the discrete logarithms for the pre-processing tokens (R15 , S15 ), (R20 , S20 ), it does not know the honest signers’ signing key shares which are required to generate the authentication transcripts (u15 , V15 ), (u20 , V20 ) for the tokens. Therefore, the honest signer will abort during partial signing because of invalid (u15 , V15 ), (u20 , V20 ).

B

PedPoP

We recall PedPoP key generation [22,6] in Figure 5.

C

Detailed Benchmark Results

The detailed benchmark data is in Table 3.

Title Suppressed Due to Excessive Length

35

PedPop.Kg(par, t, ns) $

1. Every signer idi chooses a polynomial fi (Z) ← − Zt−1 p : fi (Z) = ai,0 + ai,1 Z + · · · + ai,t−1 Z t−1 and computes Ai,k = g ai,k for k = 0, . . . , t−1. Let xi = ai,0 and Xi,0 = Ai,0 . Every idi selects $

r̄i ← − Zp and sets R̄i ← g r̄i to compute z̄i ← r̄i + hi xi where hi ← Hkg (idi , Xi,0 , Xi,0 , R̄i ). They broadcast ((R̄i , z̄i ), Ci ) where the Ci = (Ai,0 , . . . , Ai,t−1 ) is a commitment vector. 2. Given ((R̄j , z̄j ), Cj ) from each other signer idj , every signer computes: hj ← Hkg (idj , Aj,0 , Aj,0 , R̄j ) and verifies whether:

h

j R̄j Aj,0 = g z̄j .

If any checks fail, they disqualify the corresponding signer and continue to the next step. 3. Every idi computes secret shares x̄i,j = fi (idj ) and privately sends x̄i,j to signer idj for j = 1, . . . , ns. 4. Each signer idj verifies the shares they received from other signers by checking: g x̄i,j =

t−1 Y

idk

Ai,kj

k=0

If the check fails for some index i, idj broadcasts a complaint against idi . 5. For each complaint by signer idj against idi , idi broadcasts the share x̄i,j . If any revealed share fails to satisfy the verification equation, or if idi does not broadcast a share for a complaining signer, then idi is disqualified and their shares are set to 0. 6. The secret share for every idj is then: x̄j =

ns X

x̄i,j .

i=1

7. If Xi,0 = Xj,0 for any i ̸= j, then abort. Else, output the joint public key as: X̃ =

ns Y

Xi,0

i=1

Fig. 5. The PedPoP algorithm [22,6].

36

Will et al.

Table 3. Performance comparison of threshold signature schemes (excluding DKG setup). (t, n) denotes the threshold and number of signers. Scheme

Pre-comp

✓ FROST ✗

✓ FROST2 ✗

✓ ms-FROST ✗

✓ FROST2+ ✗

(t, n)

Signature Gen. (ms) Throughput (sig/sec)

Security

(35, 50) (70, 100) (105, 150) (140, 200) (35, 50) (70, 100) (105, 150) (140, 200)

0.494 0.941 1.412 1.838 0.533 0.979 1.449 1.879

2,024 1,062 708 544 1,876 1,021 690 532

TS-SUF-3

(35, 50) (70, 100) (105, 150) (140, 200) (35, 50) (70, 100) (105, 150) (140, 200)

0.293 0.537 0.789 1.115 0.332 0.574 0.826 1.155

3,412 1,862 1,267 897 3,012 1,742 1,211 866

TS-SUF-2

(35,50) (70,100) (105,150) (140,200) (35,50) (70,100) (105,150) (140,200)

0.481 0.984 1.458 1.914 0.519 1.025 1.498 1.954

2079 1016 689 522 1928 976 667 512

adp-TS-UF-4

(35, 50) (70, 100) (105, 150) (140, 200) (35, 50) (70, 100) (105, 150) (140, 200)

0.300 0.542 0.789 1.095 0.463 0.714 0.961 1.245

3,333 1,845 1,267 913 2,160 1,401 1,041 803

TS-SUF-4

Related documents

• From TS-SUF-2 to TS-SUF-4: Practical Security Enhancements for FROST2 Threshold Signatures#1187119
• CBOR Object Signing and Encryption (COSE): Hash Algorithms#502494
• Trustless Trust and Antitrust: A Synthesis#732348
• The doctrine of signatures#1193592
• Blockchain-Enabled Secure Logging for Fiscal Electronic Mechanisms: Evaluation of the Greek eSEND and myDATA Tax Systems#927651