FROST: Flexible Round-Optimized Schnorr Threshold Signatures

Abstract

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 reduces network overhead during signing operations while employing a novel technique to protect against forgery attacks applicable to similar schemes in the literature. FROST improves upon the state of the art in Schnorr threshold signature protocols, as it can safely perform signing operations in a single round without limiting concurrency of signing operations, yet allows for true threshold signing, as only a threshold t out of n possible participants are required for signing operations, such that $t\le n$. FROST can be used as either a two-round protocol, or optimized to a single-round signing protocol with a pre-processing stage. FROST achieves its efficiency improvements in part 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 proofs of security demonstrating that FROST is secure against chosen-message attacks assuming the discrete logarithm problem is hard and the adversary controls fewer participants than the threshold.

1 Introduction

Threshold signature schemes are a cryptographic primitive to facilitate joint ownership over a private key by a set of participants, such that a threshold number of participants must cooperate to issue a signature that can be verified by a single public key. Threshold signatures are useful across a range of settings that require a distributed root of trust among a set of equally trusted parties.

Similarly to signing operations in a single-party setting, some implementations of threshold signature schemes require performing signing operations at scale and under heavy load. For example, threshold signatures can be used by a set of signers to authenticate financial transactions in cryptocurrencies [16], or to sign a network consensus produced by a set of trusted authorities [22]. In both of these examples, as the number of signing parties or signing operations increases, the number of communication rounds between participants required to produce the joint signature becomes a performance bottleneck, in addition to the increased load experienced by each signer. This problem is further exacerbated when signers utilize network-limited devices or unreliable networks for transmission, or protocols that wish to allow signers to participate in signing operations asynchronously. As such, optimizing the network overhead of signing operations is highly beneficial to real-world applications of threshold signatures.

Today in the literature, the best threshold signature schemes are those that rely on pairing-based cryptography [6, 7], and can perform signing operations in a single round among participants. However, relying on pairing-based signature schemes is undesirable for some implementations in practice, such as those that do not wish to introduce a new cryptographic assumption, or that wish to maintain backwards compatibility with an existing signature scheme such as Schnorr signatures. Surprisingly, today’s best non-pairing-based threshold signature constructions that produce Schnorr signatures with unlimited concurrency [14, 28] require at least three rounds of communication during signing operations, whereas constructions with fewer network rounds [14] must limit signing concurrency to protect against a forgery attack [10].

In this work, we present FROST, a Flexible Round-Optimized Schnorr Threshold signature scheme¹ that addresses the need for efficient threshold signing operations while improving upon the state of the art to ensure strong security properties without limiting the parallelism of signing operations. FROST can be used as either a two-round protocol where signers send and receive two messages in total, or optimized to a (non-broadcast) single-round signing protocol with a pre-processing stage. FROST achieves improved efficiency in the optimistic case that no participant misbehaves. However, in the case where a misbehaving participant contributes malformed values during the protocol, honest parties can identify and exclude the misbehaving participant, and re-run the protocol.

The flexible design of FROST lends itself to supporting a number of practical use cases for threshold signing. Because the preprocessing round can be performed separately from the signing round, signing operations can be performed asynchronously; once the preprocessing round is complete, signers only need to receive and eventually reply with a single message to create a signature. Further, while some threshold schemes in the literature require all participants to be active during signing operations [9, 14], and refer to the threshold property of the protocol as merely a security property, FROST allows any threshold number of participants to produce valid signatures. Consequently, FROST can support use cases where a subset of participants (or participating devices) can remain offline, a property that is often desirable for security in practice.

Contributions. In this work, we present the following contributions.

• We review related threshold signature schemes and present a detailed analysis of their performance and designs.

• We present FROST, a Flexible Round-Optimized Schnorr Threshold signature scheme. FROST improves upon the state of the art for Schnorr threshold signatures by defining a signing protocol that can be optimized to a (non-broadcast) single-round operation with a preprocessing stage. Unlike many prior Schnorr threshold schemes, FROST remains secure against known forgery attacks without limiting concurrency of signing operations.

• We present a proof of security and correctness for an interactive two-round variant of FROST, building upon proofs of security for prior related threshold schemes. We then demonstrate how this proof extends to FROST in the single-round setting.

Organization. We present background information in Sect. 2; in Sect. 3 we give an overview of related threshold Schnorr signature constructions. In Sect. 4 we review notation and security assumptions maintained for our work, and we introduce FROST in Sect. 5. In Sect. 6 we give proofs of security and correctness for FROST, and discuss operational considerations in Sect. 7. We conclude in Sect. 8.

2 Background

Let $\mathbb {G}$ be a group of prime order q in which the Decisional Diffie-Hellman problem is hard, and let g be a generator of $\mathbb {G}$. Let H be a cryptographic hash function mapping to $\mathbb {Z}_q^*$. We denote by $x \overset{\$}{\leftarrow }S$ that x is uniformly randomly selected from S.

2.1 Threshold Schemes

Cryptographic protocols called (t, n)-threshold schemes allow a set of n participants to share a secret s, such that any t out of the n participants are required to cooperate in order to recover s, but any subset of fewer than t participants cannot recover any information about the secret.

Shamir Secret Sharing. Many threshold schemes build upon Shamir secret sharing [27], a (t, n)-threshold scheme that relies on Lagrange interpolation to recover a secret. In Shamir secret sharing, a trusted central dealer distributes a secret s to n participants in such a way that any cooperating subset of t participants can recover the secret. To distribute this secret, the dealer first selects $t-1$ coefficients $a_1, \dots , a_{t-1}$ at random, and uses the randomly selected values as coefficients to define a polynomial $f(x) = s + \sum _{i=1}^{t-1} a_i x^i$ of degree $t-1$ where $f(0) = s$. The secret shares for each participant $P_i$ are subsequently (i, f(i)), which the dealer is trusted to distribute honestly to each participant $P_1, \dots , P_n$. To reconstruct the secret, at least t participants perform Lagrange interpolation to reconstruct the polynomial and thus find the value $s=f(0)$. However, no group of fewer than t participants can reconstruct the secret, as at least t points are required to reconstruct a polynomial of degree $t-1$.

Verifiable Secret Sharing. Feldman’s Verifiable Secret Sharing (VSS) Scheme [11] builds upon Shamir secret sharing, adding a verification step to demonstrate the consistency of a participant’s share with a public commitment that is assumed to be correctly visible to all participants. To validate that a share is well formed, each participant validates their share using this commitment. If the validation fails, the participant can issue a complaint against the dealer, and take actions such as broadcasting this complaint to all other participants. FROST similarly uses this technique as well.

The commitment produced in Feldman’s scheme is as follows. As before in Shamir secret sharing, a dealer samples $t-1$ random values $(a_{1}, \dots , a_{t-1})$, and uses these values as coefficients to define a polynomial f of degree $t-1$ such that $f(0) = s$. However, along with distributing the private share (i, f(i)) to each participant $P_i$, the dealer also distributes the public commitment , where $\phi _0 = g^{s}$ and $\phi _j = g^{a_j}$.

Note that in a distributed setting, each participant $P_i$ must be sure to have the same view of as all other participants. In practice, implementations guarantee consistency of participants’ views by using techniques such as posting commitments to a centralized server that is trusted to provide a single view to all participants, or adding another protocol round where participants compare their received commitment values to ensure they are identical.

Threshold Signature Schemes. Threshold signature schemes leverage the (t, n) security properties of threshold schemes, but allow participants to produce signatures over a message using their secret shares such that anyone can validate the integrity of the message, without ever reconstructing the secret. In threshold signature schemes, the secret key s is distributed among the n participants, while a single public key Y is used to represent the group. Signatures can be generated by a threshold of t cooperating signers. For our work, we require the resulting signature produced by the threshold signature scheme to be valid under the Schnorr signature scheme [26], which we introduce in Sect. 2.3.

Because threshold signature schemes ensure that no participant (or indeed any group of fewer than t participants) ever learns the secret key s, the generation of s and distribution of shares $s_1, \dots , s_n$ often require generating shares using a less-trusted method than relying on a central dealer. FROST instead makes use of a Distributed Key Generation (DKG) protocol, which we describe in Sect. 2.2. Similarly, generating Schnorr signatures in a threshold setting requires that the random nonce k be generated in such a way that each participant contributes to but does not know the resulting k. To perform this task, FROST uses additive secret sharing, which we now describe.

