Internet-Draft FROST August 2020
Komlo & Goldberg Expires 8 February 2021 [Page]
Workgroup:
Crypto Forum Research Group
Internet-Draft:
draft-komlo-frost-00
Published:
Intended Status:
Informational
Expires:
Authors:
C. Komlo
University of Waterloo, Zcash Foundation
I. Goldberg
University of Waterloo

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. This draft describes 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 number of participants are required for 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 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.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on 8 February 2021.

Table of Contents

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 [GGK_15], or to sign a network consensus produced by a set of trusted authorities [MOT_11]. 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 [BLS04] [BDN18], 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 [SS01] [GJKR03] require at least three rounds of communication during signing operations, whereas constructions with fewer network rounds [GJKR03] must limit signing concurrency to protect against a forgery attack [DEF_19].

This draft describes 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. (Signatures generated using the FROST protocol can also be referred to as "FROSTy signatures".) 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 [GJKR03] [DJN_20], 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.

Organization. We describe background information important to understanding FROST in Section 2, and in Section 3 we review notation and security assumptions. Section 4 describes the FROST protocol, and Section 5 reviews security considerations for FROST. In Section 6 we describe implementation considerations.

2. Background

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 [Sha79], 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 a1, ..., at-1 at random, and uses the randomly selected values as coefficients to define a polynomial f(x) = s + SUM(ai xi, i=1...t-1) of degree t-1 where f(0) = s. The secret shares for each participant Pi are subsequently (i, f(i)), which the dealer is trusted to distribute honestly to each participant P1, ..., Pn. 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 [Fel87] 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 (a1, ..., at-1), and uses these values as coefficients to define a polynomial fi of degree t-1 such that f(0) = s. However, along with distributing the private share (i, f(i)) to each participant Pi, the dealer also distributes the public commitment

C = < A0, ..., At-1 >, where A0 = gs and Aj = g^{aj}

Note that in a distributed setting, each participant Pi must be sure to have the same view of C 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.

2.2. 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 [Sch89]. We introduce Schnorr signatures in Section 2.4.

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 s1, ..., sn often require generating shares using a less-trusted method than relying on a central dealer. Instead, these schemes (including FROST) make use of a Distributed Key Generation (DKG) protocol, which we describe next.

2.3. Distributed Key Generation

While some threshold schemes such as Shamir secret sharing rely on a trusted dealer to generate and distribute secret shares to all participants, not all threat models can allow for such a high degree of trust in a single individual. Distributed Key Generation (DKG) supports such threat models by enabling every participant to contribute 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 si of the corresponding secret s such that no set of participants smaller than the threshold knows s.

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

2.4. Schnorr Signatures

Often, it is desirable for signatures produced by threshold signing operations to be indistinguishable from signatures produced by a single participant, consequently remaining backwards compatible with existing systems, and also preventing a privacy leak of the identities of the individual signers. For our work, we require signatures produced by FROST signing operations to be indistinguishable from Schnorr signatures, and thus verifiable using the standard Schnorr verification operations. To this end, we now describe Schnorr signing and verification operations [Sch89] in a single-signer setting.

Let G be a group with prime order q and generator g, and let H be a cryptographic hash function mapping to Zq*. A Schnorr signature is generated over a message m by the following steps:

  1. Sample a random nonce k <-$- Zq; compute the commitment R = gk in G
  2. Compute the challenge c = H(m,R)
  3. Using the secret key s, compute the response z = k + s * c in Zq
  4. Define the signature over m to be SIG = (z, c)

Validating the integrity of m using the public key Y=gs and the signature SIG is performed as follows:

  1. Parse SIG as (z, c).
  2. Compute R' = gz * Y-c
  3. Compute c' = H(m, R')
  4. Output 1 if c = c' to indicate success; otherwise, output 0.

Schnorr signatures are simply the standard Sigma-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.5. Additive Secret Sharing

Similarly to the single-party setting described above, FROST requires generating a random nonce k for each signing operation. However, in the threshold setting, k should be generated in such a way that each participant contributes to but does not know the resulting k (properties that performing a DKG as described in Section 2.3 also achieve). Key to the design of FROST is the observation that while an arbitrary t out of n entities are required to participate in a signing operation, a simpler t-out-of-t scheme will suffice to generate the random nonce k.

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 t participants to jointly compute a shared secret s by each participant Pi contributing a value si such that the resulting shared secret is s=SUM(si, i=1...t), the summation of each participant's share. Consequently, this t-out-of-t secret sharing can be performed non-interactively; each participant directly chooses their own si.

