FROST Guide Threshold RedPallas: FROST and its Zcash integration surfaces 2 Threshold Schnorr signatures 4 Signing and aggregation

3 Key generation

This section states the status of key generation in RFC 9591 and ZIP 312 and the two protocols that output the threshold key material of Definition 2.5: key generation by a trusted dealer and distributed key generation. Each is proved to output valid key material and is classified by Definition 1.1.

3.1 Trusted-dealer key generation

RFC 9591 places key generation out of its scope and, for completeness, specifies key generation by a trusted dealer in Appendix C (“Trusted Dealer Key Generation”); Section 1 (“Introduction”) says so. Its Section 5 (“Two-Round FROST Signing Protocol”) names the two mechanisms by which the key material of Definition 2.5 may be configured, a trusted dealer and a distributed key generation protocol, and specifies neither beyond that appendix. ZIP 312 specifies no key generation (“Non-requirements”). Its “Key Generation” requires key generation to be consistent with FROST, referring to the dealer appendix of RFC 9591 for guidance, and names the spend authorising key $\mathsf{ask}$ as the key to be shared. It records that $\mathsf{ask}$ is usually derived from the spending key $\mathsf{sk}$ but need not be; that not deriving it permits distributed key generation, since the key so generated is unpredictable; and that not deriving it prevents recovery of the secret from a seed phrase, which the ZIP notes may be desirable for FROST. The security analysis of Bellare, Tessaro and Zhu (ePrint 2022/833, in its current revision, whose preliminary version is part of the analysis RFC 9591 cites) models key generation as an algorithm run by a trusted party. Two protocols output key material: the dealer of RFC 9591, Appendix C, in this subsection, and the distributed key generation of ePrint 2020/852, Figure 1, in §3.2.

Assumption 3.1 (Honest dealer).

The dealer runs Construction 3.2 as written:

1.

it samples $s$ and the coefficients $a_{1},\dots,a_{t-1}$ uniformly and independently from its own randomness;
2.

it reveals $s$ , the coefficients and the shares only as the construction prescribes, the share of $P_{j}$ to $P_{j}$ alone;
3.

it deletes $s$ , the coefficients and the shares once the shares are distributed.

The adversary of Definition 2.11 does not control the dealer and never obtains its state.

The three clauses are the trust requirements of RFC 9591, Appendix C: the dealer is trusted to generate good randomness, to delete secret values after distributing the shares, and to keep secret values confidential; the appendix further requires that the dealer delete the secret key and the secret key shares upon completion.

Construction 3.2 (Dealer sharing of a threshold key).

Let $(t,n)$ be threshold parameters with identifiers $1,\dots,n$ (Definition 2.1), over the group $\mathbb{G}$ of prime order $q$ with generator $B$ and scalar field $\mathbb{F}_{q}$ . The dealer proceeds as follows.

1.

It samples the signing key $s\xleftarrow{\$}\mathbb{F}_{q}$ uniformly and $a_{1},\dots,a_{t-1}\xleftarrow{\$}\mathbb{F}_{q}$ independently and uniformly.
2.

It sets $a_{0}:=s$ and

$f(X)\;:=\;\sum_{k=0}^{t-1}a_{k}X^{k}\;\in\;\mathbb{F}_{q}[X],$

a sharing of $s$ by Crypto Guide, Construction “Shamir $t$ -of- $n$ secret sharing”.
3.

For $j=1,\dots,n$ it sends the secret share $(j,\mathit{sk}_{j})$ , with $\mathit{sk}_{j}:=f(j)$ , to $P_{j}$ over a mutually authenticated confidential channel (Definition 2.10, type (c)).
4.

It sends the coefficient commitments

$A_{k}\;:=\;[a_{k}]B,\qquad k=0,\dots,t-1,$

to every party, the participants and the Coordinator, by consistent broadcast (Definition 2.10, type (d)).
5.

It deletes $s$ , the coefficients and the shares.

Participant $P_{j}$ aborts if its view of $(A_{0},\dots,A_{t-1})$ differs from that of another party, and aborts if

[\mathit{sk}_{j}]B\;\neq\;\sum_{k=0}^{t-1}[j^{k}]A_{k}.

Every party computes the group information

\mathit{PK}\;:=\;A_{0},\qquad\mathit{PK}_{i}\;:=\;\sum_{k=0}^{t-1}[i^{k}]A_{k}% \quad(i=1,\dots,n)

