idnits 2.17.1 draft-komlo-frost-00.txt: -(913): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == There are 4 instances of lines with non-ascii characters in the document. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (7 August 2020) is 1351 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 1 error (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Crypto Forum Research Group C. Komlo 3 Internet-Draft University of Waterloo, Zcash Foundation 4 Intended status: Informational I. Goldberg 5 Expires: 8 February 2021 University of Waterloo 6 7 August 2020 8 FROST: Flexible Round-Optimized Schnorr Threshold Signatures 9 draft-komlo-frost-00 11 Abstract 13 Unlike signatures in a single-party setting, threshold signatures 14 require cooperation among a threshold number of signers each holding 15 a share of a common private key. Consequently, generating signatures 16 in a threshold setting imposes overhead due to network rounds among 17 signers, proving costly when secret shares are stored on network- 18 limited devices or when coordination occurs over unreliable networks. 19 This draft describes FROST, a Flexible Round-Optimized Schnorr 20 Threshold signature scheme that reduces network overhead during 21 signing operations while employing a novel technique to protect 22 against forgery attacks applicable to similar schemes in the 23 literature. FROST improves upon the state of the art in Schnorr 24 threshold signature protocols, as it can safely perform signing 25 operations in a single round without limiting concurrency of signing 26 operations, yet allows for true threshold signing, as only a 27 threshold number of participants are required for signing operations. 28 FROST can be used as either a two-round protocol where signers send 29 and receive two messages in total, or optimized to a single-round 30 signing protocol with a pre-processing stage. FROST achieves its 31 efficiency improvements in part by allowing the protocol to abort in 32 the presence of a misbehaving participant (who is then identified and 33 excluded from future operations)--a reasonable model for practical 34 deployment scenarios. 36 Status of This Memo 38 This Internet-Draft is submitted in full conformance with the 39 provisions of BCP 78 and BCP 79. 41 Internet-Drafts are working documents of the Internet Engineering 42 Task Force (IETF). Note that other groups may also distribute 43 working documents as Internet-Drafts. The list of current Internet- 44 Drafts is at https://datatracker.ietf.org/drafts/current/. 46 Internet-Drafts are draft documents valid for a maximum of six months 47 and may be updated, replaced, or obsoleted by other documents at any 48 time. It is inappropriate to use Internet-Drafts as reference 49 material or to cite them other than as "work in progress." 51 This Internet-Draft will expire on 8 February 2021. 53 Copyright Notice 55 Copyright (c) 2020 IETF Trust and the persons identified as the 56 document authors. All rights reserved. 58 This document is subject to BCP 78 and the IETF Trust's Legal 59 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 60 license-info) in effect on the date of publication of this document. 61 Please review these documents carefully, as they describe your rights 62 and restrictions with respect to this document. Code Components 63 extracted from this document must include Simplified BSD License text 64 as described in Section 4.e of the Trust Legal Provisions and are 65 provided without warranty as described in the Simplified BSD License. 67 Table of Contents 69 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 70 2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 4 71 2.1. Threshold Schemes . . . . . . . . . . . . . . . . . . . . 4 72 2.2. Threshold Signature Schemes . . . . . . . . . . . . . . . 5 73 2.3. Distributed Key Generation . . . . . . . . . . . . . . . 6 74 2.4. Schnorr Signatures . . . . . . . . . . . . . . . . . . . 6 75 2.5. Additive Secret Sharing . . . . . . . . . . . . . . . . . 7 76 2.6. Attacks on Parallelized Schnorr Multisignatures . . . . . 8 77 3. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 9 78 4. FROST: Flexible Round-Optimized Schnorr Threshold 79 Signatures . . . . . . . . . . . . . . . . . . . . . . . 10 80 4.1. Key Generation . . . . . . . . . . . . . . . . . . . . . 11 81 4.2. Threshold Signing with Unrestricted Parallelism . . . . . 13 82 5. Security Considerations . . . . . . . . . . . . . . . . . . . 18 83 5.1. Proof of Security Properties . . . . . . . . . . . . . . 18 84 5.2. Aborting on Misbehaviour . . . . . . . . . . . . . . . . 18 85 6. Operational Considerations . . . . . . . . . . . . . . . . . 18 86 6.1. Publishing Commitments to a Commitment Server . . . . . . 18 87 6.2. Adaptively Choosing the Set of Signing Participants . . . 19 88 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 19 89 8. Informative References . . . . . . . . . . . . . . . . . . . 20 90 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 21 92 1. Introduction 94 Threshold signature schemes are a cryptographic primitive to 95 facilitate joint ownership over a private key by a set of 96 participants, such that a threshold number of participants must 97 cooperate to issue a signature that can be verified by a single 98 public key. Threshold signatures are useful across a range of 99 settings that require a distributed root of trust among a set of 100 equally trusted parties. 102 Similarly to signing operations in a single-party setting, some 103 implementations of threshold signature schemes require performing 104 signing operations at scale and under heavy load. For example, 105 threshold signatures can be used by a set of signers to authenticate 106 financial transactions in cryptocurrencies [GGK_15], or to sign a 107 network consensus produced by a set of trusted authorities [MOT_11]. 108 In both of these examples, as the number of signing parties or 109 signing operations increases, the number of communication rounds 110 between participants required to produce the joint signature becomes 111 a performance bottleneck, in addition to the increased load 112 experienced by each signer. This problem is further exacerbated when 113 signers utilize network-limited devices or unreliable networks for 114 transmission, or protocols that wish to allow signers to participate 115 in signing operations asynchronously. As such, optimizing the 116 network overhead of signing operations is highly beneficial to real- 117 world applications of threshold signatures. 119 Today in the literature, the best threshold signature schemes are 120 those that rely on pairing-based cryptography [BLS04] [BDN18], and 121 can perform signing operations in a single round among participants. 122 However, relying on pairing-based signature schemes is undesirable 123 for some implementations in practice, such as those that do not wish 124 to introduce a new cryptographic assumption, or that wish to maintain 125 backwards compatibility with an existing signature scheme such as 126 Schnorr signatures. Surprisingly, today's best non-pairing-based 127 threshold signature constructions that produce Schnorr signatures 128 with unlimited concurrency [SS01] [GJKR03] require at least three 129 rounds of communication during signing operations, whereas 130 constructions with fewer network rounds [GJKR03] must limit signing 131 concurrency to protect against a forgery attack [DEF_19]. 133 This draft describes FROST, a Flexible Round-Optimized Schnorr 134 Threshold signature scheme that addresses the need for efficient 135 threshold signing operations while improving upon the state of the 136 art to ensure strong security properties _without_ limiting the 137 parallelism of signing operations. (Signatures generated using the 138 FROST protocol can also be referred to as "FROSTy signatures".) 139 FROST can be used as either a two-round protocol where signers send 140 and receive two messages in total, or optimized to a (non-broadcast) 141 single-round signing protocol with a pre-processing stage. FROST 142 achieves improved efficiency in the optimistic case that no 143 participant misbehaves. However, in the case where a misbehaving 144 participant contributes malformed values during the protocol, honest 145 parties can identify and exclude the misbehaving participant, and re- 146 run the protocol. 148 The flexible design of FROST lends itself to supporting a number of 149 practical use cases for threshold signing. Because the preprocessing 150 round can be performed separately from the signing round, signing 151 operations can be performed _asynchronously_; once the preprocessing 152 round is complete, signers only need to receive and eventually reply 153 with a single message to create a signature. Further, while some 154 threshold schemes in the literature require all participants to be 155 active during signing operations [GJKR03] [DJN_20], and refer to the 156 threshold property of the protocol as merely a security property, 157 FROST allows any threshold number of participants to produce valid 158 signatures. Consequently, FROST can support use cases where a subset 159 of participants (or participating devices) can remain offline, a 160 property that is often desirable for security in practice. 162 *Organization.* We describe background information important to 163 understanding FROST in Section 2, and in Section 3 we review notation 164 and security assumptions. Section 4 describes the FROST protocol, 165 and Section 5 reviews security considerations for FROST. In 166 Section 6 we describe implementation considerations. 168 2. Background 170 2.1. Threshold Schemes 172 Cryptographic protocols called _(t,n)-threshold schemes_ allow a set 173 of n participants to share a secret s, such that any t out of the n 174 participants are required to cooperate in order to recover s, but any 175 subset of fewer than t participants cannot recover any information 176 about the secret. 178 *Shamir Secret Sharing.* Many threshold schemes build upon Shamir 179 secret sharing [Sha79], a (t,n)-threshold scheme that relies on 180 Lagrange interpolation to recover a secret. In Shamir secret 181 sharing, a trusted central dealer distributes a secret s to n 182 participants in such a way that any cooperating subset of t 183 participants can recover the secret. To distribute this secret, the 184 dealer first selects t-1 coefficients a_(1), ..., a_(t-1) at random, 185 and uses the randomly selected values as coefficients to define a 186 polynomial f(x) = s + SUM(a_(i) x^(i), i=1...t-1) of degree t-1 where 187 f(0) = s. The secret shares for each participant P_(i) are 188 subsequently (i, f(i)), which the dealer is trusted to distribute 189 honestly to each participant P_(1), ..., P_(n). To reconstruct the 190 secret, at least t participants perform Lagrange interpolation to 191 reconstruct the polynomial and thus find the value s=f(0). However, 192 no group of fewer than t participants can reconstruct the secret, as 193 at least t points are required to reconstruct a polynomial of degree 194 t-1. 196 *Verifiable Secret Sharing.* Feldman's Verifiable Secret Sharing 197 (VSS) Scheme [Fel87] builds upon Shamir secret sharing, adding a 198 verification step to demonstrate the consistency of a participant's 199 share with a public _commitment_ that is assumed to be correctly 200 visible to all participants. To validate that a share is well 201 formed, each participant validates their share using this commitment. 202 If the validation fails, the participant can issue a _complaint_ 203 against the dealer, and take actions such as broadcasting this 204 complaint to all other participants. FROST similarly uses this 205 technique as well. 207 The commitment produced in Feldman's scheme is as follows. As before 208 in Shamir secret sharing, a dealer samples t-1 random values (a_(1), 209 ..., a_(t-1)), and uses these values as coefficients to define a 210 polynomial f_(i) of degree t-1 such that f(0) = s. However, along 211 with distributing the private share (i, f(i)) to each participant 212 P_(i), the dealer also distributes the public commitment 214 C = < A_(0), ..., A_(t-1) >, where A_(0) = g^(s) and A_(j) = 215 g^{a_(j)} 217 Note that in a distributed setting, each participant P_(i) must be 218 sure to have the same view of C as all other participants. In 219 practice, implementations guarantee consistency of participants' 220 views by using techniques such as posting commitments to a 221 centralized server that is trusted to provide a single view to all 222 participants, or adding another protocol round where participants 223 compare their received commitment values to ensure they are 224 identical. 226 2.2. Threshold Signature Schemes 228 Threshold signature schemes leverage the (t,n) security properties of 229 threshold schemes, but allow participants to produce signatures over 230 a message using their secret shares such that anyone can validate the 231 integrity of the message, _without_ ever reconstructing the secret. 232 In threshold signature schemes, the secret key s is distributed among 233 the n participants, while a single public key Y is used to represent 234 the group. Signatures can be generated by a threshold of t 235 cooperating signers. 237 For our work, we require the resulting signature produced by the 238 threshold signature scheme to be valid under the Schnorr signature 239 scheme [Sch89]. We introduce Schnorr signatures in Section 2.4. 241 Because threshold signature schemes ensure that no participant (or 242 indeed any group of fewer than t participants) ever learns the secret 243 key s, the generation of s and distribution of shares s_(1), ..., 244 s_(n) often require generating shares using a less-trusted method 245 than relying on a central dealer. Instead, these schemes (including 246 FROST) make use of a Distributed Key Generation (DKG) protocol, which 247 we describe next. 249 2.3. Distributed Key Generation 251 While some threshold schemes such as Shamir secret sharing rely on a 252 trusted dealer to generate and distribute secret shares to all 253 participants, not all threat models can allow for such a high degree 254 of trust in a single individual. Distributed Key Generation (DKG) 255 supports such threat models by enabling every participant to 256 contribute equally to the generation of the shared secret. At the 257 end of running the protocol, all participants share a joint public 258 key Y, but each participant holds only a share s_(i) of the 259 corresponding secret s such that no set of participants smaller than 260 the threshold knows s. 262 FROST can use either Pedersen's DKG [Ped91] or Gennaro's DKG [GJKR07] 263 to generate the shared long-lived secret key among participants 264 during its key generation stage. 266 2.4. Schnorr Signatures 268 Often, it is desirable for signatures produced by threshold signing 269 operations to be indistinguishable from signatures produced by a 270 single participant, consequently remaining backwards compatible with 271 existing systems, and also preventing a privacy leak of the 272 identities of the individual signers. For our work, we require 273 signatures produced by FROST signing operations to be 274 indistinguishable from Schnorr signatures, and thus verifiable using 275 the standard Schnorr verification operations. To this end, we now 276 describe Schnorr signing and verification operations [Sch89] in a 277 single-signer setting. 279 Let G be a group with prime order q and generator g, and let H be a 280 cryptographic hash function mapping to Z_(q)^(*). A Schnorr 281 signature is generated over a message m by the following steps: 283 1. Sample a random nonce k <-$- Z_(q); compute the commitment R = 284 g^(k) in G 286 2. Compute the challenge c = H(m,R) 288 3. Using the secret key s, compute the response z = k + s * c in 289 Z_(q) 291 4. Define the signature over m to be SIG = (z, c) 293 Validating the integrity of m using the public key Y=g^(s) and the 294 signature SIG is performed as follows: 296 1. Parse SIG as (z, c). 298 2. Compute R' = g^(z) * Y^(-c) 300 3. Compute c' = H(m, R') 302 4. Output 1 if c = c' to indicate success; otherwise, output 0. 304 Schnorr signatures are simply the standard Sigma-protocol proof of 305 knowledge of the discrete logarithm of Y, made non-interactive (and 306 bound to the message m) with the Fiat-Shamir transform. 308 2.5. Additive Secret Sharing 310 Similarly to the single-party setting described above, FROST requires 311 generating a random nonce k for each signing operation. However, in 312 the threshold setting, k should be generated in such a way that each 313 participant _contributes to_ but _does not know_ the resulting k 314 (properties that performing a DKG as described in Section 2.3 also 315 achieve). Key to the design of FROST is the observation that while 316 an arbitrary t out of n entities are required to participate in a 317 signing operation, a simpler t-out-of-t scheme will suffice to 318 generate the random nonce k. 320 While Shamir secret sharing and derived constructions require shares 321 to be points on a secret polynomial f where f(0)=s, an _additive 322 secret sharing scheme_ allows t participants to jointly compute a 323 shared secret s by each participant P_(i) contributing a value s_(i) 324 such that the resulting shared secret is s=SUM(s_(i), i=1...t), the 325 summation of each participant's share. Consequently, this t-out-of-t 326 secret sharing can be performed non-interactively; each participant 327 directly chooses their own s_(i). 329 Benaloh and Leichter [BL88] generalize this scheme to arbitrary 330 monotone access structures, and Cramer, Damgaerd, and Ishai [CDI05] 331 present a _non-interactive_ mechanism for participants to locally 332 convert additive shares generated via the Benaloh and Leichter t-out- 333 of-n additive secret sharing construction to polynomial (Shamir) 334 form. In our work, we use the simplest t-out-of-t case of this 335 transformation, in which, if s_(i) are _additive_ secret shares of s, 336 so that s is the sum of the s_(i), then (s_(i))/(L_(i)) are _Shamir_ 337 secret shares of the same s, where the L_(i) are Lagrange 338 coefficients. 340 In FROST, participants use this technique during signing operations 341 to non-interactively generate a one-time secret nonce (as is required 342 by Schnorr signatures, described in Section 2.4) that is Shamir 343 secret shared among all t signing participants. 345 2.6. Attacks on Parallelized Schnorr Multisignatures 347 *Attack via Wagner's Algorithm.* We next describe an attack recently 348 introduced by Drijvers et al. [DEF_19] against some two-round Schnorr 349 multisignature schemes and describe how this attack applies to a 350 threshold setting. This attack can be performed when the adversary 351 has control over either choosing the message m to be signed, or the 352 ability to adaptively choose its own individual commitments used to 353 determine the group commitment R after seeing commitments from all 354 other signing parties. 356 Successfully performing the Drijvers attack requires finding a hash 357 output c^(*) = H(m^(*), R^(*)) that is the sum of T other hash 358 outputs c^(*) = SUM(H(m_(j), R_(j)), j=1...T) (where c^(*) is the 359 challenge, m_(j) the message, and R_(j) the commitment corresponding 360 to a standard Schnorr signature as described in Section 2.4). To 361 find T hash outputs that sum to c^(*), the adversary can open many 362 (say T number of) parallel simultaneous signing operations, varying 363 in each of the T parallel executions either its individual commitment 364 used to determine R_(j) or the message being signed m_(j). Drijvers 365 et al. use the k-tree algorithm of Wagner [Wag02] to find such hashes 366 and perform the attack in time O(K * b * 2^(b/(1+lg K))), where K = T 367 + 1, and b is the bitlength of the order of the group. 369 Although this attack was proposed in a multisignature n-out-of-n 370 setting, this attack applies similarly in a threshold t-out-of-n 371 setting with the same parameters for an adversary that controls up to 372 t-1 participants. We note that the threshold scheme instantiated 373 using Pedersen's DKG by Gennaro et al. [GJKR03] is likewise affected 374 by this technique and so similarly has an upper bound to the amount 375 of parallelism that can be safely allowed. 377 In Section 4.2 we discuss how FROST avoids the attack by ensuring 378 that an attacker will not gain an advantage by adaptively choosing 379 its own commitment (or that of any other of the signing participants) 380 used to determine R_(j), or adaptively selecting the message being 381 signed. 383 Drijvers et al. [DEF_19] also present a metareduction for the proofs 384 of several Schnorr multisignature schemes in the literature that use 385 a generalization of the forking lemma with rewinding, proving that 386 the security demonstrated in a single-party setting does not extend 387 when applying this proof technique to a multi-party setting. 389 *Attack via ROS Solver.* Benhamouda et al. [BLOR20] recently present 390 an efficient algorithm solving the ROS (Random inhomogeneities in a 391 Overdetermined Solvable system of linear equations) problem. The 392 authors demonstrate that threshold schemes using Gennaro et al.'s 393 DKG [GJKR07] and multisignature schemes such as two-round 394 MuSig [MPSW19] are not secure against their ROS-solving algorithm. 395 However, the authors conclude that (the current version of) FROST is 396 not affected by their ROS-solving algorithm. 398 3. Preliminaries 400 Let G be a group of prime order q in which the Decisional Diffie- 401 Hellman problem is hard, and let g be a generator of G. Let H be a 402 cryptographic hash function mapping to Z_(q)^(*). We denote by x 403 <-$- S that x is uniformly randomly selected from S. 405 Let n be the number of participants in the signature scheme, and t 406 denote the threshold of the secret-sharing scheme. Let i denote the 407 _participant identifier_ for participant P_(i) where 1 <= i <= n. 408 Let s_(i) be the long-lived secret share for participant P_(i). Let 409 Y denote the long-lived public key shared by all participants in the 410 threshold signature scheme, and let Y_(i) = g^{s_(i)} be the public 411 key share for the participant P_(i). Finally, let m be the message 412 to be signed. 414 For a fixed set S = {p_(1),...,p_(t)} of t participant identifiers in 415 the signing operation, let L_(i) = PROD( (p_(j))/(p_(j) - p_(i)), 416 j=1...t, j != i) denote the ith Lagrange coefficient for 417 interpolating over S. Note that the information to derive these 418 values depends on which t (out of n) participants are selected, and 419 uses only the participant _identifiers_, and not their _shares_. 420 (Note that if n is small, the L_(i) for every possible S can be 421 precomputed by each participant during the key generation phase of 422 the protocol as a performance optimization to avoid re-computing 423 these values for each signing operation.) 425 *Security Assumptions.* We maintain the following assumptions, which 426 implementations need to account for in practice. 428 * _Message Validation._ We assume every participant checks the 429 validity of the message m to be signed before issuing its 430 signature share. If the message is invalid, the participant 431 should take actions to discard the message and report the 432 misbehaviour to other participants. 434 * _Reliable Message Delivery._ We assume messages are sent between 435 participants using a reliable network channel. 437 * _Participant Identification._ In order to report misbehaving 438 participants, we require that values submitted by participants to 439 be identifiable within the signing group. Our protocols assume 440 participants are not forging messages by other participants, but 441 implementations can enforce this using a method of participant 442 authentication within the signing group. (For example, 443 authentication tokens or TLS certificates could serve to 444 authenticate participants to one another.) 446 4. FROST: Flexible Round-Optimized Schnorr Threshold Signatures 448 We now describe the FROST protocol, a Flexible Round-Optimized 449 Schnorr Threshold signature scheme that minimizes the network 450 overhead of producing Schnorr signatures in a threshold setting while 451 allowing for unrestricted parallelism of signing operations and only 452 a threshold number of signing participants. 454 *Efficiency over Robustness.* Prior threshold signature 455 constructions [SS01] [GJKR03] provide the property of _robustness_; 456 if one participant misbehaves and provides malformed shares, the 457 remaining honest participants can detect the misbehaviour, exclude 458 the misbehaving participant, and complete the protocol, so long as 459 the number of remaining honest participants is at least the threshold 460 t. This kind of robust construction is appropriate in settings where 461 signing participants might be arbitrary entities from the Internet, 462 for example. 464 However, in settings where one can expect misbehaving participants to 465 be rare, threshold signing protocols can be relaxed to be more 466 efficient in the "optimistic" case that all participants honestly 467 follow the protocol. In the case that a participant does misbehave, 468 honest participants can identify the misbehaving participant and 469 abort the protocol. The honest participants can then simply re-run 470 the protocol amongst themselves, excluding the misbehaving 471 participant. Consequently, FROST trades off robustness in the 472 protocol for improved efficiency in this way. 474 *Signature Aggregator Role.* We instantiate FROST using a semi- 475 trusted _signature aggregator_ role, denoted as SA. Such a role is 476 often practical in a real-world setting; we include this role as it 477 also allows for improved efficiency. However, FROST can be 478 instantiated without a signature aggregator. To do so, each 479 participant simply performs a broadcast in place of SA performing 480 coordination. 482 The signature aggregator role can be performed by _any_ participant 483 in the protocol, or even an external party, provided they know the 484 participants' public-key shares Y_(i). SA is trusted to report 485 misbehaving participants (we assume participants can authenticate 486 themselves to one another, as discussed in Section 3) and to publish 487 the group's signature at the end of the protocol. If SA deviates 488 from the protocol, the protocol remains secure against adaptive 489 chosen message attacks, as SA is not given any more of a privileged 490 view than the adversary we model. A malicious SA does have the power 491 to perform denial-of-service attacks and to falsely report 492 misbehaviour by participants, but _cannot_ learn the private key or 493 cause improper messages to be signed. Note this signature aggregator 494 role is also used in prior threshold signature constructions in the 495 literature [GJKR03] as an optimization. 497 4.1. Key Generation 499 *FROST KeyGen* 501 *Round 1* 503 1. Every participant P_(i) samples t random values (a_(i0), ..., 504 a_(i(t-1)))) <-$- Z_(q), and uses these values as coefficients to 505 define a polynomial f_(i)(x) = SUM(a_(ij) x^(j), j=0...t-1) of 506 degree t-1 over Z_(q). 508 2. Every P_(i) computes a proof of knowledge to the corresponding 509 secret a_(i0) by calculating a Schnorr signature SIG_(i) = (w_(i), 510 c_(i)) using a_(i0) as the secret key, such that k <-$- Z_(q), 511 R_(i) = g^(k), c_(i) = H(i, CTX, g^{a_(i0)}, R_(i)), w_(i) = k + 512 a_(i0)* c_(i), with CTX being a context string to prevent replay 513 attacks. 515 3. Every participant P_(i) computes a public commitment C_(i) = < 516 A_(i0), ..., A_(i(t-1)) >, where A_(ij) = g^{a_(ij)}, 0 <= j <= 517 t-1 519 4. Every P_(i) broadcasts C_(i), SIG_(i) to all other participants. 521 5. Upon receiving C_(p), SIG_(p) from participants 1 <= p <= n, p != 522 i, participant P_(i) verifies SIG_(p) = (w_(p), c_(p)), aborting 523 on failure, by checking: c_(p) =?= H(p, CTX, A_(p0), g^{w_(p)} * 524 A_(p0)^{-c_(p)}) 526 *Round 2* 528 1. Each P_(i) securely sends to each other participant P_(p) a 529 secret share (p, f_(i)(p)), and keeps (i, f_(i)(i)) for 530 themselves. 532 2. Each P_(i) verifies their shares by calculating: g^{f_(p)(i)} =?= 533 PROD(A_(pk)^((i^k mod q)),k=0...t-1), aborting if the check fails. 535 3. Each P_(i) calculates their long-lived private signing share by 536 computing s_(i) = SUM(f_(p)(i), p=1...n), and stores s_(i) 537 securely. 539 4. Each P_(i) calculates their public verification share Y_(i) = 540 g^{s_(i)}, and the group's public key Y = PROD(A_(j0), j=1...n). 541 Any participant can compute the public verification share of any 542 other participant by calculating Y_(i) = PROD( (A_(jk))^((i^k mod 543 q)), j=1...n, k=0...t-1) 545 To generate long-lived key shares in our scheme's key generation 546 protocol, FROST builds upon Pedersen's DKG for key generation; we 547 detail these protocol steps in the above algorithm. Note that 548 Pedersen's DKG is simply where each participant executes Feldman's 549 VSS as the dealer in parallel, and derives their secret share as the 550 sum of the shares received from each of the n VSS executions. In 551 addition to the base Pedersen DKG protocol, FROST additionally 552 requires each participant to demonstrate knowledge of their secret 553 a_(i0) by providing other participants with proof in zero knowledge, 554 instantiated as a Schnorr signature, to protect against rogue-key 555 attacks [BBS03] in the setting where t >= n/2. 557 To begin the key generation protocol, a set of participants must be 558 formed using some out-of-band mechanism decided upon by the 559 implementation. After participating in the Ped-DKG protocol, each 560 participant P_(i) holds a value (i, s_(i)) that is their long-lived 561 secret signing share. Participant P_(i)'s public key share Y_(i) = 562 g^{s_(i)} is used by other participants to verify the correctness of 563 P_(i)'s signature shares in the following signing phase, while the 564 group public key Y can be used by parties external to the group to 565 verify signatures issued by the group in the future. 567 *View of Commitment Values.* As required for _any_ multi-party 568 protocol using Feldman's VSS, the key generation stage in FROST 569 similarly requires participants to maintain a consistent view of 570 commitments C_(i), 1 <= i <= n issued during the execution of Ped- 571 DKG. In this work, we assume participants broadcast the commitment 572 values honestly (e.g., participants do not provide different 573 commitment values to a subset of participants); recall Section 2.1 574 where we described techniques to achieve this guarantee in practice. 576 *Security tradeoffs.* While Gennaro et al. [GJKR07] describe the 577 "Stop, Kill, and Rewind" variant of Ped-DKG (where the protocol 578 terminates and is re-run if misbehaviour is detected) as vulnerable 579 to influence by the adversary, we note that in a real-world setting, 580 good security practices typically require that the cause of 581 misbehaviour is investigated once it has been detected; the protocol 582 is not allowed to terminate and re-run continuously until the 583 adversary finds a desirable output. Further, many protocols in 584 practice do not prevent an adversary from aborting and re-executing 585 key agreement at any point in the protocol; adversaries in protocols 586 such as the widely used TLS protocol can skew the distribution of the 587 resulting key simply by re-running the protocol. 589 However, implementations wishing for a robust DKG can adapt our key 590 generation protocol to the robust construction presented by Gennaro 591 et al. [GJKR07]. Note that the efficiency of the DKG for the key 592 generation phase is not extremely critical, because this operation 593 must be done only _once per key generation_ for long-lived keys. For 594 the per-signature operations, FROST optimizes the generation of 595 random values _without_ utilizing a DKG, as discussed next. 597 4.2. Threshold Signing with Unrestricted Parallelism 599 We now introduce the signing protocol for FROST. This operation 600 builds upon known techniques in the literature [AAM20] [GJKR03] by 601 employing additive secret sharing and share conversion in order to 602 non-interactively generate the nonce value for each signature. 603 However, signing operations in FROST additionally leverage a binding 604 technique to avoid known forgery attacks without limiting 605 concurrency. We present FROST signing in two parts: a pre-processing 606 phase and a single-round signing phase. However, these stages can be 607 combined for a simple two-round protocol if desired. 609 As a reminder, the attack of Drijvers et al. [DEF_19] requires the 610 adversary to either see the victim's T commitment values before 611 selecting their own commitment, or to adaptively choose the message 612 to be signed, so that the adversary can manipulate the resulting 613 challenge c for the set of participants performing a group signing 614 operation. To prevent this attack without limiting concurrency, 615 FROST binds each participant's response to a specific message as well 616 as the set of participants and their commitments used for that 617 particular signing operation. In doing so, combining responses over 618 different messages or participant/commitment pairs results in an 619 invalid signature, thwarting attacks such as those of Drijvers et al. 621 *Preprocess(Q) -> (i, D_(i1), E_(i1), ..., D_(iQ), E_(iQ))* 623 Each participant P_(i), i in {1, ..., n} performs this stage prior to 624 signing. Let j be a counter for a specific nonce/commitment share 625 pair, and Q be the number of pairs generated at a time, such that Q 626 signing operations can be performed before performing another 627 preprocess step. 629 1. Create an empty list L_(i). Then, for 1 <= j <= Q, perform the 630 following: 632 1.a Sample single-use nonces (d_(ij), e_(ij)) <-$- Z_(q)^(*) x 633 Z_(q)^(*) 635 1.b Derive commitment shares (D_(ij), E_(ij)) = (g^{d_(ij)}, 636 g^{e_(ij)}). 638 1.c Append (D_(ij), E_(ij)) to L_(i). Store ((d_(ij), D_(ij)), 639 (e_(ij), E_(ij))) for later use in signing operations. 641 2. Publish (i, L_(i)) to a predetermined location, as specified by 642 the implementation. 644 *Preprocessing Stage.* We present above a preprocessing stage where 645 participants generate and publish Q commitments at a time. In this 646 setting, Q determines the number of nonces that are generated and 647 their corresponding commitments that are published in a single 648 preprocess step, and correspondingly the number of signing operations 649 that can be performed before the participant must perform this 650 preprocessing stage again. Note that implementations that do not 651 wish to cache commitments can instead use a two-round protocol, where 652 participants publish a single commitment to each other in the first 653 round. 655 Each participant P_(i) begins by generating a list of _single-use_ 656 private nonce pairs and corresponding public commitment shares 657 ((d_(ij), D_(ij) = g^{d_(ij)}), (e_(ij), E_(ij) = g^{e_(ij)})) for 658 j=1,...,Q, where j is a counter that identifies the next nonce/ 659 commitment share pair available to use for signing. Each P_(i) then 660 publishes (i, L_(i)), where L_(i) is their list of commitment shares 661 L_(i) = <(D_(ij), E_(ij)) for j=1,...,Q>. The location where 662 participants publish these values can depend on the implementation; 663 options include broadcasting to all other participants or publishing 664 to a centralized location that all participants can access (we 665 discuss these options further in Section 6). The set of (i, L_(i)) 666 tuples are then stored by any entity that might perform the signature 667 aggregator role during signing. 669 *Sign(m) -> (m, SIG)* 671 Let SA denote the signature aggregator (who themselves can be one of 672 the t signing participants). Let S be the set of participants 673 selected for use for this signing operation. Let B = < (i, D_(ij), 674 E_(ij)) for i in S> denote the ordered list of participant indices 675 corresponding to each participant P_(i), and L_(i) be the set of 676 available commitment values for P_(i) that were published during the 677 Preprocess stage. Each identifier i is coupled with the jth 678 commitments (D_(ij), E_(ij)) published by P_(i) that will be used for 679 this particular signing operation. Let H_(1), H_(2) be hash 680 functions whose outputs are in Z_(q)^(*). 682 1. SA begins by fetching the next available commitment for each 683 participant P_(i) in S from L_(i) and constructs B. 685 2. For each i in S, SA sends P_(i) the tuple (m, B). 687 3. After receiving (m, B), each P_(i) first validates the message m, 688 and then checks D_(p j), E_(p j) in G^(*) for each commitment in 689 B, aborting if either check fails. 691 4. Each P_(i) then computes the set of binding values r_(p) = 692 H_(1)(p, m, B), p in S. Each P_(i) then derives the group 693 commitment R = PROD(D_(pj) * (E_(pj))^{r_(p)}, p in S), and the 694 challenge c = H_(2)(m, R). 696 5. Each P_(i) computes their response using their long-lived secret 697 share s_(i) by computing z_(i) = d_(ij) + (e_(ij) * r_(i)) + L_(i) 698 * s_(i) * c, using S to determine L_(i). 700 6. Each P_(i) securely deletes ((d_(ij), D_(ij)), (e_(ij), E_(ij))) 701 from their local storage, and then returns z_(i) to SA. 703 7. The signature aggregator SA performs the following steps: 705 7.a Derive r_(i) = H_(1)(i,m,B) and R_(i) = D_(ij) * 706 (E_(ij))^{r_(i)} for i in S, and subsequently R=PROD(R_(i), i 707 in S) and c = H_(2)(m,R). 709 7.b Verify the validity of each response by checking g^{z_(i)} 710 =?= R_(i) * {Y_(i)}^{c * L_(i)} for each signing share z_(i), i 711 in S. If the equality does not hold, first identify and report 712 the misbehaving participant, and then abort. Otherwise, 713 continue. 715 7.c Compute the group's response z = SUM(z_(i), i in S) 717 7.d Publish the signature SIG = (z, c) along with the message m. 719 *Signing Protocol.* At the beginning of the signing protocol above, 720 SA selects t participants (possibly including itself) to participate 721 in the signing. Let S be the set of those t participants. SA then 722 selects the next available commitment (D_(ij), E_(ij)) for each 723 participant in S, which are later used to generate a secret share to 724 a random commitment R for the signing group. (Each participant 725 contributes to the group commitment R, which corresponds to the 726 commitment g^(k) to the nonce k in step 1 of the single-party Schnorr 727 signature scheme in Section 2.4.) This technique is a t-out-of-t 728 additive secret sharing; the resulting secret nonce is k = SUM(k_(i), 729 i in S), where each k_(i) = d_(ij) + e_(ij) * r_(i) (we next describe 730 how participants calculate r_(i)), and (d_(ij), e_(ij)) correspond to 731 the (D_(ij) = g^{d_(ij)}, E_(ij)=g^{e_(ij)}) values published during 732 the Preprocess stage. Recall from Section 2.5 that if the k_(i) are 733 _additive_ shares of k, then each (k_(i))/(L_(i)) are t-out-of-t 734 _Shamir_ shares of k. 736 After these steps, SA then creates the set B, where B is the ordered 737 list of tuples <(i, D_(ij), E_(ij)) for i in S>. SA then sends (m, 738 B) to every P_(i), i in S. 740 After receiving (m, B) from SA to initialize a signing operation, 741 each participant checks that m is a message they are willing to sign. 742 Then, using m and B, all participants derive the "binding values" 743 r_(i), i in S such that r_(i) = H_(1)(i, m, B), where H_(1) is a hash 744 function whose outputs are in Z_(q)^(*). 746 Each participant can then compute the commitment R_(i) for each 747 participant in S by deriving R_(i) = D_(ij) * (E_(ij))^{r_(i)}. Doing 748 so binds the message, the set of signing participants, and each 749 participant's commitment to each signature share, such that signature 750 shares on one message cannot be used for another, assuming that 751 (d_(ij), e_(ij)) remain secret and are used only once. This binding 752 technique thwarts the attack of Drijvers et al. described in 753 Section 2.6 as attackers cannot combine signature shares across 754 disjoint signing operations or permute the set of signers or 755 published commitments for each signer. 757 The commitment for the set of signers is then simply R = PROD(R_(i), 758 i in S). As in single-party Schnorr signatures, each participant 759 computes the challenge c = H_(2)(m,R). 761 Each participant's response z_(i) to the challenge can be computed 762 using the single-use nonces (d_(ij), e_(ij)) and the long-term secret 763 shares s_(i), which are t-out-of-n (degree t-1) Shamir secret shares 764 of the group's long-lived secret key s. Recalling that 765 (k_(i))/(L_(i)) are degree t-1 Shamir secret shares of k, we see that 766 (k_(i))/(L_(i)) + s_(i) * c are degree t-1 Shamir secret shares of 767 the correct response z = k + s * c for a plain (single-party) Schorr 768 signature. Using share conversion again, and that k_(i) = d_(ij) + 769 (e_(ij) * r_(i)), we get that z_(i) = d_(ij) + (e_(ij) * r_(i)) + 770 L_(i) * s_(i) * c are t-out-of-t additive shares of z. 772 SA finally checks the consistency of each participant's reported 773 z_(i) with their commitment share (D_(ij), E_(ij)) and their public 774 key share Y_(i). If every participant issued a correct z_(i), then 775 the sum of the z_(i) values, along with c, forms the Schnorr 776 signature on m. This signature will verify properly to a verifier 777 unaware that FROST was used to generate the signature, and who checks 778 it with the standard single-party Schnorr verification equation with 779 Y as the public key (Section 2.4). 781 *Handling Ephemeral Outstanding Shares.* Because each nonce and 782 commitment share generated during the preprocessing stage described 783 in the Preprocess algorithm must be used _at most once_, participants 784 delete these values after using them in a signing operation, as 785 indicated in Step 5 in the Sign algorithm. An accidentally reused 786 (d_(ij), e_(ij)) can lead to exposure of the participant's long-term 787 secret s_(i), so participants must securely delete them, and defend 788 against snapshot rollback attacks as in any implementation of Schnorr 789 signatures. 791 However, if SA chooses to re-use a commitment set (D_(ij), E_(ij)) 792 during the signing protocol, doing so simply results in the 793 participant P_(i) aborting the protocol, and consequently does not 794 increase the power of SA. 796 5. Security Considerations 798 5.1. Proof of Security Properties 800 We present proofs and arguments of security in our technical 801 report [KG20] to show that FROST is secure against chosen-message 802 attacks, assuming the discrete logarithm problem is hard and the 803 adversary controls fewer participants than the threshold. The 804 strategy is as follows. We first define an intermediate protocol 805 called FROST-Interactive that has one extra round of communication in 806 each of the Preprocess and Sign phases, and prove the security of 807 FROST-Interactive in the random oracle model. We then give a 808 heuristic argument that the differences between FROST-Interactive and 809 FROST itself do not adversely affect its security. 811 5.2. Aborting on Misbehaviour 813 As discussed above, the goal of FROST is to save communication rounds 814 (particularly at signing time), at the cost of sacrificing 815 robustness. Consequently, FROST requires participants to abort once 816 they have detected misbehaviour. 818 If one of the signing participants provides an incorrect signature 819 share, SA will detect that and abort the protocol, if SA is itself 820 behaving correctly. The protocol can then be rerun with the 821 misbehaving party removed. If SA is itself misbehaving, and even if 822 up to t-1 participants are corrupted, SA still cannot produce a valid 823 signature on a message not approved by at least one honest 824 participant. 826 6. Operational Considerations 828 6.1. Publishing Commitments to a Commitment Server 830 The preprocessing step for FROST in Section 4.2 requires some agreed- 831 upon location for participants to publish their commitments to. We 832 now discuss choices for such a location for implementations, and 833 possible security implications. 835 While participants could simply broadcast commitments to each other, 836 this approach requires memory overhead and possibly coordination 837 effort. Alternatively, implementations may wish to employ a 838 commitment server specifically tasked with performing and managing of 839 participants' commitment shares. While the commitment server may be 840 a separate entity, we note that the signature aggregator SA can also 841 provide this service in addition to its other duties. In this 842 setting, the commitment server is trusted to provide the correct 843 (i.e, valid and unused) commitment shares upon request. If the 844 commitment server chose to act maliciously, it could either prevent 845 participants from performing the protocol by denial of service, or it 846 could provide stale or malformed commitment values on behalf of 847 honest participants, causing uncertainty as to whether the commitment 848 server or the participant was the misbehaving entity. However, 849 simply having access to the set of a participant's _public_ published 850 commitments does not grant any additional powers, and a misbehaving 851 commitment server (or SA) that provides old commitment values for a 852 signing operation simply results in either a denial of service or an 853 invalid signature. If SA assumes the commitment server role itself, 854 any uncertainty as to who is the cause of misbehaviour can be 855 avoided, and allows SA to carry out their role to report misbehaviour 856 when it occurs. 858 6.2. Adaptively Choosing the Set of Signing Participants 860 While FROST requires exactly t signers due to the structure of non- 861 interactively generating the nonce k (more specifically, so 862 participants can determine L_(i) during signing), implementations can 863 still adaptively choose signing participants based on their 864 availability if the implementation does not wish to assume which t 865 signers are online and available when beginning a FROST signing 866 operation. 868 How implementations should determine the availability of 869 participants, and select which t participants will perform signing, 870 falls outside FROST, and will depend on the implementation details of 871 the communications among the participants. In the worst case, 872 however, implementations can simply add an additional round before 873 performing the FROST signing protocol, during which participants can 874 demonstrate their availability and coordinate how available signers 875 are selected to perform the signing round (such as using some simple 876 tie-breaking exercise or ordering rule). 878 7. Acknowledgments 880 We thank Douglas Stebila for his helpful observations on the proof of 881 security and deriving security bounds. We thank Richard Barnes for 882 his helpful discussion on practical constraints and for identifying 883 significant optimizations to a prior version of FROST, which our 884 final version of FROST builds upon. 886 We thank George Tankersley, Henry DeValence, Deirdre Connolly, and 887 Ian Miers for their feedback and discussions about real-world 888 applications of threshold signatures. We thank Omer Shlomovits and 889 Elichai Turkel for pointing out the case of rogue-key attacks in 890 plain Ped-DKG and the suggestion to use a proof of knowledge for 891 a_(i0) as a prevention mechanism. 893 We acknowledge the helpful description of additive secret sharing and 894 share conversion as a useful technique to non-interactively generate 895 secrets for Shamir secret-sharing schemes by Lueks [Lue17],S.2.5.2. 897 8. Informative References 899 [AAM20] Abidin, A., Aly, A., and M.A. Mustafa, "Collaborative 900 Authentication Using Threshold Cryptography", Emerging 901 Technologies for Authorization and Authentication , 2020. 903 [BBS03] Bellare, M., Boldyreva, A., and J. Staddon, "Randomness 904 Re-use in Multi-recipient Encryption Schemeas", Public Key 905 Cryptography , 2003. 907 [BDN18] Boneh, D., Drijvers, M., and G. Neven, "Compact Multi- 908 signatures for Smaller Blockchains", ASIACRYPT , 2018. 910 [BL88] Benaloh, J. and J. Leichter, "Generalized Secret Sharing 911 and Monotone Functions", CRYPTO , 1988. 913 [BLOR20] Benhamouda, F., Lepoint, T., Orrù, M., and M. Raykova, "On 914 the (in)security of ROS", 2020, 915 . 917 [BLS04] Boneh, D., Lynn, B., and H. Shacham, "Short Signatures 918 from the Weil Pairing", Journal of Cryptology , 2004. 920 [CDI05] Cramer, R., Damgård, I., and Y. Ishai, "Share Conversion, 921 Pseudorandom Secret-Sharing and Applications to Secure 922 Computation", Theory of Cryptography , 2005. 924 [DEF_19] Drijvers, M., Edalatnejad, K., Ford, B., Kiltz, E., Loss, 925 J., Neven, G., and I. Stepanovs, "On the Security of Two- 926 Round Multi-Signatures", 2019 IEEE Symposium on Security 927 and Privacy (SP) , 2019. 929 [DJN_20] Damgård, I., Jakobsen, T.P., Nielsen, J.B., Pagter, J.I., 930 and M.B. Østergård, "Fast Threshold ECDSA with Honest 931 Majority", 2020, . 933 [Fel87] Feldman, P., "A Practical Scheme for Non-interactive 934 Verifiable Secret Sharing", Proceedings of the 28th Annual 935 Symposium on Foundations of Computer Science , 1987. 937 [GGK_15] Goldfeder, S., Gennaro, R., Kalodner, H., Bonneau, J., 938 Kroll, J.A., Felten, E.W., and A. Narayanan, "Securing 939 Bitcoin wallets via a new DSA/ECDSA threshold signature 940 scheme", 2015. 942 [GJKR03] Gennaro, R., Jarecki, S., Krawczyk, H., and T. Rabin, 943 "Secure Applications of Pedersen's Distributed Key 944 Generation Protocol", Topics in Cryptology - CT-RSA 2003 , 945 2003. 947 [GJKR07] Gennaro, R., Jarecki, S., Krawczyk, H., and T. Rabin, 948 "Secure Distributed Key Generation for Discrete-Log Based 949 Cryptosystems", Journal of Cryptology , 2007. 951 [KG20] Komlo, C. and I. Goldberg, "FROST: Flexible Round- 952 Optimized Schnorr Threshold Signatures", 2020, 953 . 955 [Lue17] Lueks, W., "Security and Privacy via Cryptography -- 956 Having your cake and eating it too", 2017. 958 [MOT_11] Mittal, P., Olumofin, F., Troncoso, C., Borisov, N., and 959 I. Goldberg, "PIR-Tor: Scalable Anonymous Communication 960 Using Private Information Retrieval", 20th USENIX Security 961 Symposium , 2011. 963 [MPSW19] Maxwell, G., Poelstra, A., Seurin, Y., and P. Wuille, 964 "Simple Schnorr multi-signatures with applications to 965 Bitcoin", Designs, Codes and Cryptography , 2019. 967 [Ped91] Pedersen, T.P., "A Threshold Cryptosystem without a 968 Trusted Party (Extended Abstract)", EUROCRYPT '91 , 1991. 970 [SS01] Stinson, D.R. and R. Strobl, "Provably Secure Distributed 971 Schnorr Signatures and a (t, n) Threshold Scheme for 972 Implicit Certificates", Proceedings of the 6th 973 Australasian Conference on Information Security and 974 Privacy , 2001. 976 [Sch89] Schnorr, C., "Efficient Identification and Signatures for 977 Smart Cards", CRYPTO , 1989. 979 [Sha79] Shamir, A., "How to share a secret", Communications of the 980 ACM , 1979. 982 [Wag02] Wagner, D., "A Generalized Birthday Problem", CRYPTO , 983 2002. 985 Authors' Addresses 987 Chelsea Komlo 988 University of Waterloo, Zcash Foundation 989 Email: ckomlo@uwaterloo.ca 991 Ian Goldberg 992 University of Waterloo 994 Email: iang@uwaterloo.ca