path: root/80/5d97ffedc7cfff98405bb62ca568cdec731cb9

Return-Path: <earonesty@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id BB758EBD
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 10 Jul 2018 11:46:37 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f51.google.com (mail-wm0-f51.google.com [74.125.82.51])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B31565D3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 10 Jul 2018 11:46:36 +0000 (UTC)
Received: by mail-wm0-f51.google.com with SMTP id s13-v6so12425221wmc.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 10 Jul 2018 04:46:36 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=q32-com.20150623.gappssmtp.com; s=20150623;
	h=mime-version:references:in-reply-to:from:date:message-id:subject:to
	:cc; bh=S0VVVFZApDHB55YZOlypkYHNNvnFg73np/qWy4W+s9U=;
	b=ZnIgg2DAumdmNVMsERsWtchg5ziHamojIL+hwrTvQMd/jPmM23XrwHsdJzqfCg2N2Z
	hq/L6wUuc7W+PuhpiFt+1W6sL4vGQNOCTeJda4ReIw0Wo1cuH93BOUUE5jZrL6F+EG6y
	+ikkh9wFXr7H8m4QMAZf9fX3IEZolpEir2zPvZ1YifoQ2wlUz+f88ZmqwCGEBP9pzPzS
	9lkKXNNt+cGb1UNLNtczvOWrhLH3leYl7XihiZZekg1Lx813pltMbvKdCJx1UrheU/Fn
	fAkFB0WuNYpFB4d++uuNkVe5o6D6d2C/VLzqPhwSyqkAepwXgTep1ztD54+7pHAu9sem
	NntQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:references:in-reply-to:from:date
	:message-id:subject:to:cc;
	bh=S0VVVFZApDHB55YZOlypkYHNNvnFg73np/qWy4W+s9U=;
	b=niUhLo3Ap8uXrPj89ZpCiPIY0ynIqS832a1Rm8Mt11M5/eEArfuL3AqeFOSl409oDf
	sw/Pt1O5Xy7foMcc/+Bcd3vC4p433ugYKQjh6FwvBqxIfOJKiCMZOLTzYMEUhNApGxgd
	x63lSQMx+jgcsQfx90m0k1JKUJDQhEk0fTXCFyD/5sWaImYzWaTXrrbdd/haocX8NMQA
	Nl0oL1ZH7gzOPCtTVLidx04BtBYv7ioXsYaf+3ixIaazb0EQj94NPybPy4YPY8qo3glA
	eMM2uEw8FdyZLkuwoyKvEaE8a2ztoHAfAqmYFt7eKCZ7gOAD79FEm/ugPKMg+cimKrfu
	mjKw==
X-Gm-Message-State: APt69E3YRHEwrEMrCSk9gOTVrsPD/XkHjmx4oqz6lUsd8eMotulR4Bm2
	VeSCzhLquZf+mofSFrF5wS/CqeF37AwEbPApb/EYLsm0vA==
X-Google-Smtp-Source: AAOMgpfNp7xVE+duO59QremfdRJ7vSIUv8Ik5ag/q+ASvd1uCZRrA6vQX0bk5LD2LOajn/Rc6tlsHT3Ev2V3PqAtEEc=
X-Received: by 2002:a1c:cf81:: with SMTP id
	f123-v6mr15452483wmg.3.1531223195142; 
	Tue, 10 Jul 2018 04:46:35 -0700 (PDT)
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>
In-Reply-To: <CAJowKgL0b3RT7XwRTF+ohoJCyZAW-ZJ+-8Lijj_s1rqqxgU7VQ@mail.gmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Tue, 10 Jul 2018 07:46:17 -0400
Message-ID: <CAJowKg+UaMsY_nL6SBfb20Ltki+LdhXOwwvG_mAsUq_ww3Tesg@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>
Content-Type: multipart/alternative; boundary="0000000000009e50f80570a3ae94"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, FREEMAIL_FROM, HTML_MESSAGE,
	RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
X-Mailman-Approved-At: Wed, 11 Jul 2018 01:40:20 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Multiparty signatures
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 10 Jul 2018 11:46:37 -0000

--0000000000009e50f80570a3ae94
Content-Type: text/plain; charset="UTF-8"

Basically you're just replacing addition with interpolation everywhere in
the musig construction.

