PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Will Wang, Syh-Yuan Tan, Ryan Chow, Chanson Chan, Martin Zhao

arXiv:2610.02805v1cs.CR

TL;DR

FROST2 achieves only TS-SUF-2 security in the centralized-key setting, with its pre-processing-token mechanism vulnerable to TS-UF-3 attacks. The paper introduces FROST2+ and proves TS-SUF-4 security; benchmarks report performance close to FROST2 and substantially faster than FROST when pre-computation is enabled.

  • Problem

    FROST2 achieves only TS-SUF-2 security under centralized key generation, with its pre-processing-token mechanism vulnerable to TS-UF-3 attacks.

    Source: §1 · pp. 2–3

  • Method

    FROST2+ uses a direct proof for the remaining TS-SUF-4 forgery case rather than the ATS transformation, which adds a signature key pair and signing costs.

    Source: §4 · p. 21

  • Results

    With pre-computations enabled, FROST2+ throughput is within -2.3% to 1.8% of FROST2 across group sizes and is 64.7% to 79% faster than FROST.

    Source: §5 · p. 28

  • Takeaways & Limitations

    FROST2+ is reported as the only ROM-based TS-SUF-4 scheme apart from ATS[FROST,DS], whose FROST primitive is at least 64% slower at threshold t = 0.7n.

    Source: §6 · p. 30

    In the distributed-key proof, rewinding D beyond |I| · Tmax makes D′ issue more than 2q_s Dlog queries, so D′ does not solve OMDL.

    Source: §4.1 · p. 27

Abstract

from arXiv · show

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 TS-SUF-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.

1 Introduction

FROST2 offers an efficient, two-round threshold-signature design, but its TS-SUF-2 security leaves important token-corruption attacks uncovered. The paper proposes FROST2+ to raise security to TS-SUF-4 while retaining FROST2’s efficiency and supporting distributed key generation.

1 Introduction

  • FROST2 reaches only TS-SUF-2 under centralized key generation, in part because token corruption enables TS-UF-3 forgeries.The attack exploits FROST2’s pre-processing-token mechanism and can forge under an unauthorized signer set without all honest partial signatures.Source: §1 · pp. 2–3
  • The security goals matter in practice because TS-SUF-3 protects against premature token leakage, while TS-SUF-4 prevents wrongful framing of an honest signer.The paper investigates these levels for FROST2, which improves efficiency over FROST and reduces communication rounds compared with several later three-round variants.Source: §1 · p. 3

1.1 Our Contributions

  • FROST2+ raises FROST2 to TS-SUF-4 security while preserving its two-round structure.The paper presents TS-SUF-4 as the highest tier in Bellare et al.’s hierarchical framework.Source: §1.1 · p. 3
  • FROST2+ authenticates pre-processing tokens using existing signing-key shares and token exponents rather than requiring an additional signature key pair.This contrasts with the ATS[TS, DS] transformation, which requires each signer to generate and manage an additional digital-signature key pair.Source: §1.1 · pp. 3–4
  • The authors extend the security result to PedPoP distributed key generation and describe token pre-verification that can be batched across signing sessions.Because verification is not bound to the signing message, it can be performed before partial signing while retaining FROST-style offline pre-processing.Source: §1.1 · p. 4
  • FROST2+ matches FROST2’s performance and is more efficient than FROST, while providing stronger security.The authors report comparable efficiency to FROST2 and better efficiency than FROST in the performance evaluation.Source: §1.1 · p. 4

2 Preliminaries

The preliminaries establish the OMDL assumption and the threshold-signature framework used to analyze security. They also strengthen the TS-SUF-4 forgery condition and introduce forking lemmas that support the security analysis.

2.1 One-More Discrete Logarithm (OMDL) Assumption

  • The OMDL assumption limits an adversary to fewer discrete-log queries than challenge elements while requiring it to recover discrete logs for challenge elements.The definition considers at most q−1 Dlog queries for q challenge elements.Source: §2.1 · p. 4

2.2 Lagrange Coefficient

  • A degree-(t−1) polynomial is reconstructed from t signer-coordinate and share pairs, with Lagrange coefficients defined over the signer set.The supplied passages identify the polynomial values as f(x_i)=s_i and define the coefficient using elements of S.Source: §2.2 · p. 5

2.3 Threshold Signature Scheme

  • The threshold-signature model comprises Setup, key generation, pre-processing, request generation, partial signing, aggregation, and verification algorithms.The model adopts Bellare et al.’s scheme definition with a Setup algorithm and adjusted algorithm inputs.Source: §2.3 · p. 5

2.4 Security Model

  • The model strengthens tf4 to require S2(lr)=S3(lr)=S4(lr), restoring the TS-(S)UF-4-to-3 implication without changing trivial forgeries for echo schemes with standard token checks.The change makes all honest signers in lr.S respond using honestly generated pre-processing tokens; the authors say the original and strengthened tf4 coincide for ATS[TS,DS].Source: §2.4 · pp. 6–8, Table 1 · p. 6