Benaloh and Leichter [BL88] generalize this scheme to arbitrary monotone access structures, and Cramer, Damgaerd, and Ishai [CDI05] present a non-interactive mechanism for participants to locally convert additive shares generated via the Benaloh and Leichter t-out-of-n additive secret sharing construction to polynomial (Shamir) form. In our work, we use the simplest t-out-of-t case of this transformation, in which, if si are additive secret shares of s, so that s is the sum of the si, then (si)/(Li) are Shamir secret shares of the same s, where the Li are Lagrange coefficients.

In FROST, participants use this technique during signing operations to non-interactively generate a one-time secret nonce (as is required by Schnorr signatures, described in Section 2.4) that is Shamir secret shared among all t signing participants.

2.6. Attacks on Parallelized Schnorr Multisignatures

Attack via Wagner's Algorithm. We next describe an attack recently introduced by Drijvers et al. [DEF_19] against some two-round Schnorr multisignature schemes and describe how this attack applies to a threshold 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.

Successfully performing the Drijvers attack requires finding a hash output c* = H(m*, R*) that is the sum of T other hash outputs c* = SUM(H(mj, Rj), j=1...T) (where c* is the challenge, mj the message, and Rj the commitment corresponding to a standard Schnorr signature as described in Section 2.4). 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 Rj or the message being signed mj. Drijvers et al. use the k-tree algorithm of Wagner [Wag02] to find such hashes and perform the attack in time O(K * b * 2b/(1+lg K)), where K = 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 with the same parameters for an adversary that controls up to t-1 participants. We note that the threshold scheme instantiated using Pedersen's DKG by Gennaro et al. [GJKR03] is likewise affected by this technique and so similarly has an upper bound to the amount of parallelism that can be safely allowed.

In Section 4.2 we discuss how FROST avoids the attack by ensuring that an attacker will not gain an advantage by adaptively choosing its own commitment (or that of any other of the signing participants) used to determine Rj, or adaptively selecting the message being signed.

Drijvers et al. [DEF_19] also present a metareduction for the proofs of several Schnorr multisignature schemes in the literature that use a generalization of the forking lemma with rewinding, proving that the security demonstrated in a single-party setting does not extend when applying this proof technique to a multi-party setting.

Attack via ROS Solver. Benhamouda et al. [BLOR20] recently present an efficient algorithm solving the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem. The authors demonstrate that threshold schemes using Gennaro et al.'s DKG [GJKR07] and multisignature schemes such as two-round MuSig [MPSW19] 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. Preliminaries

Let G be a group of prime order q in which the Decisional Diffie-Hellman problem is hard, and let g be a generator of G. Let H be a cryptographic hash function mapping to Zq*. We denote by x <-$- S that x is uniformly randomly selected from S.

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 Pi where 1 <= i <= n. Let si be the long-lived secret share for participant Pi. Let Y denote the long-lived public key shared by all participants in the threshold signature scheme, and let Yi = g^{si} be the public key share for the participant Pi. Finally, let m be the message to be signed.

For a fixed set S = {p1,...,pt} of t participant identifiers in the signing operation, let Li = PROD( (pj)/(pj - pi), j=1...t, j != i) denote the ith Lagrange coefficient for interpolating over S. Note that the information to derive these values depends on which t (out of n) participants are selected, and uses only the participant identifiers, and not their shares. (Note that if n is small, the Li for every possible S can be precomputed by each participant during the key generation phase of the protocol as a performance optimization to avoid re-computing these values for each signing operation.)

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

4. FROST: Flexible Round-Optimized Schnorr Threshold Signatures

We now describe the FROST protocol, 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. Prior threshold signature constructions [SS01] [GJKR03] provide the property of robustness; if one participant misbehaves and provides malformed shares, the remaining honest participants can detect the misbehaviour, exclude the misbehaving participant, and complete the protocol, so long as the number of remaining honest participants is at least the threshold t. This kind of robust construction is appropriate in settings where signing participants might be arbitrary entities from the Internet, for example.

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. The honest participants can then simply re-run the protocol amongst themselves, excluding the misbehaving participant. Consequently, FROST trades off robustness in the protocol for improved efficiency in this way.

