This section states the assumptions and games, then each security statement at the strength its support allows: the cited unforgeability theorem for FROST, with the non-interactive syntax in which it is stated and its correspondence to RFC 9591; its transfer to Orchard-protocol dealer keys, and the open composition with distributed key generation; the claimed unforgeability of the re-randomised scheme and the gaps in its proof; threshold spend authority, proved from a target notion that is itself open; unlinkability against specified outside observers, and the linkage that returned signature shares permit; and the class of the principal constructions and claims of the volume. Throughout, is a group of prime order with generator and identity ; a count of oracle queries is written , never .
The one-more discrete logarithm game for is a search game in the sense of the Crypto Guide, §“Security as a game”, Definition “Security game and advantage”. The challenger keeps a challenge counter and a query counter , both initially , and offers two oracles.
: set
, for any
The adversary outputs
The Crypto Guide names the problem in prose only. The game is that of ePrint 2022/833, Figure 9, in additive notation; its challenge queries are those that Theorem 7.9 counts.
Let be the Pallas group, of order
By its case of one challenge, the assumption implies the Ironwood Guide’s Assumption “Discrete logarithms on Pallas”.
Let , and be as in Definition 7.1 and let
the discrete logarithm of
The game is the intended one of ePrint 2024/436, Assumption 1 and
Figure 1. The restriction lies on the oracle’s queries, which are declared
combinations of and the challenges, and not on the adversary, so no
statement about algebraic adversaries is needed; the oracle of
Definition 7.1 answers any element. The printed Figure 1 is
ill-formed in three clauses: its oracle takes
Algorithm queries
The assumption of ePrint 2024/436, Theorem 1, is therefore no stronger than the OMDL assumption of the analysis RFC 9591 cites (ePrint 2022/833). Hence the analysis of ePrint 2024/436 needs no assumption beyond that of ePrint 2022/833.
A threshold signature scheme with leader requests has
servers, the participants of Definition 2.1
with identifiers
Key generation , run by a trusted party,
outputs a verification key , public auxiliary information
(the paper’s ), which holds the
verification shares, and secret keys
Token generation: server issues a first-round token and keeps a secret state for it.
A leader request , formed by the leader,
a party holding no secret of the scheme, carries a message
, a signer set
Partial signing : server answers with a partial signature computed from the state of the token , or with the failure symbol if is not an unused token of its own; each token is thus answered at most once.
Aggregation maps partial signatures to a signature .
Verification .
Strong verification , which accepts, for each pair , at most one signature.
The syntax is that of ePrint 2022/833, Section 3.1, restricted to what this volume uses. The leader is the Coordinator of Definition 2.8.
Let be an echo scheme (Definition 7.5). The game has the following procedures.
: require
Token oracle on
Partial-signing oracle on ,
Random oracle: return .
: for every recorded set
The adversary loses unless holds.
The adversary acts as the leader. The trivial-forgery predicates are
and, for
The games are those of ePrint 2022/833, Figures 2 and 3, the predicates
transcribed exactly. Under TS-SUF-3 a forgery on is trivial only if one
request for was answered by at least
Let
: draw
Token of server : draw
For a request and each
: if is
an unused token of with secret , erase and
return with
: if all partial signatures carry one , return .
: accept if and only if
: accept if
and only if equals the computed from and
The construction is ePrint 2022/833, Figure 8, in additive notation; the
paper’s token secrets
Let a ciphersuite (Definition 4.1) whose element serialisation
is total, as that of FROST(Pallas, BLAKE2b-512) is, meet
Assumption 4.2 with distance and digest length
bytes. Map RFC 9591 signing
(Constructions 4.4, 4.8
and 4.9, Definition 4.7) over key material of
Construction 3.2 at identifiers
A request naming another identifier lies outside the FROST1 game and is not
covered, and so is a suite whose serialisation is not total: its abort on
The binding-factor input
determines , except on a collision of or or on a digest used before its preimage is queried.
The challenge input is an injective reordering of , the two element encodings having fixed length.
The separated hashes and realise and as independent oracles.
Hedged nonces replace the uniform token secrets of FROST1 at the cost of Lemma 4.5 per nonce, a hop the reduction needs because it does not know the honest shares that enter .
Game hops, with additive losses (Crypto Guide, §“Security as a game”, Remark “Game-hopping”).
Game is the RFC game.
Game : every honest nonce is a uniform scalar. The
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 are the queries of and
at most evaluations by honest servers, each at an input with a
fresh -byte prefix. Hence
Game answers and at distinct inputs by
uniform scalars. Under Assumption 4.2 each answer is an
independent sample within distance of uniform, and the distinct
inputs number at most queries of , at most binding
factors and one challenge per answered request, and one challenge of the
final verification; replacing the answers one at a time costs
In , algorithm plays the FROST1 game. It relays token
queries. It simulates , and lazily and records their
queries. It answers an query
by when
Let have prime order , and let be
Construction 7.7 with servers and threshold . For
every adversary in the TS-SUF-3 game of Definition 7.6
making at most token queries, the first-round queries, and at most
random-oracle queries, there is an adversary in the
game of Definition 7.1, making at most
only the two terms and
lying under the root. Algorithm runs in about twice
the time of , plus at most
Cited: ePrint 2022/833, Theorem 5.4, whose bound, query counts and running
time are those stated, the root spanning only
RFC 9591, Section 7 (“Security Considerations”), claims security against
existential unforgeability under chosen-message attacks as defined in that
analysis, assuming that the shares are generated and distributed securely, by a
trusted dealer or by a distributed key generation protocol, and that at most
the Coordinator and
The share is bound through to , the
message, the commitment list and the identifier
(Definition 4.7). Changing the message, the signing set or any
commitment in changes some , hence and , except on
a collision of , or ; a share moved into another run
fails its share equation, and the aggregate fails verification. Without such
binding, concurrent sessions of two-round Schnorr signing admit forgeries:
in time subexponential in the bit length of , by an attack that combines
the challenges of concurrent sessions (Drijvers, Edalatnejad, Ford, Kiltz,
Loss, Neven and Stepanovs, “On the Security of Two-Round
Multi-Signatures”, IEEE Symposium on Security and Privacy 2019), which
applies to -of- threshold signing with up to
Consider a game over dealer key material (Construction 3.2)
that decides its winning condition from public data, the adversary’s output
and the transcript of its oracles, as the games of
Definition 7.6 do, over a group in which exactly half of the
in the game with unnormalised dealer key material.
The reduction plays the unnormalised game, runs the adversary unchanged on
it, and stops unless
For
Assume Assumption 7.2, and Assumption 4.2 as Proposition 6.2 instantiates it for FROST(Pallas, BLAKE2b-512) (Construction 6.1). Then Theorem 7.9, through Proposition 7.8, holds for RFC 9591 signing against adversaries whose requests list only identifiers in , with the effective randomiser zero on dealer key material (Construction 3.2) normalised by Construction 6.7 and completed in either of two ways, the corrupt participants holding the common secrets:
for a dealer that shares an derived from a spending key
that no participant holds (
The corollary covers signing with the randomiser zero only; the re-randomised protocol is the subject of §7.4.
Hybrids, then the cited statements. For (a), Lemma 6.11,
part (a), replaces the adversary that receives and the
values derived from it by one that draws itself and computes
them from
Theorem 7.9 assumes trusted key generation, and no checked source proves FROST1 unforgeable with a distributed key generation, in particular with Construction 3.6. RFC 9591, Section 7, lists secure generation by a dealer or by a distributed protocol as an assumption, not as a result. The nearest results are two. Crites, Komlo and Maller (ePrint 2021/1375, Theorem 7) prove FROST2 with their key generation unforgeable under the one-more discrete logarithm assumption and a further assumption: that an algorithm outputting a group element with a valid Schnorr proof of knowledge for it knows the element’s discrete logarithm, in that an extractor computes the logarithm from the algorithm’s code and random coins. The original paper (ePrint 2020/852) proves, under discrete logarithms, an interactive variant with its own key generation, not the specified scheme. Classification (Definition 1.1): unforgeability of FROST1 with distributed key generation is an open problem.
The game TRUF, for the instance of Definition 5.3 given by FROST with effective-randomiser map , runs as follows.
The adversary chooses and a static set
with
The challenger runs centralised key generation, a Shamir sharing of a
uniform with
Oracle , for honest , opens
session and returns Round One commitments
Oracle , once per open session: add to
the set ; set
The adversary outputs and wins if
The randomisers are adversarial, and the oracle applies itself. The advantage is the probability of winning.
The game is that of ePrint 2024/436, Definition 6 and Figure 4, in additive notation and with the evident reading of its interface; the symbol is the paper’s name for a commitment pair, not a binding factor.
Four clauses bound what TRUF covers.
TRUF is existential: its oracle records messages only, and a new signature on a signed message does not win. It is therefore weaker than Definition 5.1, which records message–signature pairs, and Theorem 1 of ePrint 2024/436 would not, as printed, give the strong notion that ZIP 312, “Requirements”, asks for (Remark 5.13, (b)).
The choice
Freshness is on the message alone. All Actions of a transaction sign one digest, so a forgery under a second Action’s randomised key on a digest already signed for another Action is not a win.
A Coordinator that chooses the effective randomiser outright (Remark 5.8) is outside the game, whose oracle applies .
Each clause is a reason why the target notion of §7.5, Definition 7.18, is stated separately.
Theorem 1 of ePrint 2024/436 claims that Rerandomized-FROST is unforgeable in the sense of Definition 7.14, in the random-oracle model under the assumption of Definition 7.3, with its Equation (3) as printed:
all three terms under one root, with
The reduction of ePrint 2024/436, Section 6, has five gaps, one per clause.
The simulated verification shares do not interpolate to
as printed. For
The Round Two logarithm query omits the Lagrange coefficient:
the share
The random-oracle simulation is not a consistent lazy sampler:
the table of stores no outputs, index and message are mixed in the
binding-factor table, one branch returns in place of , and an
unrandomised case
The forking step reprograms the signature hash at a key left undefined, does not show that the reprogrammed query is the challenge query of both forgeries when their randomised keys differ, and derives no bound, so Equation (3) is not derived.
Nonce extraction is unsound: the printed numerator has sign
errors and uses the randomisers in place of their images; and when
With the query counter of Definition 7.3 restored, these remain material gaps: a repair may exist, but no complete reduction is given, and the claim of Remark 7.16 is recorded, not used as a theorem. Classification (Definition 1.1): unforgeability of re-randomised FROST in the game of Definition 7.14 is an open problem.
Fix a key generation for threshold parameters , followed by Construction 6.7, and the ciphersuite FROST(Pallas, BLAKE2b-512), whose hashes are available as Assumption 4.2 models them.
Corruption. The adversary names a set of fewer than participants before key generation and takes their part in : it receives every message delivers to a member of and, when is interactive, sends the messages of the members of in each round after seeing the honest participants’ messages of that round. The honest participants, and a dealer, run as specified and abort as it prescribes. For Construction 3.2 the adversary receives the shares of and the coefficient commitments.
Keys. After a run of without abort it receives and every , and it controls the Coordinator.
Signing. It obtains Round One commitments from honest participants (Construction 4.4) and Round Two shares on requests with transaction data (Definition 5.9), in which it supplies the effective randomiser directly, as the wire form of ZIP 312 lets a Coordinator do; each honest participant runs Construction 5.10 with that and .
Output. The adversary outputs with
and fewer than
The scheme satisfies the notion for if every efficient adversary wins with negligible probability.
The notion is the target for ZIP 312, “Round Two - Signature Share
Generation”; no source states it. Naming
relates to , so a key whose logarithm the
adversary knows is no win;
The adversary names a static set of fewer than participants. An Orchard-protocol threshold key is generated by , the adversary taking the part of as in Definition 7.18, normalised by Construction 6.7, and completed in one of two ways:
by Construction 6.8
(
when is a dealer that shares an derived from a
spending key, by the Ironwood Guide’s Construction “Spend-side
secrets” from that spending key, which no participant holds
(
The adversary controls the Coordinator and the participants of ,
receives their state, the common secrets included, and every public field,
may create notes to any address of the key, and runs signing runs of
Construction 5.10 with the honest participants, supplying the
message, the transaction data they check (Definition 5.9)
and the effective randomiser. A note of the key is a note whose
transmission key is for the key’s . The adversary
wins by outputting a block chain containing an accepted Action whose
witness consumes a note of the key and whose signature is valid under its
on a digest such that fewer than
The experiment is the formal content of the clause of ZIP 312, “Threat Model”, that a rogue Coordinator “should not be able to create signed transactions without the approval of” participants (Definition 5.14). Freshness is on because every Action of a transaction signs one digest.
Suppose that re-randomised FROST over FROST(Pallas, BLAKE2b-512) with keys from satisfies Definition 7.18. Then, under the Ironwood Guide’s Assumptions “Knowledge soundness of the Action proof”, “Discrete logarithms on Pallas” and “GroupHash as a random oracle”, and, for keys completed as in Definition 7.19, (b), its Assumption “Pseudorandomness of PRF expansion”, no efficient adversary wins Definition 7.19 except with negligible probability. The statement is conditional: its premise is an open problem (Remark 7.22).
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 , relaying the part of
in . It completes the key. For
(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 ,
and with
(3) The witnessed key. The note is a note of the key, so
(4) Output. The Action is accepted, so its signature is
valid under on , and
The corrupt participants’ 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
The Ironwood Guide’s Proposition “Bundle binding” is stated for single holders under its hypothesis (S), that the holder signs under only . Its threshold counterpart is the hypothesis
for each threshold-signed Action of a
transaction , with randomised validating key , fewer than
If the premise of Theorem 7.20 and () hold, then under the Ironwood Guide’s Assumption “Collision resistance of BLAKE2b” and, for keys completed as in Definition 7.19, (b), its Assumption “Pseudorandomness of PRF expansion”, an adversary in Definition 7.19 that receives outputs, only with negligible probability, an accepted transaction that contains an Action with key and whose effecting data differ from those of .
Let be the output and
Hypothesis () does not follow from Definition 5.9: a Coordinator may send a second request with the same effective randomiser together with its own matching transaction data, and the check passes. It is an approval policy that the corollary assumes. The corollary is conditional, as the theorem is.
The premise of Theorem 7.20 is an open problem for
every randomiser flow. Theorem 7.9 has no randomisation. The
game of Definition 7.14 applies the randomiser hash inside its
oracle, which only the flow of Construction 5.6 matches;
wherever the Coordinator sends the effective randomiser, as in the wire form
of ZIP 312 or when it forwards a randomiser fixed elsewhere, the flow is
outside that game (Remark 5.8). The preprint’s
freshness is on messages only, and its proof is incomplete
(Remark 7.17). Composition with distributed key generation is
open (Remark 7.13). The Ironwood Guide’s Theorem
“Spend authority” does not apply: it fixes a key with
Neither ePrint 2024/436 nor ZIP 312 proves threshold unlinkability. ZIP 312, “Rationale”, argues by matching distributions: its randomiser generation “generates randomizer uniformly at random as required by RedDSA.GenRandom”, and signing is compatible with the randomisation, signing and validation of the protocol specification. Its “Requirements” defer the formal notion to the criteria of the protocol specification for signatures with re-randomisable keys. The randomiser is close to uniform, not uniform (Lemma 5.7). This subsection states a notion against specified observers and proves it.
Fix threshold parameters , the identifiers
the chain level: , the aggregate and ;
the commitment level: the chain level with the commitment list of Round One, which RFC 9591, Section 5, sends without confidentiality;
the share level: the commitment level with the returned signature shares, which RFC 9591 also sends without confidentiality.
The scheme is outsider-unlinkable at a level with distance if the observer’s views under and , its oracle answers included, are within statistical distance (Math Guide, §“Statistical distance”).
The Coordinator and the share holders are excluded because ZIP 312 trusts them with unlinkability (Definition 5.14).
Let signing be over FROST(Pallas, BLAKE2b-512), with distance
an honest Coordinator and honest signers following Construction 5.10;
the seed and the transaction data on the confidential and authenticated channel of Definition 2.10, type (b), and Round One and the returned shares on the authenticated channels of RFC 9591.
Let
The hypotheses that the observer is neither the Coordinator nor a signer of the runs, and that the randomiser channel is confidential, are necessary.
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 is replaced by a uniform scalar, one
run at a time, at
(ii) Each honest nonce is replaced by a uniform scalar, at
(iii) The rest of the view is a function of these values, the observer’s
choices and the oracle. For run : is at an input
holding , , of the list
encoding and ;
(iv) Necessity. The Coordinator and every signer of a run hold its
seed with , hence its randomiser, and so does any party that reads a
randomiser channel without confidentiality. Each computes
The proposition is scoped against the Ironwood Guide’s Definition
“Public leakage and privacy preconditions” (“Privacy”). A key with
Let
which is the same for every run of the key; the division is defined except
when
An honest share is
dividing by and subtracting
On the toy curve of Example 4.12, two re-randomised runs of
the key with randomisers and have randomised keys
and , and both give the tags
Table 3 classifies the principal constructions and claims of the volume by Definition 1.1, with its source and the section that states it. Specified objects are those of an RFC, a ZIP or the protocol specification, with the ZIP’s status; designed objects are published or constructed here without a specification; open problems have no proof in any checked source; established claims rest on a published proof. The last group lists the principal statements proved in this volume.
| Object and source | Home |
|---|---|
| Specified | |
| FROST signing, aggregation and share verification; RFC 9591 | §4 |
| Trusted-dealer key generation; RFC 9591, Appendix C | §3.1 |
| Even- requirement on the spend validating key of an Orchard-protocol key; ZIP 2005 (Proposed) | §6.3 |
| Re-randomised signing, aggregation and share verification; FROST(Pallas, BLAKE2b-512); the threat model; ZIP 312 (Draft), which omits key generation | §§5.5, 6.1, 5.6 |
| Randomiser derivation of ZIP 312 (Draft); with the signature digest as message it yields a valid threshold spend only with negligible probability (Proposition 5.5), so no randomiser derivation usable for spend authorisation is specified | §5.3 |
| Derivation with and the constraints on FROST keys; ZIP 2005 (Proposed), taking effect with NU6.3 (ZIP 258) | §6.4 |
| Message-check obligation; ZIP 312 | §5.4 |
| Consensus rule under which the aggregate is accepted; protocol specification, §“Action Descriptions” | §6.2 |
| Designed but unspecified | |
| Distributed key generation for Zcash; ePrint 2020/852, specified by no RFC or ZIP | §3.2 |
| Agreement on the common spending key | §6.4 |
| Sign normalisation of shared key material (Construction 6.7), this volume’s own | §6.3 |
| Seed-and-commitments randomiser and the order under it | §§5.3, 6.5 |
| Message-check mechanism | §5.4 |
| Threshold spend authorisation of an Action under the seed-and-commitments randomiser | §6.6 |
| Open problem | |
| Unforgeability of FROST with distributed key generation | §7.3 |
| Unforgeability of re-randomised FROST in the game of ePrint 2024/436, claimed with a gapped proof; and in the target notion, Definition 7.18 | §§7.4, 7.5 |
| Threshold strong unforgeability under re-randomised keys, Definition 5.1 | §5.6 |
| Unconditional threshold spend authority | §7.5 |
| Composition of a constructor-chosen with ZIP 312 | §6.5 |
| Established | |
| TS-SUF-3 of FROST1 under OMDL in the random-oracle model; ePrint 2022/833, Theorem 5.4 | Theorem 7.9 |
| Proved in this volume | |
| Correctness | Theorems 4.11, 5.11 |
| Validity of the aggregate | Proposition 6.3, Corollary 6.4 |
| Correspondence to FROST1 | Proposition 7.8 |
| OMDL hardness implies AOMDL hardness | Lemma 7.4 |
| No randomiser derived from the signature digest | Proposition 5.5 |
| Distance of nonces and randomisers from uniform | Lemmas 4.5, 5.7 |
| Replay and identifiable abort | Propositions 4.14, 4.10 |
| Validity of dealt and jointly generated key material | Propositions 3.3, 3.8 |
| Correctness of sign normalisation of a dealt or jointly generated sharing | Lemma 6.6, Construction 6.7 |
| Transfer of unforgeability to Orchard-protocol dealer keys | Lemmas 7.11, 6.11, Corollary 7.12 |
| Order of a threshold spend authorisation | Proposition 6.12 |
| Nonce-reuse criterion | Lemma 4.13 |
| Threshold spend authority and bundle binding from the target notion | Theorem 7.20, Corollary 7.21 |
| Outsider unlinkability at the chain and commitment levels | Proposition 7.24 |
| Linkage at the share level | Proposition 7.25 |