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>
	<CAMZUoK=iNgsZVb89gYRDUdZu0AkTGQ8cXqqbk3NXHEONBpO5ow@mail.gmail.com>
	<CAJowKgJBVdJbRvf5Y6dV4o5Jf1XyELNsT+vCrp4b-86ZYr+LYQ@mail.gmail.com>
	<CAJowKgKB1GDxvpQt1JjPr+cgyM8yztLtgJ_mZ8vsoCHyBdqkVA@mail.gmail.com>
	<CAJowKgJXzgQuxt3YMjUfOQRp4T_QybpWKpLq=x-EAif4HLNMcQ@mail.gmail.com>
In-Reply-To: <CAJowKgJXzgQuxt3YMjUfOQRp4T_QybpWKpLq=x-EAif4HLNMcQ@mail.gmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Wed, 25 Jul 2018 22:05:05 -0400
Message-ID: <CAJowKgLHadxeT4oEoQfwR62LqY9QTkrXihiBfAoHDYydqL2TNw@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000030f1ea0571dd6db5"
Subject: Re: [bitcoin-dev] Multiparty signatures
Precedence: list

--00000000000030f1ea0571dd6db5
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Also we don't need any new opcodes to support this.  Done right this could
literally go out into clients immediately.

On Fri, Jul 20, 2018, 4:18 PM Erik Aronesty <erik@q32.com> wrote:

> Sorry there were typos:
>
> - Using MuSig's solution for the blinding factor (e)
> - Using interpolation to enhance MuSig to be M of N instead of M of M
>
> References:
>
>  - MuSig
> https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-signatur=
es.html
>  - HomPrf http://crypto.stanford.edu/~dabo/papers/homprf.pdf (sections
> 7.1 and 7.4)
>
> Each party:
>
> 1. Publishes public key G*xi, G*ki, where ki is a random nonce
> 3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, for the purposes of
> interpolation
> 3. R =3D G*k =3D via interpolation of r1=3DGk1, r2=3DGk2... (see HomPrf)
> 4. L =3D H(X1,X2,=E2=80=A6) (see MuSig)
> 5. X =3D sum of all H(L,Xi)Xi (see MuSig)
> 6. Computes e =3D H(R | M | X) .... standard schnorr e... not a share
> 7. Computes si =3D ki *e+ xi * e ... where si is a "share" of the sig, an=
d
> xi is the private data, and e is the blinding factor
> 8. Publishes (si, e) as the share sig
>
> If an attacker has multiple devices, e is safe, because of the musig
> construction.
>
> But what protects k from the same multiparty birthday attack?
>
> If an attacker has multiple devices, by carefully controlling the
> selection of private keys, the attacker can try to solve
> the polynomial equation to force the selection of a "known k".
>
> A "known k" would allow an attacker to sign messages on his own.
>
> To fix this, we need to somehow "blind k as well".
>
> Does this work?
>
> The revision below seems to solve this problem.
>
> 1. Publishes public key G*xi, G*ki, where ki is a random nonce
> 3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, for the purposes of
> interpolation
> 3. R =3D G*k =3D via interpolation of r1=3DGk1, r2=3DGk2... (see HomPrf)
> 4. L =3D H(X1,X2,=E2=80=A6) (see MuSig)
> 5. L2 =3D H2(XN,XN-1,=E2=80=A6) (see MuSig... H2 is a "second hash")
> 6. X =3D sum of all H(L,Xi)Xi (see MuSig)
> 7. Computes e =3D H(R | M | X) .... standard schnorr e... not a share
> 8. Computes e2 =3D H(R | M | X2) ... a second blinding factor
> 9. Computes si =3D ki *e2 + xi * e ... where si is a "share" of the sig, =
and
> xi is the private data, and e, e2 are blinding factors
> 10. Publishes (si, e, e2) as the share sig
>
> The final signature is computed via interpolation, and e2 is can be
> subtracted to recover a "normal" schnor sig for the set of participants.
>
> Now there's no mechanism for a birthday attack on k.
>
>
>
> On Fri, Jul 20, 2018 at 1:34 PM, Erik Aronesty <erik@q32.com> wrote:
>
>> Hi, thanks for all the help.   I'm going to summarize again, and see if
>> we've arrived at the correct solution for an M of N "single sig" extensi=
on
>> of MuSig, which I think we have.
>>
>> - Using MuSig's solution for the blinding to solve the Wagner attack
>> - Using interpolation to enhance MuSig to be M of N instead of M of M
>>
>> References:
>>
>>  - MuSig
>> https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-signatu=
res.html
>>  - HomPrf http://crypto.stanford.edu/~dabo/papers/homprf.pdf (sections
>> 7.1 and 7.4)
>>
>> Each party:
>>
>> 1. Publishes public key G*xi
>> 3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, for the purposes o=
f
>> interpolation
>> 3. r =3D G*x =3D via interpolation of Gx1, Gx2... (see HomPrf)
>> 4. L =3D H(X1,X2,=E2=80=A6) (see MuSig)
>> 5. X =3D sum of all H(L,Xi)Xi (see MuSig)
>> 6. Computes e =3D H(r | M | X) .... standard schnorr e... not a share
>> 7. Computes si =3D xi - xe ... where si is a "share" of the sig, and xi =
is
>> the private data
>> 8. Publishes (si, e, G*Xi)
>>
>> Any party can then derive s from m of n shares, by interpolating, not
>> adding.
>>
>>
>>
>>
>

