IX FROST Guide: Threshold RedPallas: FROST and its Zcash integration surfaces 1 Introduction 3 Key generation

2 Threshold Schnorr signatures

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.

2.1 Participants, identifiers and signing sets

Definition 2.1 (Threshold parameters and signing sets).

Let $\mathbb{G}$ be a group of prime order $q$ with generator $B$ and scalar field $\mathbb{F}_{q}$ (§1.3). Threshold parameters are integers $t, n$ with

1\leq t\leq n<q.

There are $n$ participants $P_{1},\dots,P_{n}$ . The identifier of $P_{i}$ is $i\in\{1,\dots,n\}$ , read as an element of $\mathbb{F}_{q}$ ; identifiers are distinct and nonzero in $\mathbb{F}_{q}$ because $n<q$ . A signing set is a set $I\subseteq\{1,\dots,n\}$ with $t\leq\lvert I\rvert\leq n$ . In the notation of RFC 9591 (Table 1), $t$ is $\mathrm{MIN\_PARTICIPANTS}$ , $n$ is $\mathrm{MAX\_PARTICIPANTS}$ and $\lvert I\rvert$ is $\mathrm{NUM\_PARTICIPANTS}$ .

The constraints are those of RFC 9591, Section 5 (“Two-Round FROST Signing Protocol”): each identifier is a nonzero scalar in $[1,\mathrm{MAX\_PARTICIPANTS}]$ , distinct from every other; $\mathrm{MAX\_PARTICIPANTS}$ is less than the group order; and $\mathrm{MIN\_PARTICIPANTS}\leq\mathrm{NUM\_PARTICIPANTS}\leq\mathrm{MAX\_PARTICIPANTS}$ . The dealer of RFC 9591, Appendix C (“Trusted Dealer Key Generation”), shares at the identifiers $1,\dots,n$ . Every statement below that uses only interpolation holds verbatim for any distinct nonzero identifiers; the identifiers $1,\dots,n$ are the ones RFC 9591 requires.

Remark 2.2 (Shamir sharing).

Shamir sharing is cited, not re-derived: Crypto Guide, §“Secret sharing”, Construction “Shamir $t$ -of- $n$ secret sharing”. Its parameters $1\leq t\leq n<q$ and identifiers $1,\dots,n$ are those of Definition 2.1; its share symbol $s_{i}$ is this volume’s $\mathit{sk}_{i}$ , and the generator $G$ of the Crypto Guide’s Construction “Feldman verifiable secret sharing” is $B$ . Any $t$ shares determine the sharing polynomial and its constant term (Lemma 2.4 gives this for every signing set). Fewer than $t$ shares are jointly uniform whatever the secret (Crypto Guide, Theorem “Perfect secrecy below the threshold”). That theorem concerns the shares alone. For key material shared by a dealer, once the coefficient commitments of §2.2 are published, the point $[s]B$ is public and secrecy below the threshold is computational: the view of $t-1$ participants is computable from $[s]B$ and $t-1$ uniform scalars. Since $[s]B$ is the group key, which is published in any case, nothing further escapes (Crypto Guide, Remark “The leak, and where it is harmless”). Distributed key generation is treated in §7.3.

Definition 2.3 (Lagrange coefficients of a signing set).

Let $I$ be a signing set and $i\in I$ . The Lagrange coefficient of $i$ in $I$ is

\lambda_{I,i}\;:=\;\prod_{j\in I,\;j\neq i}\frac{j}{j-i}\;\in\;\mathbb{F}_{q},

whose denominators are nonzero because identifiers are distinct. For the Lagrange basis polynomial $\ell_{i}(X)=\prod_{j\in I,\,j\neq i}(X-j)/(i-j)$ of the nodes $I$ (Math Guide, Theorem “Lagrange interpolation”), $\lambda_{I,i}=\ell_{i}(0)$ , since $(0-j)/(i-j)=j/(j-i)$ ; it is the reconstruction weight of the Crypto Guide’s Construction “Shamir $t$ -of- $n$ secret sharing”. The specified computation takes the list of identifiers of $I$ and the identifier $i$ , and fails with the error “invalid parameters” if $i$ is absent from the list or some identifier occurs in it more than once (RFC 9591, Section 4.2, “Polynomials”).

Lemma 2.4 (Recombination over a signing set).

Let $I$ be a signing set. For every $f\in\mathbb{F}_{q}[X]$ with $\deg f\leq t-1$ ,

\sum_{i\in I}\lambda_{I,i}\,f(i)\;=\;f(0).