Signature Aggregator Role. We instantiate FROST using a semi-trusted signature aggregator role, denoted as SA. Such a role is often practical in a real-world setting; we include this role as it also allows for improved efficiency. However, FROST can be instantiated without a signature aggregator. To do so, each participant simply performs a broadcast in place of 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 Yi. SA is trusted to report misbehaving participants (we assume participants can authenticate themselves to one another, as discussed in Section 3) and to publish the group's signature at the end of the protocol. If SA deviates from the protocol, the protocol remains secure against adaptive chosen message attacks, as SA is not given any more of a privileged view than the adversary we model. A malicious 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 [GJKR03] as an optimization.

4.1. Key Generation

FROST KeyGen

Round 1

1.
Every participant Pi samples t random values (ai0, ..., ai(t-1))) <-$- Zq, and uses these values as coefficients to define a polynomial fi(x) = SUM(aij xj, j=0...t-1) of degree t-1 over Zq.
2.
Every Pi computes a proof of knowledge to the corresponding secret ai0 by calculating a Schnorr signature SIGi = (wi, ci) using ai0 as the secret key, such that k <-$- Zq, Ri = gk, ci = H(i, CTX, g^{ai0}, Ri), wi = k + ai0* ci, with CTX being a context string to prevent replay attacks.
3.
Every participant Pi computes a public commitment Ci = < Ai0, ..., Ai(t-1) >, where Aij = g^{aij}, 0 <= j <= t-1
4.
Every Pi broadcasts Ci, SIGi to all other participants.
5.
Upon receiving Cp, SIGp from participants 1 <= p <= n, p != i, participant Pi verifies SIGp = (wp, cp), aborting on failure, by checking: cp =?= H(p, CTX, Ap0, g^{wp} * Ap0^{-cp})

Round 2

1.
Each Pi securely sends to each other participant Pp a secret share (p, fi(p)), and keeps (i, fi(i)) for themselves.
2.
Each Pi verifies their shares by calculating: g^{fp(i)} =?= PROD(Apk(i^k mod q),k=0...t-1), aborting if the check fails.
3.
Each Pi calculates their long-lived private signing share by computing si = SUM(fp(i), p=1...n), and stores si securely.
4.
Each Pi calculates their public verification share Yi = g^{si}, and the group's public key Y = PROD(Aj0, j=1...n). Any participant can compute the public verification share of any other participant by calculating Yi = PROD( (Ajk)(i^k mod q), j=1...n, k=0...t-1)

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 the above algorithm. 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 ai0 by providing other participants with proof in zero knowledge, instantiated as a Schnorr signature, to protect against rogue-key attacks [BBS03] in the setting where t >= 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 Pi holds a value (i, si) that is their long-lived secret signing share. Participant Pi's public key share Yi = g^{si} is used by other participants to verify the correctness of Pi'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 Ci, 1 <= i <= n 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 Section 2.1 where we described techniques to achieve this guarantee in practice.

Security tradeoffs. While Gennaro et al. [GJKR07] 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. [GJKR07]. 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.

4.2. Threshold Signing with Unrestricted Parallelism

We now introduce the signing protocol for FROST. This operation builds upon known techniques in the literature [AAM20] [GJKR03] by employing additive secret sharing and share conversion in order 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 simple two-round protocol if desired.

As a reminder, the attack of Drijvers et al. [DEF_19] 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.

Preprocess(Q) -> (i, Di1, Ei1, ..., DiQ, EiQ)

Each participant Pi, i in {1, ..., n} performs this stage prior to signing. Let j be a counter for a specific nonce/commitment share pair, and Q be the number of pairs generated at a time, such that Q signing operations can be performed before performing another preprocess step.

1.

Create an empty list Li. Then, for 1 <= j <= Q, perform the following:

1.a
Sample single-use nonces (dij, eij) <-$- Zq* x Zq*
1.b
Derive commitment shares (Dij, Eij) = (g^{dij}, g^{eij}).
1.c
Append (Dij, Eij) to Li. Store ((dij, Dij), (eij, Eij)) for later use in signing operations.
2.
Publish (i, Li) to a predetermined location, as specified by the implementation.

Preprocessing Stage. We present above a preprocessing stage where participants generate and publish Q commitments at a time. In this setting, Q determines the number of nonces that are generated and their corresponding commitments that are published in a single preprocess step, and correspondingly the number of signing operations that can be performed before the participant must perform this preprocessing stage again. Note that implementations that do not wish to cache commitments can instead use a two-round protocol, where participants publish a single commitment to each other in the first round.