2.5 Generalized Forking Lemma Extension

  • The generalized forking lemma extension tightens the stated security loss from 1/q to 1/|SS| when the output index is restricted to SS.The extension is presented as a refinement of the generalized forking lemma [7].Source: §2.5 · p. 8

2.6 Generalized Multi-Instance Multi-Forking Lemma

  • The generalized multi-instance multi-forking lemma extends prior work to allow multiple forks per instance, changing each local instance’s success count from 1 to n.Its statement is average-case over parameters generated by GrGen, in the style of the original lemma.Source: §2.6 · p. 8
  • The associated algorithm locally rewinds each target occurrence until it collects n additional outputs with distinct responses at that occurrence.The new responses are also distinct from the original response.Source: §2.6 · pp. 9–10

3 Our Constructions

FROST2+ adds authentication checks to FROST2 while reusing existing signing material. Its pre-computation and batch-verification options preserve the stated security level, with a reduction-time trade-off for batching.

3 Our Constructions

  • FROST2+ reuses the existing signing key share and token secret exponents instead of requiring each signer to manage an extra digital-signature key pair.The SPP broadcasts the pre-processing token together with a short authentication transcript, which is verified during PS; a failed peer verification causes the signer to abort.Source: §3 · p. 11

3.1 Pre-Computations

  • In the leaderless approach, signers can collect and verify tokens before partial signing, improving runtime without compromising security.For batch verification of multiple tokens, the authentication transcript size remains constant.Source: §3.1 · p. 13, §3.2 · p. 13

3.2 Batch Verification

  • Batch verification does not affect TS-SUF-4 security, but the reduction’s runtime is linear in the number n of tokens.The authors note that the Multi-Instance Reset Lemma [21] may be explored if a tighter reduction is desired.Source: §3.2 · p. 13

4 Security Analysis

The section establishes FROST2+’s TS-SUF-4 security under OMDL by reducing forgery cases to OMDL, beginning with centralized key generation and extending the analysis to PedPoP-based distributed key generation. The proofs handle the relevant cases through event-based reductions and simulations of signer states.

4 Security Analysis

  • FROST2+ forgery success is bounded by the probabilities of E1, E2, and E3, with each event handled by an OMDL adversary.The proofs are presented first for centralized key generation; Section 4.1 extends them to decentralized key generation.Source: §4 · pp. 13–14
  • 2qs+t Chall queries and q random-oracle queries suffice for the E1 reduction B1, which addresses forgeries containing at least one forged partial signature.B1 runs in roughly twice the forger’s time, plus the time for exponentiations and group operations.Source: §4 · p. 14
  • For E2, the proof embeds OMDL challenges in honestly generated tokens and uses a mix-forking-inspired approach to recover transcript secrets and solve a challenge.E2 concerns the case S2(lr) ⊂ S3(lr), where at least one honestly generated token corresponds to a forged partial signature; B2 uses at most 2qs Chall queries and q random-oracle queries.Source: §4 · p. 18
  • After E1 and E2, the direct E3 proof covers forgeries with S2(lr) = S3(lr) ⊂ S4(lr), completing the TS-SUF-4 analysis without an extra DS key pair.The alternative ATS transformation would require an extra DS key pair, longer preprocessing information, and slower signing.Source: §4 · pp. 21, 23
  • For E3, an OMDL adversary B3 uses at most 2qs + t challenge queries and q random-oracle queries to reduce the remaining leader-request forgery case.The proof uses the equivalence between a TS-SUF-4 forger and a leader-request forger when the forgery includes a forged preprocessing token.Source: §4 · pp. 21, 23

4.1 Security with Distributed Key Generation

  • The token amendments are orthogonal to key generation, and the paper demonstrates TS-SUF-3 security in the random-oracle model when FROST2+ uses PedPoP.The DKG proof adapts the oracle simulation to PedPoP; for the E3 case it uses double forking to extract the signing key and fork proof-of-possession transcripts.Source: §4.1 · pp. 24–25
  • Theorem 3 establishes a TS-SUF-4 security bound for FROST2+ instantiated with PedPoP by reducing the E1, E2, and E3 cases to OMDL.The scheme’s token-generation and verification changes use existing key shares and token exponents, not DKG commitment or proof-of-possession messages.Source: §4.1 · pp. 24–25
  • B′1 and B′3 make at most 2qs+t Chall queries, while B′2 makes at most 2qs.Source: §4.1 · p. 25
  • The DKG wrapper defines values for honest signers and handles PedPoP hash queries; the resulting signer states are indistinguishable from those in centralized key generation.The analysis says the post-key-generation oracle simulations are therefore identical to those in Lemma 3.Source: §4.1 · pp. 25–26
  • Rewinding D′ can require too many discrete-log queries to solve OMDL, so B′1 aborts after receiving the corrupted signers’ PoPs and preserves D′’s success probability without those extra queries.The abort ensures the recorded state contains the required PoP values while avoiding additional discrete-log queries during rewinds.Source: §4.1 · p. 27
  • For event E3, B′3 follows B′1’s proving steps but uses double MIMFork without mix forking.The passage introduces a separate success-probability analysis for D′ in this case.Source: §4.1 · p. 27