But maybe I just don't understand how Wagner's algorithm is relevant here.



On Mon, Jul 9, 2018, 1:59 PM Erik Aronesty <erik@q32.com> wrote:

>  - Adaptive r choice shouldn't be possible since r is derived from the
> original threshold prf and it's not possible for a party to have any
> adaptive impact on the value of r
>  - I'm guess I don't see how an attacker can use adaptive key choice in
> this context either.   Any modification of the key should be useless
> AH!
>
> I forgot to include some assumptions.   The important part here is that
> each party only has a share of the private key and publishes a share of the
> public key.
>
> This hopefully should preclude any sort of adaptive key attack.
>
> From scratch:
>
> 1. Has a public g^x'
> 2. Computes and broadcasts g^k' ... where k' is a random number
> 3. Computes r = g^k using lagrange interpolation (see
> http://crypto.stanford.edu/~dabo/papers/homprf.pdf)
> 4. Computes H(r || M), as per standard schnorr
> 5. Computes s' = k' - xe , as per standard schnorr .. except k' is a
> "share"
> 6. Publish (s', e, g^x')
>
> Verification:
>
> With m of n share-signatures:
>
> 1. Interpolation on m of n s' shares to get s
> 2. Interpolation on m of n g^x' shares to get g^x
> 3. Standard schnorr verification
>
> The actual public key of the "set of signers" is interpolated.
>
>
>
> On Mon, Jul 9, 2018 at 12:58 PM, Gregory Maxwell <greg@xiph.org> wrote:
>
>> On Mon, Jul 9, 2018 at 4:33 PM, Erik Aronesty <erik@q32.com> wrote:
>> >>> with security assumptions that match the original Schnorr
>> construction more closely,
>> >> More closely than what?
>> > More closely than musig.
>>
>> Musig is instructions on using the original schnorr construction for
>> multiparty signing which is secure against participants adaptively
>> choosing their keys, which is something the naive scheme of just
>> interpolating keys and shares is vulnerable to. It works as
>> preprocessing on the keys, then you continue on with the naive
>> protocol. The verifier (e.g. network consensus rules) is the same.
>>
>> Now that you're back to using a cryptographic hash, I think what
>> you're suggesting is "use naive interpolation of schnorr signatures"
>> -- which you can do, including with the verifier proposed in the BIP,
>> but doing that alone is insecure against adaptive key choice (and
>> potentially adaptive R choice, depending on specifics which aren't
>> clear enough to me in your description). In particular, although it
>> seems surprising picking your interpolation locations with the hash of
>> each key isn't sufficient to prevent cancellation attacks due to the
>> remarkable power of wagner's algorithm.
>>
>
>

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

<div dir=3D"auto"><div>Basically you&#39;re just replacing addition with in=
terpolation everywhere in the musig construction.<div dir=3D"auto"><br></di=
v><div dir=3D"auto">But maybe I just don&#39;t understand how Wagner&#39;s =
algorithm is relevant here.<br><div dir=3D"auto"><br></div></div><br><br><d=
iv class=3D"gmail_quote"><div dir=3D"ltr">On Mon, Jul 9, 2018, 1:59 PM Erik=
 Aronesty &lt;<a href=3D"mailto:erik@q32.com">erik@q32.com</a>&gt; wrote:<b=
r></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">=C2=A0- Adaptive r =
choice shouldn&#39;t be possible since r is derived from the original thres=
hold prf and it&#39;s not possible for a party to have any adaptive impact =
on the value of r<div>=C2=A0- I&#39;m guess I don&#39;t see how an attacker=
 can use adaptive key choice in this context either.=C2=A0 =C2=A0Any modifi=
cation of the key should be useless</div>

<div style=3D"text-decoration-style:initial;text-decoration-color:initial">=
AH!</div><div style=3D"text-decoration-style:initial;text-decoration-color:=
initial"><br></div><div style=3D"text-decoration-style:initial;text-decorat=
ion-color:initial">I forgot to include some assumptions.=C2=A0 =C2=A0The im=
portant part here is that each party only has a share of the private key an=
d publishes a share of the public key.</div><div style=3D"text-decoration-s=
tyle:initial;text-decoration-color:initial"><br></div><div style=3D"text-de=
coration-style:initial;text-decoration-color:initial">This hopefully should=
 preclude any sort of adaptive key attack.</div><div style=3D"text-decorati=
on-style:initial;text-decoration-color:initial"><br></div><div style=3D"tex=
t-decoration-style:initial;text-decoration-color:initial">From scratch:</di=
v><div style=3D"text-decoration-style:initial;text-decoration-color:initial=
"><br></div><div style=3D"text-decoration-style:initial;text-decoration-col=
or:initial">

<div style=3D"font-size:12.8px;background-color:rgb(255,255,255);text-decor=
ation-style:initial;text-decoration-color:initial">1. Has a public g^x&#39;=
</div><div style=3D"font-size:12.8px;background-color:rgb(255,255,255);text=
-decoration-style:initial;text-decoration-color:initial">2. Computes and br=
oadcasts g^k&#39; ... where k&#39; is a random number</div><div style=3D"fo=
nt-size:12.8px;background-color:rgb(255,255,255);text-decoration-style:init=
ial;text-decoration-color:initial">3. Computes r =3D g^k using lagrange int=
erpolation (see=C2=A0<span>=C2=A0</span><span style=3D"font-size:small;back=
ground-color:rgb(255,255,255);text-decoration-style:initial;text-decoration=
-color:initial;float:none;display:inline"><a href=3D"http://crypto.stanford=
.edu/~dabo/papers/homprf.pdf" style=3D"color:rgb(17,85,204)" target=3D"_bla=
nk" rel=3D"noreferrer">http://crypto.stanford.edu/~dabo/papers/homprf.pdf</=
a>)</span></div><div style=3D"font-size:12.8px;background-color:rgb(255,255=
,255);text-decoration-style:initial;text-decoration-color:initial"><span st=
yle=3D"font-size:small;background-color:rgb(255,255,255);text-decoration-st=
yle:initial;text-decoration-color:initial;float:none;display:inline">4. Com=
putes H(r || M), as per standard schnorr</span></div><div style=3D"font-siz=
e:12.8px;background-color:rgb(255,255,255);text-decoration-style:initial;te=
xt-decoration-color:initial"><span style=3D"font-size:small;background-colo=
r:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:init=
ial;float:none;display:inline">5. Computes s&#39; =3D k&#39; - xe<span>=C2=
=A0</span><span style=3D"text-decoration-style:initial;text-decoration-colo=
r:initial;float:none;display:inline">, as per standard schnorr .. except k&=
#39; is a &quot;share&quot;</span></span></div><div style=3D"font-size:12.8=
px;background-color:rgb(255,255,255);text-decoration-style:initial;text-dec=
oration-color:initial"><span style=3D"font-size:small;background-color:rgb(=
255,255,255);text-decoration-style:initial;text-decoration-color:initial;fl=
oat:none;display:inline"><span style=3D"text-decoration-style:initial;text-=
decoration-color:initial;float:none;display:inline">6. Publish (s&#39;, e, =
g^x&#39;)</span></span></div></div><div style=3D"text-decoration-style:init=
ial;text-decoration-color:initial"><div style=3D"font-size:12.8px;backgroun=
d-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-colo=
r:initial"><span style=3D"font-size:small;background-color:rgb(255,255,255)=
;text-decoration-style:initial;text-decoration-color:initial;float:none;dis=
play:inline"><span style=3D"text-decoration-style:initial;text-decoration-c=
olor:initial;float:none;display:inline"><br>Verification:</span></span></di=
v><div style=3D"font-size:12.8px;background-color:rgb(255,255,255);text-dec=
oration-style:initial;text-decoration-color:initial"><span style=3D"font-si=
ze:small;background-color:rgb(255,255,255);text-decoration-style:initial;te=
xt-decoration-color:initial;float:none;display:inline"><span style=3D"text-=
decoration-style:initial;text-decoration-color:initial;float:none;display:i=
nline"><br></span></span></div><div style=3D"font-size:12.8px;background-co=
lor:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:in=
itial"><span style=3D"font-size:small;background-color:rgb(255,255,255);tex=
t-decoration-style:initial;text-decoration-color:initial;float:none;display=
:inline"><span style=3D"text-decoration-style:initial;text-decoration-color=
:initial;float:none;display:inline">With m of n share-signatures:</span></s=
pan></div><div style=3D"font-size:12.8px;background-color:rgb(255,255,255);=
text-decoration-style:initial;text-decoration-color:initial"><span style=3D=
"font-size:small;background-color:rgb(255,255,255);text-decoration-style:in=
itial;text-decoration-color:initial;float:none;display:inline"><span style=
=3D"text-decoration-style:initial;text-decoration-color:initial;float:none;=
display:inline"><br></span></span></div><div style=3D"font-size:12.8px;back=
ground-color:rgb(255,255,255);text-decoration-style:initial;text-decoration=
-color:initial"><span style=3D"font-size:small;background-color:rgb(255,255=
,255);text-decoration-style:initial;text-decoration-color:initial;float:non=
e;display:inline"><span style=3D"text-decoration-style:initial;text-decorat=
ion-color:initial;float:none;display:inline">1. Interpolation on m of n s&#=
39; shares to get s</span></span></div><div style=3D"font-size:12.8px;backg=
round-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-=
color:initial"><span style=3D"font-size:small;background-color:rgb(255,255,=
255);text-decoration-style:initial;text-decoration-color:initial;float:none=
;display:inline"><span style=3D"text-decoration-style:initial;text-decorati=
on-color:initial;float:none;display:inline"><span style=3D"font-size:small;=
background-color:rgb(255,255,255);text-decoration-style:initial;text-decora=
tion-color:initial;float:none;display:inline">2. Interpolation on m of n g^=
x&#39; shares to get g^x</span><br></span></span></div><div style=3D"font-s=
ize:12.8px;background-color:rgb(255,255,255);text-decoration-style:initial;=
text-decoration-color:initial"><span style=3D"font-size:small;background-co=
lor:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:in=
itial;float:none;display:inline"><span style=3D"text-decoration-style:initi=
al;text-decoration-color:initial;float:none;display:inline">3. Standard sch=
norr verification</span></span></div>