Each participant Pi begins by generating a list of single-use private nonce pairs and corresponding public commitment shares ((dij, Dij = g^{dij}), (eij, Eij = g^{eij})) for j=1,...,Q, where j is a counter that identifies the next nonce/commitment share pair available to use for signing. Each Pi then publishes (i, Li), where Li is their list of commitment shares Li = <(Dij, Eij) for j=1,...,Q>. The location where participants publish these values can depend on the implementation; options include broadcasting to all other participants or publishing to a centralized location that all participants can access (we discuss these options further in Section 6). The set of (i, Li) tuples are then stored by any entity that might perform the signature aggregator role during signing.

Sign(m) -> (m, SIG)

Let SA denote the signature aggregator (who themselves can be one of the t signing participants). Let S be the set of participants selected for use for this signing operation. Let B = < (i, Dij, Eij) for i in S> denote the ordered list of participant indices corresponding to each participant Pi, and Li be the set of available commitment values for Pi that were published during the Preprocess stage. Each identifier i is coupled with the jth commitments (Dij, Eij) published by Pi that will be used for this particular signing operation. Let H1, H2 be hash functions whose outputs are in Zq*.

1.
SA begins by fetching the next available commitment for each participant Pi in S from Li and constructs B.
2.
For each i in S, SA sends Pi the tuple (m, B).
3.
After receiving (m, B), each Pi first validates the message m, and then checks Dp j, Ep j in G* for each commitment in B, aborting if either check fails.
4.
Each Pi then computes the set of binding values rp = H1(p, m, B), p in S. Each Pi then derives the group commitment R = PROD(Dpj * (Epj)^{rp}, p in S), and the challenge c = H2(m, R).
5.
Each Pi computes their response using their long-lived secret share si by computing zi = dij + (eij * ri) + Li * si * c, using S to determine Li.
6.
Each Pi securely deletes ((dij, Dij), (eij, Eij)) from their local storage, and then returns zi to SA.
7.

The signature aggregator SA performs the following steps:

7.a
Derive ri = H1(i,m,B) and Ri = Dij * (Eij)^{ri} for i in S, and subsequently R=PROD(Ri, i in S) and c = H2(m,R).
7.b
Verify the validity of each response by checking g^{zi} =?= Ri * {Yi}^{c * Li} for each signing share zi, i in S. If the equality does not hold, first identify and report the misbehaving participant, and then abort. Otherwise, continue.
7.c
Compute the group's response z = SUM(zi, i in S)
7.d
Publish the signature SIG = (z, c) along with the message m.

Signing Protocol. At the beginning of the signing protocol above, SA selects t participants (possibly including itself) to participate in the signing. Let S be the set of those t participants. SA then selects the next available commitment (Dij, Eij) for each participant in S, which are later used to generate a secret share to a random commitment R for the signing group. (Each participant contributes to the group commitment R, which corresponds to the commitment gk to the nonce k in step 1 of the single-party Schnorr signature scheme in Section 2.4.) This technique is a t-out-of-t additive secret sharing; the resulting secret nonce is k = SUM(ki, i in S), where each ki = dij + eij * ri (we next describe how participants calculate ri), and (dij, eij) correspond to the (Dij = g^{dij}, Eij=g^{eij}) values published during the Preprocess stage. Recall from Section 2.5 that if the ki are additive shares of k, then each (ki)/(Li) are t-out-of-t Shamir shares of k.

After these steps, SA then creates the set B, where B is the ordered list of tuples <(i, Dij, Eij) for i in S>. SA then sends (m, B) to every Pi, i in S.

After receiving (m, B) from 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" ri, i in S such that ri = H1(i, m, B), where H1 is a hash function whose outputs are in Zq*.

Each participant can then compute the commitment Ri for each participant in S by deriving Ri = Dij * (Eij)^{ri}. Doing so binds the message, the set of signing participants, and each participant's commitment to each signature share, such that signature shares on one message cannot be used for another, assuming that (dij, eij) remain secret and are used only once. This binding technique thwarts the attack of Drijvers et al. described in Section 2.6 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(Ri, i in S). As in single-party Schnorr signatures, each participant computes the challenge c = H2(m,R).

