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
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
|
Return-Path: <danrobinson010@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 6624ABD1
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 Jul 2018 15:57:20 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-oi0-f43.google.com (mail-oi0-f43.google.com
[209.85.218.43])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id AB81A6BA
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 Jul 2018 15:57:19 +0000 (UTC)
Received: by mail-oi0-f43.google.com with SMTP id 13-v6so36825373ois.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 09 Jul 2018 08:57:19 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
bh=+dAcFW3Yq5xrMAzGvaphD0PlSh0/kMNfVNX2HyE/75Q=;
b=QK53DOclZGR46gmUQjqwOe+QyR+QMBuTd5JFY5IZepoYP1CrA3sePwtAPC1MjSxrgt
7cXrXYBumzoKcX0bWVQ6V5MCyLOXWWNHcO/SScKvfR+jIRWiw2uaXhCAo9fbUF2kJU0G
AOEGO+VjmIUPGBafNK0ZRlyX1Y2vjA4FiR2YifeCXTPyipQoic/AWAMDp1miy2azSG4m
TqjA4erH1+iRlDsz5aJwJ1I5gNqN0cITXF/Dzx9y/JzHRtjmhF/NEYT1Q7aIwrk/+8Qc
a0su0VWes8MtVVssw6+f8srBvDEgxBhzHw9ozIqZbSivsrWiMrvtDPqYts1/O6LFyhJ/
/1Mg==
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;
bh=+dAcFW3Yq5xrMAzGvaphD0PlSh0/kMNfVNX2HyE/75Q=;
b=kS55UkAY8KEgT4C7sSEYf6IHkytyUOfqOsgdrERRX40X8MXW6HtL6XE+/qJ1rGP5/V
K56QYKDtUz3aX+CeqcOQqZsV1S7hM7+eCy7V/6U3UeDBEh1fW5cWSwUJPAKC0Q1DE989
JzmR0MWLChJyJHo63++ScNykEIxqF2N1ikUrpHf4ejRw2+Piq72k5EWJRb0CDlQa7VWy
Y2QxXqvMKFN0Ag1QBOcBCTtrPF2Mou5CceRhueIs7hqudg2kxtV/ln6Df8V7UFOVWvao
LDqwjTgzlBWPLIr2bOFQmotb9+hEoLJsJGi9HFlw2UXIQb5GwlTzS4nvcNsS9GD+HKft
7pRQ==
X-Gm-Message-State: APt69E2JQMG5Tt5j7XbfmU29aiZK8hX5/GQ7bP4s/diiYiyxqowMnYZw
8efLd7jChE358+V1djOSUSHJgdoP3s+ZtoQaTXc=
X-Google-Smtp-Source: AAOMgpeCdenlNu6393i2GzUYpSSphL94ocn6RGOGJn/zqxQgxRqZLs0GH3rMNAIO3tWEXkDjZQVSaS7q/73y1J5CPgc=
X-Received: by 2002:aca:efd7:: with SMTP id
n206-v6mr25407129oih.70.1531151838757;
Mon, 09 Jul 2018 08:57:18 -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>
In-Reply-To: <CAJowKgJ3K=wmCEtoZXJZhrnnA8XJcHYg788KP+7MCeP4Mxf-0w@mail.gmail.com>
From: Dan Robinson <danrobinson010@gmail.com>
Date: Mon, 9 Jul 2018 11:57:07 -0400
Message-ID: <CAD438Htt-FiFAQ0O=wUsa0k0EoWitAdLyfhOfQ1GY3mEC_Pjkg@mail.gmail.com>
To: Erik Aronesty <erik@q32.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000724cc30570931147"
X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,
HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=no 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 16:34:20 +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:57:20 -0000
--000000000000724cc30570931147
Content-Type: text/plain; charset="UTF-8"
Can you please clarify which terms in that description are elliptic curve
points, and which are scalars?
On Mon, Jul 9, 2018 at 11:10 AM Erik Aronesty via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> 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
>>>
>>>
>>> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--000000000000724cc30570931147
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Can you please clarify which terms in that description are elliptic curve p=
oints, and which are scalars?<br><div class=3D"gmail_quote"><div dir=3D"ltr=
">On Mon, Jul 9, 2018 at 11:10 AM Erik Aronesty via bitcoin-dev <<a href=
=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfo=
undation.org</a>> wrote:<br></div><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div di=
r=3D"ltr"><div>Actually, it looks like in order to compute a multiparty sig=
nature you will need to broadcast shares of r first, so it's not offlin=
e :(</div><div><br></div><div>It is still seems, to me, to be a simpler mec=
hanism than musig - with security assumptions that match the original Schno=
rr construction more closely, and should therefore be easier to prove secur=
e in a multiparty context.</div><div><br></div><div>Shamir/Schnorr threshol=
d multi-signature scheme:<br></div><div><br></div><div>Each party:</div><di=
v><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 purpose=
s of Shamir polynomial interpolation</div><div>- Rolls a random k' and =
compute r' =3D g*k'<br></div><div>- Broadcast r' as a share</di=
v><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 vulnerable or=
DL is not hard</div><div>- Computes e' =3D H(M) * r'</div><div>- C=
omputes s' =3D k'-x*e'</div><div>- Share of signature is (s'=
;, e')</div><div><br></div><div>Verification is the same as Scnhorr, bu=
t 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></b=
lockquote></div></div><div class=3D"gmail_extra"><div class=3D"gmail_quote"=
><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1=
px #ccc solid;padding-left:1ex"><div class=3D"m_-5536499130187874003HOEnZb"=
><div class=3D"m_-5536499130187874003h5"><br><div class=3D"gmail_quote"><di=
v dir=3D"ltr">On Mon, Jul 9, 2018, 12:40 AM Pieter Wuille <<a href=3D"ma=
ilto: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 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"auto"><div =
class=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" ta=
rget=3D"_blank">erik@q32.com</a>> wrote:<br></div><blockquote class=3D"g=
mail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-l=
eft:1ex"><div dir=3D"auto">Because it's non-interactive, this construct=
ion can produce multisig signatures offline.=C2=A0 =C2=A0Each device produc=
es a signature using it's own k-share and x-share.=C2=A0 =C2=A0It's=
only necessary to interpolate M of n shares.<div dir=3D"auto"><br></div><d=
iv dir=3D"auto">There are no round trips.<br><div dir=3D"auto"><br></div><d=
iv dir=3D"auto">The security is Shamir + discrete log.=C2=A0=C2=A0</div><di=
v dir=3D"auto"><div dir=3D"auto"><br></div><div dir=3D"auto">it's just =
something I've been tinkering with and I can't see an obvious probl=
em.=C2=A0=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto">It's=
basically the same as schnorr, but you use a threshold hash to fix the nee=
d to be online.</div><div dir=3D"auto"><br></div><div dir=3D"auto">Just see=
ms more useful to me.</div></div></div></div></blockquote></div><div dir=3D=
"auto"><br></div><div dir=3D"auto">That sounds very useful if true, but I d=
on't think we should include novel cryptography in Bitcoin based on you=
r not 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 =
though.</div><div dir=3D"auto"><br></div><div dir=3D"auto">Cheers,</div><di=
v dir=3D"auto"><br></div><div dir=3D"auto">--=C2=A0</div><div dir=3D"auto">=
Pieter</div><div dir=3D"auto"><br></div><div dir=3D"auto"><br></div><div cl=
ass=3D"gmail_quote" dir=3D"auto"><blockquote class=3D"gmail_quote" style=3D=
"margin: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 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"auto"><div clas=
s=3D"gmail_quote" dir=3D"auto"><blockquote class=3D"gmail_quote" style=3D"m=
argin: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></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>
--000000000000724cc30570931147--
|