--00000000000030f1ea0571dd6db5
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto">Also we don&#39;t need any new opcodes to support this.=
=C2=A0 Done right this could literally go out into clients immediately.</di=
v><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Fri, Jul 20, 2018, 4:1=
8 PM Erik Aronesty &lt;<a href=3D"mailto:erik@q32.com">erik@q32.com</a>&gt;=
 wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>
<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
-color:initial">Sorry there were typos:</div><div style=3D"font-size:small;=
text-decoration-style:initial;text-decoration-color:initial"><br></div></di=
v><div style=3D"font-size:small;text-decoration-style:initial;text-decorati=
on-color:initial">- Using MuSig&#39;s solution for the blinding factor (e)<=
br></div><div style=3D"font-size:small;text-decoration-style:initial;text-d=
ecoration-color:initial">- Using interpolation to enhance MuSig to be M of =
N instead of M of M</div><div style=3D"font-size:small;text-decoration-styl=
e:initial;text-decoration-color:initial"></div><div style=3D"font-size:smal=
l;text-decoration-style:initial;text-decoration-color:initial"><br></div><d=
iv style=3D"font-size:small;text-decoration-style:initial;text-decoration-c=
olor:initial">References:</div><div style=3D"font-size:small;text-decoratio=
n-style:initial;text-decoration-color:initial"><br></div><div style=3D"font=
-size:small;text-decoration-style:initial;text-decoration-color:initial">=
=C2=A0- MuSig <a href=3D"https://blockstream.com/2018/01/23/musig-key-aggre=
gation-schnorr-signatures.html" target=3D"_blank" rel=3D"noreferrer">https:=
//blockstream.com/2018/01/23/musig-key-aggregation-schnorr-signatures.html<=
/a><br></div><div style=3D"font-size:small;text-decoration-style:initial;te=
xt-decoration-color:initial">=C2=A0- HomPrf <a href=3D"http://crypto.stanfo=
rd.edu/~dabo/papers/homprf.pdf" target=3D"_blank" rel=3D"noreferrer">http:/=
/crypto.stanford.edu/~dabo/papers/homprf.pdf</a> (sections 7.1 and 7.4)</di=
v><div style=3D"font-size:small;text-decoration-style:initial;text-decorati=
on-color:initial"><br></div><div style=3D"font-size:small;text-decoration-s=
tyle:initial;text-decoration-color:initial">Each <span class=3D"m_-66957066=
78382846522gmail-il">party</span>:</div><div style=3D"font-size:small;text-=
decoration-style:initial;text-decoration-color:initial"><br></div><div styl=
e=3D"font-size:small;text-decoration-style:initial;text-decoration-color:in=
itial">1. Publishes public key G*xi, G*ki, where ki is a random nonce<br></=
div><div style=3D"font-size:small;text-decoration-style:initial;text-decora=
tion-color:initial">3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, f=
or the purposes of interpolation</div><div style=3D"font-size:small;text-de=
coration-style:initial;text-decoration-color:initial">3. R =3D G*k =3D via =
interpolation of r1=3DGk1, r2=3DGk2... (see=C2=A0<span style=3D"background-=
color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:=
initial;float:none;display:inline">HomPrf</span>)</div><div style=3D"font-s=
ize:small;text-decoration-style:initial;text-decoration-color:initial">4. L=
 =3D H(X1,X2,=E2=80=A6) (see MuSig)<br></div><div style=3D"font-size:small;=
text-decoration-style:initial;text-decoration-color:initial">5. X =3D sum o=
f all H(L,Xi)Xi (<span style=3D"background-color:rgb(255,255,255);text-deco=
ration-style:initial;text-decoration-color:initial;float:none;display:inlin=
e">see MuSig</span>)</div><div style=3D"font-size:small;text-decoration-sty=
le:initial;text-decoration-color:initial">6. Computes e =3D H(R | M | X) ..=
.. standard schnorr e... not a share</div><div style=3D"font-size:small;tex=
t-decoration-style:initial;text-decoration-color:initial">7. Computes si =
=3D ki *e+ xi * e ... where si is a &quot;share&quot; of the sig, and xi is=
 the private data, and e is the blinding factor<br></div><div style=3D"font=
-size:small;text-decoration-style:initial;text-decoration-color:initial">8.=
 Publishes (si, e) as the share sig<br></div><div style=3D"font-size:small;=
text-decoration-style:initial;text-decoration-color:initial"><br></div><div=
>If an attacker has multiple devices, e is safe, because of the musig const=
ruction.</div><div><br></div><div>
<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
-color:initial">But what protects k from the same multiparty birthday attac=
k?=C2=A0=C2=A0</div><div style=3D"font-size:small;text-decoration-style:ini=
tial;text-decoration-color:initial"><br></div><div style=3D"font-size:small=
;text-decoration-style:initial;text-decoration-color:initial"></div></div><=
div style=3D"font-size:small;text-decoration-style:initial;text-decoration-=
color:initial">
<div style=3D"text-decoration-style:initial;text-decoration-color:initial">=
If an attacker has multiple devices, by carefully controlling the selection=
 of private keys, the attacker can try to solve <br></div><div style=3D"tex=
t-decoration-style:initial;text-decoration-color:initial">the polynomial eq=
uation to force the selection of a &quot;known k&quot;.<br><br></div><div s=
tyle=3D"text-decoration-style:initial;text-decoration-color:initial">A &quo=
t;known k&quot; would allow an attacker to sign messages on his own.</div><=
div style=3D"text-decoration-style:initial;text-decoration-color:initial"><=
br></div><div style=3D"text-decoration-style:initial;text-decoration-color:=
initial">To fix this, we need to somehow &quot;blind k as well&quot;.</div>=
<div style=3D"text-decoration-style:initial;text-decoration-color:initial">=
<br></div><div style=3D"text-decoration-style:initial;text-decoration-color=
:initial">Does this work?</div><div style=3D"text-decoration-style:initial;=
text-decoration-color:initial"><br></div><div style=3D"text-decoration-styl=
e:initial;text-decoration-color:initial">The revision below seems to solve =
this problem.<br></div><div style=3D"text-decoration-style:initial;text-dec=
oration-color:initial"><br></div><div style=3D"text-decoration-style:initia=
l;text-decoration-color:initial"></div><div style=3D"text-decoration-style:=
initial;text-decoration-color:initial">
<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
-color:initial">1. Publishes public key G*xi, G*ki, where ki is a random no=
nce<br></div><div style=3D"font-size:small;text-decoration-style:initial;te=
xt-decoration-color:initial">3. Xi =3D H(G*xi) ... Xi is the parties x coor=
dinate, for the purposes of interpolation</div><div style=3D"font-size:smal=
l;text-decoration-style:initial;text-decoration-color:initial">3. R =3D G*k=
 =3D via interpolation of r1=3DGk1, r2=3DGk2... (see=C2=A0<span style=3D"ba=
ckground-color:rgb(255,255,255);text-decoration-style:initial;text-decorati=
on-color:initial;float:none;display:inline">HomPrf</span>)</div><div style=
=3D"font-size:small;text-decoration-style:initial;text-decoration-color:ini=
tial">4. L =3D H(X1,X2,=E2=80=A6) (see MuSig)<br></div><div style=3D"font-s=
ize:small;text-decoration-style:initial;text-decoration-color:initial">
<div style=3D"text-decoration-style:initial;text-decoration-color:initial">=
5. L2 =3D H2(XN,XN-1,=E2=80=A6) (see MuSig... H2 is a &quot;second hash&quo=
t;)<br></div><div style=3D"text-decoration-style:initial;text-decoration-co=
lor:initial"></div>

6. X =3D sum of all H(L,Xi)Xi (<span style=3D"background-color:rgb(255,255,=
255);text-decoration-style:initial;text-decoration-color:initial;float:none=
;display:inline">see MuSig</span>)</div>7. Computes e =3D H(R | M | X) ....=
 standard schnorr e... not a share<div style=3D"font-size:small;text-decora=
tion-style:initial;text-decoration-color:initial">
<div style=3D"text-decoration-style:initial;text-decoration-color:initial">=
8. Computes e2 =3D H(R | M | X2) ... a second blinding factor<br></div><div=
 style=3D"text-decoration-style:initial;text-decoration-color:initial"></di=
v>

9. Computes si =3D ki *e2 + xi * e ... where si is a &quot;share&quot; of t=
he sig, and xi is the private data, and e, e2 are blinding factors<br></div=
><div style=3D"font-size:small;text-decoration-style:initial;text-decoratio=
n-color:initial">10. Publishes (si, e, e2) as the share sig<br></div><div s=
tyle=3D"font-size:small;text-decoration-style:initial;text-decoration-color=
:initial"><br></div><div style=3D"font-size:small;text-decoration-style:ini=
tial;text-decoration-color:initial">The final signature is computed via int=
erpolation, and e2 is can be subtracted to recover a &quot;normal&quot; sch=
nor sig for the set of participants.<br><br></div><div style=3D"font-size:s=
mall;text-decoration-style:initial;text-decoration-color:initial">Now there=
&#39;s no mechanism for a birthday attack on k.<br></div><div style=3D"font=
-size:small;text-decoration-style:initial;text-decoration-color:initial"><b=
r></div>

</div></div><br></div><div class=3D"gmail_extra"><br><div class=3D"gmail_qu=
ote">On Fri, Jul 20, 2018 at 1:34 PM, Erik Aronesty <span dir=3D"ltr">&lt;<=
a href=3D"mailto:erik@q32.com" target=3D"_blank" rel=3D"noreferrer">erik@q3=
2.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"m=
argin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"l=
tr"><div class=3D"gmail_extra">

<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
-color:initial">Hi, thanks for all the help.=C2=A0 =C2=A0I&#39;m going to s=
ummarize again, and see if we&#39;ve arrived at the correct solution for an=
 M of N &quot;single sig&quot; extension of MuSig, which I think we have.</=
div><div style=3D"font-size:small;text-decoration-style:initial;text-decora=
tion-color:initial"><br></div><div style=3D"font-size:small;text-decoration=
-style:initial;text-decoration-color:initial">- Using MuSig&#39;s solution =
for the blinding to solve the Wagner attack</div><div style=3D"font-size:sm=
all;text-decoration-style:initial;text-decoration-color:initial">- Using in=
terpolation to enhance MuSig to be M of N instead of M of M</div><div style=
=3D"font-size:small;text-decoration-style:initial;text-decoration-color:ini=
tial"><br></div><div style=3D"font-size:small;text-decoration-style:initial=
;text-decoration-color:initial">References:</div><div style=3D"font-size:sm=
all;text-decoration-style:initial;text-decoration-color:initial"><br></div>=
<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
-color:initial">=C2=A0- MuSig <a href=3D"https://blockstream.com/2018/01/23=
/musig-key-aggregation-schnorr-signatures.html" target=3D"_blank" rel=3D"no=
referrer">https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-=
signatures.html</a><br></div><div style=3D"font-size:small;text-decoration-=
style:initial;text-decoration-color:initial">=C2=A0- HomPrf <a href=3D"http=
://crypto.stanford.edu/~dabo/papers/homprf.pdf" target=3D"_blank" rel=3D"no=
referrer">http://crypto.stanford.edu/~dabo/papers/homprf.pdf</a> (sections =
7.1 and 7.4)</div><div style=3D"font-size:small;text-decoration-style:initi=
al;text-decoration-color:initial"><br></div><div style=3D"font-size:small;t=
ext-decoration-style:initial;text-decoration-color:initial">Each party:</di=
v><div style=3D"font-size:small;text-decoration-style:initial;text-decorati=
on-color:initial"><br></div><div style=3D"font-size:small;text-decoration-s=
tyle:initial;text-decoration-color:initial">1. Publishes public key G*xi</d=
iv><div style=3D"font-size:small;text-decoration-style:initial;text-decorat=
ion-color:initial">3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, fo=
r the purposes of interpolation</div><div style=3D"font-size:small;text-dec=
oration-style:initial;text-decoration-color:initial">3. r =3D G*x =3D via i=
nterpolation of Gx1, Gx2... (see=C2=A0<span style=3D"background-color:rgb(2=
55,255,255);text-decoration-style:initial;text-decoration-color:initial;flo=
at:none;display:inline">HomPrf</span>)</div><div style=3D"font-size:small;t=
ext-decoration-style:initial;text-decoration-color:initial">4. L =3D H(X1,X=
2,=E2=80=A6) (see MuSig)<br></div><div style=3D"font-size:small;text-decora=
tion-style:initial;text-decoration-color:initial">5. X =3D sum of all H(L,X=
i)Xi (<span style=3D"background-color:rgb(255,255,255);text-decoration-styl=
e:initial;text-decoration-color:initial;float:none;display:inline">see MuSi=
g</span>)</div><div style=3D"font-size:small;text-decoration-style:initial;=
text-decoration-color:initial">6. Computes e =3D H(r | M | X) .... standard=
 schnorr e... not a share</div><div style=3D"font-size:small;text-decoratio=
n-style:initial;text-decoration-color:initial">7. Computes si =3D xi - xe .=
.. where si is a &quot;share&quot; of the sig, and xi is the private data</=
div><div style=3D"font-size:small;text-decoration-style:initial;text-decora=
tion-color:initial">8. Publishes (si, e, G*Xi)</div><div style=3D"font-size=
:small;text-decoration-style:initial;text-decoration-color:initial"><br></d=
iv><div style=3D"font-size:small;text-decoration-style:initial;text-decorat=
ion-color:initial">Any party can then derive s from m of n shares, by inter=
polating, not adding.</div><div style=3D"font-size:small;text-decoration-st=
yle:initial;text-decoration-color:initial"><br></div><br class=3D"m_-669570=
6678382846522m_-4832618653516637091gmail-Apple-interchange-newline">

<br></div></div>
</blockquote></div><br></div>
</blockquote></div>

--00000000000030f1ea0571dd6db5--