In particular $\sum_{i\in I}\lambda_{I,i}=1$ . The statement and its proof hold verbatim for any finite set $I$ of distinct nonzero elements of $\mathbb{F}_{q}$ with $\lvert I\rvert\geq\deg f+1$ , the coefficients being defined by the same product.

Proof.

Put $d:=\lvert I\rvert-1$ , so $d\geq t-1\geq\deg f$ . By Math Guide, Theorem “Lagrange interpolation”, with nodes $I$ and targets $f(i)$ , the polynomial $g:=\sum_{i\in I}f(i)\,\ell_{i}$ has degree at most $d$ and satisfies $g(i)=f(i)$ for every $i\in I$ , that is at $d+1$ distinct points. The polynomial $f$ also has degree at most $d$ , so $g=f$ by Math Guide, Corollary “Few points determine a low-degree polynomial”. Evaluating at $0$ and using $\ell_{i}(0)=\lambda_{I,i}$ (Definition 2.3) gives the identity. The constant polynomial $f=1$ has degree $0\leq t-1$ , because $t\geq 1$ , and gives the sum one. □

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 $\sum_{i\in I}\lambda_{I,i}=1$ and refers to an external note for its proof; ePrint 2024/436, Section 5, justifies it in one line as the interpolation of the constant polynomial $1$ .