by Lemma 2.6; by this computation every party learns every verification share. Output: the share $(j,\mathit{sk}_{j})$ to $P_{j}$ , and $(\mathit{PK},\mathit{PK}_{1},\dots,\mathit{PK}_{n})$ to every party. The dealer knows $s$ . Class (Definition 1.1): specified.

The construction is that of RFC 9591, Appendix C, with its Appendices C.1 (“Shamir Secret Sharing”) and C.2 (“Verifiable Secret Sharing”). The secret is generated uniformly at random and must be derived from at least $\mathrm{Ns}$ bytes of entropy, $\mathrm{Ns}$ being the length of an encoded scalar; Appendix D (“Random Scalar Generation”) gives the generation of uniform scalars. The shares are the evaluations of $f$ at $1,\dots,n$ , the secret prepended to the coefficients, and an identifier is never $0$ (Appendix C.1). The commitment is the vector of the $[a_{k}]B$ ; a participant must abort if it does not hold the same view of it as the other participants, which a secure broadcast channel ensures (Appendix C), and must abort if its share fails the check, the failure being investigated out of band (Appendix C.2). The channel for shares is mutually authenticated and provides confidentiality and integrity (Appendix C). Consistent broadcast realises the first abort rule: under Definition 2.10, type (d), every honest recipient outputs the same vector or every honest recipient aborts.

Proposition 3.3 (Validity of dealt key material).

Let the commitments of Construction 3.2 travel by consistent broadcast (Definition 2.10, type (d)).

(i)

Under Assumption 3.1, if the broadcast does not abort, no honest participant aborts, and the shares $(j,\mathit{sk}_{j})$ with the group information $(\mathit{PK},\mathit{PK}_{1},\dots,\mathit{PK}_{n})$ are valid key material for $s$ (Definition 2.5), with $\mathit{PK}=[s]B$ .
(ii)

Without Assumption 3.1, the commitments determine a unique polynomial $f^{*}=\sum_{k}a^{*}_{k}X^{k}$ of degree at most $t-1$ with $[a^{*}_{k}]B=A_{k}$ for every $k$ ; a participant whose check passes holds $\mathit{sk}_{j}=f^{*}(j)$ ; and every honest party computes the same group information, that of $f^{*}$ . The shares that pass and the group information are thus consistent with the one polynomial $f^{*}$ , whose constant term $\log_{B}A_{0}$ the dealer chooses freely.
(iii)

Under Assumption 3.1, for every set $C$ of fewer than $t$ participants there is a randomised algorithm that, given $\mathit{PK}=[s]B$ alone, outputs a tuple distributed identically to the joint view of $C$ : its shares and the commitments. The commitments reveal $[s]B$ and nothing further to $C$ .

Proof.

(i) By steps (1) to (3), $\mathit{sk}_{j}=f(j)$ for the polynomial $f$ of degree at most $t-1$ with $f(0)=s$ . Each honest share passes its check by the identity $\sum_{k}[j^{k}]A_{k}=[f(j)]B$ displayed in Crypto Guide, Construction “Feldman verifiable secret sharing”, and consistent broadcast from an honest dealer that does not abort gives every honest party the dealer’s vector, so no honest participant aborts. Lemma 2.6, part (i), gives $\mathit{PK}=A_{0}=[f(0)]B=[s]B$ and $\mathit{PK}_{j}=[f(j)]B=[\mathit{sk}_{j}]B$ , which are the conditions of Definition 2.5.

(ii) Consistent broadcast gives every honest party the same vector $(A_{0},\dots,A_{t-1})$ , or every honest party aborts. By Crypto Guide, Proposition “What the Feldman check certifies”, that vector determines the unique $f^{*}$ with $a^{*}_{k}=\log_{B}A_{k}$ , a check passes if and only if $\mathit{sk}_{j}=f^{*}(j)$ , and nothing constrains $f^{*}(0)$ . Lemma 2.6, part (i), applied to $f^{*}$ , gives the common group information $\mathit{PK}=[f^{*}(0)]B$ and $\mathit{PK}_{j}=[f^{*}(j)]B$ .

