Review of Practical Schnorr Threshold Signatures Without the Algebraic Group Model

review-of-practical-schnorr-threshold.md

My review of Practical Schnorr Threshold Signatures Without the Algebraic Group Model

Inline comments

Page 4

However, this is non-trival because we need to consider the PedPoP DKG and the signing protocol together. The rationale behind this is that PedPoP (like Pedersen DKG) lacks the ability to be simulated. Hence, it becomes crucial to examine the combination of the DKG and the signing protocol as a unified execution in order to thoroughly analyze its properties

Lacks the ability to be simulated againast what? I'm guessing an ideal trusted party who generates a perfectly uniform key and distibutes shamir shares. But do we know tha it can't be simulated against a fucntionality that allows biasing the keys?

Page 6

(top of the page)

this share xi from the combined one x is solely feasible if the reduction possesses the secret keys belonging to all remaining signers, including those controlled by the adversary

Worth mentioning here that this is trivial if the key is "honest majority" n > 2(t-1) since then there are at least t honest parties who will receive shares during the protocol who can therefore reconstruct adversary's contribution.

Page 9

Moreover, two honest signers Si and Sj may in general output two different joint public keys pk i̸ = pk j (in which case the adversary may forge under either public key). We believe that the latter should never happen in any meaningful and secure key generation protocol. Yet, our way of modeling ensures that it is the responsibility of the scheme to exclude (or otherwise handle) these cases of inconsistency between honest signers.

I didn't understand why there is this difference between what is modelled and what is meaningful. It also seems like in the paper protocol it is guaranteed.

Page 10

3 : // Run KeyGen(i) with A controlling network connections

4 : // between signer Si and all signers Sj , j ∈ {1, . . . , n} \ {i},

5 : // and in a separate thread concurrently to other oracle calls

What does it mean to have a separate thread here. In my intuition, the game is simulating the honest parties in the protocol so this is just a back and forth between the adversary and the game. Hopefully there's no need for threads!

Page 12

Moreover, signer Si verifies the shares received from the other signers by checking

Ok so we are in the setting where the adversary is able to abort the protocol and we are not trying to add acountability as to which parties are aversarial right?

If so I claim that we need not check each share individually. We can just aggergate the shares and aggregate the polynomial coefficients and just check the aggregate share is valid against the aggregate polynomial and abort otherwise (while still verifying PoPs). Furthermore we don't need to include the public polynomial shares in the common string check for Eq. It might even be possible to have a single party do the public polynomial commitment aggregation and send it out to all other parties (while sill preserving the frist term and the PoPs for it). The parties would still receive disaggergated secret shares and just add them together themselves. This would be reduce computation to O(n) for each party when verifying shartes (assuming there is some kind of coordinating party that doesn't receieve a share doing the aggregation).

Page 19

What's with the i = min(HS)? What's so special about the minimum honest signer?

Page 20

1. I think $A_{\kappa,0} = X*$ should be explicity set (the comment on line 7 only implies it).
2. This long comment might be easier to understand the concept of a vandermode matrix is introduced in prelims or something.

Notation: I use additive rather than multiplictive notation to make the point clearer

I cannot convince myself that the values for gamma and delta are correct here. We are trying to evaluate $f_\kappa(j)$ which will be in the form $\gamma_j X^* + \delta_j$. That makes sense but let me explain what I think those values should be.

First I define function similar to $\mathsf{Lagrange}$ from the paper except it includes the point $e$ at which you are evaluating the (basis) polynomal.

$$ \mathsf{LagrangeEval}(S,i,e) = \prod_{j \in S \setminus \{ i \} } \frac{e - j}{i - j} $$

The paper's definition is:

note the relationship:

$$ \mathsf{Lagrange}(S, i) = \mathsf{LagrangeEval}(S,i,0) $$

So in the paper $\gamma_j$ is set to:

$$ \gamma_j = \mathsf{Lagrange}(CS \cup \{ j \} ,j) = \mathsf{LagrangeEval}(CS \cup \{ j \},j,0) $$

(note: the $\cup \{j\}$ is superfluous since the second argument is excluded if its in the set and $j$ is the second argument)

I think this is wrong. The simulated polynomial is determined by $t$ points:

$$ \{ (0,X^*) \} \cup \{ (k, \tilde{x}_{\kappa, k}) | k \in CS \} $$

If we let $S = CS \cup \{0\}$ then we can evaluate that polynomial as:

$$ \gamma_jX^* + \delta_j = \mathsf{LagrangeEval}(S, 0, j) X^* + \sum_{k \in CS} \mathsf{LagrangeEval}(S,k,j)\tilde{x}_{\kappa,k} $$

