FROST Guide Threshold RedPallas: FROST and its Zcash integration surfaces 3 Key generation 5 Re-randomised FROST for spend authorisation

4 Signing and aggregation

This section states FROST signing as RFC 9591 specifies it, in execution order: the ciphersuite interface with its hash roles and the encoding of a commitment list; Round One, which draws hedged nonces and commits to them; Round Two, which binds each signature share to the message and to the whole commitment list; aggregation with share verification; the correctness of an honest run; and the single use of nonces, with the exact condition under which reuse of a nonce pair exposes a share. Threshold parameters, signing sets, Lagrange coefficients and key material are those of §2; the key material is the output of either key generation of §3.

4.1 Ciphersuites and encodings

Definition 4.1 (Ciphersuite).

A ciphersuite fixes the following data.

(a)

A group $\mathbb{G}$ of prime order $q$ , written additively, with identity $\mathcal{O}$ and generator $B$ , and its scalar field $\mathbb{F}_{q}$ . Write $\mathbb{G}^{*}:=\mathbb{G}\setminus\{\mathcal{O}\}$ .
(b)

An element serialisation $\mathsf{ser}_{\mathbb{G}}$ , mapping either every element of $\mathbb{G}$ or every element of $\mathbb{G}^{*}$ injectively to a byte string of fixed length $N_{\mathrm{e}}$ , and an element deserialisation $\mathsf{deser}_{\mathbb{G}}$ , which maps a byte string to an element of $\mathbb{G}^{*}$ or fails. It fails on every string that is not the canonical encoding $\mathsf{ser}_{\mathbb{G}}(P)$ of some $P\in\mathbb{G}$ , and on the encoding of $\mathcal{O}$ where one exists; on every other string it inverts $\mathsf{ser}_{\mathbb{G}}$ . The serialisation is total if its domain is $\mathbb{G}$ .
(c)

A scalar serialisation $\mathsf{ser}_{\mathbb{F}_{q}}$ , mapping $\mathbb{F}_{q}$ injectively to byte strings of fixed length $N_{\mathrm{s}}$ , and a scalar deserialisation $\mathsf{deser}_{\mathbb{F}_{q}}$ , which fails on every string whose integer value is not below $q$ and inverts $\mathsf{ser}_{\mathbb{F}_{q}}$ otherwise.
(d)

Hash functions by role:

$H_{1},H_{2},H_{3}\colon\{0,1\}^{8*}\to\mathbb{F}_{q},\qquad H_{4},H_{5}\colon% \{0,1\}^{8*}\to\{0,1\}^{8N_{\mathrm{h}}},$

where $\{0,1\}^{8*}$ denotes the byte strings and $N_{\mathrm{h}}$ is the digest length of the suite. The roles are: $H_{1}$ the binding factor, $H_{2}$ the challenge, $H_{3}$ the nonce, $H_{4}$ the message pre-hash and $H_{5}$ the commitment-list pre-hash.
(e)

The signature encoding $\mathsf{ser}_{\mathbb{G}}(R)\,\|\,\mathsf{ser}_{\mathbb{F}_{q}}(z)$ of a pair $(R,z)\in\mathbb{G}\times\mathbb{F}_{q}$ , and the single-party verification: a pair $(R,z)$ is accepted on a message $m$ under a public key $\mathit{PK}$ if and only if

$[z]B\;=\;R+[c]\,\mathit{PK},\qquad c:=H_{2}\bigl{(}\mathsf{ser}_{\mathbb{G}}(R% )\,\|\,\mathsf{ser}_{\mathbb{G}}(\mathit{PK})\,\|\,m\bigr{)}.$

This is the verification of the Crypto Guide’s Construction “Schnorr signature” (§“From identification to signature via the Fiat–Shamir transform”) in additive form, with hash $H_{2}$ .

A ciphersuite for re-randomised signing adds

(f)

the randomiser hash $H_{R}\colon\{0,1\}^{8*}\to\mathbb{F}_{q}$ (ZIP 312, “Specification” and “Randomizer Generation”).

The ciphersuites of RFC 9591 do not define $H_{R}$ .

The data are those of RFC 9591, Sections 3.1 (“Prime-Order Group”) and 3.2 (“Cryptographic Hash Function”), and Section 6 (“Ciphersuites”), whose Appendix A (“Schnorr Signature Encoding”) fixes the encoding and whose Appendix B (“Schnorr Signature Generation and Verification for Prime-Order Groups”) the verification equation. The requirements that RFC 9591, Section 6.6 (“Ciphersuite Requirements”), places on every ciphersuite are four: the group is of prime order and every deserialisation outputs an element of its set or fails; every hash function is domain-separated with a per-suite context string, FROST(Ed25519, SHA-512) excepted for $H_{2}$ for compatibility with RFC 8032; $H_{1}$ , $H_{2}$ and $H_{3}$ have output distributions close to uniform; and the signature encoding is specified. The suite FROST(Pallas, BLAKE2b-512) separates its hashes by BLAKE2b personalisations instead, its $H_{2}$ being that of RedPallas (Construction 6.1).