(iii) Suppose first $\lvert C\rvert=t-1$ . By Crypto Guide, Theorem “Perfect secrecy below the threshold”, the shares $(\mathit{sk}_{i})_{i\in C}$ are jointly uniform on $\mathbb{F}_{q}^{t-1}$ whatever $s$ is. Given the shares, the points $[f(0)]B=\mathit{PK}$ and $[f(i)]B=[\mathit{sk}_{i}]B$ , $i\in C$ , are $t$ values of the map $x\mapsto[f(x)]B$ at distinct points; since each $A_{k}$ is a fixed $\mathbb{F}_{q}$ -linear combination of these values (interpolation in the exponent), the commitments are a function of $\mathit{PK}$ and the shares. The algorithm samples $t-1$ uniform scalars as the shares and computes the commitments so; this is the argument of Crypto Guide, Remark “The leak, and where it is harmless”. If $\lvert C\rvert<t-1$ , then, since $t\leq n$ , some set $C^{\prime}\supseteq C$ of $t-1$ participants exists; the view of $C$ is a projection of that of $C^{\prime}$ , and the algorithm for $C^{\prime}$ followed by the projection serves for $C$ . □

Remark 3.4 (Key material of an Orchard-protocol key).

For an Orchard-protocol key the shared secret is $\mathsf{ask}$ (ZIP 312, “Key Generation”). The output of Construction 3.2 then passes through Construction 6.7 in §6.3 and is completed by Construction 6.8. ZIP 312 also admits a dealer that shares an $\mathsf{ask}$ derived from a spending key; that $\mathsf{ask}$ is not sampled as in Assumption 3.1, clause (1), and §7.3 treats both cases.

3.2 Distributed key generation

Assumption 3.5 (The proof-of-knowledge hash).

The challenge hash

H_{\mathrm{dkg}}\colon\{1,\dots,n\}\times\{0,1\}^{*}\times\mathbb{G}\times% \mathbb{G}\;\to\;\mathbb{F}_{q}

of Construction 3.6, applied to an injective encoding of its input (identifier, context string, point, point), is modelled as a random oracle (Crypto Guide, §“The random oracle model”) independent of every other hash of the volume, in particular of the ciphersuite hashes of Assumption 4.2.

An instantiation achieves the independence by domain separation: a random oracle restricted to prefix-free tags yields independent random oracles (Crypto Guide, §“Domain separation and personalisation”, Proposition “Domain separation yields independent oracles”). No ZIP fixes $H_{\mathrm{dkg}}$ or the context string for the Pallas ciphersuite of ZIP 312: that ciphersuite defines the hashes $H_{1}$ to $H_{5}$ and $H_{R}$ only (“FROST(Pallas, BLAKE2b-512)”), and key generation is outside the ZIP’s scope (“Key Generation”). The volume therefore takes $H_{\mathrm{dkg}}$ as the named oracle of Assumption 3.5.

Construction 3.6 (Pedersen key generation with proofs of knowledge).

Let $(t,n)$ be threshold parameters (Definition 2.1) and $H_{\mathrm{dkg}}$ the hash of Assumption 3.5. Before Round One the participants agree, by means outside the construction, on a context string $\Phi\in\{0,1\}^{*}$ unique to the ceremony.

Round One, participant $P_{i}$ :

1.

It samples $a_{i,0},\dots,a_{i,t-1}\xleftarrow{\$}\mathbb{F}_{q}$ independently and uniformly and sets $f_{i}(X):=\sum_{k=0}^{t-1}a_{i,k}X^{k}$ .
2.

It proves knowledge of $a_{i,0}$ : it samples $\nu_{i}\xleftarrow{\$}\mathbb{F}_{q}$ and sets

$\displaystyle R_{i}:=[\nu_{i}]B,\qquad c_{i}:=H_{\mathrm{dkg}}\bigl{(}i,\Phi,[% a_{i,0}]B,R_{i}\bigr{)},$

$\displaystyle\mu_{i}:=\nu_{i}+a_{i,0}\,c_{i},\qquad\sigma_{i}:=(R_{i},\mu_{i}).$
3.

It computes $A_{i,k}:=[a_{i,k}]B$ for $k=0,\dots,t-1$ .
4.

It sends $(A_{i,0},\dots,A_{i,t-1},\sigma_{i})$ to every other party, the Coordinator included, by consistent broadcast (Definition 2.10, type (d)).
5.

For every $\ell\neq i$ it computes $c_{\ell}:=H_{\mathrm{dkg}}(\ell,\Phi,A_{\ell,0},R_{\ell})$ and aborts unless

$R_{\ell}\;=\;[\mu_{\ell}]B-[c_{\ell}]A_{\ell,0}.$

