MIME-Version: 1.0
References: <CAPg+sBj7f+=OYXuOMdNeJk3NBG67FSQSF8Xv3seFCvwxCWq69A@mail.gmail.com>
	<2e620d305c86f65cbff44b5fba548dc85c118f84.camel@timruffing.de>
	<20180812163734.GV499@boulet.lan>
	<CAJowKg+h11YkwOo-gyWCw+87Oh-9K34LOnJ1730hhpoVR2m5sA@mail.gmail.com>
	<20180903000518.GB18522@boulet.lan>
	<CAJowKg+PDtEV3je_N9Ra6u3n4+ZQ3ozYapt8ivxGYYU28Qad+w@mail.gmail.com>
	<CAAS2fgT0uBGbLBOW4TxA-qCzOLwoQ1qSV-R0dMKRzPLAm_UOqQ@mail.gmail.com>
	<CAJowKg+-45h6vraL1PpnqfhHSbG+G40L+FD7xN+C-Dn1E6Y_Vg@mail.gmail.com>
	<CAAS2fgSfdfQ2CiEabjrjspQGQufwzk84f1mzM1j_LRWqAPd8wA@mail.gmail.com>
In-Reply-To: <CAAS2fgSfdfQ2CiEabjrjspQGQufwzk84f1mzM1j_LRWqAPd8wA@mail.gmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Tue, 11 Sep 2018 13:20:01 -0400
Message-ID: <CAJowKgK3Pxev4pDH4xVLPvmHda8oAfq=fya4TY+_dodUJ7j9Nw@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>
Content-Type: multipart/alternative; boundary="0000000000001260b305759bb0e7"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Schnorr signatures BIP
Precedence: list

--0000000000001260b305759bb0e7
Content-Type: text/plain; charset="UTF-8"

Greg,

I added, stripped out, and added analogous musig delinearization 3 times in
response to stuff posted here.  I'm adding it back now. Not sure why my
head is thick around that issue.

The security advantages of a redistributable threshold system are huge.
If a system isn't redistributable, then a single lost or compromised key
results in lost coins... meaning the system is essetntially unusable.

I'm actually worried that Bitcoin releases a multisig that encourages loss.


On Tue, Sep 11, 2018 at 1:00 PM Gregory Maxwell <greg@xiph.org> wrote:

> On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty <erik@q32.com> wrote:
>
>> To answer points:
>>
>> - I switched to the medium article so that I could correct, edit and
>> improve things to make them more clear.
>> - I responded to feedback by modifying the protocol to make it work - not
>> by ignoring it.
>>
>
> To this moment there remains no response at your post.
> https://bitcointalk.org/index.php?topic=4973123.0
>
> I'm not sure how I am supposted to have figured out that you wrote a
> somewhat different repost of it elsewhere...
>
> - An M-1 rogue-key attack would require the attacker would to either
>>
>>   - attack the hash function to produce a predictable R based on a known
>> mesage
>>   - attack the DLP to influence x or k
>>
>> Neither attack gives any particular advantage to someone who has M-1 keys.
>>
>
> You keep asserting this. It isn't true. Asserting it more does not make it
> any more true.  I already explained how to attack this style of signature
> (e.g. in the BCT thread).
>
> Set aside your 'interpolation' for a moment, and imagine that you
> construct a 2 of 2 signature by just adding the keys.  Your tell me your
> key, P1  and then I tell you that my key P2 which I derived by computing
> -P1  + xG.   We now compute P = P1 + P2 = P1 + -P1 + xG = xG ... and now in
> spite adding P1 with an unknown discrete log, I know the discrete log of P
> with respect to G and I did not need to violate the standard DL security
> assumption to achieve that.
>
> With the 'interpolation' in effect the same attack applies but its
> execution is somewhat more complex: instead of adding the negation of P1  I
> must add a number of multiplicities of P1 (like P1*2, P1*3, P1*4...)
> selected so that their interpolation coefficients add up to -1. Finding a
> suitable subset requires solving a randomized modular subset sum problem
> and Wagner's algorithm provides a computationally tractable solution to it.
>
> The potential of rogue keys applies to both the keys themselves and to the
> nonces. There are several ways to prevent these attacks, the musig paper
> describes a delinearization technique which doesn't require additional
> interaction or communication.
>
> I haven't tested whether the R,s version is susceptible though.
>>
>
> There is a perfect bijection between the two encodings which is easily
> computable, so they're the same thing from an abstract security perspective.
>
>

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