The generic element serialisation of RFC 9591, Section 3.1, fails on $\mathcal{O}$ ; a suite may instead serialise every element, as FROST(Pallas, BLAKE2b-512) does with the star encoding (Ironwood Guide, Definition “Star encoding”; ZIP 312, “FROST(Pallas, BLAKE2b-512)”). In both cases the element deserialisation rejects $\mathcal{O}$ . Whether $\mathsf{ser}_{\mathbb{G}}$ is total is the one property of a suite on which Theorem 4.11 distinguishes cases.

Assumption 4.2 (The ciphersuite hashes).

The hashes $H_{1}$ , $H_{2}$ , $H_{3}$ and $H_{R}$ are modelled as random oracles into $\mathbb{F}_{q}$ (Crypto Guide, §“The random oracle model”, Definition “Random oracle”), independent of each other and of the proof-of-knowledge hash $H_{\mathrm{dkg}}$ (Assumption 3.5): each answer at a new input is an independent sample from a distribution on $\mathbb{F}_{q}$ within statistical distance $\delta$ of uniform (Math Guide, §“Statistical distance”), where $\delta$ is a parameter of the suite. The hashes $H_{4}$ and $H_{5}$ are modelled as independent random oracles into $\{0,1\}^{8N_{\mathrm{h}}}$ ; hence an algorithm making $Q$ queries finds a collision of either with probability at most

\frac{Q(Q-1)}{2}\cdot 2^{-8N_{\mathrm{h}}}

(Math Guide, §“The union bound and a birthday calculation”, Proposition “Birthday bound”). For a suite that builds every role from one hash function under distinct personalisations, the assumption is that this function, keyed by its personalisation, is a random oracle; distinct personalisations then give independent oracles (Crypto Guide, §“Domain separation and personalisation”, Proposition “Domain separation yields independent oracles”), and $\delta$ is the bias of the reduction of its output into $\mathbb{F}_{q}$ (Crypto Guide, §“Hashing to a field element”).

The assumption is the one hash assumption of every ciphersuite in this volume. RFC 9591, Section 3.2, models the ciphersuite hash as a random oracle in the security analyses it cites. The suite FROST(Pallas, BLAKE2b-512) meets the assumption with $\delta\leq p_{\mathsf{Vesta}}/2^{512}<2^{-257}$ and no further assumption, by Proposition 6.2.

Definition 4.3 (Commitment list and its encoding).

Let a ciphersuite be fixed and let $I$ be a signing set (Definition 2.1). A commitment list over $I$ is a sequence

L=\bigl{(}(i,D_{i},E_{i})\bigr{)}_{i\in I},\qquad D_{i},E_{i}\in\mathbb{G},

with one triple for each member of $I$ : $D_{i}$ is the hiding commitment and $E_{i}$ the binding commitment of member $i$ . The identifiers are distinct and the triples are sorted in ascending order of the least non-negative representative of the identifier. The signing set is read off $L$ as the set of its identifiers. The encoding of $L$ is the byte string

\mathsf{enc}(L)\;:=\;\mathop{\big{\|}}_{i\in I,\ \text{ascending}}\Bigl{(}% \mathsf{ser}_{\mathbb{F}_{q}}(i)\,\|\,\mathsf{ser}_{\mathbb{G}}(D_{i})\,\|\,% \mathsf{ser}_{\mathbb{G}}(E_{i})\Bigr{)}

of length $\lvert I\rvert(N_{\mathrm{s}}+2N_{\mathrm{e}})$ .

A commitment equal to $\mathcal{O}$ occurs only in a suite with total element serialisation, and check (3) of Construction 4.8 rejects it.

The ordering is a requirement of RFC 9591, which states that the list must be sorted in ascending order by identifier, and compares scalars by their least non-negative representative (Sections 3.1 and 4.3, “List Operations”); the encoding is that of Section 4.3. Every component has fixed length, each serialisation is injective, and the order of the triples is fixed; hence the length of $\mathsf{enc}(L)$ determines $\lvert I\rvert$ , and the string parses uniquely into the triples. The map $\mathsf{enc}$ is therefore injective on commitment lists over one suite, which the binding factors of Definition 4.7 require.

4.2 Round One: nonces and commitments

Construction 4.4 (Round One).

Participant $P_{i}$ , holding the share $\mathit{sk}_{i}$ (Definition 2.5), proceeds as follows.

1.

It draws two independent strings $T_{d},T_{e}$ , each uniform on the $32$ -byte strings, and sets the hiding nonce and the binding nonce

$d_{i}:=H_{3}\bigl{(}T_{d}\,\|\,\mathsf{ser}_{\mathbb{F}_{q}}(\mathit{sk}_{i})% \bigr{)},\qquad e_{i}:=H_{3}\bigl{(}T_{e}\,\|\,\mathsf{ser}_{\mathbb{F}_{q}}(% \mathit{sk}_{i})\bigr{)}.$
2.

It sets $D_{i}:=[d_{i}]B$ and $E_{i}:=[e_{i}]B$ .
3.

It stores $(d_{i},e_{i},D_{i},E_{i})$ , keeps $(d_{i},e_{i})$ secret, and sends $\bigl{(}\mathsf{ser}_{\mathbb{G}}(D_{i}),\mathsf{ser}_{\mathbb{G}}(E_{i})\bigr% {)}$ to the Coordinator over an authenticated channel (Definition 2.10, type (a)). If a serialisation fails, which happens only in a suite whose element serialisation is not total and only if $D_{i}$ or $E_{i}$ is $\mathcal{O}$ , the participant discards the pair and this execution of Round One fails.