And so:

$$ \gamma_j = \mathsf{LagrangeEval}(CS \cup \{ 0 \}, 0, j) \neq \mathsf{LagrangeEval}(CS \cup \{ j \},j,0) $$

There are some other things I didn't quite follow in the reduction so maybe I've just misunderstood the approach somehow but it seems to me like there is something off here.

General comments

The paper presents important simplifications to both the theory and practice of FROST style threshold Schnorr signature schemes. The paper contributes a multi-signature key generationm protocol that uses Schnorr proofs of possestion without assuming an explicit proof-of-possession security model or without using the algebraic group model. Previous works had always to do this since protocols that instantiated these PoPs with Schnorr signatures had to deal with the fact that you can't efficiently extract the secret key (that they claim to posses) from an advesary controlling many corrupted parties using the typical forking lemma algorithm that works where they control a single party. On the signing side of things the paper simplifies the specification and construction of the 2-round Schnorr threshold signature. In particular (i) showing that shares and polynomial commitments can be generated and sent at the same time and (ii) simplifying what goes into the nonce binding hash which means it's compatible with "ROAST".

Although the paper cleans up quite a few things it explcitly leaves a question untouched which is how to separate the security analysis of key generation from that of signing. The paper tries to explain why key generation and signing must be analysed together but I couldn't fully grasp the explanation and it still remains and important question in my mind. Consider this comment in recent paper from Shoup1:

Indeed, our approach is much more like that of GS21, in that we try to avoid talking about distributed protocols at all, and rather, we examine the security of the ordinary, non-threshold Schnorr scheme in “enhanced” attack modes that correspond to attacks on various types of threshold signing protocols (which may use presignatures, for example) — the details of these threshold protocols do not matter that much, so long as they are designed in a reasonably modular way so as to satisfy certain natural security properties.

Here he claims that as long as the distributed key generation is designed in a "reasonably modular way" so as to satisfy "natual" security properies (which are not made explicit) then one can analyse signing protocol security completely indepent of key generation. I am quite confused by this since on the one hand we have this paper which thinks that there is no easy way to separate these two concerns and on the other we have Shoup's paper which implies that it's so easy it can be left as an excercise to the reader!

This inflexibility in the architecutre of the security proof here may mean more work later when we need to apply tweaks to the key generation protocol. For example, it is not always the case that in a t-of-n threshold scheme you want to have the number of polynomial commitments contributed during the key generation phase (let's call it N) be precisely n. What if a trusted party distributes a key share (N=1), is Olaf's signing protocol still secure? Of course it is but since the signing protocol is only proved secure for a particualr key genertation protocol we can't say for sure (although for this case a proof should be easy to construct).

What about if N=t, that is if t parties (where we can assume one to be honest) generate a key and distribute shares to the n parties. I claim that this would be secure but it cannot be automatically assumed from the paper. Similarly there is an interesting case at N > n where you have parities that do not receive a share contribute randomn polynomial commitments to the key generation. In the case of hardware wallets this can even protect funds even if all n devices engaging in the key generation are corrupt if one of the N - n devices was not in a model where the corrupted devices cannot communicate directly with the adversary.

On Analyzing Key Generation and Signing Separately

The paper tries to explain why key generation and signing must be analysed together but I couldn't fully grasp the explanation and it still remains and important question in my mind.

Some key generation protocols ("DKGs") are fully simulation-based secure (e.g., in the UC framework). The most prominent example is "New-DKG" from GJKR [1], but all most "modern" (=recently proposed) DKGs fall into this category. Simulation-based security (or "simulatability") has the great advantage that we can combine a simulatable DKG with any (e.g., signing) protocol whose security analysis assumes a trusted setup, and security of the combination of the two protocols follows automatically. In other words, we can analyze the security key generation and signing separately.

The drawback of simulatability is that it is a very strong notion of security: Simpler and more efficient protocols, like Pedersen DKG (and its variant PedPoP), don't provide simulatability. In the concrete case of Pedersen/PedPoP, the reason is that the attacker can bias the final public key [1], e.g., the attacker has full control over the last bit of the public key and can force it to be 0. Now it turns out that this does not really help the attacker if all we want to do with the key setup is to create a Schnorr signature [1]. But this cannot be proven in a modular way. In particular, we cannot analyze the security of a signing protocol under the assumption that keys are setup as if they come from a trusted dealer,
because this assumption simply does not hold: in the case of a trusted dealer, the attacker cannot force the last bit to be 0.

So this is a trade-off, and what we wanted is a simple practical DKG. Moreover, we're not aware of any simulatable DKG in the literature that has been proven secure under dishonest majority. (And I can image this is fundamental, and you'll probably need to relax the DKG security in some way.) So we took PedPoP, and yes, this comes at cost of less modularity in the security proof, i.e., we need to analyze the combination of PedPoP+FROST3 as a monolithic thing.

