rfc9591.original   rfc9591.txt 
CFRG D. Connolly Internet Research Task Force (IRTF) D. Connolly
Internet-Draft Zcash Foundation Request for Comments: 9591 Zcash Foundation
Intended status: Informational C. Komlo Category: Informational C. Komlo
Expires: 22 March 2024 University of Waterloo, Zcash Foundation ISSN: 2070-1721 University of Waterloo, Zcash Foundation
I. Goldberg I. Goldberg
University of Waterloo University of Waterloo
C. A. Wood C. A. Wood
Cloudflare Cloudflare
19 September 2023 June 2024
Two-Round Threshold Schnorr Signatures with FROST The Flexible Round-Optimized Schnorr Threshold (FROST) Protocol for Two-
draft-irtf-cfrg-frost-15 Round Schnorr Signatures
Abstract Abstract
This document specifies the Flexible Round-Optimized Schnorr This document specifies the Flexible Round-Optimized Schnorr
Threshold (FROST) signing protocol. FROST signatures can be issued Threshold (FROST) signing protocol. FROST signatures can be issued
after a threshold number of entities cooperate to compute a after a threshold number of entities cooperate to compute a
signature, allowing for improved distribution of trust and redundancy signature, allowing for improved distribution of trust and redundancy
with respect to a secret key. FROST depends only on a prime-order with respect to a secret key. FROST depends only on a prime-order
group and cryptographic hash function. This document specifies a group and cryptographic hash function. This document specifies a
number of ciphersuites to instantiate FROST using different prime- number of ciphersuites to instantiate FROST using different prime-
order groups and hash functions. One such ciphersuite can be used to order groups and hash functions. This document is a product of the
produce signatures that can be verified with an Edwards-Curve Digital Crypto Forum Research Group (CFRG) in the IRTF.
Signature Algorithm (EdDSA, as defined in RFC8032) compliant
verifier. However, unlike EdDSA, the signatures produced by FROST
are not deterministic. This document is a product of the Crypto
Forum Research Group (CFRG) in the IRTF.
Discussion Venues
This note is to be removed before publishing as an RFC.
Discussion of this document takes place on the Crypto Forum Research
Group mailing list (cfrg@ietf.org), which is archived at
https://mailarchive.ietf.org/arch/search/?email_list=cfrg.
Source for this draft and an issue tracker can be found at
https://github.com/cfrg/draft-irtf-cfrg-frost.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This document is not an Internet Standards Track specification; it is
provisions of BCP 78 and BCP 79. published for informational purposes.
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 This document is a product of the Internet Research Task Force
and may be updated, replaced, or obsoleted by other documents at any (IRTF). The IRTF publishes the results of Internet-related research
time. It is inappropriate to use Internet-Drafts as reference and development activities. These results might not be suitable for
material or to cite them other than as "work in progress." deployment. This RFC represents the consensus of the Crypto Forum
Research Group of the Internet Research Task Force (IRTF). Documents
approved for publication by the IRSG are not candidates for any level
of Internet Standard; see Section 2 of RFC 7841.
This Internet-Draft will expire on 22 March 2024. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
https://www.rfc-editor.org/info/rfc9591.
Copyright Notice Copyright Notice
Copyright (c) 2023 IETF Trust and the persons identified as the Copyright (c) 2024 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/ Provisions Relating to IETF Documents
license-info) in effect on the date of publication of this document. (https://trustee.ietf.org/license-info) in effect on the date of
Please review these documents carefully, as they describe your rights publication of this document. Please review these documents
and restrictions with respect to this document. carefully, as they describe your rights and restrictions with respect
to this document.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction
1.1. Change Log . . . . . . . . . . . . . . . . . . . . . . . 4 2. Conventions and Definitions
2. Conventions and Definitions . . . . . . . . . . . . . . . . . 8 3. Cryptographic Dependencies
3. Cryptographic Dependencies . . . . . . . . . . . . . . . . . 9 3.1. Prime-Order Group
3.1. Prime-Order Group . . . . . . . . . . . . . . . . . . . . 9 3.2. Cryptographic Hash Function
3.2. Cryptographic Hash Function . . . . . . . . . . . . . . . 11 4. Helper Functions
4. Helper Functions . . . . . . . . . . . . . . . . . . . . . . 11 4.1. Nonce Generation
4.1. Nonce generation . . . . . . . . . . . . . . . . . . . . 11 4.2. Polynomials
4.2. Polynomials . . . . . . . . . . . . . . . . . . . . . . . 12 4.3. List Operations
4.3. List Operations . . . . . . . . . . . . . . . . . . . . . 13 4.4. Binding Factors Computation
4.4. Binding Factors Computation . . . . . . . . . . . . . . . 15 4.5. Group Commitment Computation
4.5. Group Commitment Computation . . . . . . . . . . . . . . 16 4.6. Signature Challenge Computation
4.6. Signature Challenge Computation . . . . . . . . . . . . . 17 5. Two-Round FROST Signing Protocol
5. Two-Round FROST Signing Protocol . . . . . . . . . . . . . . 18 5.1. Round One - Commitment
5.1. Round One - Commitment . . . . . . . . . . . . . . . . . 21 5.2. Round Two - Signature Share Generation
5.2. Round Two - Signature Share Generation . . . . . . . . . 22 5.3. Signature Share Aggregation
5.3. Signature Share Aggregation . . . . . . . . . . . . . . . 24 5.4. Identifiable Abort
5.4. Identifiable Abort . . . . . . . . . . . . . . . . . . . 27 6. Ciphersuites
6. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 28 6.1. FROST(Ed25519, SHA-512)
6.1. FROST(Ed25519, SHA-512) . . . . . . . . . . . . . . . . . 28 6.2. FROST(ristretto255, SHA-512)
6.2. FROST(ristretto255, SHA-512) . . . . . . . . . . . . . . 30 6.3. FROST(Ed448, SHAKE256)
6.3. FROST(Ed448, SHAKE256) . . . . . . . . . . . . . . . . . 31 6.4. FROST(P-256, SHA-256)
6.4. FROST(P-256, SHA-256) . . . . . . . . . . . . . . . . . . 33 6.5. FROST(secp256k1, SHA-256)
6.5. FROST(secp256k1, SHA-256) . . . . . . . . . . . . . . . . 34 6.6. Ciphersuite Requirements
6.6. Ciphersuite Requirements . . . . . . . . . . . . . . . . 36 7. Security Considerations
7. Security Considerations . . . . . . . . . . . . . . . . . . . 36 7.1. Side-Channel Mitigations
7.1. Side-channel mitigations . . . . . . . . . . . . . . . . 37 7.2. Optimizations
7.2. Optimizations . . . . . . . . . . . . . . . . . . . . . . 37 7.3. Nonce Reuse Attacks
7.3. Nonce Reuse Attacks . . . . . . . . . . . . . . . . . . . 38 7.4. Protocol Failures
7.4. Protocol Failures . . . . . . . . . . . . . . . . . . . . 38 7.5. Removing the Coordinator Role
7.5. Removing the Coordinator Role . . . . . . . . . . . . . . 38 7.6. Input Message Hashing
7.6. Input Message Hashing . . . . . . . . . . . . . . . . . . 39 7.7. Input Message Validation
7.7. Input Message Validation . . . . . . . . . . . . . . . . 39 8. IANA Considerations
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 40 9. References
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 40 9.1. Normative References
9.1. Normative References . . . . . . . . . . . . . . . . . . 40 9.2. Informative References
9.2. Informative References . . . . . . . . . . . . . . . . . 41 Appendix A. Schnorr Signature Encoding
Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . 42 Appendix B. Schnorr Signature Generation and Verification for
Appendix B. Schnorr Signature Encoding . . . . . . . . . . . . . 42 Prime-Order Groups
Appendix C. Schnorr Signature Generation and Verification for Appendix C. Trusted Dealer Key Generation
Prime-Order Groups . . . . . . . . . . . . . . . . . . . 42 C.1. Shamir Secret Sharing
Appendix D. Trusted Dealer Key Generation . . . . . . . . . . . 44 C.1.1. Additional Polynomial Operations
D.1. Shamir Secret Sharing . . . . . . . . . . . . . . . . . . 45 C.2. Verifiable Secret Sharing
D.1.1. Additional polynomial operations . . . . . . . . . . 47 Appendix D. Random Scalar Generation
D.2. Verifiable Secret Sharing . . . . . . . . . . . . . . . . 48 D.1. Rejection Sampling
Appendix E. Random Scalar Generation . . . . . . . . . . . . . . 50 D.2. Wide Reduction
E.1. Rejection Sampling . . . . . . . . . . . . . . . . . . . 50 Appendix E. Test Vectors
E.2. Wide Reduction . . . . . . . . . . . . . . . . . . . . . 51 E.1. FROST(Ed25519, SHA-512)
Appendix F. Test Vectors . . . . . . . . . . . . . . . . . . . . 51 E.2. FROST(Ed448, SHAKE256)
F.1. FROST(Ed25519, SHA-512) . . . . . . . . . . . . . . . . . 52 E.3. FROST(ristretto255, SHA-512)
F.2. FROST(Ed448, SHAKE256) . . . . . . . . . . . . . . . . . 53 E.4. FROST(P-256, SHA-256)
F.3. FROST(ristretto255, SHA-512) . . . . . . . . . . . . . . 55 E.5. FROST(secp256k1, SHA-256)
F.4. FROST(P-256, SHA-256) . . . . . . . . . . . . . . . . . . 57 Acknowledgments
F.5. FROST(secp256k1, SHA-256) . . . . . . . . . . . . . . . . 58 Authors' Addresses
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 60
1. Introduction 1. Introduction
RFC EDITOR: PLEASE REMOVE THE FOLLOWING PARAGRAPH The source for this
draft is maintained in GitHub. Suggested changes should be submitted
as pull requests at https://github.com/cfrg/draft-irtf-cfrg-frost.
Instructions are on that page as well.
Unlike signatures in a single-party setting, threshold signatures Unlike signatures in a single-party setting, threshold signatures
require cooperation among a threshold number of signing participants require cooperation among a threshold number of signing participants,
each holding a share of a common private key. The security of each holding a share of a common private key. The security of
threshold schemes in general assumes that an adversary can corrupt threshold schemes in general assumes that an adversary can corrupt
strictly fewer than a threshold number of signer participants. strictly fewer than a threshold number of signer participants.
This document specifies the Flexible Round-Optimized Schnorr This document specifies the Flexible Round-Optimized Schnorr
Threshold (FROST) signing protocol based on the original work in Threshold (FROST) signing protocol based on the original work in
[FROST20]. FROST reduces network overhead during threshold signing [FROST20]. FROST reduces network overhead during threshold signing
operations while employing a novel technique to protect against operations while employing a novel technique to protect against
forgery attacks applicable to prior Schnorr-based threshold signature forgery attacks applicable to prior Schnorr-based threshold signature
constructions. FROST requires two rounds to compute a signature. constructions. FROST requires two rounds to compute a signature.
Single-round signing variants based on [FROST20] are out of scope. Single-round signing variants based on [FROST20] are out of scope.
FROST depends only on a prime-order group and cryptographic hash FROST depends only on a prime-order group and cryptographic hash
function. This document specifies a number of ciphersuites to function. This document specifies a number of ciphersuites to
instantiate FROST using different prime-order groups and hash instantiate FROST using different prime-order groups and hash
functions. Two ciphersuites can be used to produce signatures that functions. Two ciphersuites can be used to produce signatures that
are compatible with Edwards-Curve Digital Signature Algorithm (EdDSA) are compatible with Edwards-Curve Digital Signature Algorithm (EdDSA)
variants Ed25519 and Ed448 as specified in [RFC8032], i.e., the variants Ed25519 and Ed448 as specified in [RFC8032], i.e., the
signatures can be verified with an [RFC8032] compliant verifier. signatures can be verified with a verifier that is compliant with
However, unlike EdDSA, the signatures produced by FROST are not [RFC8032]. However, unlike EdDSA, the signatures produced by FROST
deterministic, since deriving nonces deterministically allows for a are not deterministic, since deriving nonces deterministically allows
complete key-recovery attack in multi-party discrete logarithm-based for a complete key-recovery attack in multi-party, discrete
signatures. logarithm-based signatures.
Key generation for FROST signing is out of scope for this document. Key generation for FROST signing is out of scope for this document.
However, for completeness, key generation with a trusted dealer is However, for completeness, key generation with a trusted dealer is
specified in Appendix D. specified in Appendix C.
This document represents the consensus of the Crypto Forum Research This document represents the consensus of the Crypto Forum Research
Group (CFRG). It is not an IETF product and is not a standard. Group (CFRG). It is not an IETF product and is not a standard.
RFC EDITOR: PLEASE REMOVE THE FOLLOWING SUB-SECTION
1.1. Change Log
draft-13 and draft-14
* Hash group public key into binding computation (#439)
* Finalize test vectors (#442)
draft-12
* Address RGLC feedback (#399, #396, #395, #394, #393, #384, #382,
#397, #378, #376, #375, #374, #373, #371, #370, #369, #368, #367,
#366, #364, #363, #362, #361, #359, #358, #357, #356, #354, #353,
#352, #350, #349, #348, #347, #314)
* Fix bug in signature share serialization (#397)
* Fix various editorial issues (#385)
* Update version string constant (#307)
* Make SerializeElement reject the identity element (#306)
* Make ciphersuite requirements explicit (#302)
* Fix various editorial issues (#303, #301, #299, #297)
draft-10
* Update version string constant (#296)
* Fix some editorial issues from Ian Goldberg (#295)
draft-09
* Add single-signer signature generation to complement RFC8032
functions (#293)
* Address Thomas Pornin review comments from
https://mailarchive.ietf.org/arch/msg/crypto-panel/
bPyYzwtHlCj00g8YF1tjj-iYP2c/ (#292, #291, #290, #289, #287, #286,
#285, #282, #281, #280, #279, #278, #277, #276, #275, #273, #272,
#267)
* Correct Ed448 ciphersuite (#246)
* Various editorial changes (#241, #240)
draft-08
* Add notation for Scalar multiplication (#237)
* Add secp2561k1 ciphersuite (#223)
* Remove RandomScalar implementation details (#231)
* Add domain separation for message and commitment digests (#228)
draft-07
* Fix bug in per-rho signer computation (#222)
draft-06
* Make verification a per-ciphersuite functionality (#219)
* Use per-signer values of rho to mitigate protocol malleability
(#217)
* Correct prime-order subgroup checks (#215, #211)
* Fix bug in ed25519 ciphersuite description (#205)
* Various editorial improvements (#208, #209, #210, #218)
draft-05
* Update test vectors to include version string (#202, #203)
* Rename THRESHOLD_LIMIT to MIN_PARTICIPANTS (#192)
* Use non-contiguous signers for the test vectors (#187)
* Add more reasoning why the coordinator MUST abort (#183)
* Add a function to generate nonces (#182)
* Add MUST that all participants have the same view of VSS
commitment (#174)
* Use THRESHOLD_LIMIT instead of t and MAX_PARTICIPANTS instead of n
(#171)
* Specify what the dealer is trusted to do (#166)
* Clarify types of NUM_PARTICIPANTS and THRESHOLD_LIMIT (#165)
* Assert that the network channel used for signing should be
authenticated (#163)
* Remove wire format section (#156)
* Update group commitment derivation to have a single scalarmul
(#150)
* Use RandomNonzeroScalar for single-party Schnorr example (#148)
* Fix group notation and clarify member functions (#145)
* Update existing implementations table (#136)
* Various editorial improvements (#135, #143, #147, #149, #153,
#158, #162, #167, #168, #169, #170, #175, #176, #177, #178, #184,
#186, #193, #198, #199)
* Added methods to verify VSS commitments and derive group info
(#126, #132).
* Changed check for participants to consider only nonnegative
numbers (#133).
* Changed sampling for secrets and coefficients to allow the zero
element (#130).
* Split test vectors into separate files (#129)
* Update wire structs to remove commitment shares where not
necessary (#128)
* Add failure checks (#127)
* Update group info to include each participant's key and clarify
how public key material is obtained (#120, #121).
* Define cofactor checks for verification (#118)
* Various editorial improvements and add contributors (#124, #123,
#119, #116, #113, #109)
draft-03
* Refactor the second round to use state from the first round (#94).
* Ensure that verification of signature shares from the second round
uses commitments from the first round (#94).
* Clarify RFC8032 interoperability based on PureEdDSA (#86).
* Specify signature serialization based on element and scalar
serialization (#85).
* Fix hash function domain separation formatting (#83).
* Make trusted dealer key generation deterministic (#104).
* Add additional constraints on participant indexes and nonce usage
(#105, #103, #98, #97).
* Apply various editorial improvements.
draft-02
* Fully specify both rounds of FROST, as well as trusted dealer key
generation.
* Add ciphersuites and corresponding test vectors, including suites
for RFC8032 compatibility.
* Refactor document for editorial clarity.
draft-01
* Specify operations, notation and cryptographic dependencies.
draft-00
* Outline CFRG draft based on draft-komlo-frost.
2. Conventions and Definitions 2. Conventions and Definitions
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in "OPTIONAL" in this document are to be interpreted as described in
BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here. capitals, as shown here.
The following notation is used throughout the document. The following notation is used throughout the document.
* byte: A sequence of eight bits. byte: A sequence of eight bits.
* random_bytes(n): Outputs n bytes, sampled uniformly at random random_bytes(n): Outputs n bytes, sampled uniformly at random using
using a cryptographically secure pseudorandom number generator a cryptographically secure pseudorandom number generator (CSPRNG).
(CSPRNG).
* count(i, L): Outputs the number of times the element i is count(i, L): Outputs the number of times the element i is
represented in the list L. represented in the list L.
* len(l): Outputs the length of list l, e.g., len([1,2,3]) = 3. len(l): Outputs the length of list l, e.g., len([1,2,3]) = 3.
* reverse(l): Outputs the list l in reverse order, e.g., reverse(l): Outputs the list l in reverse order, e.g.,
reverse([1,2,3]) = [3,2,1]. reverse([1,2,3]) = [3,2,1].
* range(a, b): Outputs a list of integers from a to b-1 in ascending range(a, b): Outputs a list of integers from a to b-1 in ascending
order, e.g., range(1, 4) = [1,2,3]. order, e.g., range(1, 4) = [1,2,3].
* pow(a, b): Outputs the result, a Scalar, of a to the power of b, pow(a, b): Outputs the result, a Scalar, of a to the power of b,
e.g., pow(2, 3) = 8 modulo the relevant group order p. e.g., pow(2, 3) = 8 modulo the relevant group order p.
* || denotes concatenation of byte strings, i.e., x || y denotes the ||: Denotes concatenation of byte strings, i.e., x || y denotes the
byte string x, immediately followed by the byte string y, with no byte string x, immediately followed by the byte string y, with no
extra separator, yielding xy. extra separator, yielding xy.
* nil denotes an empty byte string. nil: Denotes an empty byte string.
Unless otherwise stated, we assume that secrets are sampled uniformly Unless otherwise stated, we assume that secrets are sampled uniformly
at random using a cryptographically secure pseudorandom number at random using a CSPRNG; see [RFC4086] for additional guidance on
generator (CSPRNG); see [RFC4086] for additional guidance on the the generation of random numbers.
generation of random numbers.
3. Cryptographic Dependencies 3. Cryptographic Dependencies
FROST signing depends on the following cryptographic constructs: FROST signing depends on the following cryptographic constructs:
* Prime-order Group, Section 3.1; * Prime-order group (Section 3.1)
* Cryptographic hash function, Section 3.2; * Cryptographic hash function (Section 3.2)
These are described in the following sections. The following sections describe these constructs in more detail.
3.1. Prime-Order Group 3.1. Prime-Order Group
FROST depends on an abelian group of prime order p. We represent FROST depends on an abelian group of prime order p. We represent
this group as the object G that additionally defines helper functions this group as the object G that additionally defines helper functions
described below. The group operation for G is addition + with described below. The group operation for G is addition + with
identity element I. For any elements A and B of the group G, A + B = identity element I. For any elements A and B of the group G, A + B =
B + A is also a member of G. Also, for any A in G, there exists an B + A is also a member of G. Also, for any A in G, there exists an
element -A such that A + (-A) = (-A) + A = I. For convenience, we element -A such that A + (-A) = (-A) + A = I. For convenience, we
use - to denote subtraction, e.g., A - B = A + (-B). Integers, taken use - to denote subtraction, e.g., A - B = A + (-B). Integers, taken
modulo the group order p, are called scalars; arithmetic operations modulo the group order p, are called "Scalars"; arithmetic operations
on scalars are implicitly performed modulo p. Since p is prime, on Scalars are implicitly performed modulo p. Since p is prime,
scalars form a finite field. Scalar multiplication is equivalent to Scalars form a finite field. Scalar multiplication is equivalent to
the repeated application of the group operation on an element A with the repeated application of the group operation on an element A with
itself r-1 times, denoted as ScalarMult(A, r). We denote the sum, itself r-1 times, denoted as ScalarMult(A, r). We denote the sum,
difference, and product of two scalars using the +, -, and * difference, and product of two Scalars using the +, -, and *
operators, respectively. (Note that this means + may refer to group operators, respectively. (Note that this means + may refer to group
element addition or scalar addition, depending on the type of the element addition or Scalar addition, depending on the type of the
operands.) For any element A, ScalarMult(A, p) = I. We denote B as operands.) For any element A, ScalarMult(A, p) = I. We denote B as
a fixed generator of the group. Scalar base multiplication is a fixed generator of the group. Scalar base multiplication is
equivalent to the repeated application of the group operation on B equivalent to the repeated application of the group operation on B
with itself r-1 times, this is denoted as ScalarBaseMult(r). The set with itself r-1 times, denoted as ScalarBaseMult(r). The set of
of scalars corresponds to GF(p), which we refer to as the scalar Scalars corresponds to GF(p), which we refer to as the Scalar field.
field. It is assumed that group element addition, negation, and It is assumed that group element addition, negation, and equality
equality comparison can be efficiently computed for arbitrary group comparison can be efficiently computed for arbitrary group elements.
elements.
This document uses types Element and Scalar to denote elements of the This document uses types Element and Scalar to denote elements of the
group G and its set of scalars, respectively. We denote Scalar(x) as group G and its set of Scalars, respectively. We denote Scalar(x) as
the conversion of integer input x to the corresponding Scalar value the conversion of integer input x to the corresponding Scalar value
with the same numeric value. For example, Scalar(1) yields a Scalar with the same numeric value. For example, Scalar(1) yields a Scalar
representing the value 1. Moreover, we use the type NonZeroScalar to representing the value 1. Moreover, we use the type NonZeroScalar to
denote a Scalar value that is not equal to zero, i.e., Scalar(0). We denote a Scalar value that is not equal to zero, i.e., Scalar(0). We
denote equality comparison of these types as == and assignment of denote equality comparison of these types as == and assignment of
values by =. When comparing Scalar values, e.g., for the purposes of values by =. When comparing Scalar values, e.g., for the purposes of
sorting lists of Scalar values, the least nonnegative representation sorting lists of Scalar values, the least nonnegative representation
mod p is used. mod p is used.
We now detail a number of member functions that can be invoked on G. We now detail a number of member functions that can be invoked on G.
* Order(): Outputs the order of G (i.e., p). Order(): Outputs the order of G (i.e., p).
* Identity(): Outputs the identity Element of the group (i.e., I). Identity(): Outputs the identity Element of the group (i.e., I).
* RandomScalar(): Outputs a random Scalar element in GF(p), i.e., a RandomScalar(): Outputs a random Scalar element in GF(p), i.e., a
random scalar in [0, p - 1]. random Scalar in [0, p - 1].
* ScalarMult(A, k): Outputs the scalar multiplication between ScalarMult(A, k): Outputs the Scalar multiplication between Element
Element A and Scalar k. A and Scalar k.
* ScalarBaseMult(k): Outputs the scalar multiplication between ScalarBaseMult(k): Outputs the Scalar multiplication between Scalar
Scalar k and the group generator B. k and the group generator B.
* SerializeElement(A): Maps an Element A to a canonical byte array SerializeElement(A): Maps an Element A to a canonical byte array buf
buf of fixed length Ne. This function raises an error if A is the of fixed length Ne. This function raises an error if A is the
identity element of the group. identity element of the group.
* DeserializeElement(buf): Attempts to map a byte array buf to an DeserializeElement(buf): Attempts to map a byte array buf to an
Element A, and fails if the input is not the valid canonical byte Element A and fails if the input is not the valid canonical byte
representation of an element of the group. This function raises representation of an element of the group. This function raises
an error if deserialization fails or if A is the identity element an error if deserialization fails or if A is the identity element
of the group; see Section 6 for group-specific input validation of the group; see Section 6 for group-specific input validation
steps. steps.
* SerializeScalar(s): Maps a Scalar s to a canonical byte array buf SerializeScalar(s): Maps a Scalar s to a canonical byte array buf of
of fixed length Ns. fixed length Ns.
* DeserializeScalar(buf): Attempts to map a byte array buf to a DeserializeScalar(buf): Attempts to map a byte array buf to a Scalar
Scalar s. This function raises an error if deserialization fails; s. This function raises an error if deserialization fails; see
see Section 6 for group-specific input validation steps. Section 6 for group-specific input validation steps.
3.2. Cryptographic Hash Function 3.2. Cryptographic Hash Function
FROST requires the use of a cryptographically secure hash function, FROST requires the use of a cryptographically secure hash function,
generically written as H, which is modeled as a random oracle in generically written as H, which is modeled as a random oracle in
security proofs for the protocol (see [FROST20] and [StrongerSec22]). security proofs for the protocol (see [FROST20] and [StrongerSec22]).
For concrete recommendations on hash functions which SHOULD be used For concrete recommendations on hash functions that SHOULD be used in
in practice, see Section 6. Using H, we introduce distinct domain- practice, see Section 6. Using H, we introduce distinct domain-
separated hashes, H1, H2, H3, H4, and H5: separated hashes H1, H2, H3, H4, and H5:
* H1, H2, and H3 map arbitrary byte strings to Scalar elements * H1, H2, and H3 map arbitrary byte strings to Scalar elements
associated with the prime-order group. associated with the prime-order group.
* H4 and H5 are aliases for H with distinct domain separators. * H4 and H5 are aliases for H with distinct domain separators.
The details of H1, H2, H3, H4, and H5 vary based on ciphersuite. See The details of H1, H2, H3, H4, and H5 vary based on the ciphersuite
Section 6 for more details about each. used. See Section 6 for more details about each.
4. Helper Functions 4. Helper Functions
Beyond the core dependencies, the protocol in this document depends Beyond the core dependencies, the protocol in this document depends
on the following helper operations: on the following helper operations:
* Nonce generation, Section 4.1; * Nonce generation (Section 4.1);
* Polynomials, Section 4.2; * Polynomials (Section 4.2);
* Encoding operations, Section 4.3; * List operations (Section 4.3);
* Signature binding computation Section 4.4; * Binding factors computation (Section 4.4);
* Group commitment computation Section 4.5; and * Group commitment computation (Section 4.5); and
* Signature challenge computation Section 4.6. * Signature challenge computation (Section 4.6).
The following sections describe these operations in more detail. The following sections describe these operations in more detail.
4.1. Nonce generation 4.1. Nonce Generation
To hedge against a bad RNG that outputs predictable values, nonces To hedge against a bad random number generator (RNG) that outputs
are generated with the nonce_generate function by combining fresh predictable values, nonces are generated with the nonce_generate
randomness with the secret key as input to a domain-separated hash function by combining fresh randomness with the secret key as input
function built from the ciphersuite hash function H. This domain- to a domain-separated hash function built from the ciphersuite hash
separated hash function is denoted H3. This function always samples function H. This domain-separated hash function is denoted as H3.
32 bytes of fresh randomness to ensure that the probability of nonce This function always samples 32 bytes of fresh randomness to ensure
reuse is at most 2^-128 as long as no more than 2^64 signatures are that the probability of nonce reuse is at most 2^-128 as long as no
computed by a given signing participant. more than 2^64 signatures are computed by a given signing
participant.
Inputs: Inputs:
- secret, a Scalar. - secret, a Scalar.
Outputs: Outputs:
- nonce, a Scalar. - nonce, a Scalar.
def nonce_generate(secret): def nonce_generate(secret):
random_bytes = random_bytes(32) random_bytes = random_bytes(32)
secret_enc = G.SerializeScalar(secret) secret_enc = G.SerializeScalar(secret)
return H3(random_bytes || secret_enc) return H3(random_bytes || secret_enc)
4.2. Polynomials 4.2. Polynomials
This section defines polynomials over Scalars that are used in the This section defines polynomials over Scalars that are used in the
main protocol. A polynomial of maximum degree t is represented as a main protocol. A polynomial of maximum degree t is represented as a
list of t+1 coefficients, where the constant term of the polynomial list of t+1 coefficients, where the constant term of the polynomial
is in the first position and the highest-degree coefficient is in the is in the first position and the highest-degree coefficient is in the
last position. For example, the polynomial x^2 + 2x + 3 has degree 2 last position. For example, the polynomial x^2 + 2x + 3 has degree 2
and is represented as a list of 3 coefficients [3, 2, 1]. A point on and is represented as a list of three coefficients [3, 2, 1]. A
the polynomial f is a tuple (x, y), where y = f(x). point on the polynomial f is a tuple (x, y), where y = f(x).
The function derive_interpolating_value derives a value used for The function derive_interpolating_value derives a value that is used
polynomial interpolation. It is provided a list of x-coordinates as for polynomial interpolation. It is provided a list of x-coordinates
input, each of which cannot equal 0. as input, each of which cannot equal 0.
Inputs: Inputs:
- L, the list of x-coordinates, each a NonZeroScalar. - L, the list of x-coordinates, each a NonZeroScalar.
- x_i, an x-coordinate contained in L, a NonZeroScalar. - x_i, an x-coordinate contained in L, a NonZeroScalar.
Outputs: Outputs:
- value, a Scalar. - value, a Scalar.
Errors: Errors:
- "invalid parameters", if 1) x_i is not in L, or if 2) any - "invalid parameters", if 1) x_i is not in L, or if 2) any
skipping to change at page 16, line 5 skipping to change at line 448
if identifier == i: if identifier == i:
return binding_factor return binding_factor
raise "invalid participant" raise "invalid participant"
4.4. Binding Factors Computation 4.4. Binding Factors Computation
This section describes the subroutine for computing binding factors This section describes the subroutine for computing binding factors
based on the participant commitment list, message to be signed, and based on the participant commitment list, message to be signed, and
group public key. group public key.
Inputs: Inputs:
- group_public_key, the public key corresponding to the group signing - group_public_key, the public key corresponding to the group signing
key, an Element. key, an Element.
- commitment_list = [(i, hiding_nonce_commitment_i, - commitment_list = [(i, hiding_nonce_commitment_i,
binding_nonce_commitment_i), ...], a list of commitments issued by binding_nonce_commitment_i), ...], a list of commitments issued by
each participant, where each element in the list indicates a each participant, where each element in the list indicates a
NonZeroScalar identifier i and two commitment Element values NonZeroScalar identifier i and two commitment Element values
(hiding_nonce_commitment_i, binding_nonce_commitment_i). This list (hiding_nonce_commitment_i, binding_nonce_commitment_i). This list
MUST be sorted in ascending order by identifier. MUST be sorted in ascending order by identifier.
- msg, the message to be signed. - msg, the message to be signed.
Outputs: Outputs:
- binding_factor_list, a list of (NonZeroScalar, Scalar) tuples - binding_factor_list, a list of (NonZeroScalar, Scalar) tuples
representing the binding factors. representing the binding factors.
def compute_binding_factors(group_public_key, commitment_list, msg): def compute_binding_factors(group_public_key, commitment_list, msg):
group_public_key_enc = G.SerializeElement(group_public_key) group_public_key_enc = G.SerializeElement(group_public_key)
// Hashed to a fixed-length. // Hashed to a fixed length.
msg_hash = H4(msg) msg_hash = H4(msg)
// Hashed to a fixed-length. // Hashed to a fixed length.
encoded_commitment_hash = encoded_commitment_hash =
H5(encode_group_commitment_list(commitment_list)) H5(encode_group_commitment_list(commitment_list))
// The encoding of the group public key is a fixed length within a ciphersuite. // The encoding of the group public key is a fixed length
rho_input_prefix = group_public_key_enc || msg_hash || encoded_commitment_hash // within a ciphersuite.
rho_input_prefix = group_public_key_enc || msg_hash ||
encoded_commitment_hash
binding_factor_list = [] binding_factor_list = []
for (identifier, hiding_nonce_commitment, for (identifier, hiding_nonce_commitment,
binding_nonce_commitment) in commitment_list: binding_nonce_commitment) in commitment_list:
rho_input = rho_input_prefix || G.SerializeScalar(identifier) rho_input = rho_input_prefix || G.SerializeScalar(identifier)
binding_factor = H1(rho_input) binding_factor = H1(rho_input)
binding_factor_list.append((identifier, binding_factor)) binding_factor_list.append((identifier, binding_factor))
return binding_factor_list return binding_factor_list
4.5. Group Commitment Computation 4.5. Group Commitment Computation
This section describes the subroutine for creating the group This section describes the subroutine for creating the group
commitment from a commitment list. commitment from a commitment list.
Inputs: Inputs:
- commitment_list = [(i, hiding_nonce_commitment_i, - commitment_list = [(i, hiding_nonce_commitment_i,
binding_nonce_commitment_i), ...], a list of commitments issued by binding_nonce_commitment_i), ...], a list of commitments issued by
each participant, where each element in the list indicates a each participant, where each element in the list indicates a
skipping to change at page 17, line 37 skipping to change at line 520
binding_factor) binding_factor)
group_commitment = ( group_commitment = (
group_commitment + group_commitment +
hiding_nonce_commitment + hiding_nonce_commitment +
binding_nonce) binding_nonce)
return group_commitment return group_commitment
Note that the performance of this algorithm is defined naively and Note that the performance of this algorithm is defined naively and
scales linearly relative to the number of signers. For improved scales linearly relative to the number of signers. For improved
performance, the group commitment can be computed using multi- performance, the group commitment can be computed using multi-
exponentation techniques such as Pippinger's algorithm; see [MultExp] exponentiation techniques such as Pippinger's algorithm; see
for more details. [MultExp] for more details.
4.6. Signature Challenge Computation 4.6. Signature Challenge Computation
This section describes the subroutine for creating the per-message This section describes the subroutine for creating the per-message
challenge. challenge.
Inputs: Inputs:
- group_commitment, the group commitment, an Element. - group_commitment, the group commitment, an Element.
- group_public_key, the public key corresponding to the group signing - group_public_key, the public key corresponding to the group signing
key, an Element. key, an Element.
skipping to change at page 18, line 26 skipping to change at line 549
group_public_key_enc = G.SerializeElement(group_public_key) group_public_key_enc = G.SerializeElement(group_public_key)
challenge_input = group_comm_enc || group_public_key_enc || msg challenge_input = group_comm_enc || group_public_key_enc || msg
challenge = H2(challenge_input) challenge = H2(challenge_input)
return challenge return challenge
5. Two-Round FROST Signing Protocol 5. Two-Round FROST Signing Protocol
This section describes the two-round FROST signing protocol for This section describes the two-round FROST signing protocol for
producing Schnorr signatures. The protocol is configured to run with producing Schnorr signatures. The protocol is configured to run with
a selection of NUM_PARTICIPANTS signer participants and a a selection of NUM_PARTICIPANTS signer participants and a
Coordinator. NUM_PARTICIPANTS is a positive non-zero integer which Coordinator. NUM_PARTICIPANTS is a positive and non-zero integer
MUST be at least MIN_PARTICIPANTS but MUST NOT be larger than that MUST be at least MIN_PARTICIPANTS, but MUST NOT be larger than
MAX_PARTICIPANTS, where MIN_PARTICIPANTS <= MAX_PARTICIPANTS, MAX_PARTICIPANTS, where MIN_PARTICIPANTS <= MAX_PARTICIPANTS and
MIN_PARTICIPANTS is a positive non-zero integer and MAX_PARTICIPANTS MIN_PARTICIPANTS is a positive and non-zero integer. Additionally,
MUST be a positive integer less than the group order. A signer MAX_PARTICIPANTS MUST be a positive integer less than the group
participant, or simply participant, is an entity that is trusted to order. A signer participant, or simply "participant", is an entity
hold and use a signing key share. The Coordinator is an entity with that is trusted to hold and use a signing key share. The Coordinator
the following responsibilities: is an entity with the following responsibilities:
1. Determining which participants will participate (at least 1. Determining the participants that will participate (at least
MIN_PARTICIPANTS in number); MIN_PARTICIPANTS in number);
2. Coordinating rounds (receiving and forwarding inputs among 2. Coordinating rounds (receiving and forwarding inputs among
participants); and participants);
3. Aggregating signature shares output by each participant, and 3. Aggregating signature shares output by each participant; and
publishing the resulting signature.
4. Publishing the resulting signature.
FROST assumes that the Coordinator and the set of signer participants FROST assumes that the Coordinator and the set of signer participants
are chosen externally to the protocol. Note that it is possible to are chosen externally to the protocol. Note that it is possible to
deploy the protocol without designating a single Coordinator; see deploy the protocol without designating a single Coordinator; see
Section 7.5 for more information. Section 7.5 for more information.
FROST produces signatures that can be verified as if they were FROST produces signatures that can be verified as if they were
produced from a single signer using a signing key s with produced from a single signer using a signing key s with
corresponding public key PK, where s is a Scalar value and PK = corresponding public key PK, where s is a Scalar value and PK =
G.ScalarBaseMult(s). As a threshold signing protocol, the group G.ScalarBaseMult(s). As a threshold signing protocol, the group
signing key s is Shamir secret-shared amongst each of the signing key s is Shamir secret-shared amongst each of the
MAX_PARTICIPANTS participants and used to produce signatures; see MAX_PARTICIPANTS participants and is used to produce signatures; see
Appendix D.1 for more information about Shamir secret sharing. In Appendix C.1 for more information about Shamir secret sharing. In
particular, FROST assumes each participant is configured with the particular, FROST assumes each participant is configured with the
following information: following information:
* An identifier, which is a NonZeroScalar value denoted i in the * An identifier, which is a NonZeroScalar value denoted as i in the
range [1, MAX_PARTICIPANTS] and MUST be distinct from the range [1, MAX_PARTICIPANTS] and MUST be distinct from the
identifier of every other participant. identifier of every other participant.
* A signing key sk_i, which is a Scalar value representing the i-th * A signing key sk_i, which is a Scalar value representing the i-th
Shamir secret share of the group signing key s. In particular, Shamir secret share of the group signing key s. In particular,
sk_i is the value f(i) on a secret polynomial f of degree sk_i is the value f(i) on a secret polynomial f of degree
(MIN_PARTICIPANTS - 1), where s is f(0). The public key (MIN_PARTICIPANTS - 1), where s is f(0). The public key
corresponding to this signing key share is PK_i = corresponding to this signing key share is PK_i =
G.ScalarBaseMult(sk_i). G.ScalarBaseMult(sk_i).
The Coordinator and each participant are additionally configured with Additionally, the Coordinator and each participant are configured
common group information, denoted "group info," which consists of the with common group information, denoted as "group info," which
following: consists of the following:
* Group public key, which is an Element in G denoted PK. * Group public key, which is an Element in G denoted as PK.
* Public keys PK_i for each participant, which are Element values in * Public keys PK_i for each participant, which are Element values in
G denoted PK_i for each i in [1, MAX_PARTICIPANTS]. G denoted as PK_i for each i in [1, MAX_PARTICIPANTS].
This document does not specify how this information, including the This document does not specify how this information, including the
signing key shares, are configured and distributed to participants. signing key shares, are configured and distributed to participants.
In general, two possible configuration mechanisms are possible: one In general, two configuration mechanisms are possible: one that
that requires a single, trusted dealer, and the other which requires requires a single trusted dealer and one that requires performing a
performing a distributed key generation protocol. We highlight key distributed key generation protocol. We highlight the key generation
generation mechanism by a trusted dealer in Appendix D for reference. mechanism by a trusted dealer in Appendix C for reference.
FROST requires two rounds to complete. In the first round, FROST requires two rounds to complete. In the first round,
participants generate and publish one-time-use commitments to be used participants generate and publish one-time-use commitments to be used
in the second round. In the second round, each participant produces in the second round. In the second round, each participant produces
a share of the signature over the Coordinator-chosen message and the a share of the signature over the Coordinator-chosen message and the
other participant commitments. After the second round completes, the other participant commitments. After the second round is completed,
Coordinator aggregates the signature shares to produce a final the Coordinator aggregates the signature shares to produce a final
signature. The Coordinator SHOULD abort if the signature is invalid; signature. The Coordinator SHOULD abort the protocol if the
see Section 5.4 for more information about dealing with invalid signature is invalid; see Section 5.4 for more information about
signatures and misbehaving participants. This complete interaction, dealing with invalid signatures and misbehaving participants. This
without abort, is shown in Figure 1. complete interaction (without being aborted) is shown in Figure 1.
(group info) (group info, (group info, (group info) (group info, (group info,
| signing key share) signing key share) | signing key share) signing key share)
| | | | | |
v v v v v v
Coordinator Signer-1 ... Signer-n Coordinator Signer-1 ... Signer-n
------------------------------------------------------------ ------------------------------------------------------------
message signing request
------------> ------------>
| |
== Round 1 (Commitment) == == Round 1 (Commitment) ==
| participant commitment | | | participant commitment | |
|<-----------------------+ | |<-----------------------+ |
| ... | | ... |
| participant commitment (commit state) ==\ | participant commitment (commit state) ==\
|<-----------------------------------------+ | |<-----------------------------------------+ |
| |
== Round 2 (Signature Share Generation) == | == Round 2 (Signature Share Generation) == |
message
------------>
| | | |
| participant input | | | | participant input | | |
+------------------------> | | +------------------------> | |
| signature share | | | | signature share | | |
|<-----------------------+ | | |<-----------------------+ | |
| ... | | | ... | |
| participant input | | | participant input | |
+------------------------------------------> / +------------------------------------------> /
| signature share |<=======/ | signature share |<=======/
<------------------------------------------+ <------------------------------------------+
| |
== Aggregation == == Aggregation ==
| |
signature | signature |
<-----------+ <-----------+
Figure 1: FROST protocol overview Figure 1: FROST Protocol Overview
Details for round one are described in Section 5.1, and details for Details for round one are described in Section 5.1 and details for
round two are described in Section 5.2. Note that each participant round two are described in Section 5.2. Note that each participant
persists some state between the two rounds, and this state is deleted persists some state between the two rounds; this state is deleted as
as described in Section 5.2. The final Aggregation step is described described in Section 5.2. The final Aggregation step is described in
in Section 5.3. Section 5.3.
FROST assumes that all inputs to each round, especially those of FROST assumes that all inputs to each round, especially those that
which are received over the network, are validated before use. In are received over the network, are validated before use. In
particular, this means that any value of type Element or Scalar particular, this means that any value of type Element or Scalar
received over the network MUST be deserialized using received over the network MUST be deserialized using
DeserializeElement and DeserializeScalar, respectively, as these DeserializeElement and DeserializeScalar, respectively, as these
functions perform the necessary input validation steps, and that all functions perform the necessary input validation steps.
messages sent over the wire MUST be encoded appropriately, e.g., that Additionally, all messages sent over the wire MUST be encoded using
Scalars and Elements are encoded using their respective functions their respective functions, e.g., Scalars and Elements are encoded
SerializeScalar and SerializeElement. using SerializeScalar and SerializeElement.
FROST assumes reliable message delivery between the Coordinator and FROST assumes reliable message delivery between the Coordinator and
participants in order for the protocol to complete. An attacker participants in order for the protocol to complete. An attacker
masquerading as another participant will result only in an invalid masquerading as another participant will result only in an invalid
signature; see Section 7. However, in order to identify misbehaving signature; see Section 7. However, in order to identify misbehaving
participants, we assume that the network channel is additionally participants, we assume that the network channel is additionally
authenticated; confidentiality is not required. authenticated; confidentiality is not required.
5.1. Round One - Commitment 5.1. Round One - Commitment
skipping to change at page 22, line 15 skipping to change at line 720
The outputs nonce and comm from participant P_i are both stored The outputs nonce and comm from participant P_i are both stored
locally and kept for use in the second round. The nonce value is locally and kept for use in the second round. The nonce value is
secret and MUST NOT be shared, whereas the public output comm is sent secret and MUST NOT be shared, whereas the public output comm is sent
to the Coordinator. The nonce values produced by this function MUST to the Coordinator. The nonce values produced by this function MUST
NOT be used in more than one invocation of sign, and the nonces MUST NOT be used in more than one invocation of sign, and the nonces MUST
be generated from a source of secure randomness. be generated from a source of secure randomness.
5.2. Round Two - Signature Share Generation 5.2. Round Two - Signature Share Generation
In round two, the Coordinator is responsible for sending the message In round two, the Coordinator is responsible for sending the message
to be signed, and for choosing which participants will participate to be signed and choosing the participants that will participate (a
(of number at least MIN_PARTICIPANTS). Signers additionally require number of at least MIN_PARTICIPANTS). Signers additionally require
locally held data; specifically, their private key and the nonces locally held data, specifically their private key and the nonces
corresponding to their commitment issued in round one. corresponding to their commitment issued in round one.
The Coordinator begins by sending each participant the message to be The Coordinator begins by sending each participant the message to be
signed along with the set of signing commitments for all participants signed along with the set of signing commitments for all participants
in the participant list. Each participant MUST validate the inputs in the participant list. Each participant MUST validate the inputs
before processing the Coordinator's request. In particular, the before processing the Coordinator's request. In particular, the
Signer MUST validate commitment_list, deserializing each group signer MUST validate commitment_list, deserializing each group
Element in the list using DeserializeElement from Section 3.1. If Element in the list using DeserializeElement from Section 3.1. If
deserialization fails, the Signer MUST abort the protocol. Moreover, deserialization fails, the signer MUST abort the protocol. Moreover,
each participant MUST ensure that its identifier and commitments each participant MUST ensure that its identifier and commitments
(from the first round) appear in commitment_list. Applications which (from the first round) appear in commitment_list. Applications that
require that participants not process arbitrary input messages are restrict participants from processing arbitrary input messages are
also required to perform relevant application-layer input validation also required to perform relevant application-layer input validation
checks; see Section 7.7 for more details. checks; see Section 7.7 for more details.
Upon receipt and successful input validation, each Signer then runs Upon receipt and successful input validation, each signer then runs
the following procedure to produce its own signature share. the following procedure to produce its own signature share.
Inputs: Inputs:
- identifier, identifier i of the participant, a NonZeroScalar. - identifier, identifier i of the participant, a NonZeroScalar.
- sk_i, Signer secret key share, a Scalar. - sk_i, signer secret key share, a Scalar.
- group_public_key, public key corresponding to the group signing - group_public_key, public key corresponding to the group signing
key, an Element. key, an Element.
- nonce_i, pair of Scalar values (hiding_nonce, binding_nonce) - nonce_i, pair of Scalar values (hiding_nonce, binding_nonce)
generated in round one. generated in round one.
- msg, the message to be signed, a byte string. - msg, the message to be signed, a byte string.
- commitment_list = [(i, hiding_nonce_commitment_i, - commitment_list = [(i, hiding_nonce_commitment_i,
binding_nonce_commitment_i), ...], a list of commitments issued by binding_nonce_commitment_i), ...], a list of commitments issued by
each participant, where each element in the list indicates a each participant, where each element in the list indicates a
NonZeroScalar identifier i and two commitment Element values NonZeroScalar identifier i and two commitment Element values
(hiding_nonce_commitment_i, binding_nonce_commitment_i). This list (hiding_nonce_commitment_i, binding_nonce_commitment_i). This list
MUST be sorted in ascending order by identifier. MUST be sorted in ascending order by identifier.
Outputs: Outputs:
- sig_share, a signature share, a Scalar. - sig_share, a signature share, a Scalar.
def sign(identifier, sk_i, group_public_key, def sign(identifier, sk_i, group_public_key,
nonce_i, msg, commitment_list): nonce_i, msg, commitment_list):
# Compute the binding factor(s) # Compute the binding factor(s)
binding_factor_list = compute_binding_factors(group_public_key, commitment_list, msg) binding_factor_list = compute_binding_factors(group_public_key,
binding_factor = binding_factor_for_participant( commitment_list, msg)
binding_factor_list, identifier) binding_factor = binding_factor_for_participant(
binding_factor_list, identifier)
# Compute the group commitment # Compute the group commitment
group_commitment = compute_group_commitment( group_commitment = compute_group_commitment(
commitment_list, binding_factor_list) commitment_list, binding_factor_list)
# Compute the interpolating value # Compute the interpolating value
participant_list = participants_from_commitment_list( participant_list = participants_from_commitment_list(
commitment_list) commitment_list)
lambda_i = derive_interpolating_value(participant_list, identifier) lambda_i = derive_interpolating_value(participant_list, identifier)
# Compute the per-message challenge # Compute the per-message challenge
challenge = compute_challenge( challenge = compute_challenge(
group_commitment, group_public_key, msg) group_commitment, group_public_key, msg)
# Compute the signature share # Compute the signature share
(hiding_nonce, binding_nonce) = nonce_i (hiding_nonce, binding_nonce) = nonce_i
sig_share = hiding_nonce + (binding_nonce * binding_factor) + sig_share = hiding_nonce + (binding_nonce * binding_factor) +
(lambda_i * sk_i * challenge) (lambda_i * sk_i * challenge)
return sig_share
return sig_share
The output of this procedure is a signature share. Each participant The output of this procedure is a signature share. Each participant
then sends these shares back to the Coordinator. Each participant sends these shares back to the Coordinator. Each participant MUST
MUST delete the nonce and corresponding commitment after completing delete the nonce and corresponding commitment after completing sign
sign, and MUST NOT use the nonce as input more than once to sign. and MUST NOT use the nonce as input more than once to sign.
Note that the lambda_i value derived during this procedure does not Note that the lambda_i value derived during this procedure does not
change across FROST signing operations for the same signing group. change across FROST signing operations for the same signing group.
As such, participants can compute it once and store it for reuse As such, participants can compute it once and store it for reuse
across signing sessions. across signing sessions.
5.3. Signature Share Aggregation 5.3. Signature Share Aggregation
After participants perform round two and send their signature shares After participants perform round two and send their signature shares
to the Coordinator, the Coordinator aggregates each share to produce to the Coordinator, the Coordinator aggregates each share to produce
a final signature. Before aggregating, the Coordinator MUST validate a final signature. Before aggregating, the Coordinator MUST validate
each signature share using DeserializeScalar. If validation fails, each signature share using DeserializeScalar. If validation fails,
the Coordinator MUST abort the protocol as the resulting signature the Coordinator MUST abort the protocol, as the resulting signature
will be invalid. If all signature shares are valid, the Coordinator will be invalid. If all signature shares are valid, the Coordinator
aggregates them to produce the final signature using the following aggregates them to produce the final signature using the following
procedure. procedure.
Inputs: Inputs:
- commitment_list = [(i, hiding_nonce_commitment_i, - commitment_list = [(i, hiding_nonce_commitment_i,
binding_nonce_commitment_i), ...], a list of commitments issued by binding_nonce_commitment_i), ...], a list of commitments issued by
each participant, where each element in the list indicates a each participant, where each element in the list indicates a
NonZeroScalar identifier i and two commitment Element values NonZeroScalar identifier i and two commitment Element values
(hiding_nonce_commitment_i, binding_nonce_commitment_i). This list (hiding_nonce_commitment_i, binding_nonce_commitment_i). This list
MUST be sorted in ascending order by identifier. MUST be sorted in ascending order by identifier.
- msg, the message to be signed, a byte string. - msg, the message to be signed, a byte string.
- group_public_key, public key corresponding to the group signing - group_public_key, public key corresponding to the group signing
key, an Element. key, an Element.
- sig_shares, a set of signature shares z_i, Scalar values, for each - sig_shares, a set of signature shares z_i, Scalar values, for each
participant, of length NUM_PARTICIPANTS, where participant, of length NUM_PARTICIPANTS, where
MIN_PARTICIPANTS <= NUM_PARTICIPANTS <= MAX_PARTICIPANTS. MIN_PARTICIPANTS <= NUM_PARTICIPANTS <= MAX_PARTICIPANTS.
Outputs: Outputs:
- (R, z), a Schnorr signature consisting of an Element R and - (R, z), a Schnorr signature consisting of an Element R and
Scalar z. Scalar z.
def aggregate(commitment_list, msg, group_public_key, sig_shares): def aggregate(commitment_list, msg, group_public_key, sig_shares):
# Compute the binding factors # Compute the binding factors
binding_factor_list = compute_binding_factors(group_public_key, commitment_list, msg) binding_factor_list = compute_binding_factors(group_public_key,
commitment_list, msg)
# Compute the group commitment # Compute the group commitment
group_commitment = compute_group_commitment( group_commitment = compute_group_commitment(
commitment_list, binding_factor_list) commitment_list, binding_factor_list)
# Compute aggregated signature # Compute aggregated signature
z = Scalar(0) z = Scalar(0)
for z_i in sig_shares: for z_i in sig_shares:
z = z + z_i z = z + z_i
return (group_commitment, z) return (group_commitment, z)
The output from the aggregation step is the output signature (R, z). The output from the aggregation step is the output signature (R, z).
The canonical encoding of this signature is specified in Section 6. The canonical encoding of this signature is specified in Section 6.
The Coordinator SHOULD verify this signature using the group public The Coordinator SHOULD verify this signature using the group public
key before publishing or releasing the signature. Signature key before publishing or releasing the signature. Signature
verification is as specified for the corresponding ciphersuite; see verification is as specified for the corresponding ciphersuite; see
Section 6 for details. The aggregate signature will verify Section 6 for details. The aggregate signature will verify
successfully if all signature shares are valid. Moreover, subsets of successfully if all signature shares are valid. Moreover, subsets of
valid signature shares will themselves not yield a valid aggregate valid signature shares will not yield a valid aggregate signature
signature. themselves.
If the aggregate signature verification fails, the Coordinator MAY If the aggregate signature verification fails, the Coordinator MAY
verify each signature share individually to identify and act on verify each signature share individually to identify and act on
misbehaving participants. The mechanism for acting on a misbehaving misbehaving participants. The mechanism for acting on a misbehaving
participant is out of scope for this specification; see Section 5.4 participant is out of scope for this specification; see Section 5.4
for more information about dealing with invalid signatures and for more information about dealing with invalid signatures and
misbehaving participants. misbehaving participants.
The function for verifying a signature share, denoted The function for verifying a signature share, denoted as
verify_signature_share, is described below. Recall that the verify_signature_share, is described below. Recall that the
Coordinator is configured with "group info" which contains the group Coordinator is configured with "group info" that contains the group
public key PK and public keys PK_i for each participant, so the public key PK and public keys PK_i for each participant. The
group_public_key and PK_i function arguments MUST come from that group_public_key and PK_i function arguments MUST come from that
previously stored group info. previously stored group info.
Inputs: Inputs:
- identifier, identifier i of the participant, a NonZeroScalar. - identifier, identifier i of the participant, a NonZeroScalar.
- PK_i, the public key for the i-th participant, where - PK_i, the public key for the i-th participant, where
PK_i = G.ScalarBaseMult(sk_i), an Element. PK_i = G.ScalarBaseMult(sk_i), an Element.
- comm_i, pair of Element values in G - comm_i, pair of Element values in G
(hiding_nonce_commitment, binding_nonce_commitment) generated in (hiding_nonce_commitment, binding_nonce_commitment) generated in
round one from the i-th participant. round one from the i-th participant.
- sig_share_i, a Scalar value indicating the signature share as - sig_share_i, a Scalar value indicating the signature share as
produced in round two from the i-th participant. produced in round two from the i-th participant.
- commitment_list = [(i, hiding_nonce_commitment_i, - commitment_list = [(i, hiding_nonce_commitment_i,
binding_nonce_commitment_i), ...], a list of commitments issued by binding_nonce_commitment_i), ...], a list of commitments issued by
each participant, where each element in the list indicates a each participant, where each element in the list indicates a
NonZeroScalar identifier i and two commitment Element values NonZeroScalar identifier i and two commitment Element values
(hiding_nonce_commitment_i, binding_nonce_commitment_i). This list (hiding_nonce_commitment_i, binding_nonce_commitment_i). This list
MUST be sorted in ascending order by identifier. MUST be sorted in ascending order by identifier.
- group_public_key, public key corresponding to the group signing - group_public_key, public key corresponding to the group signing
key, an Element. key, an Element.
- msg, the message to be signed, a byte string. - msg, the message to be signed, a byte string.
Outputs: Outputs:
- True if the signature share is valid, and False otherwise. - True if the signature share is valid, and False otherwise.
def verify_signature_share( def verify_signature_share(
identifier, PK_i, comm_i, sig_share_i, commitment_list, identifier, PK_i, comm_i, sig_share_i, commitment_list,
group_public_key, msg): group_public_key, msg):
# Compute the binding factors # Compute the binding factors
binding_factor_list = compute_binding_factors(group_public_key, commitment_list, msg) binding_factor_list = compute_binding_factors(group_public_key,
binding_factor = binding_factor_for_participant( commitment_list, msg)
binding_factor_list, identifier) binding_factor = binding_factor_for_participant(
binding_factor_list, identifier)
# Compute the group commitment # Compute the group commitment
group_commitment = compute_group_commitment( group_commitment = compute_group_commitment(
commitment_list, binding_factor_list) commitment_list, binding_factor_list)
# Compute the commitment share # Compute the commitment share
(hiding_nonce_commitment, binding_nonce_commitment) = comm_i (hiding_nonce_commitment, binding_nonce_commitment) = comm_i
comm_share = hiding_nonce_commitment + G.ScalarMult( comm_share = hiding_nonce_commitment + G.ScalarMult(
binding_nonce_commitment, binding_factor) binding_nonce_commitment, binding_factor)
# Compute the challenge # Compute the challenge
challenge = compute_challenge( challenge = compute_challenge(
group_commitment, group_public_key, msg) group_commitment, group_public_key, msg)
# Compute the interpolating value # Compute the interpolating value
participant_list = participants_from_commitment_list( participant_list = participants_from_commitment_list(
commitment_list) commitment_list)
lambda_i = derive_interpolating_value(participant_list, identifier) lambda_i = derive_interpolating_value(participant_list, identifier)
# Compute relation values # Compute relation values
l = G.ScalarBaseMult(sig_share_i) l = G.ScalarBaseMult(sig_share_i)
r = comm_share + G.ScalarMult(PK_i, challenge * lambda_i) r = comm_share + G.ScalarMult(PK_i, challenge * lambda_i)
return l == r return l == r
The Coordinator can verify each signature share before first The Coordinator can verify each signature share before aggregating
aggregating and verifying the signature under the group public key. and verifying the signature under the group public key. However,
However, since the aggregate signature is valid if all signature since the aggregate signature is valid if all signature shares are
shares are valid, this order of operations is more expensive if the valid, this order of operations is more expensive if the signature is
signature is valid. valid.
5.4. Identifiable Abort 5.4. Identifiable Abort
FROST does not provide robustness; i.e, all participants are required FROST does not provide robustness; i.e, all participants are required
to complete the protocol honestly in order to generate a valid to complete the protocol honestly in order to generate a valid
signature. When the signing protocol does not produce a valid signature. When the signing protocol does not produce a valid
signature, the Coordinator SHOULD abort; see Section 7 for more signature, the Coordinator SHOULD abort; see Section 7 for more
information about FROST's security properties and the threat model. information about FROST's security properties and the threat model.
As a result of this property, a misbehaving participant can cause a As a result of this property, a misbehaving participant can cause a
denial-of-service on the signing protocol by contributing malformed denial of service (DoS) on the signing protocol by contributing
signature shares or refusing to participate. Identifying misbehaving malformed signature shares or refusing to participate. Identifying
participants that produce invalid shares can be done by checking misbehaving participants that produce invalid shares can be done by
signature shares from each participant using verify_signature_share checking signature shares from each participant using
as described in Section 5.3. FROST assumes the network channel is verify_signature_share as described in Section 5.3. FROST assumes
authenticated to identify which signer misbehaved. FROST allows for the network channel is authenticated to identify the signer that
identifying misbehaving participants that produce invalid signature misbehaved. FROST allows for identifying misbehaving participants
shares as described in Section 5.3. FROST does not provide that produce invalid signature shares as described in Section 5.3.
accommodations for identifying participants that refuse to FROST does not provide accommodations for identifying participants
participate, though applications are assumed to detect when that refuse to participate, though applications are assumed to detect
participants fail to engage in the signing protocol. when participants fail to engage in the signing protocol.
In both cases, preventing this type of attack requires the In both cases, preventing this type of attack requires the
Coordinator to identify misbehaving participants such that Coordinator to identify misbehaving participants such that
applications can take corrective action. The mechanism for acting on applications can take corrective action. The mechanism for acting on
misbehaving participants is out of scope for this specification. misbehaving participants is out of scope for this specification.
However, one reasonable approach would be to remove the misbehaving However, one reasonable approach would be to remove the misbehaving
participant from the set of allowed participants in future runs of participant from the set of allowed participants in future runs of
FROST. FROST.
6. Ciphersuites 6. Ciphersuites
A FROST ciphersuite must specify the underlying prime-order group A FROST ciphersuite must specify the underlying prime-order group
details and cryptographic hash function. Each ciphersuite is denoted details and cryptographic hash function. Each ciphersuite is denoted
as (Group, Hash), e.g., (ristretto255, SHA-512). This section as (Group, Hash), e.g., (ristretto255, SHA-512). This section
contains some ciphersuites. Each ciphersuite also includes a context contains some ciphersuites. Each ciphersuite also includes a context
string, denoted contextString, which is an ASCII string literal (with string, denoted as contextString, which is an ASCII string literal
no NULL terminating character). (with no terminating NUL character).
The RECOMMENDED ciphersuite is (ristretto255, SHA-512) as described The RECOMMENDED ciphersuite is (ristretto255, SHA-512) as described
in Section 6.2. The (Ed25519, SHA-512) and (Ed448, SHAKE256) in Section 6.2. The (Ed25519, SHA-512) and (Ed448, SHAKE256)
ciphersuites are included for compatibility with Ed25519 and Ed448 as ciphersuites are included for compatibility with Ed25519 and Ed448 as
defined in [RFC8032]. defined in [RFC8032].
The DeserializeElement and DeserializeScalar functions instantiated The DeserializeElement and DeserializeScalar functions instantiated
for a particular prime-order group corresponding to a ciphersuite for a particular prime-order group corresponding to a ciphersuite
MUST adhere to the description in Section 3.1. Validation steps for MUST adhere to the description in Section 3.1. Validation steps for
these functions are described for each of the ciphersuites below. these functions are described for each of the ciphersuites below.
skipping to change at page 28, line 44 skipping to change at line 987
Each ciphersuite includes explicit instructions for verifying Each ciphersuite includes explicit instructions for verifying
signatures produced by FROST. Note that these instructions are signatures produced by FROST. Note that these instructions are
equivalent to those produced by a single participant. equivalent to those produced by a single participant.
Each ciphersuite adheres to the requirements in Section 6.6. Future Each ciphersuite adheres to the requirements in Section 6.6. Future
ciphersuites MUST also adhere to these requirements. ciphersuites MUST also adhere to these requirements.
6.1. FROST(Ed25519, SHA-512) 6.1. FROST(Ed25519, SHA-512)
This ciphersuite uses edwards25519 for the Group and SHA-512 for the This ciphersuite uses edwards25519 for the Group and SHA-512 for the
Hash function H meant to produce Ed25519-compliant signatures as hash function H meant to produce Ed25519-compliant signatures as
specified in Section 5.1 of [RFC8032]. The value of the specified in Section 5.1 of [RFC8032]. The value of the
contextString parameter is "FROST-ED25519-SHA512-v1". contextString parameter is "FROST-ED25519-SHA512-v1".
* Group: edwards25519 [RFC8032], where Ne = 32 and Ns = 32. Group: edwards25519 [RFC8032], where Ne = 32 and Ns = 32.
- Order(): Return 2^252 + 27742317777372353535851937790883648493 Order(): Return 2^252 + 27742317777372353535851937790883648493
(see [RFC7748]). (see [RFC7748]).
- Identity(): As defined in [RFC7748]. Identity(): As defined in [RFC7748].
- RandomScalar(): Implemented by returning a uniformly random RandomScalar(): Implemented by returning a uniformly random
Scalar in the range [0, G.Order() - 1]. Refer to Appendix E Scalar in the range [0, G.Order() - 1]. Refer to Appendix D
for implementation guidance. for implementation guidance.
- SerializeElement(A): Implemented as specified in [RFC8032], SerializeElement(A): Implemented as specified in [RFC8032],
Section 5.1.2. Additionally, this function validates that the Section 5.1.2. Additionally, this function validates that the
input element is not the group identity element. input element is not the group identity element.
- DeserializeElement(buf): Implemented as specified in [RFC8032], DeserializeElement(buf): Implemented as specified in [RFC8032],
Section 5.1.3. Additionally, this function validates that the Section 5.1.3. Additionally, this function validates that the
resulting element is not the group identity element and is in resulting element is not the group identity element and is in
the prime-order subgroup. If any of these checks fail, the prime-order subgroup. If any of these checks fail,
deserialization returns an error. The latter check can be deserialization returns an error. The latter check can be
implemented by multiplying the resulting point by the order of implemented by multiplying the resulting point by the order of
the group and checking that the result is the identity element. the group and checking that the result is the identity element.
Note that optimizations for this check exist; see [Pornin22]. Note that optimizations for this check exist; see [Pornin22].
- SerializeScalar(s): Implemented by outputting the little-endian SerializeScalar(s): Implemented by outputting the little-endian
32-byte encoding of the Scalar value with the top three bits 32-byte encoding of the Scalar value with the top three bits
set to zero. set to zero.
- DeserializeScalar(buf): Implemented by attempting to DeserializeScalar(buf): Implemented by attempting to deserialize
deserialize a Scalar from a little-endian 32-byte string. This a Scalar from a little-endian 32-byte string. This function
function can fail if the input does not represent a Scalar in can fail if the input does not represent a Scalar in the range
the range [0, G.Order() - 1]. Note that this means the top [0, G.Order() - 1]. Note that this means the top three bits of
three bits of the input MUST be zero. the input MUST be zero.
* Hash (H): SHA-512, which has 64 bytes of output Hash (H): SHA-512, which has an output of 64 bytes.
- H1(m): Implemented by computing H(contextString || "rho" || m), H1(m): Implemented by computing H(contextString || "rho" || m),
interpreting the 64-byte digest as a little-endian integer, and interpreting the 64-byte digest as a little-endian integer, and
reducing the resulting integer modulo reducing the resulting integer modulo 2^252 +
2^252+27742317777372353535851937790883648493. 27742317777372353535851937790883648493.
- H2(m): Implemented by computing H(m), interpreting the 64-byte H2(m): Implemented by computing H(m), interpreting the 64-byte
digest as a little-endian integer, and reducing the resulting digest as a little-endian integer, and reducing the resulting
integer modulo 2^252+27742317777372353535851937790883648493. integer modulo 2^252 + 27742317777372353535851937790883648493.
- H3(m): Implemented by computing H(contextString || "nonce" || H3(m): Implemented by computing H(contextString || "nonce" || m),
m), interpreting the 64-byte digest as a little-endian integer, interpreting the 64-byte digest as a little-endian integer, and
and reducing the resulting integer modulo reducing the resulting integer modulo 2^252 +
2^252+27742317777372353535851937790883648493. 27742317777372353535851937790883648493.
- H4(m): Implemented by computing H(contextString || "msg" || m). H4(m): Implemented by computing H(contextString || "msg" || m).
- H5(m): Implemented by computing H(contextString || "com" || m). H5(m): Implemented by computing H(contextString || "com" || m).
Normally H2 would also include a domain separator, but for Normally, H2 would also include a domain separator; however, for
compatibility with [RFC8032], it is omitted. compatibility with [RFC8032], it is omitted.
Signature verification is as specified in Section 5.1.7 of [RFC8032] Signature verification is as specified in Section 5.1.7 of [RFC8032]
with the constraint that implementations MUST check the group with the constraint that implementations MUST check the group
equation [8][z]B = [8]R + [8][c]PK (changed to use the notation in equation [8][z]B = [8]R + [8][c]PK (changed to use the notation in
this document). this document).
Canonical signature encoding is as specified in Appendix B. Canonical signature encoding is as specified in Appendix A.
6.2. FROST(ristretto255, SHA-512) 6.2. FROST(ristretto255, SHA-512)
This ciphersuite uses ristretto255 for the Group and SHA-512 for the This ciphersuite uses ristretto255 for the Group and SHA-512 for the
Hash function H. The value of the contextString parameter is "FROST- hash function H. The value of the contextString parameter is "FROST-
RISTRETTO255-SHA512-v1". RISTRETTO255-SHA512-v1".
* Group: ristretto255 [RISTRETTO], where Ne = 32 and Ns = 32. Group: ristretto255 [RISTRETTO], where Ne = 32 and Ns = 32.
- Order(): Return 2^252 + 27742317777372353535851937790883648493 Order(): Return 2^252 + 27742317777372353535851937790883648493
(see [RISTRETTO]). (see [RISTRETTO]).
- Identity(): As defined in [RISTRETTO]. Identity(): As defined in [RISTRETTO].
- RandomScalar(): Implemented by returning a uniformly random RandomScalar(): Implemented by returning a uniformly random
Scalar in the range [0, G.Order() - 1]. Refer to Appendix E Scalar in the range [0, G.Order() - 1]. Refer to Appendix D
for implementation guidance. for implementation guidance.
- SerializeElement(A): Implemented using the 'Encode' function SerializeElement(A): Implemented using the "Encode" function from
from [RISTRETTO]. Additionally, this function validates that [RISTRETTO]. Additionally, this function validates that the
the input element is not the group identity element. input element is not the group identity element.
- DeserializeElement(buf): Implemented using the 'Decode' DeserializeElement(buf): Implemented using the "Decode" function
function from [RISTRETTO]. Additionally, this function from [RISTRETTO]. Additionally, this function validates that
validates that the resulting element is not the group identity the resulting element is not the group identity element. If
element. If either 'Decode' or that check fails, either the "Decode" function or the check fails,
deserialization returns an error. deserialization returns an error.
- SerializeScalar(s): Implemented by outputting the little-endian SerializeScalar(s): Implemented by outputting the little-endian
32-byte encoding of the Scalar value with the top three bits 32-byte encoding of the Scalar value with the top three bits
set to zero. set to zero.
- DeserializeScalar(buf): Implemented by attempting to DeserializeScalar(buf): Implemented by attempting to deserialize
deserialize a Scalar from a little-endian 32-byte string. This a Scalar from a little-endian 32-byte string. This function
function can fail if the input does not represent a Scalar in can fail if the input does not represent a Scalar in the range
the range [0, G.Order() - 1]. Note that this means the top [0, G.Order() - 1]. Note that this means the top three bits of
three bits of the input MUST be zero. the input MUST be zero.
* Hash (H): SHA-512, which has 64 bytes of output Hash (H): SHA-512, which has 64 bytes of output.
- H1(m): Implemented by computing H(contextString || "rho" || m)
H1(m): Implemented by computing H(contextString || "rho" || m)
and mapping the output to a Scalar as described in [RISTRETTO], and mapping the output to a Scalar as described in [RISTRETTO],
Section 4.4. Section 4.4.
- H2(m): Implemented by computing H(contextString || "chal" || m) H2(m): Implemented by computing H(contextString || "chal" || m)
and mapping the output to a Scalar as described in [RISTRETTO], and mapping the output to a Scalar as described in [RISTRETTO],
Section 4.4. Section 4.4.
- H3(m): Implemented by computing H(contextString || "nonce" || H3(m): Implemented by computing H(contextString || "nonce" || m)
m) and mapping the output to a Scalar as described in and mapping the output to a Scalar as described in [RISTRETTO],
[RISTRETTO], Section 4.4. Section 4.4.
- H4(m): Implemented by computing H(contextString || "msg" || m). H4(m): Implemented by computing H(contextString || "msg" || m).
- H5(m): Implemented by computing H(contextString || "com" || m). H5(m): Implemented by computing H(contextString || "com" || m).
Signature verification is as specified in Appendix C. Signature verification is as specified in Appendix B.
Canonical signature encoding is as specified in Appendix B. Canonical signature encoding is as specified in Appendix A.
6.3. FROST(Ed448, SHAKE256) 6.3. FROST(Ed448, SHAKE256)
This ciphersuite uses edwards448 for the Group and SHAKE256 for the This ciphersuite uses edwards448 for the Group and SHAKE256 for the
Hash function H meant to produce Ed448-compliant signatures as hash function H meant to produce Ed448-compliant signatures as
specified in Section 5.2 of [RFC8032]. Note that this ciphersuite specified in Section 5.2 of [RFC8032]. Unlike Ed448 in [RFC8032],
does not allow applications to specify a context string as is allowed this ciphersuite does not allow applications to specify a context
for Ed448 in [RFC8032], and always sets the [RFC8032] context string string and always sets the context of [RFC8032] to the empty string.
to the empty string. The value of the (internal to FROST) Note that this ciphersuite does not allow applications to specify a
contextString parameter is "FROST-ED448-SHAKE256-v1". context string as is allowed for Ed448 in [RFC8032], and always sets
the [RFC8032] context string to the empty string. The value of the
(internal to FROST) contextString parameter is "FROST-
ED448-SHAKE256-v1".
* Group: edwards448 [RFC8032], where Ne = 57 and Ns = 57. Group: edwards448 [RFC8032], where Ne = 57 and Ns = 57.
- Order(): Return 2^446 - 138180668098951153520073867485154268803 Order(): Return 2^446 - 13818066809895115352007386748515426880336
36692474882178609894547503885. 692474882178609894547503885.
- Identity(): As defined in [RFC7748]. Identity(): As defined in [RFC7748].
- RandomScalar(): Implemented by returning a uniformly random RandomScalar(): Implemented by returning a uniformly random
Scalar in the range [0, G.Order() - 1]. Refer to Appendix E Scalar in the range [0, G.Order() - 1]. Refer to Appendix D
for implementation guidance. for implementation guidance.
- SerializeElement(A): Implemented as specified in [RFC8032], SerializeElement(A): Implemented as specified in [RFC8032],
Section 5.2.2. Additionally, this function validates that the Section 5.2.2. Additionally, this function validates that the
input element is not the group identity element. input element is not the group identity element.
- DeserializeElement(buf): Implemented as specified in [RFC8032], DeserializeElement(buf): Implemented as specified in [RFC8032],
Section 5.2.3. Additionally, this function validates that the Section 5.2.3. Additionally, this function validates that the
resulting element is not the group identity element and is in resulting element is not the group identity element and is in
the prime-order subgroup. If any of these checks fail, the prime-order subgroup. If any of these checks fail,
deserialization returns an error. The latter check can be deserialization returns an error. The latter check can be
implemented by multiplying the resulting point by the order of implemented by multiplying the resulting point by the order of
the group and checking that the result is the identity element. the group and checking that the result is the identity element.
Note that optimizations for this check exist; see [Pornin22]. Note that optimizations for this check exist; see [Pornin22].
- SerializeScalar(s): Implemented by outputting the little-endian SerializeScalar(s): Implemented by outputting the little-endian
57-byte encoding of the Scalar value. 57-byte encoding of the Scalar value.
- DeserializeScalar(buf): Implemented by attempting to DeserializeScalar(buf): Implemented by attempting to deserialize
deserialize a Scalar from a little-endian 57-byte string. This a Scalar from a little-endian 57-byte string. This function
function can fail if the input does not represent a Scalar in can fail if the input does not represent a Scalar in the range
the range [0, G.Order() - 1]. [0, G.Order() - 1].
* Hash (H): SHAKE256 with 114 bytes of output Hash (H): SHAKE256 with 114 bytes of output.
- H1(m): Implemented by computing H(contextString || "rho" || m), H1(m): Implemented by computing H(contextString || "rho" || m),
interpreting the 114-byte digest as a little-endian integer, interpreting the 114-byte digest as a little-endian integer,
and reducing the resulting integer modulo 2^446 - 1381806680989 and reducing the resulting integer modulo 2^446 - 1381806680989
5115352007386748515426880336692474882178609894547503885. 5115352007386748515426880336692474882178609894547503885.
- H2(m): Implemented by computing H("SigEd448" || 0 || 0 || m), H2(m): Implemented by computing H("SigEd448" || 0 || 0 || m),
interpreting the 114-byte digest as a little-endian integer, interpreting the 114-byte digest as a little-endian integer,
and reducing the resulting integer modulo 2^446 - 1381806680989 and reducing the resulting integer modulo 2^446 - 1381806680989
5115352007386748515426880336692474882178609894547503885. 5115352007386748515426880336692474882178609894547503885.
- H3(m): Implemented by computing H(contextString || "nonce" || H3(m): Implemented by computing H(contextString || "nonce" || m),
m), interpreting the 114-byte digest as a little-endian interpreting the 114-byte digest as a little-endian integer,
integer, and reducing the resulting integer modulo 2^446 - 1381 and reducing the resulting integer modulo 2^446 - 1381806680989
806680989511535200738674851542688033669247488217860989454750388 5115352007386748515426880336692474882178609894547503885.
5.
- H4(m): Implemented by computing H(contextString || "msg" || m). H4(m): Implemented by computing H(contextString || "msg" || m).
- H5(m): Implemented by computing H(contextString || "com" || m). H5(m): Implemented by computing H(contextString || "com" || m).
Normally H2 would also include a domain separator, but for Normally, H2 would also include a domain separator. However, it is
compatibility with [RFC8032], it is omitted. omitted for compatibility with [RFC8032].
Signature verification is as specified in Section 5.2.7 of [RFC8032] Signature verification is as specified in Section 5.2.7 of [RFC8032]
with the constraint that implementations MUST check the group with the constraint that implementations MUST check the group
equation [4][z]B = [4]R + [4][c]PK (changed to use the notation in equation [4][z]B = [4]R + [4][c]PK (changed to use the notation in
this document). this document).
Canonical signature encoding is as specified in Appendix B. Canonical signature encoding is as specified in Appendix A.
6.4. FROST(P-256, SHA-256) 6.4. FROST(P-256, SHA-256)
This ciphersuite uses P-256 for the Group and SHA-256 for the Hash This ciphersuite uses P-256 for the Group and SHA-256 for the hash
function H. The value of the contextString parameter is "FROST- function H. The value of the contextString parameter is "FROST-
P256-SHA256-v1". P256-SHA256-v1".
* Group: P-256 (secp256r1) [x9.62], where Ne = 33 and Ns = 32. Group: P-256 (secp256r1) [x9.62], where Ne = 33 and Ns = 32.
- Order(): Return 0xffffffff00000000ffffffffffffffffbce6faada7179 Order(): Return 0xffffffff00000000ffffffffffffffffbce6faada7179e8
e84f3b9cac2fc632551. 4f3b9cac2fc632551.
- Identity(): As defined in [x9.62]. Identity(): As defined in [x9.62].
- RandomScalar(): Implemented by returning a uniformly random RandomScalar(): Implemented by returning a uniformly random
Scalar in the range [0, G.Order() - 1]. Refer to Appendix E Scalar in the range [0, G.Order() - 1]. Refer to Appendix D
for implementation guidance. for implementation guidance.
- SerializeElement(A): Implemented using the compressed Elliptic- SerializeElement(A): Implemented using the compressed Elliptic-
Curve-Point-to-Octet-String method according to [SEC1], Curve-Point-to-Octet-String method according to [SEC1],
yielding a 33-byte output. Additionally, this function yielding a 33-byte output. Additionally, this function
validates that the input element is not the group identity validates that the input element is not the group identity
element. element.
- DeserializeElement(buf): Implemented by attempting to DeserializeElement(buf): Implemented by attempting to deserialize
deserialize a 33-byte input string to a public key using the a 33-byte input string to a public key using the compressed
compressed Octet-String-to-Elliptic-Curve-Point method Octet-String-to-Elliptic-Curve-Point method according to [SEC1]
according to [SEC1], and then performs public-key validation as and then performing public key validation as defined in
defined in section 3.2.2.1 of [SEC1]. This includes checking Section 3.2.2.1 of [SEC1]. This includes checking that the
that the coordinates of the resulting point are in the correct coordinates of the resulting point are in the correct range,
range, that the point is on the curve, and that the point is that the point is on the curve, and that the point is not the
not the point at infinity. (As noted in the specification, point at infinity. (As noted in the specification, validation
validation of the point order is not required since the of the point order is not required since the cofactor is 1.)
cofactor is 1.) If any of these checks fail, deserialization If any of these checks fail, deserialization returns an error.
returns an error.
- SerializeScalar(s): Implemented using the Field-Element-to- SerializeScalar(s): Implemented using the Field-Element-to-Octet-
Octet-String conversion according to [SEC1]. String conversion according to [SEC1].
- DeserializeScalar(buf): Implemented by attempting to DeserializeScalar(buf): Implemented by attempting to deserialize
deserialize a Scalar from a 32-byte string using Octet-String- a Scalar from a 32-byte string using Octet-String-to-Field-
to-Field-Element from [SEC1]. This function can fail if the Element from [SEC1]. This function can fail if the input does
input does not represent a Scalar in the range [0, G.Order() - not represent a Scalar in the range [0, G.Order() - 1].
1].
* Hash (H): SHA-256, which has 32 bytes of output Hash (H): SHA-256, which has 32 bytes of output.
- H1(m): Implemented as hash_to_field(m, 1) from [HASH-TO-CURVE],
Section 5.2 using expand_message_xmd with SHA-256 with H1(m): Implemented as hash_to_field(m, 1) (see [HASH-TO-CURVE],
parameters DST = contextString || "rho", F set to the scalar Section 5.2) using expand_message_xmd with SHA-256 with
parameters DST = contextString || "rho", F set to the Scalar
field, p set to G.Order(), m = 1, and L = 48. field, p set to G.Order(), m = 1, and L = 48.
- H2(m): Implemented as hash_to_field(m, 1) from [HASH-TO-CURVE], H2(m): Implemented as hash_to_field(m, 1) (see [HASH-TO-CURVE],
Section 5.2 using expand_message_xmd with SHA-256 with Section 5.2) using expand_message_xmd with SHA-256 with
parameters DST = contextString || "chal", F set to the scalar parameters DST = contextString || "chal", F set to the Scalar
field, p set to G.Order(), m = 1, and L = 48. field, p set to G.Order(), m = 1, and L = 48.
- H3(m): Implemented as hash_to_field(m, 1) from [HASH-TO-CURVE], H3(m): Implemented as hash_to_field(m, 1) (see [HASH-TO-CURVE],
Section 5.2 using expand_message_xmd with SHA-256 with Section 5.2) using expand_message_xmd with SHA-256 with
parameters DST = contextString || "nonce", F set to the scalar parameters DST = contextString || "nonce", F set to the Scalar
field, p set to G.Order(), m = 1, and L = 48. field, p set to G.Order(), m = 1, and L = 48.
- H4(m): Implemented by computing H(contextString || "msg" || m). H4(m): Implemented by computing H(contextString || "msg" || m).
- H5(m): Implemented by computing H(contextString || "com" || m). H5(m): Implemented by computing H(contextString || "com" || m).
Signature verification is as specified in Appendix C. Signature verification is as specified in Appendix B.
Canonical signature encoding is as specified in Appendix B. Canonical signature encoding is as specified in Appendix A.
6.5. FROST(secp256k1, SHA-256) 6.5. FROST(secp256k1, SHA-256)
This ciphersuite uses secp256k1 for the Group and SHA-256 for the This ciphersuite uses secp256k1 for the Group and SHA-256 for the
Hash function H. The value of the contextString parameter is "FROST- hash function H. The value of the contextString parameter is "FROST-
secp256k1-SHA256-v1". secp256k1-SHA256-v1".
* Group: secp256k1 [SEC2], where Ne = 33 and Ns = 32. Group: secp256k1 [SEC2], where Ne = 33 and Ns = 32.
- Order(): Return 0xfffffffffffffffffffffffffffffffebaaedce6af48a Order(): Return 0xfffffffffffffffffffffffffffffffebaaedce6af48a03
03bbfd25e8cd0364141. bbfd25e8cd0364141.
- Identity(): As defined in [SEC2]. Identity(): As defined in [SEC2].
- RandomScalar(): Implemented by returning a uniformly random RandomScalar(): Implemented by returning a uniformly random
Scalar in the range [0, G.Order() - 1]. Refer to Appendix E Scalar in the range [0, G.Order() - 1]. Refer to Appendix D
for implementation guidance. for implementation guidance.
- SerializeElement(A): Implemented using the compressed Elliptic- SerializeElement(A): Implemented using the compressed Elliptic-
Curve-Point-to-Octet-String method according to [SEC1], Curve-Point-to-Octet-String method according to [SEC1],
yielding a 33-byte output. Additionally, this function yielding a 33-byte output. Additionally, this function
validates that the input element is not the group identity validates that the input element is not the group identity
element. element.
- DeserializeElement(buf): Implemented by attempting to DeserializeElement(buf): Implemented by attempting to deserialize
deserialize a 33-byte input string to a public key using the a 33-byte input string to a public key using the compressed
compressed Octet-String-to-Elliptic-Curve-Point method Octet-String-to-Elliptic-Curve-Point method according to [SEC1]
according to [SEC1], and then performs public-key validation as and then performing public key validation as defined in
defined in section 3.2.2.1 of [SEC1]. This includes checking Section 3.2.2.1 of [SEC1]. This includes checking that the
that the coordinates of the resulting point are in the correct coordinates of the resulting point are in the correct range,
range, that the point is on the curve, and that the point is the point is on the curve, and the point is not the point at
not the point at infinity. (As noted in the specification, infinity. (As noted in the specification, validation of the
validation of the point order is not required since the point order is not required since the cofactor is 1.) If any
cofactor is 1.) If any of these checks fail, deserialization of these checks fail, deserialization returns an error.
returns an error.
- SerializeScalar(s): Implemented using the Field-Element-to- SerializeScalar(s): Implemented using the Field-Element-to-Octet-
Octet-String conversion according to [SEC1]. String conversion according to [SEC1].
- DeserializeScalar(buf): Implemented by attempting to DeserializeScalar(buf): Implemented by attempting to deserialize
deserialize a Scalar from a 32-byte string using Octet-String- a Scalar from a 32-byte string using Octet-String-to-Field-
to-Field-Element from [SEC1]. This function can fail if the Element from [SEC1]. This function can fail if the input does
input does not represent a Scalar in the range [0, G.Order() - not represent a Scalar in the range [0, G.Order() - 1].
1].
* Hash (H): SHA-256, which has 32 bytes of output Hash (H): SHA-256, which has 32 bytes of output.
- H1(m): Implemented as hash_to_field(m, 1) from [HASH-TO-CURVE], H1(m): Implemented as hash_to_field(m, 1) (see [HASH-TO-CURVE],
Section 5.2 using expand_message_xmd with SHA-256 with Section 5.2) using expand_message_xmd with SHA-256 with
parameters DST = contextString || "rho", F set to the scalar parameters DST = contextString || "rho", F set to the Scalar
field, p set to G.Order(), m = 1, and L = 48. field, p set to G.Order(), m = 1, and L = 48.
- H2(m): Implemented as hash_to_field(m, 1) from [HASH-TO-CURVE], H2(m): Implemented as hash_to_field(m, 1) (see [HASH-TO-CURVE],
Section 5.2 using expand_message_xmd with SHA-256 with Section 5.2) using expand_message_xmd with SHA-256 with
parameters DST = contextString || "chal", F set to the scalar parameters DST = contextString || "chal", F set to the Scalar
field, p set to G.Order(), m = 1, and L = 48. field, p set to G.Order(), m = 1, and L = 48.
- H3(m): Implemented as hash_to_field(m, 1) from [HASH-TO-CURVE], H3(m): Implemented as hash_to_field(m, 1) (see [HASH-TO-CURVE],
Section 5.2 using expand_message_xmd with SHA-256 with Section 5.2) using expand_message_xmd with SHA-256 with
parameters DST = contextString || "nonce", F set to the scalar parameters DST = contextString || "nonce", F set to the Scalar
field, p set to G.Order(), m = 1, and L = 48. field, p set to G.Order(), m = 1, and L = 48.
- H4(m): Implemented by computing H(contextString || "msg" || m). H4(m): Implemented by computing H(contextString || "msg" || m).
- H5(m): Implemented by computing H(contextString || "com" || m). H5(m): Implemented by computing H(contextString || "com" || m).
Signature verification is as specified in Appendix C. Signature verification is as specified in Appendix B.
Canonical signature encoding is as specified in Appendix B. Canonical signature encoding is as specified in Appendix A.
6.6. Ciphersuite Requirements 6.6. Ciphersuite Requirements
Future documents that introduce new ciphersuites MUST adhere to the Future documents that introduce new ciphersuites MUST adhere to the
following requirements. following requirements.
1. H1, H2, and H3 all have output distributions that are close to 1. H1, H2, and H3 all have output distributions that are close to
(indistinguishable from) the uniform distribution. (indistinguishable from) the uniform distribution.
2. All hash functions MUST be domain separated with a per-suite 2. All hash functions MUST be domain-separated with a per-suite
context string. Note that the FROST(Ed25519, SHA-512) context string. Note that the FROST(Ed25519, SHA-512)
ciphersuite does not adhere to this requirement for H2 alone to ciphersuite does not adhere to this requirement for H2 alone in
maintain compatibility with [RFC8032]. order to maintain compatibility with [RFC8032].
3. The group MUST be of prime-order, and all deserialization 3. The group MUST be of prime order and all deserialization
functions MUST output elements that belong to their respective functions MUST output elements that belong to their respective
sets of Elements or Scalars, or failure when deserialization sets of Elements or Scalars, or else fail.
fails.
4. The canonical signature encoding details are clearly specified. 4. The canonical signature encoding details are clearly specified.
7. Security Considerations 7. Security Considerations
A security analysis of FROST exists in [FROST20] and [StrongerSec22]. A security analysis of FROST is documented in [FROST20] and
At a high level, FROST provides security against Existential [StrongerSec22]. At a high level, FROST provides security against
Unforgeability Under Chosen Message Attack (EUF-CMA) attacks, as Existential Unforgeability Under Chosen Message Attacks (EUF-CMA) as
defined in [StrongerSec22]. Satisfying this requirement requires the defined in [StrongerSec22]. To satisfy this requirement, the
ciphersuite to adhere to the requirements in Section 6.6, as well as ciphersuite needs to adhere to the requirements in Section 6.6 and
the following assumptions to hold. the following assumptions must hold.
* The signer key shares are generated and distributed securely, * The signer key shares are generated and distributed securely,
e.g., via a trusted dealer that performs key generation (see e.g., via a trusted dealer that performs key generation (see
Appendix D.2) or through a distributed key generation protocol. Appendix C.2) or through a distributed key generation protocol.
* The Coordinator and at most (MIN_PARTICIPANTS-1) participants may * The Coordinator and at most (MIN_PARTICIPANTS-1) participants may
be corrupted. be corrupted.
Note that the Coordinator is not trusted with any private information Note that the Coordinator is not trusted with any private
and communication at the time of signing can be performed over a information, and communication at the time of signing can be
public channel, as long as it is authenticated and reliable. performed over a public channel as long as it is authenticated and
reliable.
FROST provides security against denial of service attacks under the FROST provides security against DoS attacks under the following
following assumptions: assumptions:
* The Coordinator does not perform a denial of service attack. * The Coordinator does not perform a DoS attack.
* The Coordinator identifies misbehaving participants such that they * The Coordinator identifies misbehaving participants such that they
can be removed from future invocations of FROST. The Coordinator can be removed from future invocations of FROST. The Coordinator
may also abort upon detecting a misbehaving participant to ensure may also abort upon detecting a misbehaving participant to ensure
that invalid signatures are not produced. that invalid signatures are not produced.
FROST does not aim to achieve the following goals: FROST does not aim to achieve the following goals:
* Post-quantum security. FROST, like plain Schnorr signatures, * Post-quantum security. FROST, like plain Schnorr signatures,
requires the hardness of the Discrete Logarithm Problem. requires the hardness of the Discrete Logarithm Problem.
* Robustness. Preventing denial-of-service attacks against * Robustness. Preventing DoS attacks against misbehaving
misbehaving participants requires the Coordinator to identify and participants requires the Coordinator to identify and act on
act on misbehaving participants; see Section 5.4 for more misbehaving participants; see Section 5.4 for more information.
information. While FROST does not provide robustness, [ROAST] is While FROST does not provide robustness, [ROAST] is a wrapper
as a wrapper protocol around FROST that does. protocol around FROST that does.
* Downgrade prevention. All participants in the protocol are * Downgrade prevention. All participants in the protocol are
assumed to agree on what algorithms to use. assumed to agree on which algorithms to use.
* Metadata protection. If protection for metadata is desired, a * Metadata protection. If protection for metadata is desired, a
higher-level communication channel can be used to facilitate key higher-level communication channel can be used to facilitate key
generation and signing. generation and signing.
The rest of this section documents issues particular to The rest of this section documents issues particular to
implementations or deployments. implementations or deployments.
7.1. Side-channel mitigations 7.1. Side-Channel Mitigations
Several routines process secret values (nonces, signing keys / Several routines process secret values (nonces, signing keys /
shares), and depending on the implementation and deployment shares), and depending on the implementation and deployment
environment, mitigating side-channels may be pertinent. Mitigating environment, mitigating side-channels may be pertinent. Mitigating
these side-channels requires implementing G.ScalarMult(), these side-channels requires implementing G.ScalarMult(),
G.ScalarBaseMult(), G.SerializeScalar(), and G.DeserializeScalar() in G.ScalarBaseMult(), G.SerializeScalar(), and G.DeserializeScalar() in
constant (value-independent) time. The various ciphersuites lend constant (value-independent) time. The various ciphersuites lend
themselves differently to specific implementation techniques and ease themselves differently to specific implementation techniques and ease
of achieving side-channel resistance, though ultimately avoiding of achieving side-channel resistance, though ultimately avoiding
value-dependent computation or branching is the goal. value-dependent computation or branching is the goal.
7.2. Optimizations 7.2. Optimizations
[StrongerSec22] presented an optimization to FROST that reduces the [StrongerSec22] presented an optimization to FROST that reduces the
total number of scalar multiplications from linear in the number of total number of Scalar multiplications from linear in the number of
signing participants to a constant. However, as described in signing participants to a constant. However, as described in
[StrongerSec22], this optimization removes the guarantee that the set [StrongerSec22], this optimization removes the guarantee that the set
of signer participants that started round one of the protocol is the of signer participants that started round one of the protocol is the
same set of signing participants that produced the signature output same set of signing participants that produced the signature output
by round two. As such, the optimization is NOT RECOMMENDED, and it by round two. As such, the optimization is NOT RECOMMENDED and is
is not covered in this document. not covered in this document.
7.3. Nonce Reuse Attacks 7.3. Nonce Reuse Attacks
Section 4.1 describes the procedure that participants use to produce Section 4.1 describes the procedure that participants use to produce
nonces during the first round of signing. The randomness produced in nonces during the first round of signing. The randomness produced in
this procedure MUST be sampled uniformly at random. The resulting this procedure MUST be sampled uniformly at random. The resulting
nonces produced via nonce_generate are indistinguishable from values nonces produced via nonce_generate are indistinguishable from values
sampled uniformly at random. This requirement is necessary to avoid sampled uniformly at random. This requirement is necessary to avoid
replay attacks initiated by other participants, which allow for a replay attacks initiated by other participants that allow for a
complete key-recovery attack. The Coordinator MAY further hedge complete key-recovery attack. The Coordinator MAY further hedge
against nonce reuse attacks by tracking participant nonce commitments against nonce reuse attacks by tracking participant nonce commitments
used for a given group key, at the cost of additional state. used for a given group key at the cost of additional state.
7.4. Protocol Failures 7.4. Protocol Failures
We do not specify what implementations should do when the protocol We do not specify what implementations should do when the protocol
fails, other than requiring that the protocol abort. Examples of fails other than requiring the protocol to abort. Examples of viable
viable failure include when a verification check returns invalid or failures include when a verification check returns invalid or the
if the underlying transport failed to deliver the required messages. underlying transport failed to deliver the required messages.
7.5. Removing the Coordinator Role 7.5. Removing the Coordinator Role
In some settings, it may be desirable to omit the role of the In some settings, it may be desirable to omit the role of the
Coordinator entirely. Doing so does not change the security Coordinator entirely. Doing so does not change the security
implications of FROST, but instead simply requires each participant implications of FROST; instead, it simply requires each participant
to communicate with all other participants. We loosely describe how to communicate with all other participants. We loosely describe how
to perform FROST signing among participants without this coordinator to perform FROST signing among participants without this coordinator
role. We assume that every participant receives as input from an role. We assume that every participant receives a message to be
external source the message to be signed prior to performing the signed from an external source as input prior to performing the
protocol. protocol.
Every participant begins by performing commit() as is done in the Every participant begins by performing commit() as is done in the
setting where a Coordinator is used. However, instead of sending the setting where a Coordinator is used. However, instead of sending the
commitment to the Coordinator, every participant instead will publish commitment to the Coordinator, every participant will publish this
this commitment to every other participant. Then, in the second commitment to every other participant. In the second round,
round, participants will already have sufficient information to participants will already have sufficient information to perform
perform signing. They will directly perform sign(). All signing, and they will directly perform sign(). All participants
participants will then publish their signature shares to one another. will then publish their signature shares to one another. After
After having received all signature shares from all other having received all signature shares from all other participants,
participants, each participant will then perform each participant will then perform verify_signature_share and then
verify_signature_share and then aggregate directly. aggregate directly.
The requirements for the underlying network channel remain the same The requirements for the underlying network channel remain the same
in the setting where all participants play the role of the in the setting where all participants play the role of the
Coordinator, in that all messages that are exchanged are public and Coordinator, in that all exchanged messages are public and the
so the channel simply must be reliable. However, in the setting that channel must be reliable. However, in the setting where a player
a player attempts to split the view of all other players by sending attempts to split the view of all other players by sending disjoint
disjoint values to a subset of players, the signing operation will values to a subset of players, the signing operation will output an
output an invalid signature. To avoid this denial of service, invalid signature. To avoid this DoS, implementations may wish to
implementations may wish to define a mechanism where messages are define a mechanism where messages are authenticated so that cheating
authenticated, so that cheating players can be identified and players can be identified and excluded.
excluded.
7.6. Input Message Hashing 7.6. Input Message Hashing
FROST signatures do not pre-hash message inputs. This means that the FROST signatures do not pre-hash message inputs. This means that the
entire message must be known in advance of invoking the signing entire message must be known in advance of invoking the signing
protocol. Applications can apply pre-hashing in settings where protocol. Applications can apply pre-hashing in settings where
storing the full message is prohibitively expensive. In such cases, storing the full message is prohibitively expensive. In such cases,
pre-hashing MUST use a collision-resistant hash function with a pre-hashing MUST use a collision-resistant hash function with a
security level commensurate with the security inherent to the security level commensurate with the security inherent to the
ciphersuite chosen. It is RECOMMENDED that applications which choose ciphersuite chosen. For applications that choose to apply pre-
to apply pre-hashing use the hash function (H) associated with the hashing, it is RECOMMENDED that they use the hash function (H)
chosen ciphersuite in a manner similar to how H4 is defined. In associated with the chosen ciphersuite in a manner similar to how H4
particular, a different prefix SHOULD be used to differentiate this is defined. In particular, a different prefix SHOULD be used to
pre-hash from H4. For example, if a fictional protocol Quux decided differentiate this pre-hash from H4. For example, if a fictional
to pre-hash its input messages, one possible way to do so is via protocol Quux decided to pre-hash its input messages, one possible
H(contextString || "Quux-pre-hash" || m). way to do so is via H(contextString || "Quux-pre-hash" || m).
7.7. Input Message Validation 7.7. Input Message Validation
Message validation varies by application. For example, some Message validation varies by application. For example, some
applications may require that participants only process messages of a applications may require that participants only process messages of a
certain structure. In digital currency applications, wherein certain structure. In digital currency applications, wherein
multiple participants may collectively sign a transaction, it is multiple participants may collectively sign a transaction, it is
reasonable to require that each participant check the input message reasonable to require each participant to check that the input
to be a syntactically valid transaction. message is a syntactically valid transaction.
As another example, some applications may require that participants As another example, some applications may require that participants
only process messages with permitted content according to some only process messages with permitted content according to some
policy. In digital currency applications, this might mean that a policy. In digital currency applications, this might mean that a
transaction being signed is allowed and intended by the relevant transaction being signed is allowed and intended by the relevant
stakeholders. Another instance of this type of message validation is stakeholders. Another instance of this type of message validation is
in the context of [TLS], wherein implementations may use threshold in the context of [TLS], wherein implementations may use threshold
signing protocols to produce signatures of transcript hashes. In signing protocols to produce signatures of transcript hashes. In
this setting, signing participants might require the raw TLS this setting, signing participants might require the raw TLS
handshake messages to validate before computing the transcript hash handshake messages to validate before computing the transcript hash
that is signed. that is signed.
In general, input message validation is an application-specific In general, input message validation is an application-specific
consideration that varies based on the use case and threat model. consideration that varies based on the use case and threat model.
However, it is RECOMMENDED that applications take additional However, it is RECOMMENDED that applications take additional
precautions and validate inputs so that participants do not operate precautions and validate inputs so that participants do not operate
as signing oracles for arbitrary messages. as signing oracles for arbitrary messages.
8. IANA Considerations 8. IANA Considerations
This document makes no IANA requests. This document has no IANA actions.
9. References 9. References
9.1. Normative References 9.1. Normative References
[HASH-TO-CURVE] [HASH-TO-CURVE]
Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R. S., Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R. S.,
and C. A. Wood, "Hashing to Elliptic Curves", Work in and C. A. Wood, "Hashing to Elliptic Curves", RFC 9380,
Progress, Internet-Draft, draft-irtf-cfrg-hash-to-curve- DOI 10.17487/RFC9380, August 2023,
16, 15 June 2022, <https://datatracker.ietf.org/doc/html/ <https://www.rfc-editor.org/info/rfc9380>.
draft-irtf-cfrg-hash-to-curve-16>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/rfc/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032, Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017, DOI 10.17487/RFC8032, January 2017,
<https://www.rfc-editor.org/rfc/rfc8032>. <https://www.rfc-editor.org/info/rfc8032>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/rfc/rfc8174>. May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[RISTRETTO] [RISTRETTO]
de Valence, H., Grigg, J., Hamburg, M., Lovecruft, I., de Valence, H., Grigg, J., Hamburg, M., Lovecruft, I.,
Tankersley, G., and F. Valsorda, "The ristretto255 and Tankersley, G., and F. Valsorda, "The ristretto255 and
decaf448 Groups", Work in Progress, Internet-Draft, draft- decaf448 Groups", RFC 9496, DOI 10.17487/RFC9496, December
irtf-cfrg-ristretto255-decaf448-08, 5 September 2023, 2023, <https://www.rfc-editor.org/info/rfc9496>.
<https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
ristretto255-decaf448-08>.
[SEC1] "Elliptic Curve Cryptography, Standards for Efficient [SEC1] Standards for Efficient Cryptography, "SEC 1: Elliptic
Cryptography Group, ver. 2", 2009, Curve Cryptography", Version 2.0, May 2009,
<https://secg.org/sec1-v2.pdf>. <https://secg.org/sec1-v2.pdf>.
[SEC2] "Recommended Elliptic Curve Domain Parameters, Standards [SEC2] Standards for Efficient Cryptography, "SEC 2: Recommended
for Efficient Cryptography Group, ver. 2", 2010, Elliptic Curve Domain Parameters", Version 2.0, January
<https://secg.org/sec2-v2.pdf>. 2010, <https://secg.org/sec2-v2.pdf>.
[x9.62] ANS, "Public Key Cryptography for the Financial Services [x9.62] American National Standards Institute, "Public Key
Industry: the Elliptic Curve Digital Signature Algorithm Cryptography for the Financial Services Industry: the
(ECDSA)", ANS X9.62-2005, November 2005. Elliptic Curve Digital Signature Algorithm (ECDSA)",
ANSI X9.62-2005, November 2005.
9.2. Informative References 9.2. Informative References
[FeldmanSecretSharing] [FeldmanSecretSharing]
Feldman, P., "A practical scheme for non-interactive Feldman, P., "A practical scheme for non-interactive
verifiable secret sharing", IEEE, 28th Annual Symposium on verifiable secret sharing", IEEE, 28th Annual Symposium on
Foundations of Computer Science (sfcs 1987), Foundations of Computer Science (sfcs 1987),
DOI 10.1109/sfcs.1987.4, October 1987, DOI 10.1109/sfcs.1987.4, October 1987,
<https://doi.org/10.1109/sfcs.1987.4>. <https://doi.org/10.1109/sfcs.1987.4>.
[FROST20] Komlo, C. and I. Goldberg, "Two-Round Threshold Signatures [FROST20] Komlo, C. and I. Goldberg, "FROST: Flexible Round-
with FROST", 22 December 2020, Optimized Schnorr Threshold Signatures", December 2020,
<https://eprint.iacr.org/2020/852.pdf>. <https://eprint.iacr.org/2020/852.pdf>.
[MultExp] Connolly, D. and C. Gouvea, "Speeding up FROST with multi- [MultExp] Connolly, D. and C. Gouvea, "Speeding up FROST with multi-
scalar multiplication", n.d., <https://zfnd.org/speeding- scalar multiplication", June 2023, <https://zfnd.org/
up-frost-with-multi-scalar-multiplication/>. speeding-up-frost-with-multi-scalar-multiplication/>.
[Pornin22] Pornin, T., "Point-Halving and Subgroup Membership in [Pornin22] Pornin, T., "Point-Halving and Subgroup Membership in
Twisted Edwards Curves", 6 September 2022, Twisted Edwards Curves", September 2022,
<https://eprint.iacr.org/2022/1164.pdf>. <https://eprint.iacr.org/2022/1164.pdf>.
[RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker,
"Randomness Requirements for Security", BCP 106, RFC 4086, "Randomness Requirements for Security", BCP 106, RFC 4086,
DOI 10.17487/RFC4086, June 2005, DOI 10.17487/RFC4086, June 2005,
<https://www.rfc-editor.org/rfc/rfc4086>. <https://www.rfc-editor.org/info/rfc4086>.
[RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
for Security", RFC 7748, DOI 10.17487/RFC7748, January for Security", RFC 7748, DOI 10.17487/RFC7748, January
2016, <https://www.rfc-editor.org/rfc/rfc7748>. 2016, <https://www.rfc-editor.org/info/rfc7748>.
[ROAST] Ruffing, T., Ronge, V., Jin, E., Schneider-Bensch, J., and [ROAST] Ruffing, T., Ronge, V., Jin, E., Schneider-Bensch, J., and
D. Schröder, "ROAST: Robust Asynchronous Schnorr Threshold D. Schröder, "ROAST: Robust Asynchronous Schnorr Threshold
Signatures", 18 September 2022, Signatures", Paper 2022/550, DOI 10.1145/3548606, November
<https://eprint.iacr.org/2022/550>. 2022, <https://eprint.iacr.org/2022/550>.
[ShamirSecretSharing] [ShamirSecretSharing]
Shamir, A., "How to share a secret", Association for Shamir, A., "How to share a secret", Association for
Computing Machinery (ACM), Communications of the ACM vol. Computing Machinery (ACM), Communications of the ACM, Vol.
22, no. 11, pp. 612-613, DOI 10.1145/359168.359176, 22, Issue 11, pp. 612-613, DOI 10.1145/359168.359176,
November 1979, <https://doi.org/10.1145/359168.359176>. November 1979, <https://doi.org/10.1145/359168.359176>.
[StrongerSec22] [StrongerSec22]
Bellare, M., Crites, E., Komlo, C., Maller, M., Tessaro, Bellare, M., Crites, E., Komlo, C., Maller, M., Tessaro,
S., and C. Zhu, "Better than Advertised Security for Non- S., and C. Zhu, "Better than Advertised Security for Non-
interactive Threshold Signatures", 1 June 2022, interactive Threshold Signatures",
DOI 10.1007/978-3-031-15985-5_18, August 2022,
<https://crypto.iacr.org/2022/ <https://crypto.iacr.org/2022/
papers/538806_1_En_18_Chapter_OnlinePDF.pdf>. papers/538806_1_En_18_Chapter_OnlinePDF.pdf>.
[TLS] Rescorla, E., "The Transport Layer Security (TLS) Protocol [TLS] Rescorla, E., "The Transport Layer Security (TLS) Protocol
Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
<https://www.rfc-editor.org/rfc/rfc8446>. <https://www.rfc-editor.org/info/rfc8446>.
Appendix A. Acknowledgments
This document was improved based on input and contributions by the
Zcash Foundation engineering team. In addition, the authors of this
document would like to thank Isis Lovecruft, Alden Torres, T.
Wilson-Brown, and Conrado Gouvea for their inputs and contributions.
Appendix B. Schnorr Signature Encoding Appendix A. Schnorr Signature Encoding
This section describes one possible canonical encoding of FROST This section describes one possible canonical encoding of FROST
signatures. Using notation from Section 3 of [TLS], the encoding of signatures. Using notation from Section 3 of [TLS], the encoding of
a FROST signature (R, z) is as follows: a FROST signature (R, z) is as follows:
struct { struct {
opaque R_encoded[Ne]; opaque R_encoded[Ne];
opaque z_encoded[Ns]; opaque z_encoded[Ns];
} Signature; } Signature;
Where Signature.R_encoded is G.SerializeElement(R) and Where Signature.R_encoded is G.SerializeElement(R),
Signature.z_encoded is G.SerializeScalar(z) and G is determined by Signature.z_encoded is G.SerializeScalar(z), and G is determined by
ciphersuite. ciphersuite.
Appendix C. Schnorr Signature Generation and Verification for Prime- Appendix B. Schnorr Signature Generation and Verification for Prime-
Order Groups Order Groups
This section contains descriptions of functions for generating and This section contains descriptions of functions for generating and
verifying Schnorr signatures. It is included to complement the verifying Schnorr signatures. It is included to complement the
routines present in [RFC8032] for prime-order groups, including routines present in [RFC8032] for prime-order groups, including
ristretto255, P-256, and secp256k1. The functions for generating and ristretto255, P-256, and secp256k1. The functions for generating and
verifying signatures are prime_order_sign and prime_order_verify, verifying signatures are prime_order_sign and prime_order_verify,
respectively. respectively.
The function prime_order_sign produces a Schnorr signature over a The function prime_order_sign produces a Schnorr signature over a
message given a full secret signing key as input (as opposed to a key message given a full secret signing key as input (as opposed to a key
share.) share).
Inputs: Inputs:
- msg, message to sign, a byte string. - msg, message to sign, a byte string.
- sk, secret key, a Scalar. - sk, secret key, a Scalar.
Outputs: Outputs:
- (R, z), a Schnorr signature consisting of an Element R and - (R, z), a Schnorr signature consisting of an Element R and
Scalar z. Scalar z.
def prime_order_sign(msg, sk): def prime_order_sign(msg, sk):
r = G.RandomScalar() r = G.RandomScalar()
R = G.ScalarBaseMult(r) R = G.ScalarBaseMult(r)
PK = G.ScalarBaseMult(sk) PK = G.ScalarBaseMult(sk)
comm_enc = G.SerializeElement(R) comm_enc = G.SerializeElement(R)
pk_enc = G.SerializeElement(PK) pk_enc = G.SerializeElement(PK)
challenge_input = comm_enc || pk_enc || msg challenge_input = comm_enc || pk_enc || msg
c = H2(challenge_input) c = H2(challenge_input)
z = r + (c * sk) // Scalar addition and multiplication z = r + (c * sk) // Scalar addition and multiplication
return (R, z) return (R, z)
The function prime_order_verify verifies Schnorr signatures with The function prime_order_verify verifies Schnorr signatures with
validated inputs. Specifically, it assumes that signature R validated inputs. Specifically, it assumes that the signature R
component and public key belong to the prime-order group. component and public key belong to the prime-order group.
Inputs: Inputs:
- msg, signed message, a byte string. - msg, signed message, a byte string.
- sig, a tuple (R, z) output from signature generation. - sig, a tuple (R, z) output from signature generation.
- PK, public key, an Element. - PK, public key, an Element.
Outputs: Outputs:
- True if signature is valid, and False otherwise. - True if signature is valid, and False otherwise.
def prime_order_verify(msg, sig = (R, z), PK): def prime_order_verify(msg, sig = (R, z), PK):
comm_enc = G.SerializeElement(R) comm_enc = G.SerializeElement(R)
pk_enc = G.SerializeElement(PK) pk_enc = G.SerializeElement(PK)
challenge_input = comm_enc || pk_enc || msg challenge_input = comm_enc || pk_enc || msg
c = H2(challenge_input) c = H2(challenge_input)
l = G.ScalarBaseMult(z) l = G.ScalarBaseMult(z)
r = R + G.ScalarMult(PK, c) r = R + G.ScalarMult(PK, c)
return l == r return l == r
Appendix D. Trusted Dealer Key Generation Appendix C. Trusted Dealer Key Generation
One possible key generation mechanism is to depend on a trusted One possible key generation mechanism is to depend on a trusted
dealer, wherein the dealer generates a group secret s uniformly at dealer, wherein the dealer generates a group secret s uniformly at
random and uses Shamir and Verifiable Secret Sharing random and uses Shamir and Verifiable Secret Sharing
[ShamirSecretSharing], as described in Appendix D.1 and Appendix D.2 [ShamirSecretSharing] as described in Appendices C.1 and C.2 to
to create secret shares of s, denoted s_i for i = 1, ..., create secret shares of s, denoted as s_i for i = 1, ...,
MAX_PARTICIPANTS, to be sent to all MAX_PARTICIPANTS participants. MAX_PARTICIPANTS, to be sent to all MAX_PARTICIPANTS participants.
This operation is specified in the trusted_dealer_keygen algorithm. This operation is specified in the trusted_dealer_keygen algorithm.
The mathematical relation between the secret key s and the The mathematical relation between the secret key s and the
MAX_PARTICIPANTS secret shares is formalized in the MAX_PARTICIPANTS secret shares is formalized in the
secret_share_combine(shares) algorithm, defined in Appendix D.1. secret_share_combine(shares) algorithm, defined in Appendix C.1.
The dealer that performs trusted_dealer_keygen is trusted to 1) The dealer that performs trusted_dealer_keygen is trusted to 1)
generate good randomness, and 2) delete secret values after generate good randomness, 2) delete secret values after distributing
distributing shares to each participant, and 3) keep secret values shares to each participant, and 3) keep secret values confidential.
confidential.
Inputs: Inputs:
- secret_key, a group secret, a Scalar, that MUST be derived from at - secret_key, a group secret, a Scalar, that MUST be derived from at
least Ns bytes of entropy. least Ns bytes of entropy.
- MAX_PARTICIPANTS, the number of shares to generate, an integer. - MAX_PARTICIPANTS, the number of shares to generate, an integer.
- MIN_PARTICIPANTS, the threshold of the secret sharing scheme, - MIN_PARTICIPANTS, the threshold of the secret sharing scheme,
an integer. an integer.
Outputs: Outputs:
- participant_private_keys, MAX_PARTICIPANTS shares of the secret - participant_private_keys, MAX_PARTICIPANTS shares of the secret
skipping to change at page 45, line 5 skipping to change at line 1726
secret_key, MAX_PARTICIPANTS, MIN_PARTICIPANTS): secret_key, MAX_PARTICIPANTS, MIN_PARTICIPANTS):
# Generate random coefficients for the polynomial # Generate random coefficients for the polynomial
coefficients = [] coefficients = []
for i in range(0, MIN_PARTICIPANTS - 1): for i in range(0, MIN_PARTICIPANTS - 1):
coefficients.append(G.RandomScalar()) coefficients.append(G.RandomScalar())
participant_private_keys, coefficients = secret_share_shard( participant_private_keys, coefficients = secret_share_shard(
secret_key, coefficients, MAX_PARTICIPANTS) secret_key, coefficients, MAX_PARTICIPANTS)
vss_commitment = vss_commit(coefficients): vss_commitment = vss_commit(coefficients):
return participant_private_keys, vss_commitment[0], vss_commitment return participant_private_keys, vss_commitment[0], vss_commitment
It is assumed the dealer then sends one secret key share to each of It is assumed that the dealer then sends one secret key share to each
the NUM_PARTICIPANTS participants, along with vss_commitment. After of the NUM_PARTICIPANTS participants, along with vss_commitment.
receiving their secret key share and vss_commitment, participants After receiving their secret key share and vss_commitment,
MUST abort if they do not have the same view of vss_commitment. The participants MUST abort if they do not have the same view of
dealer can use a secure broadcast channel to ensure each participant vss_commitment. The dealer can use a secure broadcast channel to
has a consistent view of this commitment. Furthermore, each ensure each participant has a consistent view of this commitment.
participant MUST perform vss_verify(secret_key_share_i, Furthermore, each participant MUST perform
vss_commitment), and abort if the check fails. The trusted dealer vss_verify(secret_key_share_i, vss_commitment) and abort if the check
MUST delete the secret_key and secret_key_shares upon completion. fails. The trusted dealer MUST delete the secret_key and
secret_key_shares upon completion.
Use of this method for key generation requires a mutually Use of this method for key generation requires a mutually
authenticated secure channel between the dealer and participants to authenticated secure channel between the dealer and participants to
send secret key shares, wherein the channel provides confidentiality send secret key shares, wherein the channel provides confidentiality
and integrity. Mutually authenticated TLS is one possible deployment and integrity. Mutually authenticated TLS is one possible deployment
option. option.
D.1. Shamir Secret Sharing C.1. Shamir Secret Sharing
In Shamir secret sharing, a dealer distributes a secret Scalar s to n In Shamir secret sharing, a dealer distributes a secret Scalar s to n
participants in such a way that any cooperating subset of at least participants in such a way that any cooperating subset of at least
MIN_PARTICIPANTS participants can recover the secret. There are two MIN_PARTICIPANTS participants can recover the secret. There are two
basic steps in this scheme: (1) splitting a secret into multiple basic steps in this scheme: 1) splitting a secret into multiple
shares, and (2) combining shares to reveal the resulting secret. shares and 2) combining shares to reveal the resulting secret.
This secret sharing scheme works over any field F. In this This secret sharing scheme works over any field F. In this
specification, F is the scalar field of the prime-order group G. specification, F is the Scalar field of the prime-order group G.
The procedure for splitting a secret into shares is as follows. The The procedure for splitting a secret into shares is as follows. The
algorithm polynomial_evaluate is defined in Appendix D.1.1. algorithm polynomial_evaluate is defined in Appendix C.1.1.
Inputs: Inputs:
- s, secret value to be shared, a Scalar. - s, secret value to be shared, a Scalar.
- coefficients, an array of size MIN_PARTICIPANTS - 1 with randomly - coefficients, an array of size MIN_PARTICIPANTS - 1 with randomly
generated Scalars, not including the 0th coefficient of the generated Scalars, not including the 0th coefficient of the
polynomial. polynomial.
- MAX_PARTICIPANTS, the number of shares to generate, an integer less - MAX_PARTICIPANTS, the number of shares to generate, an integer less
than the group order. than the group order.
Outputs: Outputs:
skipping to change at page 46, line 35 skipping to change at line 1787
secret_key_shares = [] secret_key_shares = []
for x_i in range(1, MAX_PARTICIPANTS + 1): for x_i in range(1, MAX_PARTICIPANTS + 1):
y_i = polynomial_evaluate(Scalar(x_i), coefficients) y_i = polynomial_evaluate(Scalar(x_i), coefficients)
secret_key_share_i = (x_i, y_i) secret_key_share_i = (x_i, y_i)
secret_key_shares.append(secret_key_share_i) secret_key_shares.append(secret_key_share_i)
return secret_key_shares, coefficients return secret_key_shares, coefficients
Let points be the output of this function. The i-th element in Let points be the output of this function. The i-th element in
points is the share for the i-th participant, which is the randomly points is the share for the i-th participant, which is the randomly
generated polynomial evaluated at coordinate i. We denote a secret generated polynomial evaluated at coordinate i. We denote a secret
share as the tuple (i, points[i]), and the list of these shares as share as the tuple (i, points[i]) and the list of these shares as
shares. i MUST never equal 0; recall that f(0) = s, where f is the shares. i MUST never equal 0; recall that f(0) = s, where f is the
polynomial defined in a Shamir secret sharing operation. polynomial defined in a Shamir secret sharing operation.
The procedure for combining a shares list of length MIN_PARTICIPANTS The procedure for combining a shares list of length MIN_PARTICIPANTS
to recover the secret s is as follows; the algorithm to recover the secret s is as follows; the algorithm
polynomial_interpolate_constant is defined in Appendix D.1.1. polynomial_interpolate_constant is defined in Appendix C.1.1.
Inputs: Inputs:
- shares, a list of at minimum MIN_PARTICIPANTS secret shares, each a - shares, a list of at minimum MIN_PARTICIPANTS secret shares, each a
tuple (i, f(i)) where i and f(i) are Scalars. tuple (i, f(i)) where i and f(i) are Scalars.
Outputs: Outputs:
- s, the resulting secret that was previously split into shares, - s, the resulting secret that was previously split into shares,
a Scalar. a Scalar.
Errors: Errors:
- "invalid parameters", if fewer than MIN_PARTICIPANTS input shares - "invalid parameters", if fewer than MIN_PARTICIPANTS input shares
are provided. are provided.
def secret_share_combine(shares): def secret_share_combine(shares):
if len(shares) < MIN_PARTICIPANTS: if len(shares) < MIN_PARTICIPANTS:
raise "invalid parameters" raise "invalid parameters"
s = polynomial_interpolate_constant(shares) s = polynomial_interpolate_constant(shares)
return s return s
D.1.1. Additional polynomial operations C.1.1. Additional Polynomial Operations
This section describes two functions. One function, denoted This section describes two functions. One function, denoted as
polynomial_evaluate, is for evaluating a polynomial f(x) at a polynomial_evaluate, is for evaluating a polynomial f(x) at a
particular point x using Horner's method, i.e., computing y = f(x). particular point x using Horner's method, i.e., computing y = f(x).
The other function, polynomial_interpolate_constant, is for The other function, polynomial_interpolate_constant, is for
recovering the constant term of an interpolating polynomial defined recovering the constant term of an interpolating polynomial defined
by a set of points. by a set of points.
The function polynomial_evaluate is defined as follows. The function polynomial_evaluate is defined as follows.
Inputs: Inputs:
- x, input at which to evaluate the polynomial, a Scalar - x, input at which to evaluate the polynomial, a Scalar
skipping to change at page 48, line 25 skipping to change at line 1859
for (x, y) in points: for (x, y) in points:
x_coords.append(x) x_coords.append(x)
f_zero = Scalar(0) f_zero = Scalar(0)
for (x, y) in points: for (x, y) in points:
delta = y * derive_interpolating_value(x_coords, x) delta = y * derive_interpolating_value(x_coords, x)
f_zero += delta f_zero += delta
return f_zero return f_zero
D.2. Verifiable Secret Sharing C.2. Verifiable Secret Sharing
Feldman's Verifiable Secret Sharing (VSS) [FeldmanSecretSharing] Feldman's Verifiable Secret Sharing (VSS) [FeldmanSecretSharing]
builds upon Shamir secret sharing, adding a verification step to builds upon Shamir secret sharing, adding a verification step to
demonstrate the consistency of a participant's share with a public demonstrate the consistency of a participant's share with a public
commitment to the polynomial f for which the secret s is the constant commitment to the polynomial f for which the secret s is the constant
term. This check ensures that all participants have a point (their term. This check ensures that all participants have a point (their
share) on the same polynomial, ensuring that they can later share) on the same polynomial, ensuring that they can reconstruct the
reconstruct the correct secret. correct secret later.
The procedure for committing to a polynomial f of degree at most The procedure for committing to a polynomial f of degree at most
MIN_PARTICIPANTS-1 is as follows. MIN_PARTICIPANTS-1 is as follows.
Inputs: Inputs:
- coeffs, a vector of the MIN_PARTICIPANTS coefficients which - coeffs, a vector of the MIN_PARTICIPANTS coefficients that
uniquely determine a polynomial f. uniquely determine a polynomial f.
Outputs: Outputs:
- vss_commitment, a vector commitment to each of the coefficients in - vss_commitment, a vector commitment to each of the coefficients in
coeffs, where each item of the vector commitment is an Element. coeffs, where each item of the vector commitment is an Element.
def vss_commit(coeffs): def vss_commit(coeffs):
vss_commitment = [] vss_commitment = []
for coeff in coeffs: for coeff in coeffs:
A_i = G.ScalarBaseMult(coeff) A_i = G.ScalarBaseMult(coeff)
vss_commitment.append(A_i) vss_commitment.append(A_i)
return vss_commitment return vss_commitment
The procedure for verification of a participant's share is as The procedure for verification of a participant's share is as
follows. If vss_verify fails, the participant MUST abort the follows. If vss_verify fails, the participant MUST abort the
protocol, and failure should be investigated out of band. protocol, and the failure should be investigated out of band.
Inputs: Inputs:
- share_i: A tuple of the form (i, sk_i), where i indicates the - share_i: A tuple of the form (i, sk_i), where i indicates the
participant identifier (a NonZeroScalar), and sk_i the participant identifier (a NonZeroScalar), and sk_i the
participant's secret key, a secret share of the constant term of f, participant's secret key, a secret share of the constant term of f,
where sk_i is a Scalar. where sk_i is a Scalar.
- vss_commitment, a VSS commitment to a secret polynomial f, a vector - vss_commitment, a VSS commitment to a secret polynomial f, a vector
commitment to each of the coefficients in coeffs, where each commitment to each of the coefficients in coeffs, where each
element of the vector commitment is an Element. element of the vector commitment is an Element.
skipping to change at page 50, line 5 skipping to change at line 1914
(i, sk_i) = share_i (i, sk_i) = share_i
S_i = G.ScalarBaseMult(sk_i) S_i = G.ScalarBaseMult(sk_i)
S_i' = G.Identity() S_i' = G.Identity()
for j in range(0, MIN_PARTICIPANTS): for j in range(0, MIN_PARTICIPANTS):
S_i' += G.ScalarMult(vss_commitment[j], pow(i, j)) S_i' += G.ScalarMult(vss_commitment[j], pow(i, j))
return S_i == S_i' return S_i == S_i'
We now define how the Coordinator and participants can derive group We now define how the Coordinator and participants can derive group
info, which is an input into the FROST signing protocol. info, which is an input into the FROST signing protocol.
Inputs: Inputs:
- MAX_PARTICIPANTS, the number of shares to generate, an integer. - MAX_PARTICIPANTS, the number of shares to generate, an integer.
- MIN_PARTICIPANTS, the threshold of the secret sharing scheme, - MIN_PARTICIPANTS, the threshold of the secret sharing scheme,
an integer. an integer.
- vss_commitment, a VSS commitment to a secret polynomial f, a vector - vss_commitment, a VSS commitment to a secret polynomial f, a vector
commitment to each of the coefficients in coeffs, where each commitment to each of the coefficients in coeffs, where each
element of the vector commitment is an Element. element of the vector commitment is an Element.
Outputs: Outputs:
- PK, the public key representing the group, an Element. - PK, the public key representing the group, an Element.
- participant_public_keys, a list of MAX_PARTICIPANTS public keys - participant_public_keys, a list of MAX_PARTICIPANTS public keys
PK_i for i=1,...,MAX_PARTICIPANTS, where each PK_i is the public PK_i for i=1,...,MAX_PARTICIPANTS, where each PK_i is the public
key, an Element, for participant i. key, an Element, for participant i.
def derive_group_info(MAX_PARTICIPANTS, MIN_PARTICIPANTS, vss_commitment) def derive_group_info(MAX_PARTICIPANTS, MIN_PARTICIPANTS,
PK = vss_commitment[0] vss_commitment):
participant_public_keys = [] PK = vss_commitment[0]
for i in range(1, MAX_PARTICIPANTS+1): participant_public_keys = []
PK_i = G.Identity() for i in range(1, MAX_PARTICIPANTS+1):
for j in range(0, MIN_PARTICIPANTS): PK_i = G.Identity()
PK_i += G.ScalarMult(vss_commitment[j], pow(i, j)) for j in range(0, MIN_PARTICIPANTS):
participant_public_keys.append(PK_i) PK_i += G.ScalarMult(vss_commitment[j], pow(i, j))
return PK, participant_public_keys participant_public_keys.append(PK_i)
return PK, participant_public_keys
Appendix E. Random Scalar Generation Appendix D. Random Scalar Generation
Two popular algorithms for generating a random integer uniformly Two popular algorithms for generating a random integer uniformly
distributed in the range [0, G.Order() -1] are as follows: distributed in the range [0, G.Order() -1] are described in the
sections that follow.
E.1. Rejection Sampling D.1. Rejection Sampling
Generate a random byte array with Ns bytes, and attempt to map to a Generate a random byte array with Ns bytes and attempt to map to a
Scalar by calling DeserializeScalar in constant time. If it Scalar by calling DeserializeScalar in constant time. If it
succeeds, return the result. If it fails, try again with another succeeds, return the result. If it fails, try again with another
random byte array, until the procedure succeeds. Failure to random byte array, until the procedure succeeds. Failure to
implement DeserializeScalar in constant time can leak information implement DeserializeScalar in constant time can leak information
about the underlying corresponding Scalar. about the underlying corresponding Scalar.
As an optimization, if the group order is very close to a power of 2, As an optimization, if the group order is very close to a power of 2,
it is acceptable to omit the rejection test completely. In it is acceptable to omit the rejection test completely. In
particular, if the group order is p, and there is an integer b such particular, if the group order is p and there is an integer b such
that |p - 2^b| is less than 2^(b/2), then RandomScalar can simply that |p - 2^b| is less than 2^(b/2), then RandomScalar can simply
return a uniformly random integer of at most b bits. return a uniformly random integer of at most b bits.
E.2. Wide Reduction D.2. Wide Reduction
Generate a random byte array with l = ceil(((3 * Generate a random byte array with l = ceil(((3 *
ceil(log2(G.Order()))) / 2) / 8) bytes, and interpret it as an ceil(log2(G.Order()))) / 2) / 8) bytes and interpret it as an
integer; reduce the integer modulo G.Order() and return the result. integer; reduce the integer modulo G.Order() and return the result.
See Section 5 of [HASH-TO-CURVE] for the underlying derivation of l. See Section 5 of [HASH-TO-CURVE] for the underlying derivation of l.
Appendix F. Test Vectors Appendix E. Test Vectors
This section contains test vectors for all ciphersuites listed in This section contains test vectors for all ciphersuites listed in
Section 6. All Element and Scalar values are represented in Section 6. All Element and Scalar values are represented in
serialized form and encoded in hexadecimal strings. Signatures are serialized form and encoded in hexadecimal strings. Signatures are
represented as the concatenation of their constituent parts. The represented as the concatenation of their constituent parts. The
input message to be signed is also encoded as a hexadecimal string. input message to be signed is also encoded as a hexadecimal string.
Each test vector consists of the following information. Each test vector consists of the following information.
* Configuration. This lists the fixed parameters for the particular * Configuration. This lists the fixed parameters for the particular
instantiation of FROST, including MAX_PARTICIPANTS, instantiation of FROST, including MAX_PARTICIPANTS,
MIN_PARTICIPANTS, and NUM_PARTICIPANTS. MIN_PARTICIPANTS, and NUM_PARTICIPANTS.
* Group input parameters. This lists the group secret key and * Group input parameters. This lists the group secret key and
shared public key, generated by a trusted dealer as described in shared public key, generated by a trusted dealer as described in
Appendix D, as well as the input message to be signed. The Appendix C, as well as the input message to be signed. The
randomly generated coefficients produced by the trusted dealer to randomly generated coefficients produced by the trusted dealer to
share the group signing secret are also listed. Each coefficient share the group signing secret are also listed. Each coefficient
is identified by its index, e.g., share_polynomial_coefficients[1] is identified by its index, e.g., share_polynomial_coefficients[1]
is the coefficient of the first term in the polynomial. Note that is the coefficient of the first term in the polynomial. Note that
the 0-th coefficient is omitted as this is equal to the group the 0-th coefficient is omitted, as this is equal to the group
secret key. All values are encoded as hexadecimal strings. secret key. All values are encoded as hexadecimal strings.
* Signer input parameters. This lists the signing key share for * Signer input parameters. This lists the signing key share for
each of the NUM_PARTICIPANTS participants. each of the NUM_PARTICIPANTS participants.
* Round one parameters and outputs. This lists the NUM_PARTICIPANTS * Round one parameters and outputs. This lists the NUM_PARTICIPANTS
participants engaged in the protocol, identified by their participants engaged in the protocol, identified by their
NonZeroScalar identifier, and for each participant: the hiding and NonZeroScalar identifier, and the following for each participant:
binding commitment values produced in Section 5.1; the randomness the hiding and binding commitment values produced in Section 5.1;
values used to derive the commitment nonces in nonce_generate; the the randomness values used to derive the commitment nonces in
resulting group binding factor input computed in part from the nonce_generate; the resulting group binding factor input computed
group commitment list encoded as described in Section 4.3; and in part from the group commitment list encoded as described in
group binding factor as computed in Section 5.2). Section 4.3; and the group binding factor as computed in
Section 5.2.
* Round two parameters and outputs. This lists the NUM_PARTICIPANTS * Round two parameters and outputs. This lists the NUM_PARTICIPANTS
participants engaged in the protocol, identified by their participants engaged in the protocol, identified by their
NonZeroScalar identifier, along with their corresponding output NonZeroScalar identifier, along with their corresponding output
signature share as produced in Section 5.2. signature share as produced in Section 5.2.
* Final output. This lists the aggregate signature as produced in * Final output. This lists the aggregate signature as produced in
Section 5.3. Section 5.3.
F.1. FROST(Ed25519, SHA-512) E.1. FROST(Ed25519, SHA-512)
// Configuration information // Configuration information
MAX_PARTICIPANTS: 3 MAX_PARTICIPANTS: 3
MIN_PARTICIPANTS: 2 MIN_PARTICIPANTS: 2
NUM_PARTICIPANTS: 2 NUM_PARTICIPANTS: 2
// Group input parameters // Group input parameters
participant_list: 1,3 participant_list: 1,3
group_secret_key: 7b1c33d3f5291d85de664833beb1ad469f7fb6025a0ec78b3a7 group_secret_key: 7b1c33d3f5291d85de664833beb1ad469f7fb6025a0ec78b3a7
90c6e13a98304 90c6e13a98304
skipping to change at page 53, line 35 skipping to change at line 2088
// Signer round two outputs // Signer round two outputs
P1 sig_share: 001719ab5a53ee1a12095cd088fd149702c0720ce5fd2f29dbecf24 P1 sig_share: 001719ab5a53ee1a12095cd088fd149702c0720ce5fd2f29dbecf24
b7281b603 b7281b603
P3 sig_share: bd86125de990acc5e1f13781d8e32c03a9bbd4c53539bbc106058bf P3 sig_share: bd86125de990acc5e1f13781d8e32c03a9bbd4c53539bbc106058bf
d14326007 d14326007
sig: 36282629c383bb820a88b71cae937d41f2f2adfcc3d02e55507e2fb9e2dd3cbe sig: 36282629c383bb820a88b71cae937d41f2f2adfcc3d02e55507e2fb9e2dd3cbe
bd9d2b0844e49ae0f3fa935161e1419aab7b47d21a37ebeae1f17d4987b3160b bd9d2b0844e49ae0f3fa935161e1419aab7b47d21a37ebeae1f17d4987b3160b
F.2. FROST(Ed448, SHAKE256) E.2. FROST(Ed448, SHAKE256)
// Configuration information // Configuration information
MAX_PARTICIPANTS: 3 MAX_PARTICIPANTS: 3
MIN_PARTICIPANTS: 2 MIN_PARTICIPANTS: 2
NUM_PARTICIPANTS: 2 NUM_PARTICIPANTS: 2
// Group input parameters // Group input parameters
participant_list: 1,3 participant_list: 1,3
group_secret_key: 6298e1eef3c379392caaed061ed8a31033c9e9e3420726f23b4 group_secret_key: 6298e1eef3c379392caaed061ed8a31033c9e9e3420726f23b4
04158a401cd9df24632adfe6b418dc942d8a091817dd8bd70e1c72ba52f3c00 04158a401cd9df24632adfe6b418dc942d8a091817dd8bd70e1c72ba52f3c00
skipping to change at page 55, line 31 skipping to change at line 2181
P1 sig_share: e1eb9bfbef792776b7103891032788406c070c5c315e3bf5d64acd4 P1 sig_share: e1eb9bfbef792776b7103891032788406c070c5c315e3bf5d64acd4
6ea8855e85b53146150a09149665cbfec71626810b575e6f4dbe9ba3700 6ea8855e85b53146150a09149665cbfec71626810b575e6f4dbe9ba3700
P3 sig_share: 815434eb0b9f9242d54b8baf2141fe28976cabe5f441ccfcd5ee7cd P3 sig_share: 815434eb0b9f9242d54b8baf2141fe28976cabe5f441ccfcd5ee7cd
b4b52185b02b99e6de28e2ab086c7764068c5a01b5300986b9f084f3e00 b4b52185b02b99e6de28e2ab086c7764068c5a01b5300986b9f084f3e00
sig: cd642cba59c449dad8e896a78a60e8edfcbd9040df524370891ff8077d47ce72 sig: cd642cba59c449dad8e896a78a60e8edfcbd9040df524370891ff8077d47ce72
1d683874483795f0d85efcbd642c4510614328605a19c6ed806ffb773b6956419537c 1d683874483795f0d85efcbd642c4510614328605a19c6ed806ffb773b6956419537c
dfdb2b2a51948733de192dcc4b82dc31580a536db6d435e0cb3ce322fbcf9ec23362d dfdb2b2a51948733de192dcc4b82dc31580a536db6d435e0cb3ce322fbcf9ec23362d
da27092c08767e607bf2093600 da27092c08767e607bf2093600
F.3. FROST(ristretto255, SHA-512) E.3. FROST(ristretto255, SHA-512)
// Configuration information // Configuration information
MAX_PARTICIPANTS: 3 MAX_PARTICIPANTS: 3
MIN_PARTICIPANTS: 2 MIN_PARTICIPANTS: 2
NUM_PARTICIPANTS: 2 NUM_PARTICIPANTS: 2
// Group input parameters // Group input parameters
participant_list: 1,3 participant_list: 1,3
group_secret_key: 1b25a55e463cfd15cf14a5d3acc3d15053f08da49c8afcf3ab2 group_secret_key: 1b25a55e463cfd15cf14a5d3acc3d15053f08da49c8afcf3ab2
65f2ebc4f970b 65f2ebc4f970b
skipping to change at page 57, line 11 skipping to change at line 2257
// Signer round two outputs // Signer round two outputs
P1 sig_share: 9285f875923ce7e0c491a592e9ea1865ec1b823ead4854b48c8a462 P1 sig_share: 9285f875923ce7e0c491a592e9ea1865ec1b823ead4854b48c8a462
87749ee09 87749ee09
P3 sig_share: 7cb211fe0e3d59d25db6e36b3fb32344794139602a7b24f1ae0dc4e P3 sig_share: 7cb211fe0e3d59d25db6e36b3fb32344794139602a7b24f1ae0dc4e
26ad7b908 26ad7b908
sig: fc45655fbc66bbffad654ea4ce5fdae253a49a64ace25d9adb62010dd9fb2555 sig: fc45655fbc66bbffad654ea4ce5fdae253a49a64ace25d9adb62010dd9fb2555
2164141787162e5b4cab915b4aa45d94655dbb9ed7c378a53b980a0be220a802 2164141787162e5b4cab915b4aa45d94655dbb9ed7c378a53b980a0be220a802
F.4. FROST(P-256, SHA-256) E.4. FROST(P-256, SHA-256)
// Configuration information // Configuration information
MAX_PARTICIPANTS: 3 MAX_PARTICIPANTS: 3
MIN_PARTICIPANTS: 2 MIN_PARTICIPANTS: 2
NUM_PARTICIPANTS: 2 NUM_PARTICIPANTS: 2
// Group input parameters // Group input parameters
participant_list: 1,3 participant_list: 1,3
group_secret_key: 8ba9bba2e0fd8c4767154d35a0b7562244a4aaf6f36c8fb8735 group_secret_key: 8ba9bba2e0fd8c4767154d35a0b7562244a4aaf6f36c8fb8735
fa48b301bd8de fa48b301bd8de
skipping to change at page 58, line 37 skipping to change at line 2331
// Signer round two outputs // Signer round two outputs
P1 sig_share: 400308eaed7a2ddee02a265abe6a1cfe04d946ee8720768899619cf P1 sig_share: 400308eaed7a2ddee02a265abe6a1cfe04d946ee8720768899619cf
abe7a3aeb abe7a3aeb
P3 sig_share: 561da3c179edbb0502d941bb3e3ace3c37d122aaa46fb54499f15f3 P3 sig_share: 561da3c179edbb0502d941bb3e3ace3c37d122aaa46fb54499f15f3
a3331de44 a3331de44
sig: 026d8d434874f87bdb7bc0dfd239b2c00639044f9dcb195e9a04426f70bfa4b7 sig: 026d8d434874f87bdb7bc0dfd239b2c00639044f9dcb195e9a04426f70bfa4b7
0d9620acac6767e8e3e3036815fca4eb3a3caa69992b902bcd3352fc34f1ac192f 0d9620acac6767e8e3e3036815fca4eb3a3caa69992b902bcd3352fc34f1ac192f
F.5. FROST(secp256k1, SHA-256) E.5. FROST(secp256k1, SHA-256)
// Configuration information // Configuration information
MAX_PARTICIPANTS: 3 MAX_PARTICIPANTS: 3
MIN_PARTICIPANTS: 2 MIN_PARTICIPANTS: 2
NUM_PARTICIPANTS: 2 NUM_PARTICIPANTS: 2
// Group input parameters // Group input parameters
participant_list: 1,3 participant_list: 1,3
group_secret_key: 0d004150d27c3bf2a42f312683d35fac7394b1e9e318249c1bf group_secret_key: 0d004150d27c3bf2a42f312683d35fac7394b1e9e318249c1bf
e7f0795a83114 e7f0795a83114
skipping to change at page 60, line 15 skipping to change at line 2405
// Signer round two outputs // Signer round two outputs
P1 sig_share: c4fce1775a1e141fb579944166eab0d65eefe7b98d480a569bbbfcb P1 sig_share: c4fce1775a1e141fb579944166eab0d65eefe7b98d480a569bbbfcb
14f91c197 14f91c197
P3 sig_share: 0160fd0d388932f4826d2ebcd6b9eaba734f7c71cf25b4279a4ca25 P3 sig_share: 0160fd0d388932f4826d2ebcd6b9eaba734f7c71cf25b4279a4ca25
81e47b18d 81e47b18d
sig: 0205b6d04d3774c8929413e3c76024d54149c372d57aae62574ed74319b5ea14 sig: 0205b6d04d3774c8929413e3c76024d54149c372d57aae62574ed74319b5ea14
d0c65dde8492a7471437e6c2fe3da49b90d23f642b5c6dbe7e36089f096dd97324 d0c65dde8492a7471437e6c2fe3da49b90d23f642b5c6dbe7e36089f096dd97324
Acknowledgments
This document was improved based on input and contributions by the
Zcash Foundation engineering team. In addition, the authors of this
document would like to thank Isis Lovecruft, Alden Torres, T. Wilson-
Brown, and Conrado Gouvea for their input and contributions.
Authors' Addresses Authors' Addresses
Deirdre Connolly Deirdre Connolly
Zcash Foundation Zcash Foundation
Email: durumcrustulum@gmail.com Email: durumcrustulum@gmail.com
Chelsea Komlo Chelsea Komlo
University of Waterloo, Zcash Foundation University of Waterloo, Zcash Foundation
Email: ckomlo@uwaterloo.ca Email: ckomlo@uwaterloo.ca
 End of changes. 280 change blocks. 
921 lines changed or deleted 733 lines changed or added

This html diff was produced by rfcdiff 1.48.