7 Security

Algorithm ${𝒜}^{\prime }$ queries $\mathrm{𝖢𝗁𝖺𝗅}$ $\mathrm{\ell }+1$ times, obtaining $X_1,\mathrm{\dots },X_{\mathrm{\ell }+1}$, and runs $𝒜$ on them as $X_0,\mathrm{\dots },X_{\mathrm{\ell }}$. On a declaration $(\alpha ,{\beta }_0,\mathrm{\dots },{\beta }_{\mathrm{\ell }})$ it queries $\mathrm{𝖣𝖫𝗈𝗀}$ on $[\alpha ]B+{\sum }_i[{\beta }_i]X_i$ and returns the answer, which is $\alpha +{\sum }_i{\beta }_i{x}_i$, the value the AOMDL oracle returns. It outputs the output of $𝒜$. The view of $𝒜$ is that of the AOMDL game, the query counts agree, and ${𝒜}^{\prime }$ wins exactly when $𝒜$ wins. □

Game hops, with additive losses (Crypto Guide, §“Security as a game”, Remark “Game-hopping”).

Game $G_0$ is the RFC game.

Game $G_1$: every honest nonce is a uniform scalar. The $2q_s$ nonces are replaced one at a time, in the order in which they are drawn. At each hop Lemma 4.5 applies with the rest of the game as the observer: its queries to $H_3$ are the $q_h$ queries of $𝒜$ and at most $2q_s$ evaluations by honest servers, each at an input with a fresh $32$-byte prefix. Hence $|\mathrm{Pr}[G_0]-\mathrm{Pr}[G_1]|\le 2q_s(\delta +(q_h+2q_s)\cdot 2^{-256})$. Game $G_2$ aborts on a collision of $H_4$ or of $H_5$, or when a hash input contains an output value of $H_4$ or $H_5$ before the query that produces it. Each of the two oracles receives at most $Q$ queries, from $𝒜$ and one per answered request, at most $q_s$ of them. By Assumption 4.2 a collision of either has probability at most $Q^2\cdot 2^{-8N_{\mathrm{h}}}$ in total; each new answer equals one of at most $Q$ digest strings already present in inputs with probability at most $Q\cdot 2^{-8N_{\mathrm{h}}}$, which over $Q$ queries and both oracles gives $2Q^2\cdot 2^{-8N_{\mathrm{h}}}$.

Game $G_3$ answers $H_1$ and $H_2$ at distinct inputs by uniform scalars. Under Assumption 4.2 each answer is an independent sample within distance $\delta$ of uniform, and the distinct inputs number at most $q_h$ queries of $𝒜$, at most $n$ binding factors and one challenge per answered request, and one challenge of the final verification; replacing the answers one at a time costs $\left(q_h+(n+1)q_s+1\right)\delta$ (Math Guide, Theorem “Properties of statistical distance”).

In $G_3$, algorithm ${𝒜}^{\prime }$ plays the FROST1 game. It relays token queries. It simulates $H_3$, $H_4$ and $H_5$ lazily and records their queries. It answers an $H_1$ query ${\mathrm{𝗌𝖾𝗋}}_{𝔾}({\mathrm{𝑃𝐾}}^{\prime })\Vert u\Vert v\parallel {\mathrm{𝗌𝖾𝗋}}_{{𝔽}_q}(i)$ by $h_1(\mathrm{𝑣𝑘},\mathrm{𝑙𝑟},i)$ when ${\mathrm{𝑃𝐾}}^{\prime }=\mathrm{𝑃𝐾}$ and $u$, $v$ are recorded outputs of $H_4$ on $m$ and of $H_5$ on $\mathrm{𝖾𝗇𝖼}(L)$, with $\mathrm{𝑙𝑟}$ formed from $(m,L)$, and by a fresh value otherwise; by (a) and the abort rule of $G_2$ the request is unique. It answers an $H_2$ query ${\mathrm{𝗌𝖾𝗋}}_{𝔾}(R)\Vert {\mathrm{𝗌𝖾𝗋}}_{𝔾}({\mathrm{𝑃𝐾}}^{\prime })\Vert m$ by $h_2(\mathrm{𝑣𝑘},m,R)$ when ${\mathrm{𝑃𝐾}}^{\prime }=\mathrm{𝑃𝐾}$, and by a fresh value otherwise; by (b) the input determines $(m,R)$, and by (c) the two simulations are independent. The checks of Construction 4.8, namely the message check, the presence of the member’s own unused pair in $L$, deserialisation of every commitment and the order of the identifiers, are decided from public data. Algorithm ${𝒜}^{\prime }$ therefore queries the partial-signing oracle exactly when the RFC participant would answer, does not query the oracle when the participant would abort, leaving the token unused in both games, since an aborting participant keeps its pair; it never submits a token already answered, and returns $z_i$, discarding $R$. The sets $S_2$, $S_3$ and $S_4$ of the two games coincide; a valid RFC signature ${\mathrm{𝗌𝖾𝗋}}_{𝔾}(R)\parallel {\mathrm{𝗌𝖾𝗋}}_{{𝔽}_q}(z)$ is a valid FROST1 signature $(R,z)$; and strong verification agrees. So ${𝒜}^{\prime }$ wins when $𝒜$ wins in $G_3$. □