The strings $T_{d}$ and $T_{e}$ must be sampled uniformly from a secure source of randomness, and a nonce pair must not be used in more than one signing run.

The construction is RFC 9591, Section 5.1 (“Round One - Commitment”), with the hedged nonce generation of Section 4.1 (“Nonce Generation”), which always samples $32$ bytes of fresh randomness and hashes them together with the serialised share. Section 5.1 requires that the nonces not be used in more than one signing and be generated from a source of secure randomness; Section 7.3 (“Nonce Reuse Attacks”) requires the randomness to be sampled uniformly. Nonces lie in $\mathbb{F}_{q}$ , not in $\mathbb{F}_{q}^{*}$ : the zero nonce is not excluded, and its consequence is case (1) of Theorem 4.11. Round One does not depend on the message or on the signing set, so a participant may run it ahead of any signing run and hold several unused pairs. The paper that introduced FROST (ePrint 2020/852, Figure 2) samples the pair uniformly from $\mathbb{F}_{q}^{*}\times\mathbb{F}_{q}^{*}$ ; the specified rule is the hedged derivation above, and this volume states it instead.

Lemma 4.5 (Hedged nonces are close to uniform).

Under Assumption 4.2, let an algorithm, the observer, make at most $q_{h}$ queries to $H_{3}$ and, at one point, choose a byte string $w$ and receive $d:=H_{3}(T\,\|\,w)$ , for $T$ uniform on the $32$ -byte strings and independent of all else. The pair formed by the observer’s view and $d$ is within statistical distance

\delta+q_{h}\cdot 2^{-256}

of the pair obtained when $d$ is replaced by a uniform element of $\mathbb{F}_{q}$ independent of all else. For the two nonces of one execution of Round One, received for one string $w$ with independent strings $T_{d}$ and $T_{e}$ , the corresponding distance is at most

2\bigl{(}\delta+q_{h}\cdot 2^{-256}\bigr{)}+2^{-256}.

Proof.

The argument is that of the Ironwood Guide’s Lemma “Distance of GenRandom from uniform” (§“Randomised validating keys”), with $32$ fresh bytes in place of $80$ and $H_{3}$ in place of the RedPallas hash. Let $E$ be the event that the observer queries $H_{3}$ at $T\,\|\,w$ . In a second experiment the answer $H_{3}(T\,\|\,w)$ is replaced, in the computation of $d$ only, by an independent sample of the answer distribution. In the lazy realisation of the random oracle the answers at other inputs are independent of the answer at $T\,\|\,w$ , so the two experiments are identical until $E$ occurs, and their outputs are within statistical distance $\mathrm{Pr}[E]$ (Crypto Guide, §“Security as a game”, Remark “Game-hopping”). In the second experiment the observer’s view is independent of $T$ , so each query has prefix $T$ with probability at most $2^{-256}$ , and $\mathrm{Pr}[E]\leq q_{h}\cdot 2^{-256}$ by the union bound. There the sample is independent of everything else, and replacing it by a uniform scalar changes the pair by at most $\delta$ (Math Guide, §“Statistical distance”, Theorem “Properties of statistical distance”, part (4)). The triangle inequality, part (2) of the same theorem, gives the first bound.

For the pair, the event $T_{d}=T_{e}$ , of probability $2^{-256}$ , is excluded at that cost; outside it the inputs $T_{d}\,\|\,w$ and $T_{e}\,\|\,w$ are distinct. The event that the observer queries either input has probability at most $2q_{h}\cdot 2^{-256}$ , and two independent samples are replaced by uniform scalars at cost $2\delta$ . □

The nonces are therefore close to uniform, not uniform, whatever the share; RFC 9591, Section 7.3, states that they are indistinguishable from values sampled uniformly at random, and the lemma quantifies that statement. For FROST(Pallas, BLAKE2b-512), with the $\delta$ of Proposition 6.2, the first bound at $q_{h}=2^{64}$ is below $2^{-191.99}$ , the term $q_{h}\cdot 2^{-256}$ dominating; in a suite with a larger $\delta$ , such as a 48-byte hash to field, $\delta$ dominates.

RFC 9591, Section 4.1, hashes the share with the fresh bytes to hedge against a generator whose output is predictable to an observer; Lemma 4.5 assumes $T$ uniform, and the volume proves no statement for a predictable $T$ . Nonces computed from the share and the message alone permit complete key recovery (RFC 9591, Sections 1 and 7.3), which is why fresh bytes are used.

Over $N=2^{64}$ executions of Round One by one participant, the $32$ -byte strings of one role, hiding or binding, repeat with probability at most $\binom{N}{2}\cdot 2^{-256}<2^{-129}$ (Math Guide, Proposition “Birthday bound”), so, by the union bound, a repeat in either role has probability at most $2^{-128}(1-2^{-64})<2^{-128}$ , the figure of RFC 9591, Section 4.1. A repeated nonce pair, the hypothesis of Lemma 4.13, requires in the same two executions equal hiding nonces and equal binding nonces.