If every check passes, it deletes the proofs $\sigma_{\ell}$ .

Round Two, participant $P_{i}$ :

1.

It sends $f_{i}(\ell)$ to each $P_{\ell}$ , $\ell\neq i$ , over a mutually authenticated confidential channel (Definition 2.10, type (c)), keeps $f_{i}(i)$ , and deletes $f_{i}$ and the values sent.
2.

For every $\ell\neq i$ it aborts unless

$[f_{\ell}(i)]B\;=\;\sum_{k=0}^{t-1}[i^{k}]A_{\ell,k}.$
3.

It sets $\mathit{sk}_{i}:=\sum_{\ell=1}^{n}f_{\ell}(i)$ and deletes the $f_{\ell}(i)$ .

Group information. Every party sets $A_{k}:=\sum_{\ell=1}^{n}A_{\ell,k}$ for $k=0,\dots,t-1$ and computes

\mathit{PK}\;:=\;A_{0},\qquad\mathit{PK}_{j}\;:=\;\sum_{k=0}^{t-1}[j^{k}]A_{k}% \quad(j=1,\dots,n)

by Lemma 2.6.

Output: $(i,\mathit{sk}_{i})$ to $P_{i}$ , and $(\mathit{PK},\mathit{PK}_{1},\dots,\mathit{PK}_{n})$ to every party. A failed check leads to abort only; its cause is investigated out of band.

The construction is that of ePrint 2020/852, Figure 1, in additive notation: the paper’s $g$ , $\phi_{i,k}$ , $k$ , $s_{i}$ , $Y_{i}$ and $Y$ are $B$ , $A_{i,k}$ , $\nu_{i}$ , $\mathit{sk}_{i}$ , $\mathit{PK}_{i}$ and $\mathit{PK}$ . The paper’s Section 5.1 describes it as Pedersen’s protocol, $n$ parallel runs of Crypto Guide, Construction “Feldman verifiable secret sharing”, one with each participant as dealer, each share being the sum of the $n$ shares received. Round One, step (2), is the Fiat–Shamir transform of Crypto Guide, Construction “Schnorr identification” (§“The Schnorr identification protocol”; §“The Fiat–Shamir transform: from interactive to non-interactive”), with statement $A_{i,0}$ , witness $a_{i,0}$ , and the prover’s identifier and $\Phi$ bound into the challenge; the verification equation of step (5) is that of the identification protocol rearranged. ePrint 2020/852, Figure 1, binds the context string into the challenge to prevent replay of proofs across ceremonies, a design claim that no cited source proves (Remark 3.9). The last part of Figure 1 computes every verification share from the broadcast commitments, which is how parties other than $P_{j}$ learn $\mathit{PK}_{j}$ .

Consistent broadcast of Round One is a hypothesis of the construction: ePrint 2020/852, Section 5.1, assumes that participants hold a consistent view of the commitments and does not provide it. A participant that sent different commitment vectors to different parties would lead them to compute different group information: different verification shares, and different group keys when the constant terms $A_{\ell,0}$ differ.

Lemma 3.7 (Sum of dealt sharings).

Let $f_{1},\dots,f_{n}\in\mathbb{F}_{q}[X]$ have degree at most $t-1$ , with coefficients $a_{\ell,k}$ and coefficient commitments $A_{\ell,k}=[a_{\ell,k}]B$ . Then $f:=\sum_{\ell=1}^{n}f_{\ell}$ has degree at most $t-1$ , constant term $f(0)=\sum_{\ell}a_{\ell,0}$ , and coefficient commitments

\Bigl{[}\sum_{\ell=1}^{n}a_{\ell,k}\Bigr{]}B\;=\;\sum_{\ell=1}^{n}A_{\ell,k},% \qquad k=0,\dots,t-1;

and $f(j)=\sum_{\ell}f_{\ell}(j)$ for every $j\in\mathbb{F}_{q}$ .

Proof.

Polynomial addition adds coefficients and does not raise the degree, so the coefficient of $X^{k}$ in $f$ is $\sum_{\ell}a_{\ell,k}$ , zero for $k\geq t$ . Evaluation at a point is additive in the polynomial. The map $a\mapsto[a]B$ is a group homomorphism $\mathbb{F}_{q}\to\mathbb{G}$ , which gives the commitments. □

Proposition 3.8 (Validity of distributed key material).