Each participant's response zi to the challenge can be computed using the single-use nonces (dij, eij) and the long-term secret shares si, which are t-out-of-n (degree t-1) Shamir secret shares of the group's long-lived secret key s. Recalling that (ki)/(Li) are degree t-1 Shamir secret shares of k, we see that (ki)/(Li) + si * c are degree t-1 Shamir secret shares of the correct response z = k + s * c for a plain (single-party) Schorr signature. Using share conversion again, and that ki = dij + (eij * ri), we get that zi = dij + (eij * ri) + Li * si * c are t-out-of-t additive shares of z.

SA finally checks the consistency of each participant's reported zi with their commitment share (Dij, Eij) and their public key share Yi. If every participant issued a correct zi, then the sum of the zi values, along with c, forms the Schnorr signature on m. This signature will verify properly to a verifier unaware that FROST was used to generate the signature, and who checks it with the standard single-party Schnorr verification equation with Y as the public key (Section 2.4).

Handling Ephemeral Outstanding Shares. Because each nonce and commitment share generated during the preprocessing stage described in the Preprocess algorithm must be used at most once, participants delete these values after using them in a signing operation, as indicated in Step 5 in the Sign algorithm. An accidentally reused (dij, eij) can lead to exposure of the participant's long-term secret si, so participants must securely delete them, and defend against snapshot rollback attacks as in any implementation of Schnorr signatures.

However, if SA chooses to re-use a commitment set (Dij, Eij) during the signing protocol, doing so simply results in the participant Pi aborting the protocol, and consequently does not increase the power of SA.

5. Security Considerations

5.1. Proof of Security Properties

We present proofs and arguments of security in our technical report [KG20] to show that FROST is secure against chosen-message attacks, assuming the discrete logarithm problem is hard and the adversary controls fewer participants than the threshold. The strategy is as follows. We first define an intermediate protocol called FROST-Interactive that has one extra round of communication in each of the Preprocess and Sign phases, and prove the security of FROST-Interactive in the random oracle model. We then give a heuristic argument that the differences between FROST-Interactive and FROST itself do not adversely affect its security.

5.2. Aborting on Misbehaviour

As discussed above, the goal of FROST is to save communication rounds (particularly at signing time), at the cost of sacrificing robustness. Consequently, FROST requires participants to abort once they have detected misbehaviour.

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

6. Operational Considerations

6.1. Publishing Commitments to a Commitment Server

The preprocessing step for FROST in Section 4.2 requires some agreed-upon location for participants to publish their commitments to. We now discuss choices for such a location for implementations, and possible security implications.

While participants could simply broadcast commitments to each other, this approach requires memory overhead and possibly coordination effort. Alternatively, implementations may wish to employ a commitment server specifically tasked with performing and managing of participants' commitment shares. While the commitment server may be a separate entity, we note that the signature aggregator SA can also provide this service in addition to its other duties. In this setting, the commitment server is trusted to provide the correct (i.e, valid and unused) commitment shares upon request. If the commitment server chose to act maliciously, it could either prevent participants from performing the protocol by denial of service, or it could provide stale or malformed commitment values on behalf of honest participants, causing uncertainty as to whether the commitment server or the participant was the misbehaving entity. However, simply having access to the set of a participant's public published commitments does not grant any additional powers, and a misbehaving commitment server (or SA) that provides old commitment values for a signing operation simply results in either a denial of service or an invalid signature. If SA assumes the commitment server role itself, any uncertainty as to who is the cause of misbehaviour can be avoided, and allows SA to carry out their role to report misbehaviour when it occurs.

6.2. Adaptively Choosing the Set of Signing Participants

While FROST requires exactly t signers due to the structure of non-interactively generating the nonce k (more specifically, so participants can determine Li during signing), implementations can still adaptively choose signing participants based on their availability if the implementation does not wish to assume which t signers are online and available when beginning a FROST signing operation.

How implementations should determine the availability of participants, and select which t participants will perform signing, falls outside FROST, and will depend on the implementation details of the communications among the participants. In the worst case, however, implementations can simply add an additional round before performing the FROST signing protocol, during which participants can demonstrate their availability and coordinate how available signers are selected to perform the signing round (such as using some simple tie-breaking exercise or ordering rule).

7. Acknowledgments

We thank Douglas Stebila for his helpful observations on the proof of security and deriving security bounds. We thank Richard Barnes for his helpful discussion on practical constraints and for identifying significant optimizations to a prior version of FROST, which our final version of FROST builds upon.