Lemma 4.6 (Repetition of a nonce pair).

Under Assumption 4.2, two of $N$ executions of Round One by one participant yield equal nonce pairs with probability at most

\binom{N}{2}\bigl{(}2^{-255}+1/q+\delta\bigr{)}^{2}.

Proof.

For two executions $j\neq k$ , the hiding strings are equal with probability $2^{-256}$ , and so are the binding strings, independently. Two answers of $H_{3}$ at distinct inputs are equal with probability at most $1/q+\delta$ , since every value has probability at most $1/q+\delta$ under a distribution within $\delta$ of uniform (Math Guide, Theorem “Properties of statistical distance”, part (3)); and when both roles have distinct strings, the two equalities constrain answers at two distinct pairs of inputs, whose probability of holding together is at most $(1/q+\delta)^{2}$ , except when the two pairs of inputs coincide, an event of probability at most $2\cdot 2^{-512}$ . Summing the cases gives at most $2^{-512}+2\cdot 2^{-256}(1/q+\delta)+(1/q+\delta)^{2}+2^{-511}(1/q+\delta)$ , which is below the square displayed; the union bound over the $\binom{N}{2}$ pairs of executions gives the claim. □

4.3 Round Two: binding factors and signature shares

Definition 4.7 (Binding factors and group commitment).

Let $\mathit{PK}$ be the group key, $m$ a message, that is a byte string, and $L$ a commitment list over a signing set $I$ (Definition 4.3). For $i\in I$ the binding factor of $i$ is

\rho_{i}:=H_{1}\Bigl{(}\mathsf{ser}_{\mathbb{G}}(\mathit{PK})\,\|\,H_{4}(m)\,% \|\,H_{5}\bigl{(}\mathsf{enc}(L)\bigr{)}\,\|\,\mathsf{ser}_{\mathbb{F}_{q}}(i)% \Bigr{)};

the commitment share of $i$ is $R_{i}:=D_{i}+[\rho_{i}]E_{i}$ ; the group commitment is $R:=\sum_{i\in I}R_{i}$ ; and the challenge is

c:=H_{2}\bigl{(}\mathsf{ser}_{\mathbb{G}}(R)\,\|\,\mathsf{ser}_{\mathbb{G}}(% \mathit{PK})\,\|\,m\bigr{)},

with $\rho_{i}$ defined whenever $\mathsf{ser}_{\mathbb{G}}(\mathit{PK})$ is, and $c$ whenever $\mathsf{ser}_{\mathbb{G}}(R)$ and $\mathsf{ser}_{\mathbb{G}}(\mathit{PK})$ are. All four are functions of the public data $(\mathit{PK},m,L)$ , computed identically by every member of $I$ and by the Coordinator.

The binding factor is that of RFC 9591, Section 4.4 (“Binding Factors Computation”), the group commitment that of Section 4.5 (“Group Commitment Computation”), and the challenge that of Section 4.6 (“Signature Challenge Computation”). The challenge input has the order nonce commitment, public key, message of the single-party challenge of Definition 4.1, part (e), so a verifier recomputes $c$ from $(R,\mathit{PK},m)$ alone. The paper’s binding value $\rho_{i}=H_{1}(i,m,B)$ , with $B$ its commitment list, and its challenge $c=H_{2}(R,Y,m)$ (ePrint 2020/852, Figure 3, in multiplicative notation with $R=\prod_{i}D_{i}E_{i}^{\rho_{i}}$ ) differ as follows: the specified binding-factor input adds the group key and pre-hashes the message and the encoded list; the challenge input is the paper’s, in the same order. For FROST(Pallas, BLAKE2b-512), $H_{2}$ is the RedPallas hash and $\mathsf{ser}_{\mathbb{G}}$ the star encoding, so $c$ is the challenge that RedPallas validation recomputes (Construction 6.1; ZIP 312, “Rationale”).

Construction 4.8 (Round Two).

Coordinator. It selects a signing set $I$ with $t\leq\lvert I\rvert\leq n$ ; takes, for each $i\in I$ , one commitment pair $(D_{i},E_{i})$ received from $P_{i}$ in Round One and not placed in any earlier request; forms the commitment list $L$ over $I$ (Definition 4.3); and sends $(m,L)$ , serialised componentwise, to each $P_{i}$ with $i\in I$ over an authenticated channel (Definition 2.10, type (a)).

Member $P_{i}$ , on receiving $(m,L)$ :

1.

it checks that $m$ is a message it is willing to sign; for spend authorisation this is the check of Definition 5.9;
2.

it checks that its identifier $i$ appears in $L$ with a commitment pair $(D_{i},E_{i})$ that it stores and has not used;
3.

it deserialises every commitment of $L$ with $\mathsf{deser}_{\mathbb{G}}$ , which fails on a non-canonical encoding and on the encoding of $\mathcal{O}$ ;
4.

it checks that the identifiers of $L$ are distinct, without which $\lambda_{I,i}$ is undefined, and in ascending order, as RFC 9591 requires of a commitment list (Section 4.3).

It aborts if any check fails. Otherwise it computes $\rho_{i}$ , $R$ and $c$ (Definition 4.7), aborting if $\rho_{i}$ or $c$ is undefined, and $\lambda_{I,i}$ (Definition 2.3), with $I$ the set of identifiers of $L$ ; sets the signature share

