Re: [Cfrg] FROST — Flexible Round-Optimized Schnorr Threshold signatures

[Chelsea Komlo <[e-mail]>]

Hello,

Thank you for posting our work to this list. We have updated the below link to include our complete technical report; keep in mind this is a draft that is currently under review. We will update this mailing list as our work nears stabilization.

https://crysp.uwaterloo.ca/software/frost/

We thank Jeff for bringing the work by Drijvers et al.[1] to our attention. We have updated our work to include an analysis of the attack presented in Drijvers; see our technical report for complete details.

I will now first summarize Drijvers et al.[1] and then give an overview of how the attack presented by Drijvers relates to FROST. Lastly, I address Jeff's points.

=== Drijvers et al. Overview ===

Drijvers et al.[1] presents several contributions. These are as follows:

First, the authors present the k-sum attack on two-round aggregate signature schemes. This attack is impractical when signing operations are performed in a single thread but becomes practical as the number of concurrent signing operations increases. The attack is performed in time O((k+1)*b*2^(b/(1+lg(k+1)))) where k is the number of open signing rounds and b is the bitlength of the underlying group. Concretely, the k-sum attack in a single-threaded setting is as costly as finding a discrete log in the group (128 bits in a 256-bit group) but when the ceiling of allowed *simultaneous* signing operations increases to k=15, the security of a susceptible scheme is decreased by a square root factor (63 bits in the same 256-bit group). See Table 1 in our work for additional concrete parameters.

Second, the authors illustrate a metareduction revealing a flaw in the security proofs for multisignature schemes that utilize the generalized forking lemma with rewinding. This metareduction demonstrates that this proof strategy in a single-party setting (as is used to prove single-party Schnorr) cannot be straightforwardly generalized to a multi-party setting.

Finally, the authors present a secure two-round Schnorr multisignature scheme which utilizes a binding technique such that participants must select their commitments before seeing others' commitments. The authors demonstrate how this technique achieves security against both the k-sum attack and metareduction.

=== Impact to FROST and Other Schnorr-Based Threshold Schemes ===

Because the first two variants of FROST do not bind participants to their commitment before seeing others' commitments, these variants require limitations on concurrency to protect against the k-sum attack (for which we provide recommended parameters in Table 1 of our work). We now additionally include a third FROST signing variant that is not impacted by the k-sum attack and thus is not limited in concurrency; however this variant requires either increased computation or an extra network round in a pre-processing stage.

Our proof of security does not utilize the generalized forking with rewinding technique; instead we provide a reduction of the end-to-end protocol including key generation. Consequently, our proof does not "fit" the hole required by the metareduction of Drijvers (see paragraph 3 of 7.2.1 in our work).

We additionally now include an assessment of the security against the k-sum attack for other Schnorr threshold schemes reviewed in our work; the more recent work by Gennaro et al.[2] is susceptible, while the prior less-efficient DKG also by Gennaro et al.[3] and its Schnorr construction are not [4].

=== Summary ===

We additionally now present a third FROST variant that can support unlimited concurrency with a slight increase in computation or alternatively an additional network round during preprocessing. For implementations who prefer limiting network rounds or computational overhead over concurrency, the first two variants of FROST remain secure against the k-sum attack within a bound on the number of allowed simultaneous signing operations.

I address Jeff's points directly below.

All best,
Chelsea

[1] https://eprint.iacr.org/2018/417.pdf
[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.6830&rep=rep1&type=pdf#page=389
[3] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.134.6445&rep=rep1&type=pdf
[4] <https://dl.acm.org/doi/10.5555/646038.678297> https://dl.acm.org/doi/10.5555/646038.678297
<https://dl.acm.org/doi/10.5555/646038.678297>


________________________________

> From: Jeff Burdges <[e-mail]>
> Date: Wed, Jan 8, 2020 at 10:01 PM
> Subject: Re: [Cfrg] FROST — Flexible Round-Optimized Schnorr
> Threshold signatures
> To: CFRG <[e-mail]>
>
>> On 7 Jan 2020, at 12:00, Tony Arcieri <[e-mail]> wrote:
>> The batched non-interactive preprocessing stage sounds particularly
> interesting for use cases like code signing.
>> https://crysp.uwaterloo.ca/software/frost/
>
> There are no security arguments in the version available there, but
> their first scheme is clearly vulnerable to the the k-sum forgery
> attack in https://eprint.iacr.org/2018/417.pdf as are all other
> published two round trip Schnorr threshold or multi-sigantures.

The above claim that all published two-round Schnorr multisignature schemes are insecure is incorrect. Drijvers et al. themselves present a two-round scheme that is secure against both the k-sum attack and metareduction; see Section 5 in Drijvers [1].

> In fact, their second variant avoids the k-sum problem by being
> hyper-interactive, but actually doing this inside any real system
> sound extremely fragile.

The second FROST variant is in fact less interactive that the other FROST variants.

As stated above, the first two variants of FROST require limited parallelism as prescribed in Table 1 of our work.

Finally, the concept of publishing ephemeral public values to a central server for asynchronous discovery as is done in the second FROST variant is not novel to our work.