Return-Path: <earonesty@gmail.com> Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id BB758EBD for <bitcoin-dev@lists.linuxfoundation.org>; 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 <bitcoin-dev@lists.linuxfoundation.org>; Tue, 10 Jul 2018 11:46:36 +0000 (UTC) Received: by mail-wm0-f51.google.com with SMTP id s13-v6so12425221wmc.1 for <bitcoin-dev@lists.linuxfoundation.org>; 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: <CAJowKgLrSe77sqO2iB7mYboo_HW=YjO4=AFdv7L5FUi2vygMiQ@mail.gmail.com> <08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de> <CAAS2fgSPUc7xRq36rZ9BVLjUTdd152Fgho4sjJXLhfrc71vPMw@mail.gmail.com> <CAJowKgL-nRcruXhWdGWrT4x+oV7i3jYST2Wa3bF5m6iT_mOyMw@mail.gmail.com> <CAPg+sBjdu4mnda-P0y7Ddu-rN7a1GiUt0hY_wYGsy_bJLKOYMA@mail.gmail.com> <CAJowKgLSQZ1LrZayDi7EFc-NSfK_AD+zBdyaF7jBeQRP7tOwYQ@mail.gmail.com> <CAPg+sBizrx20XShpeZRvZd4bfq1=E+MFUDmSC9X-xK1CSbV5kQ@mail.gmail.com> <CAJowKg+=7nS4gNmtc8a4-2cu1uCOPqxjfchFwDVqUciKNMUYWQ@mail.gmail.com> <CAJowKgJ3K=wmCEtoZXJZhrnnA8XJcHYg788KP+7MCeP4Mxf-0w@mail.gmail.com> <CAAS2fgSmA02s6Vdk_FYv6NJ4smLBgxnuT4jRYU44G7=bbzv2MA@mail.gmail.com> <CAJowKgJjQ8EGgbCurOSjTh8ij42_BVeD6dE0y67tzN0Zop3pyg@mail.gmail.com> <CAAS2fgRrkzq6Fa5T_-YDwLDkwi30LpDtMObMEBE+Fmmj0LJpBw@mail.gmail.com> <CAJowKgL0b3RT7XwRTF+ohoJCyZAW-ZJ+-8Lijj_s1rqqxgU7VQ@mail.gmail.com> In-Reply-To: <CAJowKgL0b3RT7XwRTF+ohoJCyZAW-ZJ+-8Lijj_s1rqqxgU7VQ@mail.gmail.com> From: Erik Aronesty <erik@q32.com> Date: Tue, 10 Jul 2018 07:46:17 -0400 Message-ID: <CAJowKg+UaMsY_nL6SBfb20Ltki+LdhXOwwvG_mAsUq_ww3Tesg@mail.gmail.com> To: Gregory Maxwell <greg@xiph.org> 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 <bitcoin-dev@lists.linuxfoundation.org> 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 <bitcoin-dev.lists.linuxfoundation.org> List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 <erik@q32.com> 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 <greg@xiph.org> wrote: > >> On Mon, Jul 9, 2018 at 4:33 PM, Erik Aronesty <erik@q32.com> 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 <div dir=3D"auto"><div>Basically you're just replacing addition with in= terpolation everywhere in the musig construction.<div dir=3D"auto"><br></di= v><div dir=3D"auto">But maybe I just don't understand how Wagner's = algorithm is relevant here.<br><div dir=3D"auto"><br></div></div><br><br><d= iv class=3D"gmail_quote"><div dir=3D"ltr">On Mon, Jul 9, 2018, 1:59 PM Erik= Aronesty <<a href=3D"mailto:erik@q32.com">erik@q32.com</a>> wrote:<b= r></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border= -left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">=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<div>=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</div> <div style=3D"text-decoration-style:initial;text-decoration-color:initial">= AH!</div><div style=3D"text-decoration-style:initial;text-decoration-color:= initial"><br></div><div style=3D"text-decoration-style:initial;text-decorat= ion-color:initial">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.</div><div style=3D"text-decoration-s= tyle:initial;text-decoration-color:initial"><br></div><div style=3D"text-de= coration-style:initial;text-decoration-color:initial">This hopefully should= preclude any sort of adaptive key attack.</div><div style=3D"text-decorati= on-style:initial;text-decoration-color:initial"><br></div><div style=3D"tex= t-decoration-style:initial;text-decoration-color:initial">From scratch:</di= v><div style=3D"text-decoration-style:initial;text-decoration-color:initial= "><br></div><div style=3D"text-decoration-style:initial;text-decoration-col= or:initial"> <div style=3D"font-size:12.8px;background-color:rgb(255,255,255);text-decor= ation-style:initial;text-decoration-color:initial">1. Has a public g^x'= </div><div style=3D"font-size:12.8px;background-color:rgb(255,255,255);text= -decoration-style:initial;text-decoration-color:initial">2. Computes and br= oadcasts g^k' ... where k' is a random number</div><div style=3D"fo= nt-size:12.8px;background-color:rgb(255,255,255);text-decoration-style:init= ial;text-decoration-color:initial">3. Computes r =3D g^k using lagrange int= erpolation (see=C2=A0<span>=C2=A0</span><span style=3D"font-size:small;back= ground-color:rgb(255,255,255);text-decoration-style:initial;text-decoration= -color:initial;float:none;display:inline"><a href=3D"http://crypto.stanford= .edu/~dabo/papers/homprf.pdf" style=3D"color:rgb(17,85,204)" target=3D"_bla= nk" rel=3D"noreferrer">http://crypto.stanford.edu/~dabo/papers/homprf.pdf</= a>)</span></div><div style=3D"font-size:12.8px;background-color:rgb(255,255= ,255);text-decoration-style:initial;text-decoration-color:initial"><span st= yle=3D"font-size:small;background-color:rgb(255,255,255);text-decoration-st= yle:initial;text-decoration-color:initial;float:none;display:inline">4. Com= putes H(r || M), as per standard schnorr</span></div><div style=3D"font-siz= e:12.8px;background-color:rgb(255,255,255);text-decoration-style:initial;te= xt-decoration-color:initial"><span style=3D"font-size:small;background-colo= r:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:init= ial;float:none;display:inline">5. Computes s' =3D k' - xe<span>=C2= =A0</span><span style=3D"text-decoration-style:initial;text-decoration-colo= r:initial;float:none;display:inline">, as per standard schnorr .. except k&= #39; is a "share"</span></span></div><div style=3D"font-size:12.8= px;background-color:rgb(255,255,255);text-decoration-style:initial;text-dec= oration-color:initial"><span style=3D"font-size:small;background-color:rgb(= 255,255,255);text-decoration-style:initial;text-decoration-color:initial;fl= oat:none;display:inline"><span style=3D"text-decoration-style:initial;text-= decoration-color:initial;float:none;display:inline">6. Publish (s', e, = g^x')</span></span></div></div><div style=3D"text-decoration-style:init= ial;text-decoration-color:initial"><div style=3D"font-size:12.8px;backgroun= d-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-colo= r:initial"><span style=3D"font-size:small;background-color:rgb(255,255,255)= ;text-decoration-style:initial;text-decoration-color:initial;float:none;dis= play:inline"><span style=3D"text-decoration-style:initial;text-decoration-c= olor:initial;float:none;display:inline"><br>Verification:</span></span></di= v><div style=3D"font-size:12.8px;background-color:rgb(255,255,255);text-dec= oration-style:initial;text-decoration-color:initial"><span style=3D"font-si= ze:small;background-color:rgb(255,255,255);text-decoration-style:initial;te= xt-decoration-color:initial;float:none;display:inline"><span style=3D"text-= decoration-style:initial;text-decoration-color:initial;float:none;display:i= nline"><br></span></span></div><div style=3D"font-size:12.8px;background-co= lor:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:in= itial"><span style=3D"font-size:small;background-color:rgb(255,255,255);tex= t-decoration-style:initial;text-decoration-color:initial;float:none;display= :inline"><span style=3D"text-decoration-style:initial;text-decoration-color= :initial;float:none;display:inline">With m of n share-signatures:</span></s= pan></div><div style=3D"font-size:12.8px;background-color:rgb(255,255,255);= text-decoration-style:initial;text-decoration-color:initial"><span style=3D= "font-size:small;background-color:rgb(255,255,255);text-decoration-style:in= itial;text-decoration-color:initial;float:none;display:inline"><span style= =3D"text-decoration-style:initial;text-decoration-color:initial;float:none;= display:inline"><br></span></span></div><div style=3D"font-size:12.8px;back= ground-color:rgb(255,255,255);text-decoration-style:initial;text-decoration= -color:initial"><span style=3D"font-size:small;background-color:rgb(255,255= ,255);text-decoration-style:initial;text-decoration-color:initial;float:non= e;display:inline"><span style=3D"text-decoration-style:initial;text-decorat= ion-color:initial;float:none;display:inline">1. Interpolation on m of n s&#= 39; shares to get s</span></span></div><div style=3D"font-size:12.8px;backg= round-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-= color:initial"><span style=3D"font-size:small;background-color:rgb(255,255,= 255);text-decoration-style:initial;text-decoration-color:initial;float:none= ;display:inline"><span style=3D"text-decoration-style:initial;text-decorati= on-color:initial;float:none;display:inline"><span style=3D"font-size:small;= background-color:rgb(255,255,255);text-decoration-style:initial;text-decora= tion-color:initial;float:none;display:inline">2. Interpolation on m of n g^= x' shares to get g^x</span><br></span></span></div><div style=3D"font-s= ize:12.8px;background-color:rgb(255,255,255);text-decoration-style:initial;= text-decoration-color:initial"><span style=3D"font-size:small;background-co= lor:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:in= itial;float:none;display:inline"><span style=3D"text-decoration-style:initi= al;text-decoration-color:initial;float:none;display:inline">3. Standard sch= norr verification</span></span></div> <br></div><div style=3D"text-decoration-style:initial;text-decoration-color= :initial">The actual public key of the "set of signers" is interp= olated.=C2=A0 =C2=A0<br></div><div style=3D"text-decoration-style:initial;t= ext-decoration-color:initial"><br></div><div style=3D"text-decoration-style= :initial;text-decoration-color:initial"><br></div></div><div class=3D"gmail= _extra"><br><div class=3D"gmail_quote">On Mon, Jul 9, 2018 at 12:58 PM, Gre= gory Maxwell <span dir=3D"ltr"><<a href=3D"mailto:greg@xiph.org" target= =3D"_blank" rel=3D"noreferrer">greg@xiph.org</a>></span> wrote:<br><bloc= kquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #cc= c solid;padding-left:1ex"><span>On Mon, Jul 9, 2018 at 4:33 PM, Erik Arones= ty <<a href=3D"mailto:erik@q32.com" target=3D"_blank" rel=3D"noreferrer"= >erik@q32.com</a>> wrote:<br> >>> with security assumptions that match the original Schnorr cons= truction more closely,<br> >> More closely than what?<br> </span>> More closely than musig.<br> <br> Musig is instructions on using the original schnorr construction for<br> multiparty signing which is secure against participants adaptively<br> choosing their keys, which is something the naive scheme of just<br> interpolating keys and shares is vulnerable to. It works as<br> preprocessing on the keys, then you continue on with the naive<br> protocol. The verifier (e.g. network consensus rules) is the same.<br> <br> Now that you're back to using a cryptographic hash, I think what<br> you're suggesting is "use naive interpolation of schnorr signature= s"<br> -- which you can do, including with the verifier proposed in the BIP,<br> but doing that alone is insecure against adaptive key choice (and<br> potentially adaptive R choice, depending on specifics which aren't<br> clear enough to me in your description). In particular, although it<br> seems surprising picking your interpolation locations with the hash of<br> each key isn't sufficient to prevent cancellation attacks due to the<br= > remarkable power of wagner's algorithm.<br> </blockquote></div><br></div> </blockquote></div></div></div> --0000000000009e50f80570a3ae94--