Re: [Cfrg] Call for adoption: Threshold Signatures

[Tim Ruffing <[e-mail]>]

(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:
https://eprint.iacr.org/2020/1261 

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.


Best,
Tim