The coefficients $\lambda_{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 $\mathrm{MIN\_PARTICIPANTS}$ in number (RFC 9591, Section 5).

2.2 Key material and group information

Definition 2.5 (Threshold key material).

Let $(t,n)$ be threshold parameters. Threshold key material consists of:

1.

a sharing polynomial $f(X)=\sum_{k=0}^{t-1}a_{k}X^{k}\in\mathbb{F}_{q}[X]$ with $f(0)=a_{0}=s$ , the signing key;
2.

for each identifier $j$ , the secret share $(j,\mathit{sk}_{j})$ with $\mathit{sk}_{j}=f(j)$ , held by $P_{j}$ alone;
3.

the coefficient commitments $A_{k}:=[a_{k}]B$ for $k=0,\dots,t-1$ ;
4.

the group information $(\mathit{PK},(\mathit{PK}_{j})_{j=1}^{n})$ , with group key $\mathit{PK}:=[s]B$ and verification shares $\mathit{PK}_{j}:=[\mathit{sk}_{j}]B$ , held by every party, the Coordinator included.

Shares $(\mathit{sk}_{j})_{j=1}^{n}\in\mathbb{F}_{q}^{n}$ and group information $(\mathit{PK},(\mathit{PK}_{j})_{j=1}^{n})\in\mathbb{G}^{n+1}$ are valid key material if some $f\in\mathbb{F}_{q}[X]$ with $\deg f\leq t-1$ has $f(j)=\mathit{sk}_{j}$ for every $j\in\{1,\dots,n\}$ , $\mathit{PK}=[f(0)]B$ and $\mathit{PK}_{j}=[\mathit{sk}_{j}]B$ for every $j$ . Such $f$ is unique, since $n\geq t$ (Math Guide, Corollary “Few points determine a low-degree polynomial”). No party is given $s$ or $f$ ; the definition names them. Valid key material is the output of both key generations (§3) and the input of signing.

The components are those of RFC 9591, Section 5: each participant is configured with its identifier, the share $\mathit{sk}_{i}=f(i)$ and $\mathit{PK}_{i}=[\mathit{sk}_{i}]B$ ; the group information consists of $\mathit{PK}$ and $\mathit{PK}_{i}$ for each $i$ in $[1,\mathrm{MAX\_PARTICIPANTS}]$ .

Lemma 2.6 (Group information from coefficient commitments).

Let $f=\sum_{k=0}^{t-1}a_{k}X^{k}$ and $A_{k}=[a_{k}]B$ .

(i)

The group key is $\mathit{PK}=[f(0)]B=A_{0}$ , and for every identifier $j$

$\mathit{PK}_{j}\;=\;[f(j)]B\;=\;\sum_{k=0}^{t-1}[j^{k}]A_{k}.$

Every party holding $(A_{0},\dots,A_{t-1})$ therefore computes the group information from the commitments alone.
(ii)

Let $(A_{0},\dots,A_{t-1})\in\mathbb{G}^{t}$ , however chosen, and let $\mathit{sk}_{1},\dots,\mathit{sk}_{n}\in\mathbb{F}_{q}$ satisfy $[\mathit{sk}_{j}]B=\sum_{k=0}^{t-1}[j^{k}]A_{k}$ for every $j\in\{1,\dots,n\}$ . Then $(\mathit{sk}_{j})_{j=1}^{n}$ , with the group information computed by (i), is valid key material (Definition 2.5) for the unique polynomial $f^{*}=\sum_{k}a^{*}_{k}X^{k}$ with $[a^{*}_{k}]B=A_{k}$ .

Proof.

Part (i) is the identity displayed in Crypto Guide, Construction “Feldman verifiable secret sharing”, where it follows from the homomorphism $a\mapsto[a]B$ ; that construction’s $G$ and $\Phi_{k}$ are this volume’s $B$ and $A_{k}$ . For (ii), by Crypto Guide, Proposition “What the Feldman check certifies”, the vector $(A_{0},\dots,A_{t-1})$ determines a unique polynomial $f^{*}$ of degree at most $t-1$ , and each passing check gives $\mathit{sk}_{j}=f^{*}(j)$ . Then $A_{0}=[f^{*}(0)]B$ and $\sum_{k}[j^{k}]A_{k}=[\mathit{sk}_{j}]B$ , which are the conditions of Definition 2.5. □

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.

2.3 Two-round threshold signature schemes

Remark 2.7 (Prerequisites).

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 $\mathit{PK}=[s]B$ , a signature on a message $m$ is

r\xleftarrow{\$}\mathbb{F}_{q},\quad R=[r]B,\quad c=H(R\,\|\,\mathit{PK}\,\|\,% m),\quad z=r+cs,\quad\sigma=(R,z),

and verification accepts $(R,z)$ if and only if

[z]B\;=\;R+[c]\,\mathit{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.

Definition 2.8 (Two-round threshold signature scheme with a Coordinator).

Let $(t,n)$ be threshold parameters (Definition 2.1). A two-round threshold signature scheme with a Coordinator is run by the participants $P_{1},\dots,P_{n}$ and one Coordinator: a role, which a participant may also play, that uses no share of the signing key and no nonce, and that chooses the signing set, relays messages, aggregates and publishes the signature. It consists of:

1.

Key generation, a dealer algorithm or a protocol, which outputs valid key material (Definition 2.5): $\mathit{sk}_{j}$ to $P_{j}$ , and the group information to every party.
2.

Round One, run by each $P_{i}$ independently of any message and of any signing set, which outputs a public commitment $\mathit{com}_{i}$ , sent to the Coordinator, and a secret state $\mathit{st}_{i}$ , which $P_{i}$ keeps and uses in at most one Round Two.
3.

Round Two. The Coordinator chooses a signing set $I$ and a message $m$ , and sends the request $(m,(\mathit{com}_{j})_{j\in I})$ to each $P_{i}$ with $i\in I$ . Participant $P_{i}$ either returns a signature share $z_{i}$ , computed from $\mathit{sk}_{i}$ , $\mathit{st}_{i}$ , the request and the group information, or aborts; in both cases it deletes $\mathit{st}_{i}$ .
4.

Aggregation, by which the Coordinator maps $m$ , the commitment list $(\mathit{com}_{j})_{j\in I}$ and the shares $(z_{j})_{j\in I}$ to a signature $\sigma$ or to $\bot$ .
5.

Verification, the single-party Schnorr verification of a signature on $m$ under the group key $\mathit{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 $\bot$ or a signature that verification accepts under $\mathit{PK}$ , and outputs $\bot$ 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 $\bot$ for FROST. Unforgeability notions are defined in §7, before any use.

Remark 2.9 (Scope of the syntax).

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.

The parties compute $(R,z)$ jointly, and no step computes $s$ or $r$ . Round Two binds each share to the message and the whole commitment list (Construction 4.8); unforgeability under concurrent runs is Theorem 7.9, under its assumptions (Remark 7.10).

2.4 Channels and corruption

Definition 2.10 (Channels).

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.

(a)

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.
(b)

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.
(c)

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.
(d)

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.

Definition 2.11 (Static corruption).

Before key generation the adversary fixes a set $C\subseteq\{1,\dots,n\}$ with $\lvert C\rvert\leq t-1$ . It receives the entire state of each $P_{j}$ with $j\in C$ throughout, and chooses their messages. It may in addition control the Coordinator, which holds no share of the signing key and no nonce; in the re-randomised variant it also holds the randomiser and the transaction data (Definition 5.14). It observes and schedules the network, subject to the guarantees of Definition 2.10. The set $C$ never changes, and every other participant follows the protocol.

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 $\mathrm{MIN\_PARTICIPANTS}-1$ participants may be corrupted and robustness and metadata protection are not goals, and of ZIP 312, “Threat Model”.