We thank George Tankersley, Henry DeValence, Deirdre Connolly, and Ian Miers for their feedback and discussions about real-world applications of threshold signatures. We thank Omer Shlomovits and Elichai Turkel for pointing out the case of rogue-key attacks in plain Ped-DKG and the suggestion to use a proof of knowledge for ai0 as a prevention mechanism.

We acknowledge the helpful description of additive secret sharing and share conversion as a useful technique to non-interactively generate secrets for Shamir secret-sharing schemes by Lueks [Lue17],S.2.5.2.

8. Informative References

[AAM20]
Abidin, A., Aly, A., and M.A. Mustafa, "Collaborative Authentication Using Threshold Cryptography", Emerging Technologies for Authorization and Authentication , .
[BBS03]
Bellare, M., Boldyreva, A., and J. Staddon, "Randomness Re-use in Multi-recipient Encryption Schemeas", Public Key Cryptography , .
[BDN18]
Boneh, D., Drijvers, M., and G. Neven, "Compact Multi-signatures for Smaller Blockchains", ASIACRYPT , .
[BL88]
Benaloh, J. and J. Leichter, "Generalized Secret Sharing and Monotone Functions", CRYPTO , .
[BLOR20]
Benhamouda, F., Lepoint, T., Orrù, M., and M. Raykova, "On the (in)security of ROS", , <https://eprint.iacr.org/2020/945>.
[BLS04]
Boneh, D., Lynn, B., and H. Shacham, "Short Signatures from the Weil Pairing", Journal of Cryptology , .
[CDI05]
Cramer, R., Damgård, I., and Y. Ishai, "Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation", Theory of Cryptography , .
[DEF_19]
Drijvers, M., Edalatnejad, K., Ford, B., Kiltz, E., Loss, J., Neven, G., and I. Stepanovs, "On the Security of Two-Round Multi-Signatures", 2019 IEEE Symposium on Security and Privacy (SP) , .
[DJN_20]
Damgård, I., Jakobsen, T.P., Nielsen, J.B., Pagter, J.I., and M.B. Østergård, "Fast Threshold ECDSA with Honest Majority", , <https://eprint.iacr.org/2020/501>.
[Fel87]
Feldman, P., "A Practical Scheme for Non-interactive Verifiable Secret Sharing", Proceedings of the 28th Annual Symposium on Foundations of Computer Science , .
[GGK_15]
Goldfeder, S., Gennaro, R., Kalodner, H., Bonneau, J., Kroll, J.A., Felten, E.W., and A. Narayanan, "Securing Bitcoin wallets via a new DSA/ECDSA threshold signature scheme", .
[GJKR03]
Gennaro, R., Jarecki, S., Krawczyk, H., and T. Rabin, "Secure Applications of Pedersen's Distributed Key Generation Protocol", Topics in Cryptology - CT-RSA 2003 , .
[GJKR07]
Gennaro, R., Jarecki, S., Krawczyk, H., and T. Rabin, "Secure Distributed Key Generation for Discrete-Log Based Cryptosystems", Journal of Cryptology , .
[KG20]
Komlo, C. and I. Goldberg, "FROST: Flexible Round-Optimized Schnorr Threshold Signatures", , <https://eprint.iacr.org/2020/852>.
[Lue17]
Lueks, W., "Security and Privacy via Cryptography -- Having your cake and eating it too", .
[MOT_11]
Mittal, P., Olumofin, F., Troncoso, C., Borisov, N., and I. Goldberg, "PIR-Tor: Scalable Anonymous Communication Using Private Information Retrieval", 20th USENIX Security Symposium , .
[MPSW19]
Maxwell, G., Poelstra, A., Seurin, Y., and P. Wuille, "Simple Schnorr multi-signatures with applications to Bitcoin", Designs, Codes and Cryptography , .
[Ped91]
Pedersen, T.P., "A Threshold Cryptosystem without a Trusted Party (Extended Abstract)", EUROCRYPT '91 , .
[SS01]
Stinson, D.R. and R. Strobl, "Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates", Proceedings of the 6th Australasian Conference on Information Security and Privacy , .
[Sch89]
Schnorr, C., "Efficient Identification and Signatures for Smart Cards", CRYPTO , .
[Sha79]
Shamir, A., "How to share a secret", Communications of the ACM , .
[Wag02]
Wagner, D., "A Generalized Birthday Problem", CRYPTO , .

Authors' Addresses

Chelsea Komlo
University of Waterloo, Zcash Foundation
Ian Goldberg
University of Waterloo