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"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Multiparty signatures
Precedence: list

--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&#39;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&#39;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 &lt;<a href=3D"mailto:erik@q32.com">erik@q3=
2.com</a>&gt; 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&#39;s algorithm shouldn&#39;t be applicable for a number of=
 reasons.=C2=A0 you can&#39;t birthday attack something where there&#39;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&#3=
9;re partitioning won&#39;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 &lt;<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&#39;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&#39;m choosing a random=
 number for C&#39;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&#39;t kn=
ow A or B... I only know their public keys.</div><div><br></div><div>I don&=
#39;t think it&#39;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">&lt;<a href=3D"mailto:adam.back@gmail.com" rel=3D"norefer=
rer noreferrer" target=3D"_blank">adam.back@gmail.com</a>&gt;</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 &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.or=
g" rel=3D"noreferrer noreferrer" target=3D"_blank">bitcoin-dev@lists.linuxf=
oundation.org</a>&gt; wrote:<br></div><span style=3D"font-family:sans-serif=
">&gt; Basically you&#39;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&#39;t do that without a delineariza=
tion mechanism to prevent adaptive public key choice being used to break th=
e scheme using Wagner&#39;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&#39; 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--