Additive Secret Sharing. While Shamir secret sharing and derived constructions require shares to be points on a secret polynomial f where $f(0)=s$, an additive secret sharing scheme allows a set of $\alpha$ participants to jointly compute a shared secret s by each participant $P_i$ contributing a value $s_i$ such that the resulting shared secret is $s=\sum _{i=1}^\alpha s_i$, the summation of each participant’s share. Consequently, additive secret sharing can be performed non-interactively; each participant directly chooses their own $s_i$. Benaloh and Leichter [4] generalize additive secret sharing to arbitrary monotone access structures, and Cramer, Damgård, and Ishai [8] present a non-interactive mechanism, which we use in its simplest case, for participants to locally convert additive shares of the form $s = \sum _i s_i$ to polynomial (Shamir) form, as $\frac{s_i}{\lambda _i}$ are Shamir secret shares of the same s, where the $\lambda _i$ are Lagrange coefficients. In FROST, participants use this technique during signing operations to non-interactively generate a nonce that is Shamir secret shared among all signing participants.

2.2 Distributed Key Generation

Unlike threshold schemes such as Shamir secret sharing that rely on a trusted dealer, Distributed Key Generation (DKG) ensures every participant contributes equally to the generation of the shared secret. At the end of running the protocol, all participants share a joint public key Y, but each participant holds only a share $s_i$ of the corresponding secret s such that no set of participants smaller than the threshold knows s.

Pedersen [23] presents a two-round DKG where each participant acts as the central dealer of Feldman’s VSS [11] protocol, resulting in n parallel executions of the protocol. Consequently, this protocol requires two rounds of communication between all participants; after each participant selects a secret $x_i$, they first broadcast a commitment to $x_i$ to all other participants, and then send all other participants a secret share of $x_i$.

Gennaro et al. [15] demonstrate a weakness of Pedersen’s DKG [23] such that a misbehaving participant can bias the distribution of the resulting shared secret by issuing complaints against a participant after seeing the shares issued to them by this participant. To address this issue, the authors propose a three-round protocol, modifying Pedersen’s DKG to include an additional “commitment round”, such that adversaries are prevented from adaptively disqualifying participants, thereby ensuring the value of the resulting secret is determined before participants reveal their inputs. However, in a later work, Gennaro et al. [14] prove that Pedersen’s DKG as originally described [23] is secure enough in certain contexts, as the resulting secret is sufficiently random despite the chance for bias from a misbehaving participant adaptively selecting their input after seeing inputs from other participants.

FROST can use either Pedersen’s DKG [23] or Gennaro’s DKG [15] to generate the shared long-lived secret key among participants during its key generation stage.

2.3 Schnorr Signatures

Often, it is desirable for signatures produced by threshold signing operations to be indistinguishable from signatures produced by a single participant, for reasons of backwards compatibility and to prevent privacy leaks. For our work, we require signatures produced by FROST signing operations to be indistinguishable from Schnorr signatures [26], and thus verifiable using the standard Schnorr verification operation.

A Schnorr signature is generated over a message m (employing a signature format similar to EdDSA [17]) by the following steps:

• 1. Sample a random nonce $k \overset{\$}{\leftarrow }\mathbb {Z}_q$; compute the commitment $R = g^k \in \mathbb {G}$

• 2. Compute the challenge $c = H(R, Y, m)$

• 3. Using the secret key s, compute the response $z = k + s \cdot c \in \mathbb {Z}_q$

• 4. Define the signature over m to be $\sigma = (R, z)$.

Validating the integrity of m using the public key $Y=g^s$ and the signature $\sigma$ is performed as follows:

• 1. Parse $\sigma$ as (R, z); derive $c = H(R, Y, m)$

• 2. Compute $R' = g^z \cdot Y^{-c}$

• 3. Output 1 if to indicate success; otherwise, output 0.

Schnorr signatures are simply the standard $\varSigma$-protocol proof of knowledge of the discrete logarithm of Y, made non-interactive (and bound to the message m) with the Fiat-Shamir transform.

2.4 Attacks on Parallelized Schnorr Multisignatures

Attack via Wagner’s Algorithm. We next describe an attack recently introduced by Drijvers et al. [10] against some two-round Schnorr multisignature schemes in a parallel setting. This attack can be performed when the adversary has control over either choosing the message m to be signed, or the ability to adaptively choose its own individual commitments used to determine the group commitment R after seeing commitments from all other signing parties. In Sect. 5.2 and Sect. 6 we discuss how FROST avoids the attack.

Successfully performing the Drijvers attack² requires finding a hash output $c^* = H(R^*, Y, m^*)$ that is the sum of T other hash outputs $c^* = \sum _{j=1}^{T} H(R_j, Y, m_j)$ (where $c^*$ is the challenge, $m_j$ the message, Y the public signing key, and $R_j$ the group’s commitment corresponding to a standard Schnorr signature as described in Sect. 2.3). To find T hash outputs that sum to $c^*$, the adversary can open many (say T number of) parallel simultaneous signing operations, varying in each of the T parallel executions either its individual commitment used to determine $R_j$ or $m_j$. Drijvers et al. use the k-tree algorithm of Wagner [29] to find such hashes and perform the attack in time $O(\kappa \cdot b \cdot 2^{b/(1+\lg \kappa )})$, where $\kappa = T + 1$, and b is the bitlength of the order of the group.

Although this attack was proposed in a multisignature n-out-of-n setting, this attack applies similarly in a threshold t-out-of-n setting for an adversary that controls up to $t-1$ participants. We note that this attack applies to threshold schemes proposed in the literature, such as the scheme by Gennaro et al. [14].

Drijvers et al. [10] also present a metareduction for the proofs of several Schnorr multisignature schemes that use a generalization of the forking lemma with rewinding, highlighting that the security of this proof technique does not extend to a multi-party setting. Because our proofs of security for FROST (presented in Sect. 6) reduce to the hardness of the discrete logarithm problem for the underlying group, as opposed to the one-more discrete logarithm problem, the metareduction presented by Drijvers et al. [10] does not apply to our proof strategy.

Attack via ROS Solver. Benhamouda et al. [5] recently presented a polynomial-time algorithm that solves the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem. As first described by Schnorr [25], the ROS problem challenges an adversary to find an $(\ell + 1) \times \ell$ submatrix of rank $\ell$, when given a system of $n \gg \ell$ linear equations modulo q with $\ell$ unknowns and random constant terms. Benhamouda et al. show how to solve the ROS in expected polynomial time when $\ell > \lg q$. Solving the ROS problem in the setting of Schnorr multisignatures enables an adversary that is allowed to open $\ell$ simultaneous connections to an honest participant with inputs $m_1, \dots , m_\ell$ to produce a $(\ell +1)^{\text {th}}$ signature without asking the participant for a signature on $m_{\ell +1}$. The authors demonstrate that threshold schemes using Gennaro et al.’s DKG [15] and multisignature schemes such as two-round MuSig [21] are not secure against their ROS-solving algorithm. However, the authors conclude that (the current version of) FROST is not affected by their ROS-solving algorithm.

3 Related Work

We now review prior threshold schemes with a focus on Schnorr-based designs, and split our review into robust and non-robust schemes. Robust schemes ensure that so long as t participants correctly follow the protocol, the protocol is guaranteed to complete successfully, even if a subset of participants (at most $n-t$) contribute malformed shares. Conversely, designs that are not robust simply abort after detecting any participant misbehaviour.

Robust Threshold Schemes. Stinson and Strobl [28] present a threshold signature scheme producing Schnorr signatures, using the modification of Pedersen’s DKG presented by Gennaro et al. [15] to generate both the secret key s during key generation as well as the random nonce k for each signing operation. This construction requires at minimum four rounds for each signing operation (assuming no participant misbehaves): three rounds to perform the DKG to obtain k, and one round to distribute signature shares and compute the group signature. Each round requires participants to send values to every other participant.

Gennaro et al. [14] present a threshold Schnorr signature protocol that uses a modification of Pedersen’s DKG [23] to generate both s during key generation and the random nonce k for signing operations. However, their construction requires all n signers to participate in signing, while the adversary is allowed to control up to the given threshold number of participants. Recall from Sect. 2.2 that Pedersen’s DKG requires two rounds; this construction requires an additional round for signing operations when all participants are equally trusted. Each round requires that all participants send values to all other participants. The authors also discuss an optimization that leverages a signature aggregator role, an entity trusted to gather signatures from each participant, perform validation, and publish the resulting signature, a role we also adopt in our work. In their optimized variant, participants can perform Pedersen’s DKG to generate multiple k values in a pre-processing stage independently of performing signing operations. In this variant, to compute $\ell$ signatures, signers first perform two rounds of $\ell$ parallel executions of Pedersen’s DKG, thereby generating $\ell$ random nonces. The signers can then store these pre-processed values to later perform $\ell$ single-round signing operations.