z_{i}:=d_{i}+e_{i}\rho_{i}+\lambda_{I,i}\,\mathit{sk}_{i}\,c\;\in\;\mathbb{F}_% {q};

deletes $(d_{i},e_{i})$ and $(D_{i},E_{i})$ ; and only then sends $\mathsf{ser}_{\mathbb{F}_{q}}(z_{i})$ to the Coordinator over an authenticated channel (Definition 2.10, type (a)).

The construction is RFC 9591, Section 5.2 (“Round Two - Signature Share Generation”). The Coordinator’s choice of at least $t$ and at most $n$ participants is required by Section 5. Each participant must validate the commitment list by deserialising each element, must abort if deserialisation fails, and must ensure that its identifier and commitments from Round One appear in the list (Section 5.2); applications that restrict the messages a participant signs perform further validation, which Section 7.7 (“Input Message Validation”) recommends so that participants do not act as signing oracles for arbitrary messages. The computation of $\lambda_{I,i}$ fails on an absent or repeated identifier (Section 4.2, “Polynomials”). The share equation is that of Section 5.2. After computing its share, each participant must delete the nonce and the corresponding commitment, and must not use the nonce as input more than once. The deletion is the step on which Proposition 4.14 rests.

4.4 Aggregation and share verification

Construction 4.9 (Aggregation).

The Coordinator holds $(m,L)$ and the group information $(\mathit{PK},(\mathit{PK}_{j})_{j=1}^{n})$ stored from key generation (Definition 2.5). The shares arrive over authenticated channels without confidentiality (Definition 2.10, type (a)). The Coordinator proceeds as follows.

1.

It deserialises each share with $\mathsf{deser}_{\mathbb{F}_{q}}$ and aborts if any deserialisation fails.
2.

It computes $\rho_{i}$ and $R_{i}$ for $i\in I$ , $R$ and $c$ (Definition 4.7), aborting if $\rho_{i}$ or $c$ is undefined.
3.

It sets $z:=\sum_{i\in I}z_{i}$ and outputs the signature $(R,z)$ , encoded $\mathsf{ser}_{\mathbb{G}}(R)\,\|\,\mathsf{ser}_{\mathbb{F}_{q}}(z)$ .

It should verify $(R,z)$ on $m$ under $\mathit{PK}$ by the single-party verification (Definition 4.1, part (e)) before publishing it, and should abort if the signature is invalid. It may check each share by the share equation

[z_{i}]B\;=\;R_{i}+[c\,\lambda_{I,i}]\,\mathit{PK}_{i},

in particular when the aggregate is invalid. The keys $\mathit{PK}$ and $\mathit{PK}_{i}$ in these checks are taken from the stored group information, never from the messages of the run.

The construction is RFC 9591, Section 5.3 (“Signature Share Aggregation”). The Coordinator must validate each share by deserialisation and must abort if validation fails; it should verify the signature under the group key before publishing or releasing it; if that verification fails, it may verify each share individually to identify and act on misbehaving participants; and the group key and the keys $\mathit{PK}_{i}$ used there must come from the stored group information. Section 5 requires an authenticated channel for identifying misbehaving participants and does not require confidentiality. The paper checks every share unconditionally before aggregating (ePrint 2020/852, Figure 3); the specified duties are the recommendation and the permission above, and this volume states those.

Proposition 4.10 (Identifiable abort).

Let the key material be valid (Definition 2.5), let the Coordinator be honest, and let $c$ be defined.

(i)

If the share of every member satisfies its share equation, then $[z]B=R+[c]\,\mathit{PK}$ , so the aggregate $(R,z)$ is accepted by the single-party verification on $m$ under $\mathit{PK}$ .
(ii)

The share of every member that follows Construction 4.8 satisfies its share equation.
(iii)

Hence, if the aggregate is not accepted, the share equation of some member fails, and that member deviated from the protocol; the authenticated channel identifies it as the sender of the share.

Proof.

(ii) For a member following the construction,

[z_{i}]B=[d_{i}]B+[\rho_{i}][e_{i}]B+[c\,\lambda_{I,i}][\mathit{sk}_{i}]B=R_{i% }+[c\,\lambda_{I,i}]\,\mathit{PK}_{i},

since $D_{i}=[d_{i}]B$ , $E_{i}=[e_{i}]B$ and, by validity, $\mathit{PK}_{i}=[\mathit{sk}_{i}]B$ .

(i) Let $f$ be the polynomial of degree at most $t-1$ that validity provides, with $f(j)=\mathit{sk}_{j}$ and $\mathit{PK}=[f(0)]B$ . Summing the share equations over $I$ gives

[z]B=\sum_{i\in I}R_{i}+\Bigl{[}c\sum_{i\in I}\lambda_{I,i}\,\mathit{sk}_{i}% \Bigr{]}B=R+[c\,f(0)]B=R+[c]\,\mathit{PK},

by Lemma 2.4 applied to $f$ . The challenge $c$ is the one the single-party verification recomputes from $(R,\mathit{PK},m)$ (Definition 4.7), so the verification accepts.

(iii) is the contrapositive of (i), with (ii). □