Cited: ePrint 2022/833, Theorem 5.4, whose bound, query counts and running time are those stated, the root spanning only ${\mathrm{Adv}}_{𝔾}^{\mathrm{omdl}}(ℬ)+6Q/q$; the TS-UF-4 separation is its Section 5.4, by an explicit attack at $n=20$ and $t=3$. □

The reduction plays the unnormalised game, runs the adversary unchanged on it, and stops unless $\mathrm{𝑃𝐾}\ne 𝒪$ and $\mathrm{𝑃𝐾}$ passes the parity test; since $s$ is uniform, this event has probability $(q-1)/(2q)$, and it is decided from public data before the adversary receives anything else. On the event normalisation changes nothing. The normalised key material is distributed as unnormalised dealer key material conditioned on the event: step (1) of Construction 6.7 redraws a zero secret, and negation (Lemma 6.6) maps the sharings whose group key fails the test bijectively onto those whose group key passes it, the coefficients staying uniform. The conditioned view is therefore that of the normalised game, and the win carries over. □

Hybrids, then the cited statements. For (a), Lemma 6.11, part (a), replaces the adversary that receives $\mathrm{𝗌𝗄}$ and the values derived from it by one that draws $\mathrm{𝗌𝗄}$ itself and computes them from $\mathrm{𝖺𝗄}={\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}(\mathrm{𝑃𝐾})$, rejection included, with no loss. For (b), Lemma 6.11, part (b), simulates $\mathrm{𝗇𝗄}$ and ${𝗋}_{\mathrm{𝗂𝗏𝗄}}$ from independent uniform values; the key-derivation hybrid then replaces $\mathrm{𝖺𝗌𝗄}$, before normalisation, by a uniform scalar, at the cost of Assumption “Pseudorandomness of PRF expansion”, of Lemma “Rejection in key generation” and of the $\mathrm{ToScalar}$ bias. These hybrids apply because the win is efficiently decidable from the key: the deciding algorithm answers the signing queries with the shares. What remains is the game of Definition 7.6 over normalised dealer keys. Lemma 7.11 passes to unnormalised dealer keys, which are the output of $\mathrm{𝖪𝗀}$ of FROST1; Proposition 7.8 passes such an adversary to $\mathrm{𝖥𝖱𝖮𝖲𝖳𝟣}[\mathrm{𝖯𝖺𝗅𝗅𝖺𝗌}]$; and Theorem 7.9 with Assumption 7.2 bounds that advantage. □

The proof cites statements only. Let $𝒜$ be an efficient adversary in Definition 7.19.

(1) Simulation. A reduction $ℬ$ plays Definition 7.18 with the same $C$, relaying the part of $𝒜$ in $K$. It completes the key. For $\mathrm{𝗎𝗌𝖾}\mathrm{\_}\mathrm{𝗊𝗌𝗄}=\mathrm{𝗍𝗋𝗎𝖾}$ it draws $\mathrm{𝗌𝗄}$ and computes $\mathrm{𝗇𝗄}$, $\mathrm{𝗊𝗌𝗄}$, $\mathrm{𝗊𝗄}$, ${𝗋}_{\mathrm{𝗂𝗏𝗄}}$ and $\mathrm{𝗂𝗏𝗄}$ from $\mathrm{𝗌𝗄}$ and $\mathrm{𝖺𝗄}={\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}(\mathrm{𝑃𝐾})$ (Lemma 6.11, part (a)); for $\mathrm{𝗎𝗌𝖾}\mathrm{\_}\mathrm{𝗊𝗌𝗄}=\mathrm{𝖿𝖺𝗅𝗌𝖾}$ it simulates $\mathrm{𝗇𝗄}$ and ${𝗋}_{\mathrm{𝗂𝗏𝗄}}$ (Lemma 6.11, part (b)), at a negligible cost. It gives $𝒜$ the state of $C$ and every public field, and simulates the chain and every other honest party. It relays each signing run to its oracles with the message, transaction data, commitment list and effective randomiser of $𝒜$; the honest oracles perform the check of Definition 5.9, and a failed check aborts identically in both games. The view of $𝒜$ is thus that of the experiment, and the number of honest shares returned for a pair $(\mathrm{𝗋𝗄},m)$ is the same in both games.