Our work builds upon the key generation stage of Gennaro et al. [14]; we use a variant of Pedersen’s DKG for key generation with a requirement that in the case of misbehaviour, the protocol aborts and the cause investigated out of band. However, FROST does not perform a DKG during signing operations as is done in both of the above schemes, but instead make use of additive secret sharing and share conversion. Consequently, FROST trades off robustness for more efficient signing operations, such that a misbehaving participant can cause the signing operation to abort. However, such a tradeoff is practical to many real-world settings.

Further, because FROST does not provide robustness, FROST is secure so long as the adversary controls fewer than the threshold t participants, an improvement over robust designs, which can at best provide security for $t \le n/2$ [15].

Non-robust Threshold Schemes. FROST is not unique in trading off favouring increased network efficiency over robustness. Gennaro and Goldfeder [12] present a threshold ECDSA scheme that similarly requires aborting the protocol in the case of participant misbehaviour. Their signing construction uses a two-round DKG to generate the nonce required for the ECDSA signature, leveraging additive-to-multiplicative share conversion. This DKG has been also applied in a Schnorr threshold scheme context to generate the random nonce for more efficient distributed key generation operations [18] in combination with threshold Schnorr signing operations [28]. In later work [13], Gennaro and Goldfeder define an optimization to a single-round ECDSA signing operation with a preprocessing stage, which assumes the protocol will abort in the case of failure or participant misbehaviour. Their end-to-end protocol with identifiable aborts has eight network rounds, six of which require broadcasting to all other signing participants, and two of which require performing pairwise multiplicative-to-additive share conversion protocols. Further, while the protocol can be optimized into a preprocessing phase, the choice of the signing coalition must be determined at the time of preprocessing. FROST defines a more efficient preprocessing phase as secret nonces can be generated in a distributed manner in the preprocessing phase entirely non-interactively. Further, participants can “mix” preprocessed values across different signing coalitions, as FROST requires that the choice for the signing coalition be made only during the signing stage.

Recent work by Damgård et al. [9] define an efficient threshold ECDSA construction that similarly requires aborting in the case of misbehaviour. Their design relies on generating a blinding factor $d + m \cdot e$ such that where d and e are 2t secret sharings of zero, such that the entire binding factor evaluates to zero when all signing parties are honest and agree on m. This approach is similar to FROST in that signature shares are bound to the message and to the set of signing parties. However, the security of their scheme requires the majority of participants to be honest, and $n \ge 2t+1$. Further, their scheme requires all n participants take part in signing operations, where the threshold t is simply a security parameter.

Similarly to FROST, Abidin, Aly, and Mustafa [1] present a design for authentication between devices, and use additive secret sharing to generate the nonce for Schnorr signatures in a threshold setting, a technique also used by FROST. However, the authors do not consider the Drijvers attack and consequently their design is similarly limited to restricted levels of parallelism. Further, their design does not include validity checks for responses submitted by participants when generating signatures and consequently does not detect nor identify misbehaving participants.

FROST improves upon prior work in Schnorr threshold schemes by providing a single-round signing variant with a preprocessing stage that is agnostic to the choice of the signing coalition. Further, the number of signing participants in FROST is required to be simply some $t\le n$, while remaining secure against the Drijvers attack and misbehaving participants who do not correctly follow the protocol.

4 Preliminaries

Let n be the number of participants in the signature scheme, and t denote the threshold of the secret-sharing scheme. Let i denote the participant identifier for participant $P_i$ where $1 \le i \le n$. Let $s_i$ be the long-lived secret share for participant $P_i$. Let Y denote the long-lived public key shared by all participants in the threshold signature scheme, and let $Y_i = g^{s_i}$ be the public key share for the participant $P_i$. Finally, let m be the message to be signed.

Let $\alpha$ be the number of participants performing a signing operation, where $t \le \alpha \le n$. For a set $S = \{p_1,\dots ,p_\alpha \}$ of $\alpha$ participant identifiers in the signing operation, let $\lambda _i = \prod _{j=1, j \not = i}^{\alpha } \frac{p_j}{p_j - p_i}$ denote the $i^{\text {th}}$ Lagrange coefficient for interpolating over S. Note that the information to derive these values depends on which $\alpha$ (out of n) participants are selected, and uses only the participant identifiers, and not their shares.³

Security Assumptions. We maintain the following assumptions, which implementations should account for in practice.

• Message Validation. We assume every participant checks the validity of the message m to be signed before issuing its signature share.

• Reliable Message Delivery. We assume messages are sent between participants using a reliable network channel.

• Participant Identification. In order to report misbehaving participants, we require that values submitted by participants to be identifiable within the signing group. Implementations can enforce this using a method of participant authentication within the signing group.⁴

5 FROST: Flexible Round-Optimized Schnorr Threshold Signatures

We now present FROST, a Flexible Round-Optimized Schnorr Threshold signature scheme that minimizes the network overhead of producing Schnorr signatures in a threshold setting while allowing for unrestricted parallelism of signing operations and only a threshold number of signing participants.

Efficiency over Robustness. As described in Sect. 3, prior threshold signature constructions [14, 28] provide the property of robustness. However, in settings where one can expect misbehaving participants to be rare, threshold signing protocols can be relaxed to be more efficient in the “optimistic” case that all participants honestly follow the protocol. In the case that a participant does misbehave, honest participants can identify the misbehaving participant and abort the protocol, and then re-run the protocol after excluding the misbehaving participant. FROST trades off robustness in the protocol for improved round efficiency in this way.

Signature Aggregator Role. We instantiate FROST using a semi-trusted signature aggregator role, denoted as $\mathcal {SA}$. Such a role allows for less communication overhead between signers and is often practical in a real-world setting. However, FROST can be instantiated without a signature aggregator; each participant simply performs a broadcast in place of $\mathcal {SA}$ performing coordination.

The signature aggregator role can be performed by any participant in the protocol, or even an external party, provided they know the participants’ public-key shares $Y_i$. $\mathcal {SA}$ is trusted to report misbehaving participants and to publish the group’s signature at the end of the protocol. If $\mathcal {SA}$ deviates from the protocol, the protocol remains secure against adaptive chosen message attacks, as $\mathcal {SA}$ is not given any more of a privileged view than the adversary we model in our proof of security for FROST in Sect. 6. A malicious $\mathcal {SA}$ does have the power to perform denial-of-service attacks and to falsely report misbehaviour by participants, but cannot learn the private key or cause improper messages to be signed. Note this signature aggregator role is also used in prior threshold signature constructions in the literature [14] as an optimization.

Fig. 1.

KeyGen. A distributed key generation (DKG) protocol that builds upon the DKG by Pedersen [23]. Our variant includes a protection against rogue key attacks by requiring each participant to prove knowledge of their secret value commits, and requires aborting on misbehaviour.

5.1 Key Generation

To generate long-lived key shares in our scheme’s key generation protocol, FROST builds upon Pedersen’s DKG for key generation; we detail these protocol steps in Fig. 1. Note that Pedersen’s DKG is simply where each participant executes Feldman’s VSS as the dealer in parallel, and derives their secret share as the sum of the shares received from each of the n VSS executions. In addition to the base Pedersen DKG protocol, FROST additionally requires each participant to demonstrate knowledge of their secret $a_{i0}$ by providing other participants with proof in zero knowledge, instantiated as a Schnorr signature, to protect against rogue-key attacks [2] in the setting where $t \ge n/2$.

To begin the key generation protocol, a set of participants must be formed using some out-of-band mechanism decided upon by the implementation. After participating in the Ped-DKG protocol, each participant $P_i$ holds a value $(i, s_i)$ that is their long-lived secret signing share. Participant $P_i$’s public key share $Y_i = g^{s_i}$ is used by other participants to verify the correctness of $P_i$’s signature shares in the following signing phase, while the group public key Y can be used by parties external to the group to verify signatures issued by the group in the future.

View of Commitment Values. As required for any multi-party protocol using Feldman’s VSS, the key generation stage in FROST similarly requires participants to maintain a consistent view of commitments issued during the execution of Ped-DKG. In this work, we assume participants broadcast the commitment values honestly (e.g., participants do not provide different commitment values to a subset of participants); recall Sect. 2.1 where we described techniques to achieve this guarantee in practice.

Security Tradeoffs. While Gennaro et al. [15] describe the “Stop, Kill, and Rewind” variant of Ped-DKG (where the protocol terminates and is re-run if misbehaviour is detected) as vulnerable to influence by the adversary, we note that in a real-world setting, good security practices typically require that the cause of misbehaviour is investigated once it has been detected; the protocol is not allowed to terminate and re-run continuously until the adversary finds a desirable output. Further, many protocols in practice do not prevent an adversary from aborting and re-executing key agreement at any point in the protocol; adversaries in protocols such as the widely used TLS protocol can skew the distribution of the resulting key simply by re-running the protocol.

