MIME-Version: 1.0
Sender: earonesty@gmail.com
In-Reply-To: <CAJowKg+=7nS4gNmtc8a4-2cu1uCOPqxjfchFwDVqUciKNMUYWQ@mail.gmail.com>
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>
From: Erik Aronesty <erik@q32.com>
Date: Mon, 9 Jul 2018 11:02:30 -0400
Message-ID: <CAJowKgJ3K=wmCEtoZXJZhrnnA8XJcHYg788KP+7MCeP4Mxf-0w@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000083bef80570924dd6"
Subject: Re: [bitcoin-dev] Multiparty signatures
Precedence: list

--00000000000083bef80570924dd6
Content-Type: text/plain; charset="UTF-8"

Actually, it looks like in order to compute a multiparty signature you will
need to broadcast shares of r first, so it's not offline :(

It is still seems, to me, to be a simpler mechanism than musig - with
security assumptions that match the original Schnorr construction more
closely, and should therefore be easier to prove secure in a multiparty
context.

Shamir/Schnorr threshold multi-signature scheme:

Each party:

- Has a public key g*x', where x' is their private key, and where H(g*x)
can be considered their public index for the purposes of Shamir polynomial
interpolation
- Rolls a random k' and compute r' = g*k'
- Broadcast r' as a share
- Computes g*k, via lagrange interpolation across shares.   At this point k
is not known to any party unless Shamir is vulnerable or DL is not hard
- Computes e' = H(M) * r'
- Computes s' = k'-x*e'
- Share of signature is (s', e')

Verification is the same as Scnhorr, but only after using interpolation to
get the needed (s, e, g*x) from shares of s', e' and g*x':

- Using lagrange interpolation, compute the public key g*x
- Again, using lagrange interpolation, compute (s, e)
- Verify the signature as per standard Schnorr

Security assumptions:

 - Because this is not additive, and instead we are using Shamir
combination, the additional blinding and masking steps of musig are not
needed to create a secure scheme.
 - The scheme is the same as Schnorr otherwise
 - The only thing to prove is that H(M) * r does not reveal any information
about k ... which relies on the same DL assumptions as Bitcoin itself
 - Overall, this seems, to me at least, to have a smaller attack surface
because there's fewer moving parts


On Mon, Jul 9, 2018 at 8:24 AM, Erik Aronesty <erik@q32.com> wrote:

> I was hoping that nobody in this group saw an obvious problem with it then
> I'd sit down and try to write up a paper.
>
> Not that hard to just reuse the work done on schnorr.   And demonstrate
> that there are no additional assumptions.
>
> On Mon, Jul 9, 2018, 12:40 AM Pieter Wuille <pieter.wuille@gmail.com>
> wrote:
>
>> On Sun, Jul 8, 2018, 21:29 Erik Aronesty <erik@q32.com> wrote:
>>
>>> Because it's non-interactive, this construction can produce multisig
>>> signatures offline.   Each device produces a signature using it's own
>>> k-share and x-share.   It's only necessary to interpolate M of n shares.
>>>
>>> There are no round trips.
>>>
>>> The security is Shamir + discrete log.
>>>
>>> it's just something I've been tinkering with and I can't see an obvious
>>> problem.
>>>
>>> It's basically the same as schnorr, but you use a threshold hash to fix
>>> the need to be online.
>>>
>>> Just seems more useful to me.
>>>
>>
>> That sounds very useful if true, but I don't think we should include
>> novel cryptography in Bitcoin based on your not seeing an obvious problem
>> with it.
>>
>> I'm looking forward to seeing a more complete writeup though.
>>
>> Cheers,
>>
>> --
>> Pieter
>>
>>
>>

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