5 Performance Evaluations

With pre-computations enabled, FROST2+ has throughput nearly identical to FROST2 and is faster than FROST; without pre-computations, it incurs a throughput penalty relative to FROST2 but remains faster than FROST for tested signer counts.

5 Performance Evaluations

  • The evaluation measures signing throughput over Ed25519 configurations with t=0.7n, averaging 100 rounds per configuration with pre-computations both enabled and disabled.It also presents a scalar-multiplication complexity and security comparison in Table 2.Source: §5 · p. 28, Table 2 · p. 29
  • 64.7% (n=50) to 79% (n=150) faster than FROST with pre-computations, while Fig. 3 compares signatures per second across four schemes.At n=200, FROST2+ reaches 913 signatures/sec, versus 897 for FROST2 and 544 for FROST.Source: §5 · p. 28, Figure 3 · p. 29
  • Within -2.3% to 1.8%, FROST2+ throughput is nearly identical to FROST2 across group sizes when pre-computations are enabled.The benchmark excludes token-verification and pre-processing-round timings when pre-computations are enabled.Source: §5 · p. 28
  • 2160 vs. 3012 sig/s at n=50: without pre-computations, FROST2+ is slower than FROST2 but still outperforms FROST for every tested n.The comparison attributes the remaining advantage over FROST to the lighter-weight CompPar algorithm.Source: §5 · p. 28

6 Conclusion

The conclusion presents FROST2+ as an enhanced FROST2 scheme with proven TS-SUF-4 security under the OMDL assumption in the ROM, with static corruption and centralized or distributed key generation.

6 Conclusion

  • FROST2+ achieves proven TS-SUF-4 security under OMDL in the ROM with static corruption and centralized or distributed key generation.Source: §6 · p. 30

A.1 Types of Forgeries

Figure 4 recalls conditions for strong forgeries in threshold signature schemes that are echo schemes, including FROST2.

A.1 Types of Forgeries

  • Figure 4 presents the conditions under which a strong forgery can be achieved in an echo threshold signature scheme such as FROST2.Source: §A.1 · p. 32

A.2 TS-UF-3 Attack

The section recalls Bellare et al.’s TS-UF-3 attack on FROST2 and explains why the attack does not work on the proposed schemes.

A.2 TS-UF-3 Attack

  • Bellare et al.’s attack shows that FROST2’s best possible security level is TS-SUF-2, following its TS-UF-3 attack.Source: §A.2 · p. 32
  • In the attack, corrupted signers know honest signers’ pre-processing tokens before generating theirs and obtain a first signer’s partial signature.Source: §A.2 · p. 32
  • The attack is valid because S2={1} is a proper subset of S3=S4={1,2}; the proposed schemes block it because the attacker cannot generate a valid authentication transcript for the combined token.Honest signers therefore abort during partial signing.Source: §A.2 · p. 33

A.3 TS-UF-4 Attack

The section presents a TS-UF-4 attack against FROST2 and explains why the attack does not work on the proposed schemes.

A.3 TS-UF-4 Attack

  • The example uses corrupted signers P5 and P10 to target a signing request by P11, P15, and P20 for message M.The request's pre-processing-token details and subsequent attack steps are described in the supplied passage fragments.Source: §A.3 · p. 34
  • The attack is a valid TS-UF-4 attack because S2(lr) = S3(lr) ⊂ S4(lr).Here S2 = S3 = {11}, while S4 = {11, 15, 20}.Source: §A.3 · p. 34
  • The attack does not work on the proposed schemes because the attacker lacks honest signers’ key shares needed for valid token-authentication transcripts, causing aborts.The attacker may know the discrete logarithms of tokens for P15 and P20, but not the signing-key shares needed to generate (u15, V15) and (u20, V20).Source: §A.3 · p. 34

B PedPoP

The section recalls PedPoP key generation and points to Figure 5 for the algorithm.

B PedPoP

  • PedPoP key generation is recalled in Figure 5.The supplied passage identifies the figure as the PedPoP algorithm.Source: B PedPoP · p. 34

C Detailed Benchmark Results

The section directs readers to Table 3 for detailed benchmark data; the table excludes DKG setup and defines its (t, n) parameters.

C Detailed Benchmark Results

Loading 2610.02805v1…