However, implementations wishing for a robust DKG can adapt our key generation protocol to the robust construction presented by Gennaro et al. [15]. Note that the efficiency of the DKG for the key generation phase is not extremely critical, because this operation must be done only once per key generation for long-lived keys. For the per-signature operations, FROST optimizes the generation of random values without utilizing a DKG, as discussed next.

5.2 Threshold Signing with Unrestricted Parallelism

We now introduce the signing protocol for FROST. This operation builds upon known techniques in the literature [1, 14] by employing additive secret sharing and share conversion to non-interactively generate the nonce value for each signature. However, signing operations in FROST additionally leverage a binding technique to avoid known forgery attacks without limiting concurrency. We present FROST signing in two parts: a pre-processing phase and a single-round signing phase. However, these stages can be combined for a single two-round protocol if desired.

As a reminder, the attack of Drijvers et al. [10] requires the adversary to either see the victim’s T commitment values before selecting their own commitment, or to adaptively choose the message to be signed, so that the adversary can manipulate the resulting challenge c for the set of participants performing a group signing operation. To prevent this attack without limiting concurrency, FROST “binds” each participant’s response to a specific message as well as the set of participants and their commitments used for that particular signing operation. In doing so, combining responses over different messages or participant/commitment pairs results in an invalid signature, thwarting attacks such as those of Drijvers et al.

Fig. 2.

FROST preprocessing protocol

Preprocessing Stage. We present in Fig. 2 a preprocessing stage where participants generate and publish $\pi$ commitments at a time. In this setting, $\pi$ determines the number of nonces that are generated and their corresponding commitments that are published in a single preprocess step. Implementations that do not wish to cache commitments can instead use a two-round signing protocol, where participants publish a single commitment to each other in the first round.

Each participant $P_i$ begins by generating a list of single-use private nonce pairs and corresponding public commitment shares $\langle ((d_{ij}, D_{ij} = g^{d_{ij}}), (e_{ij}, E_{ij} = g^{e_{ij}})) \rangle _{j=1}^\pi$, where j is a counter that identifies the next nonce/commitment share pair available to use for signing. Each $P_i$ then publishes $(i, L_i)$, where $L_i$ is their list of commitment shares $L_i = \langle (D_{ij}, E_{ij}) \rangle _{j=1}^\pi$. The location where participants publish these values can depend on the implementation (which we discuss further in Sect. 7). The set of $(i, L_i)$ tuples are then stored by any entity that might perform the signature aggregator role during signing.

Fig. 3.

FROST single-round signing protocol

Signing Protocol. At the beginning of the signing protocol in Fig. 3, $\mathcal {SA}$ selects $\alpha : t \le \alpha \le n$ participants (possibly including itself) to participate in the signing. Let S be the set of those $\alpha$ participants. $\mathcal {SA}$ then selects the next available commitment $(D_i, E_i) : i \in S$, which are later used to generate a secret share to a random commitment R for the signing group.⁵

The resulting secret nonce is $k = \sum _{i \in S} k_i$, where each $k_i = d_i + e_i \cdot \rho _i$ (we next describe how participants calculate $\rho _i$), and $(d_i, e_i)$ correspond to the $(D_i = g^{d_i}, E_i=g^{e_i})$ values published during the Preprocess stage. Recall from Sect. 2.1 that if the $k_i$ are additive shares of k, then the $\frac{k_i}{\lambda _i}$ are Shamir shares of k.

After these steps, $\mathcal {SA}$ then creates the set B, where B is the ordered list of tuples $\langle (i, D_i, E_i)\rangle _{i \in S}$. $\mathcal {SA}$ then sends (m, B) to every $P_i, i \in S$.

After receiving (m, B) from $\mathcal {SA}$ to initialize a signing operation, each participant checks that m is a message they are willing to sign. Then, using m and B, all participants derive the “binding values” $\rho _i, i \in S$ such that $\rho _i = H_1(i, m, B)$, where $H_1$ is a hash function whose outputs are in $\mathbb {Z}_q^*$.

Each participant then computes the commitment $R_i$ for each participant in S by deriving $R_i = D_i \cdot (E_i)^{\rho _i}$. Doing so binds the message, the set of signing participants, and each participant’s commitment to each signature share. This binding technique thwarts the attack of Drijvers et al. described in Sect. 2.4 as attackers cannot combine signature shares across disjoint signing operations or permute the set of signers or published commitments for each signer.

The commitment for the set of signers is then simply $R = \prod _{i \in S} R_i$. As in single-party Schnorr signatures, each participant computes the challenge $c = H_2(R, Y, m)$.

Each participant’s response $z_i$ to the challenge can be computed using the single-use nonces $(d_i, e_i)$ and the long-term secret shares $s_i$, converted to additive form:

$$ z_i = d_i + (e_i \cdot \rho _i) + \lambda _i \cdot s_i \cdot c $$

$\mathcal {SA}$ finally checks the consistency of each participant’s reported $z_i$ with their commitment share $(D_i, E_i)$ and their public key share $Y_i$. If every participant issued a correct $z_i$, the group’s response is $z = \sum _{i \in S} z_i$, and the group signature on m is $\sigma =(R, z)$. This signature is verifiable to anyone performing a standard Schnorr verification operation with Y as the public key (Sect. 2.3).

Handling Ephemeral Outstanding Shares. Because each nonce and commitment share generated during the preprocessing stage described in Fig. 2 must be used at most once, participants should delete these values after using them in a signing operation, as indicated in Step 5 in Fig. 3. An accidentally reused $(d_{ij}, e_{ij})$ can lead to exposure of the participant’s long-term secret $s_i$.

However, if $\mathcal {SA}$ chooses to re-use a commitment set $(D_i, E_i)$ during the signing protocol, doing so simply results in the participant $P_i$ aborting the protocol, and consequently does not increase the power of $\mathcal {SA}$.

6 Security

We now present proofs of correctness and a high-level overview of our proof of security against chosen-message attacks for FROST. We present our complete proofs of security in Appendix A.

6.1 Correctness

Signatures in FROST are constructed from two polynomials; the first polynomial $F_1(x)$ defines the secret sharing of the private signing key s (such that $Y = g^s$) and the second polynomial $F_2(x)$ defines the secret sharing of the nonce k such that $k = \sum _{i \in S} d_i + e_i \cdot \rho _i$ using the associated public data (m, B) to determine $\rho _i$. During the key generation phase described in Fig. 1, the first polynomial $F_1(x) = \sum _{j=1}^n f_j(x)$ is generated such that the secret key shares are $s_i = F_1(i)$ and the secret key is $s = F_1(0)$.

During the signature phase (Fig. 3), each of the $\alpha : t \le \alpha \le n$ participants selected for signing use a pair of nonces $(d_i, e_i)$ to define a degree $\alpha -1$ polynomial $F_2(x)$, interpolating the values $(i,\frac{d_i + e_i \cdot H_1(i, m, B)}{\lambda _i})$, such that $F_2(0) = \sum _{i \in S} d_i + e_i \cdot \rho _i$.

Then let $F_3(x) = F_2(x) + c \cdot F_1(x)$, where $c = H_2(R, Y, m)$. Now $z_i$ equals $d_i + (e_i \cdot \rho _i) + \lambda _i \cdot s_i \cdot c = \lambda _i (F_2(i) + c \cdot F_1(i)) = \lambda _i F_3(i)$, so $z = \sum _{i \in S} z_i$ is simply the Lagrange interpolation of $F_3(0) = (\sum _{i \in S} d_i + e_{ij} \cdot \rho _i) + c \cdot s$. Because $R = g^{\sum _{i \in S} d_i + e_i \cdot \rho _i}$ and $c = H_2(R, Y, m)$, (R, z) is a correct Schnorr signature on m.

6.2 Security Against Chosen Message Attacks

We now present a high-level overview of the proof of security against chosen-message attacks for FROST; our complete proofs are in Appendix A. We begin by summarizing a proof of security for an interactive variant of FROST that we call FROST-Interactive, and then demonstrate how the proof extends to plain FROST.

We employ the generalized forking strategy used by Bellare and Neven [3] to create a reduction to the security of the discrete logarithm problem (DLP) in $\mathbb {G}$. We prove security against the standard notion of existential unforgeability against chosen message attacks (EUF-CMA) by demonstrating that the difficulty to an adversary to forge FROST signatures by performing an adaptively chosen message attack in the random oracle model reduces to the difficulty of computing the discrete logarithm of an arbitrary challenge value $\omega$ in the underlying group, so long as the adversary controls fewer than the threshold t participants.

