diff options
| author | Erik Aronesty <erik@q32.com> | 2018-07-19 08:24:39 -0400 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2018-07-19 12:24:54 +0000 |
| commit | 2886bd3cd5369f6b040ab5bb72201778c6b81a92 (patch) | |
| tree | bc9bf049cc50c573b541d15d56e1600400051c8c | |
| parent | 74ce8f7b6d9f82d5ba2517a61974e33931362a54 (diff) | |
| download | pi-bitcoindev-2886bd3cd5369f6b040ab5bb72201778c6b81a92.tar.gz pi-bitcoindev-2886bd3cd5369f6b040ab5bb72201778c6b81a92.zip | |
Re: [bitcoin-dev] Multiparty signatures
| -rw-r--r-- | 63/76df22de5d034d7a66db00c9eaac05e0951f69 | 234 |
1 files changed, 234 insertions, 0 deletions
diff --git a/63/76df22de5d034d7a66db00c9eaac05e0951f69 b/63/76df22de5d034d7a66db00c9eaac05e0951f69 new file mode 100644 index 000000000..a5477f41e --- /dev/null +++ b/63/76df22de5d034d7a66db00c9eaac05e0951f69 @@ -0,0 +1,234 @@ +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 562A6C3A + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 19 Jul 2018 12:24:54 +0000 (UTC) +X-Greylist: whitelisted by SQLgrey-1.7.6 +Received: from mail-wm0-f44.google.com (mail-wm0-f44.google.com [74.125.82.44]) + by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5B3FC784 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 19 Jul 2018 12:24:53 +0000 (UTC) +Received: by mail-wm0-f44.google.com with SMTP id h20-v6so6166631wmb.4 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 19 Jul 2018 05:24:53 -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=WZxiYH8jkzpvNaSbv7q4mXieujmKQpM3gu/v0djgsKU=; + b=Pl3/6CCwmQXbKJnrU2ZibKrku+QXgG/nKcY0x8iq9f/Vb9wcz5o06Z/9T80ibGsIyx + CzazOX7gdPjVCk7eK6RShj8nW8hLAtXQUIQolKCl8/5zrlUv2txMCk+wpmjIHyNr9CWi + zZySJ6xshI8v0JHqZJiD8zdz1BGRDnMkCFYJUVGvLSU7zBf+y7rM+/ez/JvDln1GaXN0 + I7IgUUiwerGUnrnwjGAmRG+q7uE2PEobXonphc+5OE0aB0RPdiK6alLYmErGyVPEwPYf + VdnTgTdq0zwBpaXaigzf51GUTxfeKdYOlzkry4HKI24mIwJt5wd0vBFLrfS6+TQ0hMPm + OsTg== +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=WZxiYH8jkzpvNaSbv7q4mXieujmKQpM3gu/v0djgsKU=; + b=IX5SDwvy3plII3/M7QcDJfs+8Z7zWN/YGznhFqfdiJ8MHTtTrdtfZ8HVu3QAHfyfmp + oZL32uENAziPSRNuw1mzBUHUi0ZdzClgQbN46Cmaq3r7xv5Mor8V7IyQw7nGB5mWHc7X + RONqwGUW/K170m5k8UyrZDgEa4gWl4iWtb1udN5aCtz8Os2vh6wuM3Sgoj49GATP9gPi + bNYVfTqhk7D3THt6JFc8BKzKk4GYEQdGVLoAFWgEeJq/q83LjlownOk9d+lBAXjjALqE + 7ZRH0aoKoq0Lm6ENmW97Yrl7PEVHz5TcrnHXVjNx7JwwWIbZ6eN6iQ3cS5rQIL1ScTOo + XzZw== +X-Gm-Message-State: AOUpUlHk3R7LutO4FtXYHERR/VQdBV9LSmfHokvUM8XiloeIjvpaZv6S + VkCcyKdVhPOQwxi2OJbarmEvjXKxpF/sT3LZFfUFVBVC1Q== +X-Google-Smtp-Source: AAOMgpdmOrazoIs0C/iQ2x0OxvF6sF2rtPkQGBdYQ/dAUDRtTFiULENgJir46qJr2l6R4GgzdLbTnOJ2iRmnv7piQtQ= +X-Received: by 2002:a1c:8952:: with SMTP id l79-v6mr3904764wmd.7.1532003091836; + Thu, 19 Jul 2018 05:24:51 -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> + <CAJowKg+UaMsY_nL6SBfb20Ltki+LdhXOwwvG_mAsUq_ww3Tesg@mail.gmail.com> + <CALqxMTHYaspkn8JupaHBeLDxLOfZbnwcne2AVeFZe2ADOefktA@mail.gmail.com> + <CAJowKg+rC9rmv--NxtrFQ=ea4B20u0ozkmA5hARpA4wLinnVQg@mail.gmail.com> + <CAJowKg+QxcU0ECpZrvUckXQfBpn6Qri=gWzLA7+Y2mvTAq_mSw@mail.gmail.com> +In-Reply-To: <CAJowKg+QxcU0ECpZrvUckXQfBpn6Qri=gWzLA7+Y2mvTAq_mSw@mail.gmail.com> +From: Erik Aronesty <erik@q32.com> +Date: Thu, 19 Jul 2018 08:24:39 -0400 +Message-ID: <CAJowKgJO8o4coqsB_jpBiQKMQOggq9gG+Bde+EbymhUauK94mA@mail.gmail.com> +To: adam@cypherspace.org +Content-Type: multipart/alternative; boundary="000000000000157453057159441b" +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: Thu, 19 Jul 2018 12:51:32 +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: Thu, 19 Jul 2018 12:24:54 -0000 + +--000000000000157453057159441b +Content-Type: text/plain; charset="UTF-8" + +Probably because my descriptions are a bit vague and rambling. + +but I can't help but think that a SMC of a bitcoin private key, followed by +a secure multiparty computation of a signature is going to be more secure +overall. + +I couldn't figure out how to do it offline. But one round of exchange +seems to work. + +It comes down to the blinding factor (k). All parties need to agree to it +... which creates the second round. + +On Thu, Jul 19, 2018, 8:16 AM Erik Aronesty <erik@q32.com> wrote: + +> Also Wagner's algorithm shouldn't be applicable for a number of reasons. +> you can't birthday attack something where there's only a single variable +> that you can modify. And when you change the equation from additive you +> now have a multi-dimensional equation we're partitioning won't function. +> this is the basis of the perfect security of Shamir secret sharing. +> +> On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty <erik@q32.com> wrote: +> +>> OK, so you're going with this scenario: +>> +>> 1. I know Apub and Bpub, +>> 2. I know M is 3 +>> 3. I'm choosing a random number for C's private key +>> +>> Cpub is g^C +>> +>> The equation I am solving for .. and trying to factor myself out of is +>> g^Ax + g^B*2 + g^C*3 +>> +>> I don't know A or B... I only know their public keys. +>> +>> I don't think it's possible to adaptively choose C for an attack on the +>> multisig construction, when using hash of the public key as the X +>> coordinate in the polynomial, because in order to satisfy the equation and +>> factor out C, you would need to be able to break the hash. +>> +>> With an additive construction, yes... adaptive attacks are possible. +>> But in a shamir secret sharing interpolation, you need a public X +>> coordinate as well as a secret share. Choosing hash(pub) as X, prevents +>> this attack. +>> +>> +>> On Wed, Jul 11, 2018 at 6:35 AM, Adam Back <adam.back@gmail.com> wrote: +>> +>>> On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev < +>>> bitcoin-dev@lists.linuxfoundation.org> wrote: +>>> > Basically you're just replacing addition with interpolation everywhere +>>> in the musig construction +>>> +>>> Yes, but you can't do that without a delinearization mechanism to +>>> prevent adaptive public key choice being used to break the scheme using +>>> Wagner's attack. It is not specific to addition, it is a generalized +>>> birthday attack. +>>> +>>> Look at the delinearization mechanism for an intuition, all public keys +>>> are hashed along with per value hash, so that pre-commits and forces the +>>> public keys to be non-adaptively chosen. +>>> +>>> Adaptively chosen public keys are dangerous and simple to exploit for +>>> example pub keys A+B, add party C' he chooses C=C'-A-B, now we can sign for +>>> A+B+C using adaptively chose public key C. +>>> +>>> Btw Wagner also breaks this earlier delinearization scheme +>>> S=H(A)*A+H(B)*B+H(C)*C +>>> +>>> Adam +>>> +>> +>> + +--000000000000157453057159441b +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"auto">Probably because my descriptions are a bit vague and ramb= +ling.<div dir=3D"auto"><br></div><div dir=3D"auto">but I can't help but= + think that a SMC of a bitcoin private key, followed by a secure multiparty= + computation of a signature is going to be more secure overall.</div><div d= +ir=3D"auto"><br></div><div dir=3D"auto">I couldn't figure out how to do= + it offline.=C2=A0 But one round of exchange seems to work.</div><div dir= +=3D"auto"><br></div><div dir=3D"auto">It comes down to the blinding factor = +(k).=C2=A0 All parties need to agree to it ... which creates the second rou= +nd.</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Thu, Jul = +19, 2018, 8:16 AM Erik Aronesty <<a href=3D"mailto:erik@q32.com">erik@q3= +2.com</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"ma= +rgin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"au= +to">Also Wagner's algorithm shouldn't be applicable for a number of= + reasons.=C2=A0 you can't birthday attack something where there's o= +nly a single variable that you can modify.=C2=A0 =C2=A0 And when you change= + the equation from additive you now have a multi-dimensional equation we= +9;re partitioning won't function.=C2=A0 this is the basis of the perfec= +t security of Shamir secret sharing.</div><br><div class=3D"gmail_quote"><d= +iv dir=3D"ltr">On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty <<a href=3D"= +mailto:erik@q32.com" target=3D"_blank" rel=3D"noreferrer">erik@q32.com</a>&= +gt; wrote:<br></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">OK, so = +you're going with this scenario:<br><div><br></div><div>1. I know Apub = +and Bpub,</div><div>2. I know M is 3</div><div>3. I'm choosing a random= + number for C's private key</div><div><br></div><div>Cpub is g^C</div><= +div><br></div><div>The equation I am solving for .. and trying to factor my= +self out of is g^Ax + g^B*2 + g^C*3</div><div><br></div><div>I don't kn= +ow A or B... I only know their public keys.</div><div><br></div><div>I don&= +#39;t think it's possible to adaptively choose C for an attack on the m= +ultisig construction, when using=C2=A0hash of the public key as the X coord= +inate in the polynomial, because in order to satisfy the equation and facto= +r out C, you would need to be able to break the hash.</div><div><br></div><= +div>With an additive construction, yes... adaptive attacks are possible.=C2= +=A0 =C2=A0But in a shamir secret sharing interpolation, you need a public X= + coordinate as well as a secret share.=C2=A0 =C2=A0Choosing hash(pub) as X,= + prevents this attack.</div><div><br></div></div><div class=3D"gmail_extra"= +><br><div class=3D"gmail_quote">On Wed, Jul 11, 2018 at 6:35 AM, Adam Back = +<span dir=3D"ltr"><<a href=3D"mailto:adam.back@gmail.com" rel=3D"norefer= +rer noreferrer" target=3D"_blank">adam.back@gmail.com</a>></span> wrote:= +<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-lef= +t:1px #ccc solid;padding-left:1ex"><div dir=3D"auto"><span><div dir=3D"ltr"= + style=3D"font-family:sans-serif">On Wed, Jul 11, 2018, 02:42 Erik Aronesty= + via bitcoin-dev <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.or= +g" rel=3D"noreferrer noreferrer" target=3D"_blank">bitcoin-dev@lists.linuxf= +oundation.org</a>> wrote:<br></div><span style=3D"font-family:sans-serif= +">> Basically you're just replacing addition with interpolation ever= +ywhere in the musig construction</span>=C2=A0<div dir=3D"auto"><br></div></= +span><div dir=3D"auto">Yes, but you can't do that without a delineariza= +tion mechanism to prevent adaptive public key choice being used to break th= +e scheme using Wagner's attack. It is not specific to addition, it is a= + generalized birthday attack.</div><div dir=3D"auto"><br></div><div dir=3D"= +auto">Look at the delinearization mechanism for an intuition, all public ke= +ys are hashed along with per value hash, so that pre-commits and forces the= + public keys to be non-adaptively chosen.=C2=A0</div><div dir=3D"auto"><br>= +</div><div dir=3D"auto">Adaptively chosen public keys are dangerous and sim= +ple to exploit for example pub keys A+B, add party C' he chooses C=3DC&= +#39;-A-B, now we can sign for A+B+C using adaptively chose public key C.</d= +iv><div dir=3D"auto"><br></div><div dir=3D"auto">Btw Wagner also breaks thi= +s earlier delinearization scheme S=3DH(A)*A+H(B)*B+H(C)*C</div><span class= +=3D"m_5467970328507897024m_-2119242826565656256HOEnZb"><font color=3D"#8888= +88"><div dir=3D"auto"><br></div><div dir=3D"auto">Adam</div></font></span><= +/div> +</blockquote></div><br></div> +</blockquote></div> +</blockquote></div> + +--000000000000157453057159441b-- + |