Research
From TS-SUF-2 to TS-SUF-4: Practical Security Enhancements for FROST2 Threshold Signatures
FROST2 is an efficient two-round threshold Schnorr signature scheme, but Bellare et al. (CRYPTO 2022) showed that under the one-more discrete logarithm assumption, with static corruption and…

- arXiv
- 2610.02805
- Published
- 2026-10-02
- Authors
- Will Wang, Syh-Yuan Tan, Ryan Chow, Chanson Chan, Martin Zhao
AI summary
Overview
Research area: Cryptographic protocol security — specifically threshold Schnorr signature schemes (FROST and its variants) used to secure digital assets in blockchain and distributed systems, analysed within the TS-(S)UF-i provable-security framework of Bellare et al.
Technical level: Advanced. The paper is written for readers comfortable with discrete-logarithm assumptions, random-oracle-model reductions, forking lemmas, and threshold secret sharing; the protocols themselves would be readable at an intermediate level, but the security proofs are not.
Scope (one sentence): The paper defines and proves a modified FROST2 protocol, called FROST2+, that lifts FROST2 from TS-SUF-2 to the top TS-SUF-4 security level under the same one-more discrete logarithm assumption, in both centralized and distributed key generation settings, without losing practical efficiency.
What This Paper Is About
FROST2 is an efficient two-round threshold Schnorr signature scheme, but Bellare et al. (CRYPTO 2022) showed that under the one-more discrete logarithm assumption, with static corruption and centralized key generation, it only reaches TS-SUF-2 — the second level of a five-level hierarchy — because of an attack on its pre-processing token mechanism (the TS-UF-3 attack), which resembles the rogue public key attack on multi-signatures. That attack lets an adversary forge under an unauthorized signer set without obtaining the partial signatures of all honest signers. The authors ask whether FROST2 can be repaired to reach the same TS-SUF-3 and TS-SUF-4 levels that FROST reaches, and answer yes with FROST2+, which authenticates pre-processing tokens using only material already present in the protocol.
Key Contributions
-
A new scheme, FROST2+. An enhanced FROST2 variant that adds lightweight pre-processing token verification, mitigating both TS-UF-3 and TS-UF-4 attacks while preserving FROST2's two-round structure and efficiency.
-
TS-SUF-4 security proof in the CKG setting. FROST2+ is proven TS-SUF-4 secure under the OMDL assumption in the random oracle model, with static corruption and centralized key generation — the same assumptions used for the original FROST2 analysis.
-
Security carried over to DKG. The authors show the security levels are maintained when key generation moves from centralized key generation to a distributed key generation protocol, instantiated with PedPoP.
-
Efficiency engineering and benchmarking. Token verification is decoupled from the signing message, enabling pre-verification to speed up partial signing and per-signer batch verification across multiple signing sessions. Benchmarks using ZCash's FROST library show FROST2+ performance comparable to FROST2 and about 64–79% faster than FROST when precomputation is enabled.
-
A refined security model. The paper adopts Cremers et al.'s strengthened trivial-forgery predicate for
tf_4— requiring S₂(lr) = S₃(lr) = S₄(lr) rather than only S₂(lr) = S₄(lr) — to restore downward implications (TS-(S)UF-4 implying TS-(S)UF-3) across the hierarchy without weakening lower levels, at the level Cremers et al. call SiGu-4:aLRhPP.
Main Findings
- FROST2 is capped at TS-SUF-2. Per Bellare et al. (CRYPTO 2022), FROST2's weakness in its pre-processing token mechanism permits a TS-UF-3 forgery, so it is not eligible for the upgrade path that lifts FROST to TS-SUF-4.
- FROST2+ reaches TS-SUF-4. The added token verification closes the TS-UF-3 and TS-UF-4 vulnerabilities under OMDL in the ROM, with static corruption and centralized key generation.
- No extra key material required. Unlike Bellare et al.'s ATS[TS, DS] transformation, which requires every signer to generate and manage an additional digital signature key-pair, FROST2+ authenticates tokens using only the signing key share and the secret exponents already in the pre-processing token (R, S).
- DKG compatibility. Security holds when initialized with PedPoP distributed key generation, not just centralized key generation.
- Token verification is cheap and batchable. Because the verification values do not depend on the signing message, pre-verification can be done ahead of time and batched per signer across sessions, preserving FROST-style offline pre-processing.
- Benchmark result. Against ZCash's FROST library, FROST2+ is comparable to FROST2 and about 64–79% faster than FROST when precomputation is enabled. (Absolute timings, hardware, group choice and the concrete benchmark parameters are not available in the supplied text.)
- Prior work falls short of the target. ROAST adds token aggregation and signature share verification with a reduction to original FROST2; Olaf combines ROAST with SimplPedPoP and proves only TS-SUF-2; FROST-Mask, ms-FROST and FaFROST target adaptive security via masking rather than the TS-SUF-3/TS-SUF-4 levels in this static-corruption ROM setting.
Methodology in Plain English
The starting point is a known attack. In FROST-style "echo" schemes, an honest signer only issues a partial signature if the leader's request contains that signer's own honestly generated pre-processing token. If tokens carry no proof of origin, an adversary can substitute or manipulate them and assemble a valid signature for a signer set it should not control.
The fix is to make each token self-authenticating. When a signer produces a token, it picks three random secret exponents, publishes the corresponding group elements alongside a value that ties those elements, the signer's public key share, and the joint public key together through a hash, and derives a single checkable value from the signer's secret key share and those random exponents (the paper writes this as u = v + sk·e + r·e² + s·e³ with e = H_pp(X̃, X_i, R, S, V)). Anyone can check that value; only the holder of the key share could have produced it. The signer keeps the random exponents in its state so it can later answer challenges with the real partial signature.
For the proof, the authors cannot rely on the standard forking lemma without paying a large security loss, so they use two tools: a generalized forking lemma extension (from Bellare et al.) that reduces the loss from 1/q to 1/|SS| when the adversary's output index is confined to a known set, and a new generalized multi-instance multi-forking lemma. The latter extends Bagherzandi et al.'s multi-instance forking lemma to allow multiple forks per instance, so the reduction can extract several discrete-logarithm solutions from one adversary run; its stated accepting probability is at least ε̂/8. With those, the OMDL reduction goes through and yields TS-SUF-4.
Why This Matters
Impact on research. The paper shows the TS-(S)UF hierarchy is not just a classification exercise: a concrete, widely deployed-style protocol can be moved two levels up with a small, self-contained protocol change rather than an add-on signature layer. It also demonstrates that the "FROST is stuck below FROST2's successors" impression is not fundamental, and it contributes a strengthened forking tool (multiple forks per instance) that other threshold-scheme proofs can reuse.
Real-world applications:
- Threshold custody of blockchain assets, where a quorum of signers must authorize a transfer without any single party holding the full key.
- Distributed validator and node-key management in proof-of-stake networks, where pre-processing tokens are generated offline for throughput.
- Cross-chain bridges and MPC-backed wallets that rely on leaderless, high-throughput signing sessions with offline token preparation.
- Accountability-sensitive deployments: TS-SUF-4 prevents an honest signer from being wrongfully framed for a forgery, which matters for slashing logic and dispute resolution.
Industry relevance. FROST is undergoing IETF standardization and NIST has issued a call for contributions on threshold multi-party schemes, so any change that raises FROST2's security level without a meaningful performance cost is directly relevant to implementers. The benchmark against ZCash's FROST library and the roughly 64–79% speed advantage over FROST under precomputation give engineering teams a concrete reason to consider the variant.
Future Directions
- Independent benchmarking and implementation hardening. The reported comparison uses one library (ZCash's FROST); reproducing the 64–79% figure across other implementations, group choices and network conditions is left open, and the paper's own parameters are not visible in the supplied text.
- Reconciling with the adaptive-security line of work. The proof is in the static-corruption model, whereas FROST-Mask, ms-FROST and FaFROST target adaptive security (some under the AGM, some under the ROM). Whether FROST2+'s token authentication composes with masking, and whether it can reach adaptive security with up to t/2 corruptions like the cited AOMDL/ROM results, is a natural open question.
- Transfer to sibling schemes. Applying the same token-authentication idea to FROST3, ROAST, Olaf and other echo schemes, and checking whether the strengthened
tf_4predicate changes their proofs, is unaddressed. - Standardization and parameter guidance. How the extra token fields (R, S, u, V) and the pre-verification step should be specified in an IETF-style document, and what concrete group sizes and batching limits to recommend, remains to be settled.
Target Audience
Protocol designers and cryptographic engineers implementing threshold Schnorr signing for blockchain custody, validators or bridges; applied cryptographers working on threshold signature security models and forking-lemma reductions; and standards contributors following IETF FROST and NIST threshold-scheme activity. Readers without a background in provable security will find the constructions readable but should treat the security analysis (Sections 2.4–2.6 and 4) as specialist material.
Authors’ 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…
The full abstract on arXiv