path: root/c8/79a95c1b5eb5d6247a29f6e7a3e570dbc1aee7

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 5D0B7E83
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon,  9 Jul 2018 17:59:27 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f47.google.com (mail-wm0-f47.google.com [74.125.82.47])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8206CE2
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon,  9 Jul 2018 17:59:26 +0000 (UTC)
Received: by mail-wm0-f47.google.com with SMTP id b188-v6so22062155wme.3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 09 Jul 2018 10:59:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
	h=mime-version:sender:in-reply-to:references:from:date:message-id
	:subject:to:cc;
	bh=2TuFV03se2iO2Nud6dIJmr5HUOpQ5VdmFf7fU60l4K4=;
	b=AYISbW8taIHXbojlyCwZAHeCq4J8TXO6A6Madz7cQHm5uWsaUquW8taBslu31+rRt7
	k/mJHxiBSJEUdG3QdeIpgkW1/1M+dXOk7HMPpuYzu9eVEdO58+41wUuSYe+0copKyPJX
	w+gj3zR05bVb+u9YV6bMO6fQrmQsmO4MlgeLVjrvtlJGp75NVrz4tOqY3/TfKUbFYGxN
	GvtprynmEqHgeIlfu2WcKcXcMEQRnnqTgBKiVB7JdCR0sYpSsrMiYxsjEMkJvK54I11F
	BNPlD+cVldThW1iuIaF5rWG+ZljxAclLLCBPBUbtzaaD004S1owmcwS51bT7hfj3LW45
	YPDw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=q32-com.20150623.gappssmtp.com; s=20150623;
	h=mime-version:sender:in-reply-to:references:from:date:message-id
	:subject:to:cc;
	bh=2TuFV03se2iO2Nud6dIJmr5HUOpQ5VdmFf7fU60l4K4=;
	b=TX+tAfH2Lu0rGMxapo/7V9kT957uOVHDNDGZcDu58c7JjgQ4TObw/qau73V/aV5Ycx
	mK806xnbnEDDjzGDPC6UbcMlI7Hk83UsOAljt/QhG5VIb7zMba0xXZnVoaino4tBsDPL
	7ZMnvH6xCSLwqRXdIGKyuxzrVUwzYWvC7vxKHiX+fV8mENGySrjFIx+35TKTurdQtDcy
	sLfVcSQ0tbjA4RfXBgjFLTzg+3W7tWdlbPTsyo4biDveoNikeidam7wwma0Tp+B2nT1a
	0QRNKWQ1eMuY/ShW++T9Uq//MWCcinn7+Rkyttm1cSjRsaxSjKIUx5trwCNKKnFTuBA4
	45Ng==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:sender:in-reply-to:references:from
	:date:message-id:subject:to:cc;
	bh=2TuFV03se2iO2Nud6dIJmr5HUOpQ5VdmFf7fU60l4K4=;
	b=HdbcyWPJAukVtFvYe9Gg+cl5NaN7QJLmslF9xES7pImNzSQYpk/pP8ixfwxH7f0qTx
	DFmqTFGJnvwRNux4rTJCpfS6f3ZCidmrILssqwU5zcq5uHkaHfWyVfWFI9KjRld01rsj
	yG3TK5wBOAJyauAw0kd2OX4iY7E3pRAk7SA+i5y8O61c7Ozr/N1S8gtS3sVdLJmFr6hC
	BIWtvuLyfTQBgKIfURtTw5UMRq2xE5tEvArFHb6XapgyDJkm8hYcxQJbbw8hiXjI8l+8
	Ens8Ta7d1ab/SYC+JOCXfWyOUd4guCLI7fv7P15nTJgKGEdquJ31d1tNTw3Tux5RR8D5
	8zCw==
X-Gm-Message-State: APt69E3Gz/JUIaxsdbOsqIHXipQdfb5BdoCv2tni+JWWib+pE1xky+r4
	2H2QC277E7uUVsFj1yZQq7Yr1JTi98+9e14lnVNSScZcv5DH
X-Google-Smtp-Source: AAOMgpeUbcisFkFlur8vYVYN3Fn67hAqOAhJPatI6ip12hMKa7FHKO7/+LJ/o1QodooOKxzODQupB4FOf6+j5pI/GGs=
X-Received: by 2002:a1c:dc41:: with SMTP id
	t62-v6mr13388549wmg.42.1531159165004; 
	Mon, 09 Jul 2018 10:59:25 -0700 (PDT)
MIME-Version: 1.0
Sender: earonesty@gmail.com
Received: by 2002:a1c:b786:0:0:0:0:0 with HTTP;
	Mon, 9 Jul 2018 10:59:23 -0700 (PDT)