<br></div><div style=3D"text-decoration-style:initial;text-decoration-color=
:initial">The actual public key of the &quot;set of signers&quot; is interp=
olated.=C2=A0 =C2=A0<br></div><div style=3D"text-decoration-style:initial;t=
ext-decoration-color:initial"><br></div><div style=3D"text-decoration-style=
:initial;text-decoration-color:initial"><br></div></div><div class=3D"gmail=
_extra"><br><div class=3D"gmail_quote">On Mon, Jul 9, 2018 at 12:58 PM, Gre=
gory Maxwell <span dir=3D"ltr">&lt;<a href=3D"mailto:greg@xiph.org" target=
=3D"_blank" rel=3D"noreferrer">greg@xiph.org</a>&gt;</span> wrote:<br><bloc=
kquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #cc=
c solid;padding-left:1ex"><span>On Mon, Jul 9, 2018 at 4:33 PM, Erik Arones=
ty &lt;<a href=3D"mailto:erik@q32.com" target=3D"_blank" rel=3D"noreferrer"=
>erik@q32.com</a>&gt; wrote:<br>
&gt;&gt;&gt; with security assumptions that match the original Schnorr cons=
truction more closely,<br>
&gt;&gt; More closely than what?<br>
</span>&gt; More closely than musig.<br>
<br>
Musig is instructions on using the original schnorr construction for<br>
multiparty signing which is secure against participants adaptively<br>
choosing their keys, which is something the naive scheme of just<br>
interpolating keys and shares is vulnerable to. It works as<br>
preprocessing on the keys, then you continue on with the naive<br>
protocol. The verifier (e.g. network consensus rules) is the same.<br>
<br>
Now that you&#39;re back to using a cryptographic hash, I think what<br>
you&#39;re suggesting is &quot;use naive interpolation of schnorr signature=
s&quot;<br>
-- which you can do, including with the verifier proposed in the BIP,<br>
but doing that alone is insecure against adaptive key choice (and<br>
potentially adaptive R choice, depending on specifics which aren&#39;t<br>
clear enough to me in your description). In particular, although it<br>
seems surprising picking your interpolation locations with the hash of<br>
each key isn&#39;t sufficient to prevent cancellation attacks due to the<br=
>
remarkable power of wagner&#39;s algorithm.<br>
</blockquote></div><br></div>
</blockquote></div></div></div>

--0000000000009e50f80570a3ae94--