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

Chelsea Komlo <ckomlo@uwaterloo.ca> Wed, 29 January 2020 13:37 UTC

Return-Path: <ckomlo@uwaterloo.ca>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A71BC12009C for <cfrg@ietfa.amsl.com>; Wed, 29 Jan 2020 05:37:14 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.698
X-Spam-Level:
X-Spam-Status: No, score=-2.698 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=uwaterloo.ca
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5PK2Ai6GWoVg for <cfrg@ietfa.amsl.com>; Wed, 29 Jan 2020 05:37:11 -0800 (PST)
Received: from phage7.uwaterloo.ca (phage7.uwaterloo.ca [129.97.128.175]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 98A2D120088 for <cfrg@irtf.org>; Wed, 29 Jan 2020 05:37:11 -0800 (PST)
Received: from pps.filterd (phage7.uwaterloo.ca [127.0.0.1]) by phage7.uwaterloo.ca (8.16.0.27/8.16.0.27) with SMTP id 00TDX4Qw011188 for <cfrg@irtf.org>; Wed, 29 Jan 2020 08:37:10 -0500
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=uwaterloo.ca; h=from : to : subject : date : message-id : references : in-reply-to : content-type : mime-version; s=default; bh=zT3LgQeb4Ey0Y/Nnu/zzaLHFrR99iD6Z6WcRBmnkfWc=; b=mfd8OMyBMIFQt47XNQXbG640jUcRazHeG654ZEwuDuDEjls+vUUMCxUe8a1diug7Fnym EbKmy/o2voI8OwI7Dp0jt/F2haDeqdAA8FdVO5Z2WmgB7VazFUlvoMTOY8ic6R6KaMl0 qiK0igwsyjptwqVhF9+yqKVckrXGeUsIuKQ=
Received: from connhm04.connect.uwaterloo.ca (connhm04.connect.uwaterloo.ca [172.16.137.68]) by phage7.uwaterloo.ca with ESMTP id 2xrkhsc8rc-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-SHA256 bits=128 verify=NOT) for <cfrg@irtf.org>; Wed, 29 Jan 2020 08:37:09 -0500
Received: from connhm03.connect.uwaterloo.ca (172.16.137.67) by connhm04.connect.uwaterloo.ca (172.16.137.68) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1713.5; Wed, 29 Jan 2020 08:37:09 -0500
Received: from connhm03.connect.uwaterloo.ca ([fe80::75cd:8a4e:9af2:113c]) by connhm03.connect.uwaterloo.ca ([fe80::75cd:8a4e:9af2:113c%18]) with mapi id 15.01.1713.009; Wed, 29 Jan 2020 08:37:09 -0500
From: Chelsea Komlo <ckomlo@uwaterloo.ca>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: =?Windows-1252?Q?[Cfrg]_FROST_=97_Flexible_Round-Optimized_Schnorr_Thresh?= =?Windows-1252?Q?old_signatures?=
Thread-Index: AQHV0YotrRqTInGh5U239gvJDWBwgKgBpKeW
Date: Wed, 29 Jan 2020 13:37:08 +0000
Message-ID: <e652ba84e0ec47958de80d34fb93837a@uwaterloo.ca>
References: <CAHOTMVJOnLb2WC5zNJWc+-qTVn0erYoAerKoikwf5Sc+4pannw@mail.gmail.com> <EDB59D88-7A84-4211-96D6-5E83AF15724F@gnunet.org>, <CAJoqpTJ3UKsOq5ioEt1xm2sQRoBOnXgFitsko-o9Pdi4LJqkgA@mail.gmail.com>
In-Reply-To: <CAJoqpTJ3UKsOq5ioEt1xm2sQRoBOnXgFitsko-o9Pdi4LJqkgA@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [99.250.194.225]
Content-Type: multipart/alternative; boundary="_000_e652ba84e0ec47958de80d34fb93837auwaterlooca_"
MIME-Version: 1.0
X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 priorityscore=1501 malwarescore=0 suspectscore=0 phishscore=0 bulkscore=0 spamscore=0 clxscore=1011 lowpriorityscore=0 mlxscore=0 impostorscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1911140001 definitions=main-2001290113
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/USYUleqIjS-mq93oGPSV-Tu0ndQ>
Subject: Re: [Cfrg] =?windows-1252?q?FROST_=97_Flexible_Round-Optimized_Schno?= =?windows-1252?q?rr_Threshold_signatures?=
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 29 Jan 2020 13:39:16 -0000

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 <burdges@gnunet.org>
> Date: Wed, Jan 8, 2020 at 10:01 PM
> Subject: Re: [Cfrg] FROST — Flexible Round-Optimized Schnorr
> Threshold signatures
> To: CFRG <cfrg@irtf.org>
>
>> On 7 Jan 2020, at 12:00, Tony Arcieri <bascule@gmail.com> 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.