In-Reply-To: <CAAS2fgRrkzq6Fa5T_-YDwLDkwi30LpDtMObMEBE+Fmmj0LJpBw@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>
	<CAJowKgJ3K=wmCEtoZXJZhrnnA8XJcHYg788KP+7MCeP4Mxf-0w@mail.gmail.com>
	<CAAS2fgSmA02s6Vdk_FYv6NJ4smLBgxnuT4jRYU44G7=bbzv2MA@mail.gmail.com>
	<CAJowKgJjQ8EGgbCurOSjTh8ij42_BVeD6dE0y67tzN0Zop3pyg@mail.gmail.com>
	<CAAS2fgRrkzq6Fa5T_-YDwLDkwi30LpDtMObMEBE+Fmmj0LJpBw@mail.gmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Mon, 9 Jul 2018 13:59:23 -0400
X-Google-Sender-Auth: 4KcOZ0m3KNl7GApKWywcQ1Pfh-8
Message-ID: <CAJowKgL0b3RT7XwRTF+ohoJCyZAW-ZJ+-8Lijj_s1rqqxgU7VQ@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>
Content-Type: multipart/alternative; boundary="0000000000001ff48b057094c6a7"
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: Mon, 09 Jul 2018 17:59:51 +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: Mon, 09 Jul 2018 17:59:27 -0000

--0000000000001ff48b057094c6a7
Content-Type: text/plain; charset="UTF-8"

 - 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.
>

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

<div dir=3D"ltr">=C2=A0- Adaptive r choice shouldn&#39;t be possible since =
r is derived from the original threshold 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 g=
uess I don&#39;t see how an attacker can use adaptive key choice in this co=
ntext either.=C2=A0 =C2=A0Any modification of the key should be useless</di=
v>

<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" target=3D"_blank" style=3D"color:rgb(17,85,20=
4)">http://crypto.stanford.edu/~<wbr>dabo/papers/homprf.pdf</a>)</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">4. Computes H(r || M=
), as per standard schnorr</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">5. Computes s&#39; =3D k&#39; - xe<span>=C2=A0</span><span=
 style=3D"text-decoration-style:initial;text-decoration-color: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.8px;background-c=
olor:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:i=
nitial"><span style=3D"font-size:small;background-color:rgb(255,255,255);te=
xt-decoration-style:initial;text-decoration-color:initial;float:none;displa=
y:inline"><span style=3D"text-decoration-style:initial;text-decoration-colo=
r:initial;float:none;display:inline">6. Publish (s&#39;, e, g^x&#39;)</span=
></span></div></div><div style=3D"text-decoration-style:initial;text-decora=
tion-color:initial"><div style=3D"font-size:12.8px;background-color:rgb(255=
,255,255);text-decoration-style:initial;text-decoration-color:initial"><spa=
n style=3D"font-size:small;background-color:rgb(255,255,255);text-decoratio=
n-style:initial;text-decoration-color:initial;float:none;display:inline"><s=
pan style=3D"text-decoration-style:initial;text-decoration-color:initial;fl=
oat:none;display:inline"><br>Verification:</span></span></div><div style=3D=
"font-size:12.8px;background-color:rgb(255,255,255);text-decoration-style:i=
nitial;text-decoration-color:initial"><span style=3D"font-size:small;backgr=
ound-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-c=
olor:initial;float:none;display:inline"><span style=3D"text-decoration-styl=
e:initial;text-decoration-color:initial;float:none;display:inline"><br></sp=
an></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"><span =
style=3D"text-decoration-style:initial;text-decoration-color:initial;float:=
none;display:inline">With m of n share-signatures:</span></span></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:smal=
l;background-color:rgb(255,255,255);text-decoration-style:initial;text-deco=
ration-color:initial;float:none;display:inline"><span style=3D"text-decorat=
ion-style:initial;text-decoration-color:initial;float:none;display:inline">=
<br></span></span></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-decor=
ation-style:initial;text-decoration-color:initial;float:none;display:inline=
"><span style=3D"text-decoration-style:initial;text-decoration-color:initia=
l;float:none;display:inline">1. Interpolation on m of n s&#39; shares to ge=
t s</span></span></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-decora=
tion-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"><span style=3D"font-size:small;background-color=
:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initi=
al;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-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">3. Standard schnorr verificatio=
n</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">greg@xiph.org</a>&gt;</span> wrote:<br><blockquote class=3D"gma=
il_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-lef=
t:1ex"><span class=3D"">On Mon, Jul 9, 2018 at 4:33 PM, Erik Aronesty &lt;<=
a href=3D"mailto:erik@q32.com">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>

--0000000000001ff48b057094c6a7--