1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
|
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 4B343D0E
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 Jul 2018 15:02:34 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wr1-f42.google.com (mail-wr1-f42.google.com
[209.85.221.42])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3B85F67E
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 Jul 2018 15:02:33 +0000 (UTC)
Received: by mail-wr1-f42.google.com with SMTP id j5-v6so4826393wrr.8
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 09 Jul 2018 08:02:33 -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; bh=V5MWyMoiNlhWZIyNOxA5lTfhmqhYl6GjrShketfNI98=;
b=HOAklU+QatJLa9bHrBMKDBW5xaBbodFs68lfVqvI6yCgNLDGI7DkHW5+ZNlKhkcGHt
RJ3uXGs6RLUEoBabVkiTwsqz8yiyJ142HXmfqwtduNm0g7ztwMSZeQKwnSuRN9GzeczT
MPJUdKQU5IZPfSnubfaiSdRET5SAQeYQuUDCyS6XA12inw8p+spF9ianMYNrIFFrxVuB
qd4ecnG9uqMh0OKqd1iZ+5bsPQt3MTVpTSeXA4l0OvG+Wv8Ef2AebMRUY37j2jZt2X2M
7IY+YBogHxuUvmzOpEpBI+4bjvqp8vIZf2PiYUv48GtTlKhFoYbCMXgzaHY1n0oz8Nsh
nkjg==
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; bh=V5MWyMoiNlhWZIyNOxA5lTfhmqhYl6GjrShketfNI98=;
b=1NbBgd94VTqfAVoxHOYR+PSc8h9/jFkgup/8sJcdW8Yvl1zxZJGWoaMxAd4CiSZkpB
jaDCZY94ZBcL90XXFCTzuqW2yz1qxCUFaHUlxRhFYq9I+h32ogefu4p6s36JBmGzbW3b
fiXHT3u3sn+csXRPXGEYUbVxHlnd1uz2KnoZoC00gKKQA1EMITpW/RIXrKhEi47eEKZ3
sShV/BzImhxdSv80phIBAfTMW6GSuYJWXt9EoBKIUfpEkKlYK9PoDtdsz74DHm+Cfpn8
JNC+UyTqZDO+kT4exbaHB3UMms6G7+DDas8MHAb5RzgDXN4Q7IOiNoLWxQXuUN+YtYii
QDcA==
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;
bh=V5MWyMoiNlhWZIyNOxA5lTfhmqhYl6GjrShketfNI98=;
b=GFJ9AvzbDFzXLsZ7+JRpLIziW+6q7iZu108BnbI0OrjIoZMMdTdIF65++5/1uIET2a
m7jc+KNpqQ7esdT06QF7i1t6/wNYdUSOZB5b8V8KJqGZuc7Ff0AQiryYGhQYn5P/pf03
+mFqiv8mtPp0kwoACa5LlYPQ26EtF/JndDZuz6KkEFNHAkntADKem/IDUGyk6dark7Q8
SH6td8G4SYwu9wAPwHn2lSrs0XqkQBXaCqTYZqpsb4vaDwqRlYpte99Nd7p9r9Rt71ie
rToVUTfOdPzCTlDJJUKB58JT0AvBk38vAf0ZwsF7GB310UcUX+d4l4ajUufN2wep9qOc
Zumg==
X-Gm-Message-State: APt69E2MKXkQ0XIVTDVh1q4A2tK8IsO6qJPSCIiyhIcsma+pIvMnmNZw
Wi33eDk3gixV/6ymX63hb6yUP//Jy6dhJ8oOymzJrb2Deq/1
X-Google-Smtp-Source: AAOMgpe5N5vZ1qrmZOzWBcJfF1zTB3GGQBx/YV7RS4Khs4lr+1FeZ9iP+RWJE4oCa3Aa9u+XuyX+BnXAMiqVcj+XmWo=
X-Received: by 2002:a5d:46c6:: with SMTP id
g6-v6mr14001065wrs.76.1531148551567;
Mon, 09 Jul 2018 08:02:31 -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 08:02:30 -0700 (PDT)
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
X-Google-Sender-Auth: qNjxRk3Or_f0jpKgibJYp5idQfE
Message-ID: <CAJowKgJ3K=wmCEtoZXJZhrnnA8XJcHYg788KP+7MCeP4Mxf-0w@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000083bef80570924dd6"
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 15:04:57 +0000
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 15:02:34 -0000
--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'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', where x' 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=
9; and compute r' =3D g*k'<br></div><div>- Broadcast r' 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' =3D H(M) * r'</div><=
div>- Computes s' =3D k'-x*e'</div><div>- Share of signature is=
(s', e')</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', e' and g*x':</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'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"><<a h=
ref=3D"mailto:erik@q32.com" target=3D"_blank">erik@q32.com</a>></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'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 <<a href=3D"mailto=
:pieter.wuille@gmail.com" target=3D"_blank">pieter.wuille@gmail.com</a>>=
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 <<a href=3D"mailto:erik@q32.com" rel=3D"noreferrer" target=
=3D"_blank">erik@q32.com</a>> 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's non-interactive, this construction =
can produce multisig signatures offline.=C2=A0 =C2=A0Each device produces a=
signature using it's own k-share and x-share.=C2=A0 =C2=A0It'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's just some=
thing I've been tinkering with and I can't see an obvious problem.=
=C2=A0=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto">It'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'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--
|