(2) Extraction. On the block chain output by $𝒜$, $ℬ$ runs the extractor of Assumption “Knowledge soundness of the Action proof” and finds an Action that meets the winning condition, stopping if there is none. Its witness gives ${\mathrm{𝖺𝗄}}_w^{\mathbb{P}}$, ${\alpha }_w$ and ${\mathrm{𝗂𝗏𝗄}}_w$ with $\mathrm{𝗋𝗄}={\mathrm{𝖺𝗄}}_w^{\mathbb{P}}+[{\alpha }_w]G^{\mathrm{𝖲𝗉𝖾𝗇𝖽𝖠𝗎𝗍𝗁}}$ and the consumed note’s transmission key $[{\mathrm{𝗂𝗏𝗄}}_w]{𝗀}_{𝖽}$, where ${\mathrm{𝗂𝗏𝗄}}_w={\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}}_{𝗋_{\mathrm{𝗂𝗏𝗄}}^{}{}_w{}^{}}^{\mathrm{𝗂𝗏𝗄}}({\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}({\mathrm{𝖺𝗄}}_w^{\mathbb{P}}),{\mathrm{𝗇𝗄}}_w)$ (Ironwood Guide, Definition “Orchard Action statement”).

(3) The witnessed key. The note is a note of the key, so $[{\mathrm{𝗂𝗏𝗄}}_w]{𝗀}_{𝖽}=[\mathrm{𝗂𝗏𝗄}]{𝗀}_{𝖽}$. The point ${𝗀}_{𝖽}\ne 𝒪$ has prime order $p_{\mathrm{𝖵𝖾𝗌𝗍𝖺}}$, and ${\mathrm{𝗂𝗏𝗄}}_w$ and $\mathrm{𝗂𝗏𝗄}$ are integers below , so ${\mathrm{𝗂𝗏𝗄}}_w=\mathrm{𝗂𝗏𝗄}$. The Ironwood Guide’s Proposition “Binding of $\mathrm{𝗂𝗏𝗄}$ to $(\mathrm{𝖺𝗄},\mathrm{𝗇𝗄})$” gives ${\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}({\mathrm{𝖺𝗄}}_w^{\mathbb{P}})={\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}(\mathrm{𝑃𝐾})$, except with negligible probability, and its Lemma “Coordinate extraction identifies opposite points” gives ${\mathrm{𝖺𝗄}}_w^{\mathbb{P}}=[\theta ]\mathrm{𝑃𝐾}$ for some $\theta \in \{1,-1\}$.

(4) Output. The Action is accepted, so its signature $\sigma$ is valid under $\mathrm{𝗋𝗄}$ on $m$, and $\mathrm{𝗋𝗄}=[\theta ]\mathrm{𝑃𝐾}+[{\alpha }_w]B$. Algorithm $ℬ$ outputs $(\theta ,{\alpha }_w,m,\sigma )$, which wins Definition 7.18 by the winning condition of the experiment and step (1).

The corrupt participants’ $\mathrm{𝗇𝗄}$ and the other common secrets enter only through the simulation of Lemma 6.11, and no step uses their secrecy; there the proof departs from the single-holder case. The losses are the failure probability of the extractor, the binding term and, for $\mathrm{𝗎𝗌𝖾}\mathrm{\_}\mathrm{𝗊𝗌𝗄}=\mathrm{𝖿𝖺𝗅𝗌𝖾}$, the simulation term, all negligible. □

Let $T^{\prime }$ be the output and $m^{\prime }:=\mathrm{𝖲𝗂𝗀𝖧𝖺𝗌𝗁}(T^{\prime })$. If $m^{\prime }=\mathrm{𝖲𝗂𝗀𝖧𝖺𝗌𝗁}(T)$, descending the digest tree of the Ironwood Guide’s Definition “Signature digest”, whose nodes hash unambiguous encodings under their personalisations, from the equal roots to a node whose inputs differ gives a collision, which has negligible probability by Assumption “Collision resistance of BLAKE2b” there. Otherwise $m^{\prime }\ne \mathrm{𝖲𝗂𝗀𝖧𝖺𝗌𝗁}(T)$, and by (${\mathrm{S}}_t$) fewer than $t-|C|$ honest participants returned shares for the pair $({\mathrm{𝗋𝗄}}_i,m^{\prime })$; the signature ${\sigma }^{\prime }$ of $T^{\prime }$ for that Action, valid under ${\mathrm{𝗋𝗄}}_i$ on $m^{\prime }$, is fresh on the pair. The reduction of Theorem 7.20, which relayed the effective randomiser ${\alpha }_i$ with ${\mathrm{𝗋𝗄}}_i=\mathrm{𝑃𝐾}+[{\alpha }_i]B$ and simulated the common secrets by Lemma 6.11, outputs $(1,{\alpha }_i,m^{\prime },{\sigma }^{\prime })$, a win in Definition 7.18. □