Lacks the ability to be simulated againast what? I'm guessing an ideal trusted party who generates a perfectly uniform key and distibutes shamir shares. But do we know tha it can't be simulated against a fucntionality that allows biasing the keys?

When we wrote this, our world of the view was that there are just two classes of DKGs: DKGs that are fully simulatable and DKGs that are not. Now you bring up that maybe we could relax simulatability such that it explicitly allows the attacker to bias the key, but not more. This is a very interesting idea that has also been brought up by Jon Katz recently [2].

I believe this gives raise to interesting research questions:
Is PedPoP (or a similarly simple DKG) simulatable-with-bias (even under dishonest majority) And does this suffice to prove FROST unforgeable?

This is not trivial:

• What's the exact kind of bias that we need to allow so that we get a simple DKG but still a proof for FROST?
• We'll need to extract from the PoPs. This is an issue in the UC framework if the PoPs are simple Schnorr signatures, because we can't rewind in UC. What could we do here? AGM UC? GGM? Fischlin transform (ugh but ok, this is just for the DKG)?
• We can't have consensus under dishonest majority, so different parties may have different views on the outcome of the DKG. This could make the ideal functionality rather complicated. (In our paper, we handle all of this in the unforgeability definition.)

We could reach out to him and see if he's interested in this, but his focus may be on honest majority and robust DKGs. But even a simple chat could be fruitful.

[1] The best reference is their JoC version: https://link.springer.com/content/pdf/10.1007/s00145-006-0347-3.pdf
[2] see the very last sentence in https://eprint.iacr.org/2023/1094.pdf: "It is also possible to define variants of the key-generation functionality that ensure robustness, but are weaker than FKeyGen in that they allow the attacker to bias the public key. We leave a full consideration of such variants to future work." See also his talk at the NIST threshold workshop, in particular slide "DKG with Shift": https://csrc.nist.gov/csrc/media/Presentations/2023/mpts2023-day1-talk-dl-dkg/images-media/mpts2023-1b1-slides--katz--DKG-DL.pdf

(More to follow...)

However, this is non-trival because we need to
consider the PedPoP DKG and the signing protocol together. The rationale
behind this is that PedPoP (like Pedersen DKG) lacks the ability to be simulated.
Hence, it becomes crucial to examine the combination of the DKG and the signing
protocol as a unified execution in order to thoroughly analyze its properties

Lacks the ability to be simulated againast what? I'm guessing an ideal trusted party who generates a perfectly uniform key and distibutes shamir shares.
But do we know tha it can't be simulated against a fucntionality that allows biasing the keys?

(I think my previous comment addressed this one, but I agree that the writing is a bit unclear here.)

---

this share xi from the combined one x is solely feasible if the reduction possesses
the secret keys belonging to all remaining signers, including those controlled by
the adversary

Worth mentioning here that this is trivial if the key is "honest majority" n > 2(t-1) since then there are at least t honest parties who will receive shares during the protocol who can therefore reconstruct adversary's contribution.

Agreed.

---

Moreover, two honest signers
Si and Sj may in general output two different joint public keys pk i̸ = pk j (in
which case the adversary may forge under either public key). We believe that the
latter should never happen in any meaningful and secure key generation protocol.
Yet, our way of modeling ensures that it is the responsibility of the scheme to
exclude (or otherwise handle) these cases of inconsistency between honest signers.

I didn't understand why there is this difference between what is modelled and what is meaningful. It also seems like in the paper protocol it is guaranteed.

I assume we can agree that we wouldn't want a protocol in which honest S1 outputs pk1 and honest S2 outputs pk2 != pk1.

So one approach is that we could formalize this as some kind of "key agreement" property, and then restrict the unforgeability definition to KeyGen protocols that have this property. But we did something else: We simply ignored key agreement and wrote an unforgeability definition that works even for KeyGen protocols that don't have key agreement. Does this make sense? Do you think the presentation can be improved here?

I think the underlying issue here is that the paper considers only unforgeability. But this is ultimately not sufficient in practice: You want also some kind of correctness/robustness property. At least you'd want something along these lines: "If KeyGen returns a pki for some honest signer Si, then Si knows that a run of the signing protocol with honest signers will work." Note that this is somewhere in the middle between correctness (where typically everyone is honest) and (which is guaranteed output delivery in the presence of the adversary): It could be described as "correctness of the signing protocol after the adversary was present during KeyGen."