The mechanism for acting on an identified member is outside RFC 9591 (Section 5.4, “Identifiable Abort”). FROST provides no robustness (Sections 5.4 and 7): one member that withholds or corrupts its share prevents the signature, and a failed run is restarted from Round One with fresh nonces, since the consumed pairs are deleted.

4.5 Correctness of FROST signing

Theorem 4.11 (Correctness of FROST).

Let the key material be valid (Definition 2.5), as key generation by a dealer or by the distributed protocol outputs it (Propositions 3.3 and 3.8); let $I$ be a signing set and $m$ a message that every member of $I$ accepts; and let every party follow Constructions 4.4, 4.8 and 4.9. Then, outside the three cases below, the run outputs $(R,z)$ with

R=[r]B,\qquad z=r+c\,s,\qquad r:=\sum_{i\in I}(d_{i}+e_{i}\rho_{i}),

which the single-party verification accepts on $m$ under $\mathit{PK}$ . In the three cases the run aborts.

(1)

Zero nonce. Some $d_{i}$ or $e_{i}$ , $i\in I$ , is $0$ , so $D_{i}$ or $E_{i}$ is $\mathcal{O}$ . In a suite whose element serialisation is not total, Round One fails on it; in every suite the run aborts no later than check (3) of Round Two, since $\mathsf{deser}_{\mathbb{G}}$ rejects $\mathcal{O}$ . Under Assumption 4.2 the probability of this case is at most $2\lvert I\rvert(\delta+1/q)$ per run.
(2)

Identity group commitment. Only in a suite whose element serialisation is not total, as the generic serialisation of RFC 9591 is not: $R=\mathcal{O}$ , so $c$ is undefined. Under Assumption 4.2 the probability of this case, outside case (1), is at most $\delta+1/q$ per run.
(3)

Identity group key. Only in a suite whose element serialisation is not total: $s=0$ , so $\mathit{PK}=\mathcal{O}$ and $\rho_{i}$ and $c$ are undefined. For $s$ uniform in $\mathbb{F}_{q}$ , as under Assumption 3.1, its probability is $1/q$ per key generation.

A suite with a total element serialisation, such as FROST(Pallas, BLAKE2b-512), has only case (1).

Proof.

Write $r_{i}:=d_{i}+e_{i}\rho_{i}$ , so that $z_{i}=r_{i}+c\,\lambda_{I,i}\,\mathit{sk}_{i}$ . The nonce $r=\sum_{i\in I}r_{i}$ is additively shared by construction: each summand is formed locally, with no dealer and no interaction; and $R=\sum_{i\in I}R_{i}=\sum_{i\in I}[r_{i}]B=[r]B$ . The Lagrange coefficients turn the Shamir shares $\mathit{sk}_{i}=f(i)$ of $s=f(0)$ into additive shares $\lambda_{I,i}\,\mathit{sk}_{i}$ with sum $s$ , by Lemma 2.4, since $f$ has degree at most $t-1$ by validity. Hence

z=\sum_{i\in I}z_{i}=r+c\,s,\qquad[z]B=[r]B+[c][s]B=R+[c]\,\mathit{PK},

where $c=H_{2}(\mathsf{ser}_{\mathbb{G}}(R)\,\|\,\mathsf{ser}_{\mathbb{G}}(\mathit{PK% })\,\|\,m)$ is the challenge the verifier recomputes (Definition 4.7). Outside the three cases, every check of Round Two passes: $m$ is accepted, each member’s pair is stored and unused, every commitment lies in $\mathbb{G}^{*}$ and deserialises, the identifiers of $L$ are distinct and sorted, and $\rho_{i}$ and $c$ are defined. Every share deserialises, being an honest serialisation, so aggregation outputs $(R,z)$ .

(1) Each of the $2\lvert I\rvert$ nonces is an answer of $H_{3}$ , equal to $0$ with probability at most $1/q+\delta$ , because under a distribution within $\delta$ of uniform every value has probability at most $1/q+\delta$ (Math Guide, Theorem “Properties of statistical distance”, part (3)). Since $B$ generates a group of prime order, $[d]B=\mathcal{O}$ if and only if $d=0$ . The union bound gives $2\lvert I\rvert(1/q+\delta)$ .

(2) Outside case (1), fix $i\in I$ ; then $E_{i}\neq\mathcal{O}$ . Condition on all answers of $H_{3}$ , $H_{4}$ and $H_{5}$ , and on the answers of $H_{1}$ at every input other than that of $\rho_{i}$ . Then $R=\mathcal{O}$ if and only if $[\rho_{i}]E_{i}$ equals the element $-D_{i}-\sum_{j\in I\setminus\{i\}}R_{j}$ , which is fixed; since $E_{i}$ generates $\mathbb{G}$ , this holds for exactly one value of $\rho_{i}$ . The binding factor $\rho_{i}$ is the answer of $H_{1}$ at an input with suffix $\mathsf{ser}_{\mathbb{F}_{q}}(i)$ , distinct from the inputs of the other members, whose suffixes differ; so it takes that value with probability at most $1/q+\delta$ .

