Re: [Cfrg] Call for adoption: Threshold Signatures

Tim Ruffing <> Wed, 28 October 2020 17:31 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id E636E3A0045 for <>; Wed, 28 Oct 2020 10:31:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 0TsEVNpkJb-G for <>; Wed, 28 Oct 2020 10:31:29 -0700 (PDT)
Received: from ( [IPv6:2001:67c:2050::465:201]) (using TLSv1.2 with cipher ECDHE-RSA-CHACHA20-POLY1305 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 269FE3A003E for <>; Wed, 28 Oct 2020 10:31:28 -0700 (PDT)
Received: from ( [IPv6:2001:67c:2050:105:465:1:1:0]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-384) server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by (Postfix) with ESMTPS id 4CLwbf0RqvzQlWQ for <>; Wed, 28 Oct 2020 18:31:26 +0100 (CET)
X-Virus-Scanned: amavisd-new at
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=MBO0001; t=1603906283; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=6N9hUx8FY6YTqc8zwWOdbVUZSboHqkdOlglyy9Y3hKk=; b=AcNBrGmvJXucNkZ1v3ngb1wwIvTTbMeH8cZDtDT9W4ik2w3oVjMfp5mOdTbU5oAndfUaCA EOue/JejRuoJnj4TCPEPl0XIlTkmZ2m7VfkMscoiYy6mZ/YCxnUtOrvoXRK0BtFr0uP7GR ba4Qq44z0cF3i3el7SWBIrNgxsPxPZ/e+R+c1WXJ/7Rk8wLxhryzfN+K3XtPomToFPZpP3 ++0ud1ggeVXvdLsMsmg9S9eHudP23Ra2SfjdAIXH2uGaFtD9BkNm6epQn1+Hyc8z+USVkC Y6VMzZlVxSdbAtrqAaJLJUnEvtTrz/CciGJFbyv3G/KnSWjDLymsu9CS2DzuUQ==
Received: from ([]) by ( []) (amavisd-new, port 10030) with ESMTP id y0k6QSoLl3Cy for <>; Wed, 28 Oct 2020 18:31:21 +0100 (CET)
Message-ID: <>
From: Tim Ruffing <>
Date: Wed, 28 Oct 2020 18:31:19 +0100
Content-Type: text/plain; charset="UTF-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
X-Rspamd-Score: -1.95 / 15.00 / 15.00
X-Rspamd-Queue-Id: C8BA917E6
X-Rspamd-UID: 022419
Archived-At: <>
Subject: Re: [Cfrg] Call for adoption: Threshold Signatures
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 28 Oct 2020 17:31:31 -0000

(Sorry for starting this as a new thread, I was not subscribed to the
list before, so I can't easily reply to an existing message.)

Let me chime in since MuSig2 was brought up here. As mentioned, we have
an independent proof of a variant of 1.5-DWMS, which we call MuSig2.
Since it's "1.5", it's more similar to FROST than 1.5-DWMS: 

The main difference between MuSig2 and 1.5-DWMS is that we use key
aggregation with delinearization, so we don't need a KOSK assumption or
proofs of possession.  

We provide two proofs, one in the ROM for 4 witnesses (we call them
nonces) and one in ROM+AGM for 2 witnesses. But the reason why we need
4 witnesses (think 3.5-DWMS) is our way of doing key aggregation, which
means we need to use the forking lemma twice. As soon as you assume
KOSK or proofs of possession, it *should* be possible to use 2
witnesses even with our ROM-only proof (but the devil can be in details
as usual with provable security...). 

I think none of these three security proofs for multisignature schemes
should be seen as strong indication that FROST is secure. The FROST
paper is certainly better for judging the security of FROST, even
though the proof uses a non-standard heuristic. Threshold signatures
are a different beast than multisignatures. 

But I certainly believe these three proofs plus the FROST proof confirm
the idea that using a linear combination is a valid defense against
attacks on concurrent sessions. In that sense, our ROM+AGM proof
indicates that 1.5 is indeed enough.

Since we're interested in threshold signatures we may or may not try to
write up a proof in the future that a threshold variant of MuSig2
(which is essentially FROST with delinearized key aggregation) is
secure. I conjecture that this is doable, at least if you additionally
add proofs of possession. 

Why have delinearized key aggregation plus proofs of possession, you
may ask. I think in the applications in Bitcoin that we have in mind,
we're mostly interested in having unified key aggregation procedure
that works for threshold signatures and also works for multisignatures
in a non-interactive way. Since you need interactive setup anyway for
threshold signatures, you could simply add proofs of possession there
but retain the delinearized key aggregation to be compatible to
multisignatures which support non-interactive key aggregation. I wonder
if this aspect is something that the CFRG wants to consider, too.

> c) are you willing to help work on this item and/or review it

In principle yes, because I'm anyway interested in following
discussions around threshold signatures.