Noone has really formalized this property properly, at least not in this dishonest majority setting. What papers typically do is that they assume that KeyGen has run properly and there is some magic way to ensure that all signers are synchronized and agree on the key. This is reasonable if you are able and are willing to run BFT, but only then.

In our paper, we felt that going into this will expand the scope of the paper too much (or in other words, we didn't have a nice solution ready...). What we did is to formalize this "agreement" property for Eq, which is supposed to ensure something like "key agreement", but what we did there is at most a half-baked thing, and that's why Jonas and I are now working on this DKG document. Perhaps those results will also make me want to update that part of the paper. By the way, I was very reassuring to see that we're not the only ones having trouble with this.

---

3 : // Run KeyGen(i) with A controlling network connections
4 : // between signer Si and all signers Sj , j ∈ {1, . . . , n} \ {i},
5 : // and in a separate thread concurrently to other oracle calls

What does it mean to have a separate thread here.
In my intuition, the game is simulating the honest parties in the protocol so this is just a back and forth between the adversary and the game. Hopefully there's no need for threads!

KeyGen may be an interactive protocol that runs in multiple rounds and expects messages from multiple parties. We want to model that the adversary controls the network and the scheduling arbitrarily, e.g., the attacker can send a first-round KeyGen message as malicious S3 to honest S1, then (adaptively) send a first-round message as honest S1 to honest S2, etc... Even interleaving OKeyGen and OSign should be possible, e.g., if KeyGen has returned for honest S1, then a OPreRound(1, ...) for S1 should be possible, even if KeyGen has not returned for S2 yet.

I agree that modeling OKeyGen it as a "procedure-style" oracle that can be queried and gives a response is a bit off. We went through a lot of back and forth on this. The problem here is that we're dealing with two different paradigms of computation: KeyGen is an interactive protocol, whereas PreRound and SignRound are just procedures/algorithms. That's a bit uncommon. Typically, you'd either model everything as a procedure or as a protocol. The signing protocol is much cleaner to represent as separate algorithms, so we used this paradigm here. This restricts the model to "semi-interactive" signing protocols with one prep round and one signing round. For KeyGen, we want our model to be generic, and we don't know how many rounds there will be, so we modelled this as a protocol. I'm honestly open to suggestions on how to improve this.

In the end, the job of the challenger is to simulate multiple honest signers concurrently, and I think threads are the most natural abstraction here. (How would you implement the challenger in a real programming language? I claim you'd either use threads or end up emulating them by doing the state handling manually.) But yeah, I see that this can be confusing in a paper. Perhaps even notation can help. If we could make OKeyGen look more like a protocol execution (in the style of <KeyGen(...),KeyGen(...),..., A(...)>, this may already be better.

By the way, I think these kinds of issues why other papers don't have pseudocode-style definitions of unforgeability (or if they have, like BTZ22, they ignore KeyGen). It's just annoying to deal with, so everyone tries to avoid it.

---

Moreover, signer Si verifies the shares received from the other signers by
checking

Ok so we are in the setting where the adversary is able to abort the protocol and we are not trying to add acountability as to which parties are aversarial right?

Yes.

If so I claim that we need not check each share individually. We can just aggergate the shares and aggregate the polynomial coefficients and just check the aggregate share is valid against the aggregate polynomial and abort otherwise (while still verifying PoPs).

Yes, this should be totally fine. We anyway will use only the aggregate share. Nice observation!

Furthermore we don't need to include the public polynomial shares in the common string check for Eq.

I'm not sure about this. Don't all honest signers need to check that they agree on the aggregate polynomial? Or are you saying think the first term is enough?

Note the security proof doesn't rely on the PoPs being included in Eq (bottom of p. 13). We included them "just in case", and it restricts pretty much what the adversary can do. In practice, you'd probably anyway use a hash of the string to make it constant-size, and hashing is so cheap that I'm not sure we need to bother about this.

(Note to self: Typo: t_i should be \eta_i, twice...)

It might even be possible to have a single party do the public polynomial commitment aggregation and send it out to all other parties (while sill preserving the frist term and the PoPs for it). The parties would still receive disaggergated secret shares and just add them together themselves. This would be reduce computation to O(n) for each party when verifying shartes (assuming there is some kind of coordinating party that doesn't receieve a share doing the aggregation).

Nice idea. I'll need to think about this more, but yes, this seems plausible.

---

What's with the i = min(HS)? What's so special about the minimum honest signer?

Nothing. The reduction needs to pick some set of PoPs of the malicious signers, so, for the sake of avoiding the axiom of choice (just kidding), we pick those that have been received by min(HS).

This is related to what I said above: Since the PoPs are included in Eq, we actually know that everyone has received the same PoPs. But our reduction doesn't need to deal with this and simply picks those received by min(HS).

---

1. I think $A_{\kappa,0} = X*$ should be explicity set (the comment on line 7 only implies it).
2. This long comment might be easier to understand the concept of a vandermode matrix is introduced in prelims or something.

Indeed, thanks.

I cannot convince myself that the values for gamma and delta are correct here.

I haven't looked at this in detail, but yeah, this entire part was a bit rushed. We should rework it... I'll also reach to my coauthors about this.

In fact, we also planned to work on a proof of TS-UF-1. At the moment, we only show TS-UF-0, but we believe that a more sophisticated reduction could show TS-UF-1. (And we have a counterexample for TS-UF-2.) But I guess we should first polish this proof here a bit. :)

There are some other things I didn't quite follow in the reduction so maybe I've just misunderstood the approach somehow but it seems to me like there is something off here.

Happy to hear about them, if you're willing to write them up. Or if it's more efficient to discuss these in a call, we could also do this. Anyway, thanks a lot for this very detailed helpful. This was more helpful than the reviews we got from the conference, even though the reviewer's feedback was very helpful too.

Thanks for thoughts on separation of keygen and signing. That indeed cleared up a lot of things for me. I also hadn't seen Katz's recent paper.

So one approach is that we could formalize this as some kind of "key agreement" property, and then restrict the unforgeability definition to KeyGen protocols that have this property. But we did something else: We simply ignored key agreement and wrote an unforgeability definition that works even for KeyGen protocols that don't have key agreement. Does this make sense? Do you think the presentation can be improved here?

Yes that makes sense. Maybe you could just reword the explanation a bit to state clearly that this is to avoid enforcing unnecessary structure on the protocol. It sounded like "All keygens have this important property but nevertheless we've decided to ensure this is left up to the protocol designers to guarantee this". Why you did that is clear to me now but not when I read it.

For KeyGen, we want our model to be generic, and we don't know how many rounds there will be, so we modelled this as a protocol. I'm honestly open to suggestions on how to improve this.

I do not have any suggestions about how to make this better unfortunately. I think when writing this comment I was still sulking about things not being simulated against an ideal functionality since if KeyGen were simulation secure then it could more easily be understood as a step in the procedure where you activate the ideal functionality (and then it would be the extra "thread" running the keygen). I understand better now after your explanation and thinking about it some more.

It might even be possible to have a single party do the public polynomial commitment aggregation and send it out to all other parties (while sill preserving the frist term and the PoPs for it). The parties would still receive disaggergated secret shares and just add them together themselves. This would be reduce computation to O(n) for each party when verifying shartes (assuming there is some kind of coordinating party that doesn't receieve a share doing the aggregation).

Yes this is what I was thinking. For our project we have a coordinator with a lot of computational power and then small devices as our actual secret share holders.

Nothing. The reduction needs to pick some set of PoPs of the malicious signers, so, for the sake of avoiding the axiom of choice (just kidding), we pick those that have been received by min(HS).

Happy to hear about them, if you're willing to write them up. Or if it's more efficient to discuss these in a call, we could also do this. Anyway, thanks a lot for this very detailed helpful. This was more helpful than the reviews we got from the conference, even though the reviewer's feedback was very helpful too.

I think it pretty much hinges on me not understanding this part of the simulation. Let me know if you guys update this part of it or if I can help explain where I'm getting stuck.

---

Follow up on one of my comments: do you think the parties doing keygen and signing can be disjoint or at not equal? For example a set of parties K generate key shares for a signing parties S where S != K. See https://github.com/jonasnick/bip-frost-dkg/pull/1/files#diff-b335630551682c19a781afebcf4d07bf978fb1f8ac04c6bf87428ed5106870f5R234 for why I think it's important (sorry about the weird formatting!).

My intuition is yes because I think of the security of these two phases as being separate. I think this questions has practical implications for us because we'd like to use more devices to help generate the key than actually get shares.

Thanks again for helping me understand your paper.

It might even be possible to have a single party do the public polynomial commitment aggregation and send it out to all other parties (while sill preserving the frist term and the PoPs for it). The parties would still receive disaggergated secret shares and just add them together themselves. This would be reduce computation to O(n) for each party when verifying shartes (assuming there is some kind of coordinating party that doesn't receieve a share doing the aggregation).

Yes this is what I was thinking.

This is not surprising because you've replied to your own text here. ;) Sorry, I didn't mark it as a quote properly...