(3) Since $B$ generates a group of prime order, $\mathit{PK}=[s]B=\mathcal{O}$ if and only if $s=0$ , and $\mathsf{ser}_{\mathbb{G}}(\mathit{PK})$ , an input of every $\rho_{i}$ and of $c$ , is then undefined. A uniform $s\in\mathbb{F}_{q}$ is $0$ with probability $1/q$ . □

For FROST(Pallas, BLAKE2b-512), with the $\delta$ of Proposition 6.2, the bound of case (1) is below $2^{-251.9}$ for $\lvert I\rvert=2$ and below $2^{-251.3}$ for $\lvert I\rvert=3$ . In a suite with the parameters $q=p_{\mathsf{Vesta}}$ and that $\delta$ but a serialisation that is not total, the bound of case (2) would be below $2^{-253.9}$ .

The output of a threshold run is a single-party Schnorr signature under the group key. It carries no threshold marker: a verifier applies to it, with $(\mathit{PK},m)$ alone and no knowledge of $t$ , $n$ or $I$ , the verification it applies to a signature of one signer. RFC 9591 states this in Section 5, under which signatures can be verified as if produced by a single signer holding $s$ , and in Section 6, under which the verification instructions of each suite are equivalent to those for a single participant; Appendix B gives that verification.

Example 4.12 (A two-of-three signing run).

Every number below is output by the volume’s toy script; none is computed by hand. The group is the curve $y^{2}=x^{3}+11$ over $\mathbb{F}_{1009}$ , whose group of points has prime order $q=967$ , with generator $B=(1,298)$ . A point $(x,y)$ is serialised as the two-byte little-endian integer $x+2^{15}(y\bmod 2)$ , and $\mathcal{O}$ as zero, the analogue of the star encoding; a scalar is serialised as a two-byte little-endian integer. The hashes are BLAKE2b-512 under the personalisations that FROST(Pallas, BLAKE2b-512) assigns to $H_{1}$ to $H_{5}$ (Construction 6.1), the scalar-valued ones read as little-endian integers and reduced modulo $967$ . The $32$ fresh bytes of each nonce are fixed strings, so that the run is reproducible; the example therefore does not follow the sampling rule of Construction 4.4.

Key material. A dealer with $t=2$ , $n=3$ uses $f(X)=321+778X$ , so $s=321$ and

\mathit{sk}_{1}=132,\quad\mathit{sk}_{2}=910,\quad\mathit{sk}_{3}=721.

The coefficient commitments are $A_{0}=(526,125)$ and $A_{1}=(433,783)$ , and by Lemma 2.6 the group information is $\mathit{PK}=A_{0}$ and $\mathit{PK}_{j}=A_{0}+[j]A_{1}$ :

\mathit{PK}_{1}=(963,797),\quad\mathit{PK}_{2}=(587,458),\quad\mathit{PK}_{3}=% (30,509),

each equal to $[\mathit{sk}_{j}]B$ .

Round One. Members $1$ and $3$ draw

	$\displaystyle d_{1}$	$\displaystyle=155,$	$\displaystyle e_{1}$	$\displaystyle=457,$	$\displaystyle D_{1}$	$\displaystyle=(942,518),$	$\displaystyle E_{1}$	$\displaystyle=(309,697),$
	$\displaystyle d_{3}$	$\displaystyle=464,$	$\displaystyle e_{3}$	$\displaystyle=724,$	$\displaystyle D_{3}$	$\displaystyle=(958,797),$	$\displaystyle E_{3}$	$\displaystyle=(582,220).$

Round Two. The signing set is $I=\{1,3\}$ , with

\lambda_{I,1}=3\cdot(3-1)^{-1}=3/2=485,\qquad\lambda_{I,3}=1\cdot(1-3)^{-1}=-1% /2=483

modulo $967$ . Then $\lambda_{I,1}+\lambda_{I,3}=1$ and $\lambda_{I,1}\,\mathit{sk}_{1}+\lambda_{I,3}\,\mathit{sk}_{3}=321=s$ , as Lemma 2.4 requires with $f=1$ and with the sharing polynomial. For the message $m$ equal to the ASCII string toy message, the binding factors are $\rho_{1}=869$ and $\rho_{3}=285$ , the group commitment is $R=(972,62)$ and the challenge is $c=628$ . The shares are $z_{1}=419$ and $z_{3}=717$ , and each satisfies its share equation $[z_{i}]B=D_{i}+[\rho_{i}]E_{i}+[c\,\lambda_{I,i}]\,\mathit{PK}_{i}$ .

Aggregation. The aggregate is $z=169$ , and $[z]B=R+[c]\,\mathit{PK}$ holds. The toy group gives no security; the example checks the algebra only.

4.6 Single use of nonces

Lemma 4.13 (Reuse of a nonce pair exposes the share).

Let member $P_{i}$ answer $k$ Round Two requests, $j=1,\dots,k$ , with one nonce pair $(d,e)$ and share $\mathit{sk}_{i}$ . Its responses are

z_{j}=d+e\,\rho_{j}+\mu_{j}\,\mathit{sk}_{i},\qquad\mu_{j}:=\lambda_{I_{j},i}% \,c_{j},