<div dir=3D"ltr"><div>Greg, <br></div><div><br></div><div>I added, stripped=
 out, and added analogous musig delinearization 3 times in response to stuf=
f posted here.=C2=A0 I&#39;m adding it back now. Not sure why my head is th=
ick around that issue.<br></div><div></div><div><br></div><div>The security=
 advantages of a redistributable threshold system are huge.=C2=A0=C2=A0 If =
a system isn&#39;t redistributable, then a single lost or compromised key r=
esults in lost coins... meaning the system is essetntially unusable.</div><=
div><br></div><div>I&#39;m actually worried that Bitcoin releases a multisi=
g that encourages loss.<br></div><div><br></div><div><br></div><div><br></d=
iv></div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Tue, Sep 11, 20=
18 at 1:00 PM Gregory Maxwell &lt;<a href=3D"mailto:greg@xiph.org">greg@xip=
h.org</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"lt=
r"><div dir=3D"ltr">On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty &lt;<a hr=
ef=3D"mailto:erik@q32.com" target=3D"_blank">erik@q32.com</a>&gt; wrote:<br=
><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"marg=
in:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1e=
x"><div dir=3D"ltr">
<div>To answer points:</div><div><br></div><div>- I switched to the medium =
article so that I could correct, edit and improve things to make them more =
clear.</div><div></div><div>- I responded to feedback by modifying the prot=
ocol to make it work - not by ignoring it.</div></div></blockquote><div><br=
></div><div>To this moment there remains no response at your post.<br></div=
><div><a href=3D"https://bitcointalk.org/index.php?topic=3D4973123.0" targe=
t=3D"_blank">https://bitcointalk.org/index.php?topic=3D4973123.0</a><br></d=
iv><div>=C2=A0</div><div>I&#39;m not sure how I am supposted to have figure=
d out that you wrote a somewhat different repost of it elsewhere...<br></di=
v><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=
=3D"ltr">- An M-1 rogue-key attack would require the attacker would to eith=
er <br><div><br></div><div>=C2=A0 - attack the hash function to produce a p=
redictable R based on a known mesage</div><div>=C2=A0 - attack the DLP to i=
nfluence x or k=C2=A0</div><div><br></div><div>Neither attack gives any par=
ticular advantage to someone who has M-1 keys.</div></div></blockquote><div=
><br></div><div>You keep asserting this. It isn&#39;t true. Asserting it mo=
re does not make it any more true.=C2=A0 I already explained how to attack =
this style of signature (e.g. in the BCT thread).<br></div><div><br></div><=
div>Set aside your &#39;interpolation&#39; for a moment, and imagine that y=
ou construct a 2 of 2 signature by just adding the keys.=C2=A0 Your tell me=
 your key, P1=C2=A0 and then I tell you that my key P2 which I derived by c=
omputing -P1=C2=A0 + xG.=C2=A0=C2=A0 We now compute P =3D P1 + P2 =3D P1=C2=
=A0+ -P1=C2=A0+ xG =3D xG ... and now in spite adding P1 with an unknown di=
screte log, I know the discrete log of P with respect to G and I did not ne=
ed to violate the standard DL security assumption to achieve that.</div><di=
v><br></div><div>With the &#39;interpolation&#39; in effect the same attack=
 applies but its execution is somewhat more complex: instead of adding the =
negation of P1=C2=A0 I must add a number of multiplicities of P1 (like P1*2=
, P1*3, P1*4...) selected so that their interpolation coefficients add up t=
o -1. Finding a suitable subset requires solving a randomized modular subse=
t sum problem and Wagner&#39;s algorithm provides a computationally tractab=
le solution to it.</div><div><br></div><div>The potential of rogue keys app=
lies to both the keys themselves and to the nonces. There are several ways =
to prevent these attacks, the musig paper describes a delinearization techn=
ique which doesn&#39;t require additional interaction or communication.<br>=
</div><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px =
0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div=
 dir=3D"ltr"><div>I haven&#39;t tested whether the R,s version is susceptib=
le though.=C2=A0=C2=A0 <br></div></div></blockquote><div><br></div><div>The=
re is a perfect bijection between the two encodings which is easily computa=
ble, so they&#39;re the same thing from an abstract security perspective.<b=
r></div><div>=C2=A0</div></div></div></div>
</blockquote></div>

--0000000000001260b305759bb0e7--