Our technical report is currently available.
Unlike signatures in a single-party setting, threshold signatures require cooperation among a threshold number of signers each holding a share of a common private key. Consequently, generating signatures in a threshold setting imposes overhead due to network rounds among signers, proving costly when secret shares are stored on network-limited devices or when coordination occurs over unreliable networks. In this work, we present FROST, a Flexible Round-Optimized Schnorr Threshold signature scheme that improves upon the state of the art to reduce network overhead during signing operations. We introduce three variants of signing operations in FROST. We begin with two variants that are limited in concurrency but efficient in per-user computation; the first reduces the number of messages participants send and receive to two in total, and the second variant is a further optimization to a single-round signing protocol with a batched non-interactive pre-processing stage. We next present a third variant that does not restrict concurrency of signing operations but is more costly in per-signature computation. Across all variants, FROST achieves its efficiency improvements by allowing the protocol to abort in the presence of a misbehaving participant (who is then identified and excluded from future operations)—a reasonable model for practical deployment scenarios. We present two use cases of threshold signatures demonstrating the practicality of this tradeoff to real-world implementations, and prove FROST is as secure as Schnorr's signature scheme in a single-party setting.