FROST-Interactive. In FROST-Interactive, $\rho _i$ is established using a “one-time” verifiable random function (VRF),⁶ as $\rho _i = a_{ij} + (b_{ij} \cdot H_{\rho }(m, B))$, where $(a_{ij}, b_{ij})$ are selected and committed to as $(A_{ij}=g^{a_{ij}}, B_{ij}=g^{b_{ij}})$ during the preprocessing stage, along with zero-knowledge proofs of knowledge of $(a_{ij}, b_{ij})$. To perform a signing operation, participants first generate $\rho _i$ in the first round of the signing protocol using $(a_{ij}, b_{ij})$, and then publish $\rho _i$ to the signature aggregator, which distributes all $\rho _\ell , \ell \in S$ to all signing participants. These $\rho _\ell , \ell \in S$ values are then used by all signing participants to compute R in the second round of the signing protocol, which participants use to calculate and publish $z_i$.

Summary of Proof for EUF-CMA Security for FROST-Interactive. Let $n_h$ be the number of queries made to the random oracle, $n_p$ be the number of allowed preprocess queries, and $n_s$ be the number of allowed signing queries. We assume there exists a forger $\mathcal {F}$ that $(\tau , n_h, n_p, n_s, \epsilon )$-breaks FROST-Interactive, meaning that $\mathcal {F}$ can compute a forgery for a signature generated by FROST-Interactive in time $\tau$ with success $\epsilon$, but is limited to making $n_h$ number of random oracle queries, $n_p$ number of preprocess queries, and $n_s$ number of signing queries. We construct an algorithm C that $(\tau ', \epsilon ')$-solves the discrete logarithm problem in $\mathcal {G}$, for an arbitrary challenge value $\omega \in \mathbb {G}$, using as a subroutine a forger $\mathcal {F}$ that can forge FROST signatures.

Without loss of generality, we assume $\mathcal {F}$ controls $t-1$ participants.

Theorem 1

If the discrete logarithm problem in $\mathbb {G}$ is $(\tau ', \epsilon ')$-hard, then the FROST-Interactive signature scheme over $\mathbb {G}$ with n signing participants, a threshold of t, and a preprocess batch size of $\pi$ is $(\tau , n_h, n_p, n_s, \epsilon )$-secure whenever

$$ \epsilon ' \le \frac{\epsilon ^2}{2 n_h + (\pi +1) n_p + 1} \quad and $$

$$ \tau ' = 4\tau + (30\pi n_p + (4t-2)n_s + (n+t-1)t + 6) \cdot t_{exp} + O(\pi n_p + n_s + n_h + 1) $$

such that $t_{exp}$ is the time of an exponentiation in $\mathbb {G}$, assuming the number of participants compromised by the adversary is less than the threshold t.

Proof Sketch for FROST-Interactive. We provide our complete proof in Appendix A, but summarize here. We prove Theorem 1 by contradiction.

We begin by embedding the challenge value $\omega$ into the group public key Y. The coordinator algorithm C then uses the generalized forking algorithm $GF_\mathcal {A}$ to initialize the simulator $\mathcal {A}(Y, \{h_1, \dots , h_{n_r} \}; \beta )$, providing the group public key Y, outputs for $n_r = 2 n_h + (\pi +1) n_p + 1$ random oracle queries denoted as $\{ h_1, \dots , h_{n_r}\} \overset{\$}{\leftarrow }H$, and the random tape $\beta$. $\mathcal {A}$ then invokes the forger $\mathcal {F}$, simulating the responses to $\mathcal {F}$’s random oracle queries by providing values selected from $\{ h_1, \dots , h_{n_r}\}$, and also simulates the honest party $P_t$ in the KeyGen, Preprocess, and Sign procedures.

To simulate signing without knowing the secret key corresponding to $P_t$’s own public key $Y_t$, $\mathcal {A}$ generates the commitment and signature for participant $P_t$ by publishing $(D_{tj} = g^{z_{tj}} \cdot (Y_t)^{-c_j}, E_{tj})$ such that $z_{tj} \overset{\$}{\leftarrow }\mathbb {Z}_q$, $c_j$ is the next unused value from the set of random oracle outputs supplied by $GF_\mathcal {A}$, and $E_{tj} = g^{e_{tj}}, e_{tj} \overset{\$}{\leftarrow }\mathbb {Z}_q^*$. To determine which challenge $c_j$ to return for a particular commitment $(D_{ij}, E_{ij})$ when simulating a signing operation, $\mathcal {A}$ forks $\mathcal {F}$ to extract its $(a_{ij}, b_{ij})$ VRF keys from its zero-knowledge proofs during Preprocess for each participant $P_\ell$ controlled by $\mathcal {F}$, and consequently can directly compute its corresponding $\rho _\ell$. Hence, $\mathcal {A}$ can compute R strictly before $\mathcal {F}$ for every signing query, and thus can always correctly program the random oracle for the query $H_2(R, Y, m)$ to return the correct $c_j$ embedded in $D_{tj}$.

Once $\mathcal {A}$ has returned a valid forgery $\sigma =(R, z)$ and the index J associated to the random oracle query $h_J$ such that $h_J = c$, $GF_\mathcal {A}$ re-executes $\mathcal {A}$ with the same random tape $\beta$ and public key Y, but with responses to random oracle queries

$\{h_1, \dots , h_{J-1}, h'_J, \dots , h'_{n_r} \}$, where $\{h'_{J}, \dots , h'_{n_r} \} \overset{\$}{\leftarrow }H$. Doing so simulates the “forking” of $\mathcal {A}$ at a specific point in its execution, such that all behaviour of $\mathcal {A}$ is identical between executions up to the $J^{\text {th}}$ random oracle query, but different thereafter.

Consequently, given a forger $\mathcal {F}$ that with probability $\epsilon$ produces a valid forgery, the probability that $\mathcal {A}$ returns a valid forgery for FROST-Interactive is $\epsilon$, and the probability that $GF_\mathcal {A}$ returns two valid forgeries using the same commitment after forking $\mathcal {A}$ is $\frac{\epsilon ^2}{n_r}$.

The running time for C to compute the discrete logarithm by procuring two forgeries from FROST-Interactive is four times that for $\mathcal {F}$ (because of the forking of $\mathcal {A}$, which itself forks $\mathcal {F}$), plus the time to compute $(30\pi n_p + (4t-2)n_s + (n+t-1)t + 6)$ exponentiations, and $O(\pi n_p + n_s + n_h + 1)$ other minor operations, such as table lookups.

Extension of Proof to FROST. We now heuristically demonstrate how the change from FROST-Interactive to FROST does not open a hole in the proof. The difference between FROST-Interactive and FROST is the replacement of the interactive VRF in FROST-Interactive with a hash function (modelled by a random oracle) to derive $\rho _i$. This change still achieves the properties required of $\rho _i$, as deterministic, unpredictable, and bound to (i, m, B). However, the key distinction when generating $\rho _i$ via a VRF versus a hash function is that in FROST-Interactive, the VRF query is part of the signing algorithm, and so each such query uses up a $(d_i, e_i)$ pair; therefore, the adversary can learn only one $\rho _i(m,B)$ value for any given $(i, D_i, E_i) \in B$, and importantly, this allows the simulator $\mathcal {A}$ in the proof to always be able to set $H_2(R, Y, m)$ to the correct $c_j$ value. In plain FROST, the adversary can query the random oracle $\rho _i = H_1(i, m, B)$ polynomially many times, even with the same $(i, D_i, E_i) \in B$. The adversary will be able to produce a forgery if⁷ (slightly generalizing the Drijvers attack to arbitrary linear combinations instead of just sums) they can find $m^*$, $r^*$, and $\langle m_j, B_j, \gamma _j \rangle _{j=1}^\pi$ such that

$$\begin{aligned} H_2(R^*, Y, m^*) = \sum _{j=1}^\pi \gamma _j \cdot H_2(R_j, Y, m_j) \end{aligned}$$

(1)

where $\displaystyle R_j = \prod _{(i,D,E)\in B_j} D\cdot E^{H_1(i,m_j,B_j)}$, $\displaystyle \widehat{R_j} = D_{jt}\cdot E_{jt}^{H_1(i,m_j,B_j)}$, $\displaystyle R^* = g^{r^*} \cdot \prod _{j=1}^\pi \widehat{R_j}^{\gamma _j}$, each $B_j$ contains the honest party’s $(t, D_{jt}, E_{jt})$, and $m^*$ is not one of the $m_j$.

Importantly, the key difference between FROST and schemes susceptible to the Drijvers attack is that in FROST, the $R^*$ in the left side of Eq. 1 is itself a function of all the inputs to the hash functions on the right side. Drijvers can use Wagner’s generalized birthday attack [29] because the left and right sides of Eq. 1 are independent for schemes vulnerable to their attack, and so Wagner’s algorithm can find a collision between a list of possible values on the left (the $(m^*, R^*)$ terms) and a (larger) list of possible values on the right (the $(m_j, R_j)$ terms). In FROST, however, each combination of values on the right changes $R^*$, and so the list of possible values on the left (varying $m^*$, for example) changes for each such combination, increasing the cost to an attacker from the generalized birthday collision attack to multiple preimage attacks.

