Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id BB758EBD for ; Tue, 10 Jul 2018 11:46:37 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f51.google.com (mail-wm0-f51.google.com [74.125.82.51]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B31565D3 for ; Tue, 10 Jul 2018 11:46:36 +0000 (UTC) Received: by mail-wm0-f51.google.com with SMTP id s13-v6so12425221wmc.1 for ; Tue, 10 Jul 2018 04:46:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=q32-com.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=S0VVVFZApDHB55YZOlypkYHNNvnFg73np/qWy4W+s9U=; b=ZnIgg2DAumdmNVMsERsWtchg5ziHamojIL+hwrTvQMd/jPmM23XrwHsdJzqfCg2N2Z hq/L6wUuc7W+PuhpiFt+1W6sL4vGQNOCTeJda4ReIw0Wo1cuH93BOUUE5jZrL6F+EG6y +ikkh9wFXr7H8m4QMAZf9fX3IEZolpEir2zPvZ1YifoQ2wlUz+f88ZmqwCGEBP9pzPzS 9lkKXNNt+cGb1UNLNtczvOWrhLH3leYl7XihiZZekg1Lx813pltMbvKdCJx1UrheU/Fn fAkFB0WuNYpFB4d++uuNkVe5o6D6d2C/VLzqPhwSyqkAepwXgTep1ztD54+7pHAu9sem NntQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=S0VVVFZApDHB55YZOlypkYHNNvnFg73np/qWy4W+s9U=; b=niUhLo3Ap8uXrPj89ZpCiPIY0ynIqS832a1Rm8Mt11M5/eEArfuL3AqeFOSl409oDf sw/Pt1O5Xy7foMcc/+Bcd3vC4p433ugYKQjh6FwvBqxIfOJKiCMZOLTzYMEUhNApGxgd x63lSQMx+jgcsQfx90m0k1JKUJDQhEk0fTXCFyD/5sWaImYzWaTXrrbdd/haocX8NMQA Nl0oL1ZH7gzOPCtTVLidx04BtBYv7ioXsYaf+3ixIaazb0EQj94NPybPy4YPY8qo3glA eMM2uEw8FdyZLkuwoyKvEaE8a2ztoHAfAqmYFt7eKCZ7gOAD79FEm/ugPKMg+cimKrfu mjKw== X-Gm-Message-State: APt69E3YRHEwrEMrCSk9gOTVrsPD/XkHjmx4oqz6lUsd8eMotulR4Bm2 VeSCzhLquZf+mofSFrF5wS/CqeF37AwEbPApb/EYLsm0vA== X-Google-Smtp-Source: AAOMgpfNp7xVE+duO59QremfdRJ7vSIUv8Ik5ag/q+ASvd1uCZRrA6vQX0bk5LD2LOajn/Rc6tlsHT3Ev2V3PqAtEEc= X-Received: by 2002:a1c:cf81:: with SMTP id f123-v6mr15452483wmg.3.1531223195142; Tue, 10 Jul 2018 04:46:35 -0700 (PDT) MIME-Version: 1.0 References: <08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de> In-Reply-To: From: Erik Aronesty Date: Tue, 10 Jul 2018 07:46:17 -0400 Message-ID: To: Gregory Maxwell Content-Type: multipart/alternative; boundary="0000000000009e50f80570a3ae94" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Wed, 11 Jul 2018 01:40:20 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Multiparty signatures X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 10 Jul 2018 11:46:37 -0000 --0000000000009e50f80570a3ae94 Content-Type: text/plain; charset="UTF-8" Basically you're just replacing addition with interpolation everywhere in the musig construction. But maybe I just don't understand how Wagner's algorithm is relevant here. On Mon, Jul 9, 2018, 1:59 PM Erik Aronesty wrote: > - Adaptive r choice shouldn't be possible since r is derived from the > original threshold prf and it's not possible for a party to have any > adaptive impact on the value of r > - I'm guess I don't see how an attacker can use adaptive key choice in > this context either. Any modification of the key should be useless > AH! > > I forgot to include some assumptions. The important part here is that > each party only has a share of the private key and publishes a share of the > public key. > > This hopefully should preclude any sort of adaptive key attack. > > From scratch: > > 1. Has a public g^x' > 2. Computes and broadcasts g^k' ... where k' is a random number > 3. Computes r = g^k using lagrange interpolation (see > http://crypto.stanford.edu/~dabo/papers/homprf.pdf) > 4. Computes H(r || M), as per standard schnorr > 5. Computes s' = k' - xe , as per standard schnorr .. except k' is a > "share" > 6. Publish (s', e, g^x') > > Verification: > > With m of n share-signatures: > > 1. Interpolation on m of n s' shares to get s > 2. Interpolation on m of n g^x' shares to get g^x > 3. Standard schnorr verification > > The actual public key of the "set of signers" is interpolated. > > > > On Mon, Jul 9, 2018 at 12:58 PM, Gregory Maxwell wrote: > >> On Mon, Jul 9, 2018 at 4:33 PM, Erik Aronesty wrote: >> >>> with security assumptions that match the original Schnorr >> construction more closely, >> >> More closely than what? >> > More closely than musig. >> >> Musig is instructions on using the original schnorr construction for >> multiparty signing which is secure against participants adaptively >> choosing their keys, which is something the naive scheme of just >> interpolating keys and shares is vulnerable to. It works as >> preprocessing on the keys, then you continue on with the naive >> protocol. The verifier (e.g. network consensus rules) is the same. >> >> Now that you're back to using a cryptographic hash, I think what >> you're suggesting is "use naive interpolation of schnorr signatures" >> -- which you can do, including with the verifier proposed in the BIP, >> but doing that alone is insecure against adaptive key choice (and >> potentially adaptive R choice, depending on specifics which aren't >> clear enough to me in your description). In particular, although it >> seems surprising picking your interpolation locations with the hash of >> each key isn't sufficient to prevent cancellation attacks due to the >> remarkable power of wagner's algorithm. >> > > --0000000000009e50f80570a3ae94 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Basically you're just replacing addition with in= terpolation everywhere in the musig construction.

But maybe I just don't understand how Wagner's = algorithm is relevant here.



On Mon, Jul 9, 2018, 1:59 PM Erik= Aronesty <erik@q32.com> wrote:
=C2=A0- Adaptive r = choice shouldn't be possible since r is derived from the original thres= hold prf and it's not possible for a party to have any adaptive impact = on the value of r
=C2=A0- I'm guess I don't see how an attacker= can use adaptive key choice in this context either.=C2=A0 =C2=A0Any modifi= cation of the key should be useless
= AH!

I forgot to include some assumptions.=C2=A0 =C2=A0The im= portant part here is that each party only has a share of the private key an= d publishes a share of the public key.

This hopefully should= preclude any sort of adaptive key attack.

From scratch:

1. Has a public g^x'=
2. Computes and br= oadcasts g^k' ... where k' is a random number
3. Computes r =3D g^k using lagrange int= erpolation (see=C2=A0=C2=A0http://crypto.stanford.edu/~dabo/papers/homprf.pdf)

On Mon, Jul 9, 2018 at 12:58 PM, Gre= gory Maxwell <greg@xiph.org> wrote:
On Mon, Jul 9, 2018 at 4:33 PM, Erik Arones= ty <erik@q32.com> wrote:
>>> with security assumptions that match the original Schnorr cons= truction more closely,
>> More closely than what?
> More closely than musig.

Musig is instructions on using the original schnorr construction for
multiparty signing which is secure against participants adaptively
choosing their keys, which is something the naive scheme of just
interpolating keys and shares is vulnerable to. It works as
preprocessing on the keys, then you continue on with the naive
protocol. The verifier (e.g. network consensus rules) is the same.

Now that you're back to using a cryptographic hash, I think what
you're suggesting is "use naive interpolation of schnorr signature= s"
-- which you can do, including with the verifier proposed in the BIP,
but doing that alone is insecure against adaptive key choice (and
potentially adaptive R choice, depending on specifics which aren't
clear enough to me in your description). In particular, although it
seems surprising picking your interpolation locations with the hash of
each key isn't sufficient to prevent cancellation attacks due to the remarkable power of wagner's algorithm.

--0000000000009e50f80570a3ae94--