where $\rho_{j}$ , $c_{j}$ and $I_{j}$ are the binding factor of $i$ , the challenge and the signing set of request $j$ , all computable from public data. Each response is affine in the unknown $(d,e,\mathit{sk}_{i})\in\mathbb{F}_{q}^{3}$ with coefficient vector $v_{j}:=(1,\rho_{j},\mu_{j})$ . Say that $\mathit{sk}_{i}$ is determined by $(z_{j},v_{j})_{j\leq k}$ if every $x\in\mathbb{F}_{q}^{3}$ with $v_{j}\cdot x=z_{j}$ for all $j$ has third coordinate $\mathit{sk}_{i}$ . The following are equivalent:

(a)

$\mathit{sk}_{i}$ is determined by $(z_{j},v_{j})_{j\leq k}$ ;
(b)

$(0,0,1)$ lies in the span of $v_{1},\dots,v_{k}$ (Math Guide, §“Linear combinations, span, and linear independence”, Definition “Linear combination and span”);
(c)

the points $(\rho_{j},\mu_{j})$ do not all lie on one line $\mu=\alpha+\beta\rho$ with $\alpha,\beta\in\mathbb{F}_{q}$ .

In particular, three responses with linearly independent coefficient vectors determine $\mathit{sk}_{i}$ ; two responses with distinct binding factors never do, and every value of $\mathit{sk}_{i}$ is then consistent with them; and two responses with equal binding factors and $\mu_{1}\neq\mu_{2}$ determine

\mathit{sk}_{i}=(z_{1}-z_{2})/(\mu_{1}-\mu_{2}).

Proof.

(b) implies (a): if $(0,0,1)=\sum_{j}a_{j}v_{j}$ , then every consistent $x$ has third coordinate $\sum_{j}a_{j}(v_{j}\cdot x)=\sum_{j}a_{j}z_{j}$ , one value, which the true unknown attains.

(a) implies (c): suppose every point lies on $\mu=\alpha+\beta\rho$ , and put $u:=(\alpha,\beta,-1)$ . Then $v_{j}\cdot u=\alpha+\beta\rho_{j}-\mu_{j}=0$ for every $j$ , so $(d,e,\mathit{sk}_{i})+\gamma u$ is consistent for every $\gamma\in\mathbb{F}_{q}$ , and its third coordinate $\mathit{sk}_{i}-\gamma$ takes every value; $\mathit{sk}_{i}$ is not determined.

(c) implies (b): if two points have equal $\rho$ and distinct $\mu$ , then $v_{1}-v_{2}$ (for those two) is a nonzero multiple of $(0,0,1)$ . Otherwise distinct points have distinct $\rho$ . Two points with distinct $\rho$ lie on a line $\mu=\alpha+\beta\rho$ , so (c) forces at least three distinct points, not all on one such line; no vertical line contains them either, since their $\rho$ are distinct. Hence some three of them are not collinear, their vectors $(1,\rho,\mu)$ are linearly independent, and they span $\mathbb{F}_{q}^{3}$ , which contains $(0,0,1)$ .

The particular cases follow: independent vectors span $\mathbb{F}_{q}^{3}$ ; two points with distinct $\rho$ lie on a line $\mu=\alpha+\beta\rho$ , and the proof of (a) implies (c) shows every value of $\mathit{sk}_{i}$ consistent; and with $\rho_{1}=\rho_{2}$ , $z_{1}-z_{2}=(\mu_{1}-\mu_{2})\,\mathit{sk}_{i}$ . □

The last case is the Crypto Guide’s Proposition “Nonce reuse is fatal” (§“Security in the random oracle model and the forking lemma”) applied to the effective nonce $d+e\rho$ . Whoever sees the shares and the public data can compute $\mathit{sk}_{i}$ in the determined cases, since the shares travel without confidentiality (Definition 2.10, type (a)). RFC 9591 states the risk (Sections 1 and 7.3) and forbids the reuse (Section 5.2).

In the toy group of Example 4.12, member $1$ answers three requests on the message toy message over $I=\{1,3\}$ with its pair $(d,e)=(155,457)$ , the requests differing only in the commitments of member $3$ . The triples $(\rho_{j},\mu_{j},z_{j})$ are $(682,413,819)$ , $(403,331,773)$ and $(947,46,955)$ . The determinant of the three coefficient vectors is $347\neq 0$ , and solving the system gives $\mathit{sk}_{1}=132$ . From the first two responses alone, the value $133$ with $(d,e)=(802,325)$ is also consistent, so $\mathit{sk}_{1}$ is not determined.

Proposition 4.14 (Replayed commitments).

A Coordinator that places in a Round Two request a commitment pair of member $P_{i}$ that $P_{i}$ has already used to answer a request obtains no response from $P_{i}$ , unless $P_{i}$ still stores a second copy of that pair from another execution of Round One, an event whose probability over $N$ executions is at most $\binom{N}{2}(2^{-255}+1/q+\delta)^{2}$ (Lemma 4.6). Outside that event a replay denies service only, and yields no second response under one nonce pair, the hypothesis of Lemma 4.13.

Proof.

A member responds only for a pair that it stores and has not used, by check (2) of Construction 4.8, and it deletes a pair when it answers with it. Outside that event no second copy of the pair is stored, so a used pair is no longer stored, check (2) fails and the member aborts. □

The Coordinator may in addition track, per group key, the commitments already used (RFC 9591, Section 7.3).