As such, we heuristically argue that the difference between generating $\rho _i$ via the one-time VRF in FROST-Interactive and the random oracle in plain FROST has no security consequence.

6.3 Aborting on Misbehaviour

FROST requires participants to abort once they have detected misbehaviour, with the benefit of fewer communication rounds in an honest setting.

If one of the signing participants provides an incorrect signature share, $\mathcal {SA}$ will detect that and abort the protocol, if $\mathcal {SA}$ is itself behaving correctly. The protocol can then be rerun with the misbehaving party removed. If $\mathcal {SA}$ is itself misbehaving, and even if up to $t-1$ participants are corrupted, $\mathcal {SA}$ still cannot produce a valid signature on a message not approved by at least one honest participant.

7 Implementation and Operational Considerations

We have implemented FROST in Rust, using Ristretto over curve25519 [19] for the group operations. Our source code can be found at https://crysp.uwaterloo.ca/software/frost.

We now discuss two topics that may be of interest to implementors.

Publishing Commitments. The preprocessing step for FROST in Sect. 5.2 requires some agreed-upon location for participants to publish their commitments to, such as a commitment server, which is trusted to provide the correct (i.e., valid and unused) commitment shares upon request. If malicious, it could perform a denial-of-service attack, or it could provide stale or malformed commitment values on behalf of honest participants. However, simply having access to the set of a participant’s public published commitments does not grant any additional powers.

Performing Two-Round FROST Without Central Roles. While the round complexity of FROST can be optimized using central roles such as the signature aggregator, some implementations may wish to remain completely decentralized. In this setting, participants can simply broadcast commitments to each other, and perform signing using a two-round setting (foregoing the preprocessing step) for further simplicity.

8 Conclusion

While threshold signatures provide a unique cryptographic functionality that is applicable across a range of settings, implementations incur network overhead costs when performing signing operations under heavy load. As such, minimizing the number of network rounds required for threshold signing operations has practical benefits for network-limited devices or where signers can go offline but wish to perform a signing operation asynchronously. In this work, we introduce FROST, a flexible Schnorr-based threshold signature scheme that improves upon the state of the art by minimizing the number of network rounds required for signing without limiting the parallelism of signing operations. We present an optimized variant of FROST as a single-round signing protocol with a preprocessing phase, but the protocol can be used in a two-round setting. While FROST requires aborting on misbehaviour, such a tradeoff is often practical in a real-world setting, assuming such cases of misbehaviour are rare. We present proofs of security and correctness for FROST, demonstrating FROST is secure against chosen-message attacks assuming the adversary controls fewer than a threshold number of participants, and the discrete logarithm problem is hard.

A  Proof of Security

In Sect. 6.2, we presented a high-level overview of the proof of security for FROST-Interactive. We now present the proof in detail.

1.1 A.1  Preliminaries

