This section fixes the setting that every later protocol assumes: the participants, their identifiers, the signing sets and their Lagrange coefficients; the threshold key material and the group information that coefficient commitments determine; the syntax and correctness of a two-round threshold Schnorr signature scheme with a Coordinator; and the channel types and the static corruption model. Notation is that of §1.3.
Let G be a group of prime order q with generator B and scalar
field F q (§1.3). Threshold parameters are
integers
| 1 ≤ t ≤ n < q . |
There are n participants
The constraints are those of RFC 9591, Section 5 (“Two-Round FROST Signing Protocol”): the identifiers are distinct nonzero scalars in [1, MAX _ PARTICIPANTS] ; the bound MAX _ PARTICIPANTS is less than the group order; and
| MIN _ PARTICIPANTS ≤ NUM _ PARTICIPANTS ≤ MAX _ PARTICIPANTS . |
The dealer of RFC 9591, Appendix C (“Trusted
Dealer Key Generation”), shares at the identifiers
Shamir sharing is cited, not re-derived: Crypto Guide,
§“Secret sharing”, Construction “Shamir t -of- n secret sharing”.
Its parameters
Let I be a signing set and
| λ I, i := ∏ j ∈ I, j ≠ i j j − i ∈ F q, |
whose denominators are nonzero because identifiers are distinct. For the
Lagrange basis polynomial
Let I be a signing set. For every
| ∑ i ∈ I λ I, i f (i) = f (0) . |
In particular
Put
The proof is given in place: the Math Guide’s Proposition “Lagrange
polynomials sum to one” concerns its roots-of-unity domain and does not
apply to the nodes I . ZIP 312, “Rationale”, uses the sum
The coefficients λ I, i depend on the identifiers of I alone, not on the shares or on the polynomial (Definition 2.3). Hence the signing set is chosen per signing run, after key generation, by the Coordinator of Definition 2.8, which determines the participants, at least MIN _ PARTICIPANTS in number (RFC 9591, Section 5).
Let (t, n) be threshold parameters. Threshold key material consists of:
a sharing polynomial
for each identifier j , the secret share
(j, sk j) with
the coefficient commitments
the group information
(PK, (PK j) j = 1 n) , with group key
Shares
The components are those of RFC 9591, Section 5: each participant is
configured with its identifier, the share
Let
The group key is
| PK j = [f (j)] B = ∑ k = 0 t − 1 [j k] A k . |
Every party holding (A 0, ..., A t − 1) therefore computes the group information from the commitments alone.
Let
Part (i) is the identity displayed in Crypto Guide, Construction
“Feldman verifiable secret sharing”, where it follows from the
homomorphism
RFC 9591, Appendix C.2 (“Verifiable Secret Sharing”), derives the group information from the commitment vector in this way. Both key generations of §3 cite the lemma.
The syntax of a signature scheme, existential unforgeability under
chosen-message attack and strong unforgeability are those of Crypto
Guide, §“Syntax and security goal” (Definitions “Digital signature
scheme”, “Existential unforgeability under chosen-message attack” and
“Strong unforgeability”), which admits correctness with overwhelming
probability. The single-party Schnorr signature is Crypto Guide,
§“From identification to signature via the Fiat–Shamir transform”,
Construction “Schnorr signature”, perfectly correct by its Proposition
“Perfect correctness”. In additive notation with generator B , signing
key s and public key
| r ← $ F q, R = [r] B, c = H (R ‖ PK ‖ m), z = r + c s, σ = (R, z), |
and verification accepts (R, z) if and only if
| [z] B = R + [c] PK . |
The Crypto Guide’s response s is written z here, s being the signing key. The challenge input order (nonce commitment, public key, message) is that of RFC 9591, Section 4.6 (“Signature Challenge Computation”), and of RedPallas; the hash and the encodings of FROST are fixed by the ciphersuite (Definition 4.1). Discrete logarithms and random oracles are those of the Crypto Guide, §“The discrete logarithm problem” and §“The random oracle model”, as §1.3 records.
Let (t, n) be threshold parameters (Definition 2.1). A
two-round threshold signature scheme with a Coordinator is run by
the participants
Key generation, a dealer algorithm or a protocol, which outputs valid key material (Definition 2.5): sk j to P j , and the group information to every party.
Round One, run by each P i independently of any message and of any signing set, which outputs a public commitment com i , sent to the Coordinator, and a secret state st i , which P i keeps and uses in at most one Round Two.
Round Two. The Coordinator chooses a signing set I and a
message m , and sends the request (m, (com j) j ∈ I)
to each P i with
Aggregation, by which the Coordinator maps m , the commitment list (com j) j ∈ I and the shares (z j) j ∈ I to a signature σ or to ⊥ .
Verification, the single-party Schnorr verification of a signature on m under the group key PK .
The scheme is correct if, for all valid key material output by key generation, every signing set I and every message m , a run in which every party is honest outputs either ⊥ or a signature that verification accepts under PK , and outputs ⊥ with probability negligible in the security parameter.
The parties and the rounds are those of RFC 9591, Section 5: the Coordinator determines the participants, coordinates the rounds, aggregates the signature shares and publishes the signature; Round One produces commitments; Round Two produces a signature share over the message and the commitments that the Coordinator supplies. Theorem 4.11 bounds the probability of ⊥ for FROST. Unforgeability notions are defined in §7, before any use.
The two-round form is the one RFC 9591 specifies (Section 5). Single-round signing with commitments preprocessed in batches (ePrint 2020/852) is out of the scope of RFC 9591 (Section 1, “Introduction”) and of this volume.
Every message of every protocol in this volume travels on a channel of one of the following four types, and the protocol names the type.
An authenticated channel with reliable delivery: the receiver learns the sender and the unmodified message; delivery is assured, as completion of the protocol requires; the content is visible to an observer of the network. It carries the signing messages: the Round One commitments, the Round Two request and the returned shares.
A confidential and authenticated channel: a channel of type (a) whose content is hidden from every party but its endpoints. It carries the Round Two request of the re-randomised variant with its confidential inputs, named in Construction 5.10.
A mutually authenticated confidential channel: a channel of type (b) in which each endpoint is authenticated to the other. It carries dealt shares and the evaluations of round two of distributed key generation.
Consistent broadcast: every honest recipient outputs the same value from the sender, whether or not the sender is honest, or every honest recipient aborts. If the sender is honest, an honest recipient that does not abort outputs the value sent. It carries the coefficient commitments and the proofs of knowledge of key generation.
Realisations are not described. For what authentication provides against an adversary that controls the network, see Crypto Guide, §“Active attacks and the role of authentication”.
Each type is tied to its source. Type (a) is that of RFC 9591, Section 5, which assumes reliable delivery for completion and an authenticated channel, confidentiality not being required; Section 7 (“Security Considerations”) adds that signing may run over a public channel provided it is authenticated and reliable. Authentication is what identifies a misbehaving participant: without it, a party masquerading as another causes only an invalid signature (RFC 9591, Section 5). Type (b) is that of ZIP 312, “Round Two - Signature Share Generation”, which requires a confidential and authenticated channel and records the difference from RFC 9591. Type (c) is that of RFC 9591, Appendix C, which requires a mutually authenticated secure channel with confidentiality and integrity for dealt shares, and of ePrint 2020/852, Figure 1, in which round two of key generation sends the evaluations securely. Type (d) is required by RFC 9591, Appendix C, under which participants must abort if they do not hold the same view of the commitment vector, and by ePrint 2020/852, Figure 1, which broadcasts commitments and proofs.
Before key generation the adversary fixes a set
A malicious Coordinator can deny service, by withholding requests, the
aggregate or its publication, and can falsely report a participant as
misbehaving; no honest party can prevent either, since FROST provides no
robustness (RFC 9591, Section 7; ePrint 2020/852, Section 5, “Signature
Aggregator Role”). What a malicious Coordinator cannot do is stated in
§7, either as a theorem (Theorem 7.9,
Theorem 7.20) or as an open problem
(Remark 7.22); Definition 2.11
asserts none of it. The re-randomised variant further trusts the
Coordinator and every share holder with the privacy of the transaction
(Definition 5.14). Adaptive corruption, metadata privacy and
network privacy are out of scope. The model is that of RFC 9591,
Section 7, under which the Coordinator and at most