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>
In-Reply-To: <CAJowKg+UaMsY_nL6SBfb20Ltki+LdhXOwwvG_mAsUq_ww3Tesg@mail.gmail.com>
Reply-To: adam@cypherspace.org
From: Adam Back <adam.back@gmail.com>
Date: Wed, 11 Jul 2018 11:35:08 +0100
Message-ID: <CALqxMTHYaspkn8JupaHBeLDxLOfZbnwcne2AVeFZe2ADOefktA@mail.gmail.com>
To: Erik Aronesty <erik@q32.com>,
	Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000b1147a0570b6cd6b"
Subject: Re: [bitcoin-dev] Multiparty signatures
Precedence: list

--000000000000b1147a0570b6cd6b
Content-Type: text/plain; charset="UTF-8"

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

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

<div dir=3D"auto"><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:bi=
tcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org<=
/a>&gt; wrote:<br></div><span style=3D"font-family:sans-serif">&gt; Basical=
ly you&#39;re just replacing addition with interpolation everywhere in the =
musig construction</span>=C2=A0<div dir=3D"auto"><br></div><div dir=3D"auto=
">Yes, but you can&#39;t do that without a delinearization mechanism to pre=
vent adaptive public key choice being used to break the 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 del=
inearization mechanism for an intuition, all public keys are hashed along w=
ith per value hash, so that pre-commits and forces the public keys to be no=
n-adaptively chosen.=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"aut=
o">Adaptively chosen public keys are dangerous and simple to exploit for ex=
ample 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.</div><div dir=3D"auto">=
<br></div><div dir=3D"auto">Btw Wagner also breaks this earlier delineariza=
tion scheme S=3DH(A)*A+H(B)*B+H(C)*C</div><div dir=3D"auto"><br></div><div =
dir=3D"auto">Adam</div></div>

--000000000000b1147a0570b6cd6b--