Consider an execution of Construction 3.6 without abort in which the Round One messages travel by consistent broadcast. For each $\ell$ let $f^{*}_{\ell}$ be the unique polynomial of degree at most $t-1$ whose coefficient commitments are $A_{\ell,0},\dots,A_{\ell,t-1}$ , let $f^{*}:=\sum_{\ell}f^{*}_{\ell}$ , and let $\mathit{sk}_{j}:=f^{*}(j)$ for every identifier $j$ . Then:

(i)

every honest participant $P_{i}$ outputs $\mathit{sk}_{i}=f^{*}(i)$ ;
(ii)

every honest party computes the same group information, $\mathit{PK}=[f^{*}(0)]B$ and $\mathit{PK}_{j}=[f^{*}(j)]B$ ;
(iii)

the shares $\mathit{sk}_{j}$ with this group information are valid key material (Definition 2.5) for the signing key

$s\;=\;f^{*}(0)\;=\;\sum_{\ell=1}^{n}\log_{B}A_{\ell,0}.$

If every participant is honest, $f^{*}_{\ell}=f_{\ell}$ for every $\ell$ .

Proof.

The polynomials $f^{*}_{\ell}$ exist and are unique by Crypto Guide, Proposition “What the Feldman check certifies”. An honest $P_{i}$ broadcasts the commitments of its own $f_{i}$ , so $f_{i}=f^{*}_{i}$ and its kept value is $f_{i}(i)=f^{*}_{i}(i)$ . Each received $f_{\ell}(i)$ , $\ell\neq i$ , passed the check of Round Two, step (2), so equals $f^{*}_{\ell}(i)$ by the same proposition. Hence $\mathit{sk}_{i}=\sum_{\ell}f^{*}_{\ell}(i)=f^{*}(i)$ by Lemma 3.7, which is (i). Consistent broadcast gives every honest party the same $A_{\ell,k}$ , hence the same $A_{k}=\sum_{\ell}A_{\ell,k}$ , which by Lemma 3.7 are the coefficient commitments of $f^{*}$ , of degree at most $t-1$ . Lemma 2.6, part (i), applied to $f^{*}$ gives $\mathit{PK}=[f^{*}(0)]B$ and $\mathit{PK}_{j}=[f^{*}(j)]B=[\mathit{sk}_{j}]B$ , which is (ii); with the shares $\mathit{sk}_{j}=f^{*}(j)$ these are the conditions of Definition 2.5, which is (iii), and $f^{*}(0)=\sum_{\ell}f^{*}_{\ell}(0)=\sum_{\ell}\log_{B}A_{\ell,0}$ . If every participant is honest, each broadcasts the commitments of its own polynomial, so $f^{*}_{\ell}=f_{\ell}$ . □

Remark 3.9 (Rogue keys and robustness).

The statements of this remark are design claims of ePrint 2020/852; none is a theorem. The proofs of knowledge of Round One, step (2), are the change from Pedersen’s protocol: the paper adds them against rogue-key attacks, in which a participant chooses its commitment as a function of the others’ commitments to bias the group key, in the setting $t\geq n/2$ (Section 5.1). No source cited in this volume proves Construction 3.6 secure, or proves FROST as RFC 9591 specifies it unforgeable with it; §7.3 states what is known (Remark 7.13). The protocol is not robust: any failed proof or share check aborts the whole execution and its cause is investigated out of band (Figure 1; Section 3), so one participant can prevent key generation.

Construction 3.6 is designed but unspecified for Zcash (Definition 1.1). The protocol is published (ePrint 2020/852, Figure 1), but no RFC or ZIP specifies a distributed key generation: RFC 9591 places key generation out of scope (Section 1), and ZIP 312 specifies none (“Key Generation”). ZIP 2005 (Proposed), “Usage with FROST”, names the FROST distributed key generation protocol without a specification behind the reference; the revision of ZIP 312 proposed in pull request 895 names a different key-generation protocol, so its adoption would not specify this one. Its Zcash instantiation, the hash $H_{\mathrm{dkg}}$ and the context string $\Phi$ , is fixed by no ZIP (Assumption 3.5).

	$\displaystyle R_{i}:=[\nu_{i}]B,\qquad c_{i}:=H_{\mathrm{dkg}}\bigl{(}i,\Phi,[% a_{i,0}]B,R_{i}\bigr{)},$
	$\displaystyle\mu_{i}:=\nu_{i}+a_{i,0}\,c_{i},\qquad\sigma_{i}:=(R_{i},\mu_{i}).$