Our proof strategy is to demonstrate that the security of FROST-Interactive reduces to the difficulty of computing the discrete logarithm of an arbitrary challenge value $\omega$. At a high level, $\omega$ will be embedded into a public key Y representing a set of participants, such that Y is the output of these participants cooperating to perform the FROST KeyGen protocol. Then, to compute the discrete logarithm of $\omega$, a forger $\mathcal {F}$ will produce two forgeries $(\sigma , \sigma '), \sigma \ne \sigma '$ for the same commitment value R and message m. Using $(\sigma , \sigma ')$, the discrete logarithm of $\omega$ can subsequently be extracted.

We now describe how we perform this proof strategy in detail, starting by introducing four different algorithms that we use in our proof, and expanding further below.

• $\mathcal {F}$ represents a forger that with probability $\epsilon$ and in time t can compute a forgery $\sigma$ for a public key Y, where Y was generated as part of the FROST KeyGen protocol.

• $\mathcal {A}$ represents a simulator that invokes $\mathcal {F}$ and simulates the necessary inputs/outputs for $\mathcal {F}$ to perform its forgery attack. Specifically, $\mathcal {A}$ simulates honest participants in FROST KeyGen and signing operations, as well as random oracle queries.

• $GF_\mathcal {A}$ represents the Generalized Forking Algorithm that establishes a random tape and outputs to random oracle queries, and invokes $\mathcal {A}$ with these values in order to produce two forgeries $(\sigma , \sigma ')$.

• C represents the coordination algorithm that accepts a challenge value $\omega$ and invokes the other algorithms in order to obtain $(\sigma , \sigma ')$, which it then uses to compute the discrete logarithm of $\omega$.

Adversary Powers. When performing its forgery attack, we grant $\mathcal {F}$ the role of the signature aggregator $\mathcal {SA}$. Without loss of generality, we assume $\mathcal {F}$ controls $t-1$ participants, and has full power over how these participants behave, what secret and public values they generate, etc. We also assume the participant $P_t$ is in the signing set S.

We now further describe $GF_\mathcal {A}$ and C; note these algorithms remain largely unchanged from their use by Bellare and Neven [3]. We describe the implementation of $\mathcal {A}$ in the proof directly.

Generalized Forking Algorithm and Lemma. We build upon the Generalized Forking Algorithm and Lemma by Bellare and Neven [3], which simulates the rewinding of the adversary $\mathcal {A}$, and which we describe next.

Generalized Forking Algorithm. Let $n_r$ be the maximum number of random oracle outputs that $\mathcal {A}$ may need to generate, and let h be the number of possible outputs from the random oracle H.

The adversary $\mathcal {A}$ is an algorithm that accepts as inputs a public key Y, the randomly selected set $h_1, \dots , h_{n_r}$ of random oracle outputs, and a random tape $\beta$. $\mathcal {A}$ outputs an integer J which represents the index corresponding to the random oracle query that can be used to derive c for the forgery $\sigma =(R, z)$, along with $\sigma$ itself. $GF_\mathcal {A}$ (Algorithm 1) plays the role of setting up these inputs and outputs, and executing $\mathcal {A}$ accordingly.

The execution $GF_\mathcal {A}$ is as follows: first $GF_\mathcal {A}$ instantiates a random tape $\beta$, and generates random outputs $h_1, \dots , h_{n_r}$ which will then be used by $\mathcal {A}$ to simulate the outputs for each random oracle query. $GF_\mathcal {A}$ then executes $\mathcal {A}$ with these inputs as well as a public key Y. $\mathcal {A}$ uses the forger $\mathcal {F}$ as a subroutine to perform its forgery attack, simulating all input and output whenever $\mathcal {F}$ requests a signing operation or random oracle query. Eventually, $\mathcal {F}$ outputs a forgery $\sigma$ with probability $\epsilon$, which $\mathcal {A}$ returns along with its corresponding index for the random oracle query that can be used to derive c for $\sigma$. After $\mathcal {A}$ outputs $(J, \sigma )$, $GF_\mathcal {A}$ first checks to see if the output is a successful forgery, as indicated by when $J \ge 1$. If so, it continues to the second execution of $\mathcal {A}$.

For the second execution of $\mathcal {A}$, $GF_\mathcal {A}$ will feed in the same random tape $\beta$, but will supply a different set of simulated responses for the random oracle H. In order to “fork” $\mathcal {A}$, $GF_\mathcal {A}$ will supply the same responses $h_1, \dots , h_{J-1}$, but will provide different responses for $h_J, \dots , h_{n_r}$. In doing so, $GF_\mathcal {A}$ simulates forking the adversary at a specific point when performing its attack similar to the proof model by Pointcheval and Stern [24], but without needing to rewind $\mathcal {A}$ to a specific point.

After its second execution, $\mathcal {A}$ will return $(J', \sigma ')$ or $\bot$. If but the output from the random oracle queries is different such that $h_J \ne h_J'$, then $GF_\mathcal {A}$ will output 1 to indicate success along with the two forgeries $\sigma , \sigma '$ and the two random oracle queries corresponding to these forgeries $(h_J, h_J')$. These values can then be used by the coordination algorithm C to determine the discrete logarithm of the challenge value $\omega$ (we provide more details on how to perform this operation below).

Generalized Forking Lemma. We will now see how the generalized forking lemma presented by Bellare and Neven [3] determines the probability that $GF_\mathcal {A}$ will return a successful output. Let acc be the accepting probability of $\mathcal {A}$, or the probability that $J \ge 1$, and let h be the total number of possible outputs of H. Let $e'$ be the advantage of solving the discrete logarithm problem over some group $\mathbb {G}$. Recall that $n_r$ is the maximum number of random oracle outputs $\mathcal {A}$ may need to generate.

Lemma 1

Generalized Forking Lemma [3] Let frk be defined by the following probability:

$$ \text {frk} = Pr [b=1 : x \overset{\$}{\leftarrow }IG : (b, \sigma , \sigma ') \overset{\$}{\leftarrow }GF_\mathcal {A}(x)] $$

where IG is an input generator for a challenge input x. Then

$$ e' \ge \text {frk} \ge \text {acc} \cdot (\frac{\text {acc}}{n_r} - \frac{1}{h}) $$

Lemma 1 demonstrates the probability $e'$ that running the generalized forking algorithm $GF_\mathcal {A}$ will produce two valid forgeries $\sigma =(R, z)$ and $\sigma '=(R', z')$ along with their respective challenge responses from the random oracle $(h_J, h_J')$ over the same message m and public commitment R, and so enable the extraction of the desired discrete logarithm.

Embedding the Challenge Value During KeyGen. We use a coordination algorithm C described in Algorithm 2 to perform setup for $GF_\mathcal {A}$ and to derive the discrete logarithm of the challenge value $\omega$ afterward.

Simulating KeyGen. We now describe how C embeds the challenge value $\omega$ into the group public key Y during a simulation of the KeyGen phase; Y is in turn fed as input into $GF_\mathcal {A}$. For simplicity of notation, we let $n=t$ (where n is the total number of participants and t is the threshold), and $\mathcal {F}$ controls $t-1$ participants, and $\mathcal {A}$ simulates the $t^{\text {th}}$ (honest) participant to $\mathcal {F}$. The case for general n is similar.

For the first round of the key generation protocol, $\mathcal {A}$ simulates $P_t$ as follows. Let be the set of public commitments $\phi _{i1}, \dots , \phi _{i(t-1)}$ for participant $P_i$. To calculate and to distribute shares $f_t(1), \dots , f_t(t-1)$ to the $t-1$ participants corrupted by $\mathcal {F}$, $\mathcal {A}$ does the following:

• 1. Randomly generate $\bar{x}_{t1}, \dots , \bar{x}_{t(t-1)}$ to serve as the secret shares corresponding to $f_t(1), \dots , f_t(t-1)$

• 2. Set $\phi _{t0}$ to be the challenge value $\omega$

• 3. Calculate $\phi _{t1}, \dots , \phi _{t(t-1)}$ by performing Lagrange interpolation in the exponent, or $\phi _{tk} = \omega ^{\lambda _{k0} } \cdot g^{ \sum _{i=1}^{t-1} \lambda _{ki} \cdot \bar{x}_{ti}}$

$\mathcal {A}$ then broadcasts for $P_t$. For the second round, $\mathcal {A}$ sends $(1, \bar{x}_{t1}), \dots , (t-1, \bar{x}_{t(t-1)})$ to the participants $P_1, \dots , P_{t-1}$ corrupted by $\mathcal {F}$. Further, $\mathcal {A}$ simulates the proof of knowledge for $a_{t0}$ by deriving $\sigma$ as:

$$\begin{aligned} c_t, z \overset{\$}{\leftarrow }\mathbb {Z}_q\text {; }R = g^z \cdot \omega ^{-c_t}\text {; and } \sigma = (R, z) \end{aligned}$$

$\mathcal {A}$ derives the public key for $P_t$ by following the same steps they would use to calculate the public key for their peers (as the discrete log of the challenge value $\omega$ is unknown), by deriving $Y_t = \prod _{j=1}^n \prod _{k=0}^{t-1} \phi _{jk}^{t^k \bmod q}$.

The participants controlled by $\mathcal {F}$ can derive their private key shares $s_i$ by directly following the KeyGen protocol, then deriving $Y_i = g^{s_i}$. We will see in the proof for FROST-Interactive how $\mathcal {A}$ can still simulate signing for the honest party $P_t$ to $\mathcal {F}$ even without knowing its corresponding private key share. Each party (honest or corrupted by $\mathcal {F}$) can follow the KeyGen protocol to derive the group’s long-lived public key, by calculating $Y = \prod _{j=1}^n \phi _{j0}$.

In addition, C must obtain $\mathcal {F}$’s secret values $(a_{10}, \dots , a_{(t-1)0})$ using the extractor for the zero-knowledge proofs that $\mathcal {F}$ generates. C will use these values next in order to convert the discrete logarithm for the group public key Y into the discrete logarithm for the challenge value $\omega$.

Solving Discrete Logarithm of the Challenge. We now describe how two forged signatures $(\sigma , \sigma ')$ along with the challenge values from the random oracle query $(h_J, h_J')$ produced as output from $GF_\mathcal {A}$ can be used by C to extract the discrete logarithm of the challenge value $\omega$. We give an overview of the algorithm ExtractDLog in Algorithm 3, which C uses as a subroutine. Note that the advantage $e'$ used later in our proofs denotes the advantage of $C(\omega )$ of solving the discrete logarithm for the challenge value $\omega$.

We can compute dlog(Y), because

$$ R = g^z \cdot Y^{-h_J} = g^{z'} \cdot Y^{-h_{J}'} $$

and since $h_J \ne h_J'$, then

$$ dlog(Y) = \frac{(z'-z)}{(h_J'-h_J)} $$

The discrete logarithm corresponding to $\omega$ can then be extracted as follows:

$$\begin{aligned} a_{t0} = dlog(Y) - \sum _{i=1}^{t-1} a_{i0} = dlog(\omega ) \end{aligned}$$

(2)

As discussed in Sect. A.1, all of $\mathcal {F}$’s $a_{i0}, i \ne t$ values are known as these were extracted by $\mathcal {A}$ while performing the key generation protocol. Hence, C can extract $a_{t0}$ using Eq. 2, resulting in learning the discrete log of the challenge value $\omega$.

1.2 A.2  Proof of Security for FROST-Interactive

Due to the difficulty of simulating zero-knowledge proofs in parallel, for the purposes of proving the security of FROST, we will first prove security against an interactive two-round variant of the FROST signing operation, which we call FROST-Interactive. In Sect. 6.2, we discuss how the security for FROST-Interactive extends to plain FROST.

FROST-Interactive. FROST-Interactive uses the same KeyGen protocol to generate long-lived keys as regular FROST, as further described in Sect. 5.1. We present an overview of the Preprocess step for FROST-Interactive in Fig. 4, and the signing step in Fig. 5.

The distinction between the signing operations for plain FROST and FROST-Interactive is how the binding value $\rho _i$ is generated. Because of the difficulty of simulating non-interactive zero-knowledge proofs of knowledge (NIZKPKs) in a concurrent setting, we instantiate FROST-Interactive using a one-time VRF, from which each participant generates their value $\rho _i$ given the inputs (m, B). We prove this variant to be secure against the standard notion of EUF-CMA security.

Preprocess. The Preprocess phase for FROST-Interactive differs from FROST in two ways. First, participants additionally generate one-time VRF keys $(a_{ij}, b_{ij})$ and their commitments $(A_{ij} = g^{a_{ij}}, B_{ij} = g^{b_{ij}})$ along with the usual FROST nonce values $(d_{ij}, e_{ij})$ and their commitments $(D_{ij} = g^{d_{ij}}, E_{ij} = g^{e_{ij}})$ along with a zero-knowledge proof of knowledge for the $(a_{ij}, b_{ij})$ one-time VRF keys. These keys are later used to generate $\rho _i$ during the signing phase.

We require Preprocess for FROST-Interactive to be performed serially so that the simulator can efficiently extract the discrete logarithm of the adversary’s non-interactive zero knowledge proof of knowledge of its VRF keys via rewinding. In the setting of plain FROST, the Preprocess step can be performed non-interactively, and thus the requirement of performing this step serially is no longer relevant.

Sign. To perform signing, $\mathcal {SA}$ first sends (m, B) to each participant, and each participant responds with $\rho _i = a_{ij} + b_{ij} \cdot H_{\rho }(m, B)$, where B is derived similarly to in plain FROST via the ordered list of tuples $(i, D_{ij}, E_{ij}), i \in S$. In the second round, $\mathcal {SA}$ then sends each $\rho _i$ to each of the signing participants, who use these values to derive R and then to calculate their own response $z_i$.

Fig. 4.

FROST-interactive two-round preprocessing protocol

Fig. 5.

FROST-interactive two-round signing protocol

Proof of Security for FROST-Interactive. We now present a proof of EUF-CMA security for FROST-Interactive, demonstrating that an adversary that can compute forgeries acting against FROST-Interactive can be used to compute the discrete logarithm of an arbitrary challenge value.

Let $n_h$ be the number of queries made to the random oracle, $n_p$ be the number of allowed preprocess queries, and $n_s$ be the number of allowed signing queries.

Theorem 2

If the discrete logarithm problem in $\mathbb {G}$ is $(\tau ', \epsilon ')$-hard, then the FROST-Interactive signature scheme over $\mathbb {G}$ with n signing participants, a threshold of t, and a preprocess batch size of $\pi$ is $(\tau , n_h, n_p, n_s, \epsilon )$-secure whenever

$$ \epsilon ' \le \frac{\epsilon ^2}{2 n_h + (\pi +1) n_p + 1} $$

and

$$ \tau ' = 4\tau + (30\pi n_p + (4t-2)n_s + (n+t-1)t + 6) \cdot t_{exp} + O(\pi n_p + n_s + n_h + 1) $$

such that $t_{exp}$ is the time of an exponentiation in $\mathbb {G}$, assuming the number of participants compromised by the adversary is less than the threshold t.

Proof

We prove the theorem by contradiction. Assume that $\mathcal {F}$ can $(\tau , n_h, n_p, n_s, \epsilon )$-break the unforgeability property of FROST-Interactive. We will demonstrate that an algorithm C that can $(\tau ', \epsilon ')$-solve the discrete logarithm of an arbitrary challenge value $\omega \in \mathbb {G}$. We first describe the simulator $\mathcal {A}$, which uses $\mathcal {F}$ as a black-box forger.

We now describe how $\mathcal {A}$ simulates FROST-Interactive to $\mathcal {F}$ in Algorithm 4. Recall that $\mathcal {F}$ controls $t-1$ participants, and $\mathcal {A}$ simulates a single honest participant $P_t$.

Let $n_r = 2 n_h + (\pi + 1)n_p + 1$ denote the maximum number of random oracle outputs $\mathcal {A}$ may require.

After performing the key generation phase as described in Sect. A.1, $\mathcal {A}$ invokes $\mathcal {F}$ to perform its forgery attack. $\mathcal {A}$ simulates both the responses to the random oracle queries of $\mathcal {F}$ as well as the role of $P_t$ in the Preprocess and Sign algorithms.

Simulating Random Oracle Queries. For each random oracle query to $H_{\rho }$, $H_2$, $H_3$, and $H_4$, $\mathcal {A}$ responds by first checking a corresponding associative table (initialized to empty on start) to see if the output has already been determined for that query. If no such output exists, $\mathcal {A}$ sets the output to the next available value from $\{ h_1, \dots , h_{n_r} \}$ supplied by $GF_\mathcal {A}$ upon start, indicated by ctr. After setting the output, $\mathcal {A}$ increments ctr and returns the freshly assigned output. In lieu of the $H_1(i, m, B)$ hash function used in FROST (presented in Sect. 5.2), FROST-Interactive uses an interactive one-time VRF with input $H_{\rho }(m, B)$ to provide this binding mechanism.

Simulating Preprocess. To perform the Preprocess stage, $\mathcal {A}$ simulates the honest participant $P_t$, following the protocol honestly with exception of the following steps. When generating $D_{tj}$, $\mathcal {A}$ first picks $\bar{c}_j$ as the next available $h_{ctr}$ value, and keeps track of which one it used by setting $C[j] = ctr$ in a list C. $\mathcal {A}$ randomly selects $\bar{z}_{tj} \overset{\$}{\leftarrow }\mathbb {Z}_q$, and then derives $D_{tj} = g^{\bar{z}_{tj}} \cdot {Y_t}^{-\bar{c}_j}$.

$\mathcal {A}$ honestly computes and publishes its proof of knowledge of the $(a_{tj}, b_{tj})$ values in Round 2. However, during this round, $\mathcal {A}$ itself forks $\mathcal {F}$ in order to extract the discrete logarithms $(a_{\ell j}, b_{\ell j})$ of the commitment values $(A_{\ell j}, B_{\ell j})$ for all of the players $P_\ell$ controlled by $\mathcal {F}$. $\mathcal {A}$ is able to learn these values by rewinding $\mathcal {F}$ to the point before it makes the query $\Phi = H_3(K_1, \dots , K_t)$, and programming the random oracle to return a different random output $\Phi '$. Then, when $\mathcal {F}$ republishes $J_i : i \ne t$ for all dishonest parties that $\mathcal {F}$ controls, $\mathcal {A}$ can solve for the discrete log for each commitment.

Simulating Signing. $\mathcal {F}$ initiates the FROST-Interactive signing protocol in the role of $\mathcal {SA}$, sending (m, B) in Round 1. Upon receiving these values, $\mathcal {A}$ is able to compute not only its $\rho _t$, but also all of the other $\rho _\ell$ values for all of the other participants, because of its knowledge of the $(a_{\ell j}, b_{\ell j})$ that $\mathcal {A}$ obtained during Round 2 of the preprocessing stage. Using these $\rho _\ell$ values, it can compute the R that will be used in Round 2, and program $H_2(R, Y, m) = \bar{c}_j$. It also saves C[j], the ctr value such that $\bar{c}_k = h_{ctr}$, as $J_2[R, Y, m]$ in a table $J_2$.

Note that $\mathcal {A}$ is never required to guess which output from the random oracle to program to correctly issue a signature, because $\mathcal {A}$ can always compute R before $\mathcal {F}$ can, and consequently can program the random oracle $H_2(R, Y, m)$ with perfect success. Conversely, a signing request by $\mathcal {A}$ in the simulation for plain Schnorr succeeds only with probability $1/(n_h + n_s + 1)$ [3].

Finding the Discrete Logarithm of the Challenge Input. As described in Sect. A.1, using the two forgeries $(\sigma , \sigma ')$, the discrete logarithm of $\omega$ can be derived.

Recall that the probability of $\mathcal {F}$ succeeding for one run of $\mathcal {A}$ is simply $\epsilon$, as $\mathcal {A}$ can return the correct challenge for each signing query. Then, using the forking lemma, the probability that the discrete logarithm of $\omega$ can be extracted after $\mathcal {A}$ is run twice is at least $\frac{\epsilon ^2}{n_r}$ (ignoring the negligible $\frac{\epsilon }{h}$ term, as h—the number of possible hash outputs—is typically at least $2^{256}$), and the total time required to extract the discrete logarithm of the challenge value is:

$$ \tau ' = 4\tau + (30\pi n_p + (4t-2)n_s + (n+t-1)t + 6) \cdot t_{exp} + O(\pi n_p + n_s + n_h + 1) $$

The running time for C to compute the discrete logarithm by procuring two forgeries from FROST-Interactive is four times that for $\mathcal {F}$ (because of the forking of $\mathcal {A}$, which itself forks $\mathcal {F}$), plus the time to compute $(30\pi n_p + (4t-2)n_s + (n+t-1)t + 6)$ exponentiations:

• In simulating KeyGen, $(t-1)\cdot t$ to compute , 2 to compute R, and $n\cdot t$ to compute $Y_t$

• In each of two executions of $\mathcal {A}$:

  • 7 in each of $\pi$ iterations of Round 1 of simulating Preprocess,

  • 8$\pi$ to validate each of two versions of $t-1$ $J_\ell$ lists in Round 2 of simulating Preprocess,

  • $t-1$ to validate the $\rho _\ell$ and t to compute R in each simulation of Sign,

  • 2 to compute R to verify the output of $\mathcal {F}$.

and $O(\pi n_p + n_s + n_h + 1)$ other minor operations, such as table lookups.

1.3 A.3  Extension of FROST-Interactive to FROST

In this section, we describe the changes we make to FROST-Interactive to remove one round of communication in each of the Preprocess and the Sign phases. We argue in Sect. 6 why our changes do not harm the security of the protocol.

Removal of One-Time Verifiable Random Functions to Generate $\rho _i$. The primary difference between FROST-Interactive and FROST is that in the former, interactive one-time VRFs are used to generate the $\rho _i$ binding values. In FROST, on the other hand, these values are generated with random oracles (modelling hash functions). Removing the one-time VRFs removes the VRF keys $(a_{ij},b_{ij})$ and their commitments $(A_{ij}, B_{ij})$ from the protocol.

Removal of One Round of the Sign Phase. With the one-time VRFs removed, all participants can compute every other participants’ $\rho _i$ values non-interactively, and so the first round of the Sign protocol for FROST-Interactive (where participants exchange their $\rho _i$ values) is no longer necessary for FROST.

Removal of the Proofs of Knowledge of the One-Time VRF Keys and One Round of the Preprocess Phase. As the one-time VRF keys are removed, so are their proofs of knowledge $J_i$ in the Preprocess phase. Removing the $J_i$ then makes the $K_i$ unused, and removing the $K_i$ removes the first round of the Preprocess phase.