<div dir=3D"ltr"><div>Actually, it looks like in order to compute a multipa=
rty signature you will need to broadcast shares of r first, so it&#39;s not=
 offline :(</div><div><br></div><div>It is still seems, to me, to be a simp=
ler mechanism than musig - with security assumptions that match the origina=
l Schnorr construction more closely, and should therefore be easier to prov=
e secure in a multiparty context.</div><div><br></div><div>Shamir/Schnorr t=
hreshold multi-signature scheme:<br></div><div><br></div><div>Each party:</=
div><div><br></div><div>- Has a public key g*x&#39;, where x&#39; is their =
private key, and where H(g*x) can be considered their public index for the =
purposes of Shamir polynomial interpolation</div><div>- Rolls a random k&#3=
9; and compute r&#39; =3D g*k&#39;<br></div><div>- Broadcast r&#39; as a sh=
are</div><div>- Computes g*k, via lagrange interpolation across shares.=C2=
=A0 =C2=A0At this point k is not known to any party unless Shamir is vulner=
able or DL is not hard</div><div>- Computes e&#39; =3D H(M) * r&#39;</div><=
div>- Computes s&#39; =3D k&#39;-x*e&#39;</div><div>- Share of signature is=
 (s&#39;, e&#39;)</div><div><br></div><div>Verification is the same as Scnh=
orr, but only after using interpolation to get the needed (s, e, g*x) from =
shares of s&#39;, e&#39; and g*x&#39;:</div><div><br></div><div>

<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
-color:initial">- Using lagrange interpolation, compute the public key g*x<=
/div>- Again, using lagrange interpolation, compute (s, e)=C2=A0</div><div>=
- Verify the signature as per standard Schnorr</div><div><br></div><div>Sec=
urity assumptions:<br></div><div><br></div><div>=C2=A0- Because this is not=
 additive, and instead we are using Shamir combination, the additional blin=
ding and masking steps of musig are not needed to create a secure scheme.=
=C2=A0=C2=A0<br></div><div>=C2=A0- The scheme is the same as Schnorr otherw=
ise</div><div>=C2=A0- The only thing to prove is that H(M) * r does not rev=
eal any information about k ... which relies on the same DL assumptions as =
Bitcoin itself</div><div>=C2=A0- Overall, this seems, to me at least, to ha=
ve a smaller attack surface because there&#39;s fewer moving parts</div><di=
v>=C2=A0</div></div><div class=3D"gmail_extra"><br><div class=3D"gmail_quot=
e">On Mon, Jul 9, 2018 at 8:24 AM, Erik Aronesty <span dir=3D"ltr">&lt;<a h=
ref=3D"mailto:erik@q32.com" target=3D"_blank">erik@q32.com</a>&gt;</span> w=
rote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;borde=
r-left:1px #ccc solid;padding-left:1ex"><div dir=3D"auto">I was hoping that=
 nobody in this group saw an obvious problem with it then I&#39;d sit down =
and try to write up a paper.=C2=A0=C2=A0<div dir=3D"auto"><br></div><div di=
r=3D"auto">Not that hard to just reuse the work done on schnorr.=C2=A0 =C2=
=A0And demonstrate that there are no additional assumptions.</div></div><di=
v class=3D"HOEnZb"><div class=3D"h5"><br><div class=3D"gmail_quote"><div di=
r=3D"ltr">On Mon, Jul 9, 2018, 12:40 AM Pieter Wuille &lt;<a href=3D"mailto=
:pieter.wuille@gmail.com" target=3D"_blank">pieter.wuille@gmail.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"auto"><div clas=
s=3D"gmail_quote" dir=3D"auto"><div dir=3D"ltr">On Sun, Jul 8, 2018, 21:29 =
Erik Aronesty &lt;<a href=3D"mailto:erik@q32.com" rel=3D"noreferrer" target=
=3D"_blank">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"auto">Because it&#39;s non-interactive, this construction =
can produce multisig signatures offline.=C2=A0 =C2=A0Each device produces a=
 signature using it&#39;s own k-share and x-share.=C2=A0 =C2=A0It&#39;s onl=
y necessary to interpolate M of n shares.<div dir=3D"auto"><br></div><div d=
ir=3D"auto">There are no round trips.<br><div dir=3D"auto"><br></div><div d=
ir=3D"auto">The security is Shamir + discrete log.=C2=A0=C2=A0</div><div di=
r=3D"auto"><div dir=3D"auto"><br></div><div dir=3D"auto">it&#39;s just some=
thing I&#39;ve been tinkering with and I can&#39;t see an obvious problem.=
=C2=A0=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto">It&#39;s ba=
sically the same as schnorr, but you use a threshold hash to fix the need t=
o be online.</div><div dir=3D"auto"><br></div><div dir=3D"auto">Just seems =
more useful to me.</div></div></div></div></blockquote></div><div dir=3D"au=
to"><br></div><div dir=3D"auto">That sounds very useful if true, but I don&=
#39;t think we should include novel cryptography in Bitcoin based on your n=
ot seeing an obvious problem with it.</div><div dir=3D"auto"><br></div><div=
 dir=3D"auto">I&#39;m looking forward to seeing a more complete writeup tho=
ugh.</div><div dir=3D"auto"><br></div><div dir=3D"auto">Cheers,</div><div d=
ir=3D"auto"><br></div><div dir=3D"auto">--=C2=A0</div><div dir=3D"auto">Pie=
ter</div><div dir=3D"auto"><br></div><div dir=3D"auto"><br></div><div class=
=3D"gmail_quote" dir=3D"auto"><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class=3D"=
gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;b=
order-left:1px #ccc solid;padding-left:1ex"><div dir=3D"auto"><div class=3D=
"gmail_quote" dir=3D"auto"><blockquote class=3D"gmail_quote" style=3D"margi=
n:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
</blockquote></div></div>
</blockquote></div>
</blockquote></div></div>
</blockquote></div>
</div></div></blockquote></div><br></div>

--00000000000083bef80570924dd6--