Sufficiency is proved by hybrids (i) to (iii), from each assignment towards one common game. The argument is statistical and programs no oracle, so it has no abort term.

(i) Each randomiser ${\widehat{\alpha }}_k$ is replaced by a uniform scalar, one run at a time, at $\delta +Q_h\cdot 2^{-256}$ per run, by Lemma 5.7 applied with the rest of the game as the observer; its queries to $H_R$ are among the $Q_h$, each other honest evaluation having its own fresh $32$-byte prefix. Then every ${\mathrm{𝗋𝗄}}_k=\mathrm{𝑃𝐾}+[{\widehat{\alpha }}_k]B$ is uniform and independent of the group keys and of the other runs (Ironwood Guide, Proposition “Unlinkability of randomised validating keys”, part (i)).

(ii) Each honest nonce is replaced by a uniform scalar, at $\delta +Q_h\cdot 2^{-256}$ per nonce, by Lemma 4.5 applied in the same way, whatever the share. The commitments are then uniform and independent of the keys, and so is the event of a zero nonce and the abort it causes.

(iii) The rest of the view is a function of these values, the observer’s choices and the oracle. For run $k$: ${\rho }_i$ is $H_1$ at an input holding ${\mathrm{𝗌𝖾𝗋}}_{𝔾}({\mathrm{𝗋𝗄}}_k)$, $H_4(m_k)$, $H_5$ of the list encoding and $i$; $R={\sum }_{i\in I_k}(D_i+[{\rho }_i]E_i)$; $c=H_2({\mathrm{𝗌𝖾𝗋}}_{𝔾}(R)\Vert {\mathrm{𝗌𝖾𝗋}}_{𝔾}({\mathrm{𝗋𝗄}}_k)\Vert m_k)$; and $z$ is the unique scalar with $[z]B=R+[c]{\mathrm{𝗋𝗄}}_k$ (Theorem 5.11). The binding-factor input holds ${\mathrm{𝗋𝗄}}_k$ and not $\mathrm{𝑃𝐾}$ because Construction 5.10 substitutes the shifted key; with $\mathrm{𝑃𝐾}$ there, the check that $R$ is the sum of the $D_i+[{\rho }_i]E_i$ under a candidate $\mathrm{𝑃𝐾}$ would test whether a run belongs to that key. After (i) and (ii) the view has one distribution under $a^0$ and under $a^1$. The triangle inequality (Math Guide, §“Statistical distance”, Theorem “Properties of statistical distance”) over both chains of hybrids, each of $N$ randomiser hops and $2{\sum }_k|I_k|$ nonce hops, gives the bound.

(iv) Necessity. The Coordinator and every signer of a run hold its seed with $L$, hence its randomiser, and so does any party that reads a randomiser channel without confidentiality. Each computes ${\mathrm{𝖺𝗄}}^{\mathbb{P}}=\mathrm{𝑃𝐾}=\mathrm{𝗋𝗄}-[\widehat{\alpha }]G^{\mathrm{𝖲𝗉𝖾𝗇𝖽𝖠𝗎𝗍𝗁}}$ and so links the run to every run of the key, distinguishing two assignments that differ on it, except when the two independent group keys coincide. A randomiser reused across two runs of one key gives both the same shifted key (ePrint 2024/436, Section 7). Hence the exclusions and the confidential randomiser channel are necessary; this part is the volume’s one statement of why that channel is confidential. □

An honest share is $z_i=d_i+e_i{\rho }_i+{\lambda }_{I,i}c({\mathrm{𝑠𝑘}}_i+\widehat{\alpha })$ (Construction 5.10), so

dividing by ${\lambda }_{I,i}c$ and subtracting $\mathrm{𝗋𝗄}=\mathrm{𝑃𝐾}+[\widehat{\alpha }]B$ gives ${\mathrm{𝑃𝐾}}_i-\mathrm{𝑃𝐾}$. Here ${\lambda }_{I,i}\ne 0$ for distinct non-zero identifiers, and $c$ is an answer of $H_2$, which takes the value $0$ with probability at most $1/q+\delta$ (Math Guide, Theorem “Properties of statistical distance”, part (3)). With $f$ the sharing polynomial, the tags are the values $[g(j)]B$ of $g:=f-f(0)$, of degree at most $t-1$; $t$ of them determine $[g(j)]B$ for every $j$ by Lagrange interpolation in the exponent (Math Guide, Theorem “Lagrange interpolation”), the map $a\mapsto [a]B$ being linear. For a dealer key with $t\ge 2$, $g(j)={\sum }_{k\ge 1}{a}_k{j}^k$ is uniform for $j\ne 0$, since $a_1$ is uniform and independent of the other coefficients; so the tags of two independent keys at $j$ agree with probability $1/q$. For $t=1$, $f$ is constant and $g=0$. □