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

Tony Arcieri <bascule@gmail.com> Tue, 07 January 2020 17:00 UTC

Return-Path: <bascule@gmail.com>
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 67D82120802 for <cfrg@ietfa.amsl.com>; Tue, 7 Jan 2020 09:00:26 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 2q608CThLVq7 for <cfrg@ietfa.amsl.com>; Tue, 7 Jan 2020 09:00:23 -0800 (PST)
Received: from mail-oi1-x236.google.com (mail-oi1-x236.google.com [IPv6:2607:f8b0:4864:20::236]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E2B0612018B for <cfrg@irtf.org>; Tue, 7 Jan 2020 09:00:22 -0800 (PST)
Received: by mail-oi1-x236.google.com with SMTP id c16so105137oic.3 for <cfrg@irtf.org>; Tue, 07 Jan 2020 09:00:22 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=+OWtebgnQbVccjt9hrLyUca3/1BOzSoUw2t5oOU/ddo=; b=CKuE4cv7+NAv44oOW7Kt9taIOKVo9fJeYH+cVT8IWiKtqWAZ+IY8/u/1qMvmhYvfim tA4j6A25GDmjrD8LgoY6vuIeZeQ0rgwHDZHkvzlKHThLZ4w0ZT0KQ3gD5Ke2u7kAaQ4s PIt3/xm0kumQEZV6F3ep0T0j9xRevyUtDgG3A5dVKVganldqZpeK83UWPgQO6QIEqkoN ew/xW0ss99zmOlyky8FASy5XusILCtbTridroAjWt7Rb2Q5GvbcSYbt18BzAb/mbOP/2 PUFZjZ0+mraey1aDmiiRZhV7hXhtqGeuc8367zAbhVDMBaDnJIp2QJUtHjyXK/JGSeOf c1sQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=+OWtebgnQbVccjt9hrLyUca3/1BOzSoUw2t5oOU/ddo=; b=OzlxA6TGYNLuVcKxPWT4OE3KeuGqe1pDR4Bu7jESRBQrzr3SDhWAmsQuEvZAJgvPzf QDssHA11JhNGorvAWLLTEN3xyzi33IUz5DS0V9tbW1aZblIHBOXd2Scuz0W1JK2w3jYw JM38sVNr0i/cmdTekrOMIGvFv/ArB/ofFLUblyeKmAWwVLlM+4p9uPesPBFOVmUl0Sl8 UjPRido8XIhJYlMuJnuhV51Sp3oVZR9DQ723kTzixsOUuurNIMIxqADCY+dG5rvCXYAQ wX1pukG8Jgt2ldkkR1pDQaKeS85gaWtz2aK+woqZEpagqGlbqpktnnrAHvHXUarkNWdX CdaA==
X-Gm-Message-State: APjAAAVc8JDnn05Q0YNiOMihEEomsjPs3dBFi/dKI0zCaNs8zb86HsaZ lAZsQbG2RbYHmB09lBFHkR7dLfr6BA6vicBauIj444mDL6g=
X-Google-Smtp-Source: APXvYqzUFWiyNvESK0PrNvOAGEn+rr9XNlcd/H59OFRw+kkU6dpZg8+kOemdvWBFaaeaPPDsKMfnnJCB7gklqfOnPJA=
X-Received: by 2002:aca:54cc:: with SMTP id i195mr423242oib.126.1578416421758; Tue, 07 Jan 2020 09:00:21 -0800 (PST)
MIME-Version: 1.0
From: Tony Arcieri <bascule@gmail.com>
Date: Tue, 7 Jan 2020 12:00:10 -0500
Message-ID: <CAHOTMVJOnLb2WC5zNJWc+-qTVn0erYoAerKoikwf5Sc+4pannw@mail.gmail.com>
To: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000206af7059b8fb68d"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ddpXXADNElT6XuhJGIIkgn733S4>
Subject: [Cfrg] =?utf-8?q?FROST_=E2=80=94_Flexible_Round-Optimized_Schnor?= =?utf-8?q?r_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: Tue, 07 Jan 2020 17:00:26 -0000

With the recent discussions around threshold Ed25519 multisignatures, I
thought this would be of interest to the group.

The batched non-interactive preprocessing stage sounds particularly
interesting for use cases like code signing.

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

Unlike signatures in a single-party setting, threshold signatures require
> cooperation among a threshold number of signers each holding a share of a
> common private key. Consequently, generating signatures in a threshold
> setting imposes overhead due to network rounds among signers, proving
> costly when secret shares are stored on network-limited devices or when
> coordination occurs over unreliable networks. In this work, we present
> FROST, a Flexible Round-Optimized Schnorr Threshold signature scheme that
> improves upon the state of the art to reduce network overhead during
> signing operations. We present two variants of signing operations in FROST,
> the first requiring participants to send and receive two messages in total,
> and an optimized single-round variant with a batched non-interactive
> pre-processing stage. FROST achieves its efficiency improvements by
> allowing the protocol to abort in the presence of a misbehaving party (who
> is then identified and excluded from future operations)—a reasonable model
> for practical deployment scenarios. We present two use cases of threshold
> signatures demonstrating the practicality of this tradeoff to real-world
> implementations, and prove FROST is as secure as Schnorr's signature scheme
> in a single-party setting.


-- 
Tony Arcieri