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
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
|
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 3E37AC77
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 20 Jul 2018 20:18:51 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f53.google.com (mail-wm0-f53.google.com [74.125.82.53])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 20A864FA
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 20 Jul 2018 20:18:50 +0000 (UTC)
Received: by mail-wm0-f53.google.com with SMTP id o11-v6so10502088wmh.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 20 Jul 2018 13:18:49 -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=QerNuAPlXmedDTjuePUSh3MdEHW3elJzbN/t4fu/PUc=;
b=t3JqOyP1yRiA4WMdPH8r9+G6d+gAxp348BWU1jaak9PBnpY2afCKwK33Hohk2oYfB2
eCkiWgN5s463cmlQVa4H2Dze+wdjb9SjgGWcB+JljH6/e3KXwCw8GjzDleTBEttbjauY
5aIZZn7lGphzMIZsfD0nyQ8ZV2AT9+6Qh8KcGJzkqimnFIhSOJLIQN1l+mEpv3XFpkxr
EFISLythoSmvRjjYyNDTVQjbs52a05GQ+ODh3SnjCsLfRdqG/rrh4VTJdDYgVyNFl6Oh
GORhZI+WLaS+OKhnCyKUPhhclTAQOWirbL+094ItXDGHukKFmEyW3XUFDeOvA8xewrbM
a0bQ==
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=QerNuAPlXmedDTjuePUSh3MdEHW3elJzbN/t4fu/PUc=;
b=IWyh1j7pRhoWD7BojJWTZmI3W3IWvX5RzxLl5CuIHzRM8DmHis2iz2BUyXUZSRRecI
7Pfy53x1AqXY1quNHJTTgy7htMkN3GMb66LH+oyICN2O/FUFhCbDkfXdA5KUmezn3KRP
97o/KlyY2lmnzNVolhqyYnueWYol32zQGJYvkA1KOpUXCvpmGsQKUHkYA5GWRJg6upAb
QTJjdq5zVmsJUr35Wgb1MnuM5W5rQp1ArFfYruO+BVOKTQd1VJEWTY5ymwDN4GRHFQpZ
4aQwYcCBHQXOA4AG8lb1CNTRqtoJA2pN9KxXqAE9YS4w8RYa/ODHDO7XngTirhS03x4W
2/+g==
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=QerNuAPlXmedDTjuePUSh3MdEHW3elJzbN/t4fu/PUc=;
b=ovImbB7iagz/s52IvWkrTNq0GV/RaIrkoBc26VxkMj8k7mQHWvzKPMPb0BriAxsrhM
YfLL+o4lDMG1RTPqgQUUkLN2smlDUbNhxqcCbFm/E+XxTygjYJ5mexwdGb3U+iSQ9A7a
ybWKSxpnvcKKOYjDlpCUBlr0WI1Y1ozAdrvvY+B1UPTnEGub7fljsvrbKz6s2XQPuIzO
b9inSxv9Enbg9IvlDBJBW24qwfYLuTyCWsjV6PW0cWjQOWnbNmHAXMhS0V+Aeg9aZ1cw
RAaNagVUxQPlikqervtIxookykfZX1BvKlYgzjqSRx2p/tqWoYZAfvZI7fcHHGWPUBUK
9ffw==
X-Gm-Message-State: AOUpUlFrmInqZ3sHRtBkEhQ3RCnzvaVdQGnGCaECxebTWxk5ZpVnjq4A
Mmx+Y5sWALNh0Uxspb2vUoM9FpsND5+rvKKIcTtbmCIOx/tJ
X-Google-Smtp-Source: AAOMgpfDpuhq11JVk6lnoi1I8WB0gGTT5xQuYD31GLiBR1IxuOxJfG1COJ9yW7hgomEETpuvH2ajT2lGDLH+9AgJsv4=
X-Received: by 2002:a1c:c019:: with SMTP id
q25-v6mr2310904wmf.148.1532117928301;
Fri, 20 Jul 2018 13:18:48 -0700 (PDT)
MIME-Version: 1.0
Sender: earonesty@gmail.com
Received: by 2002:a1c:b786:0:0:0:0:0 with HTTP; Fri, 20 Jul 2018 13:18:47
-0700 (PDT)
In-Reply-To: <CAJowKgKB1GDxvpQt1JjPr+cgyM8yztLtgJ_mZ8vsoCHyBdqkVA@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>
<CAJowKgL0b3RT7XwRTF+ohoJCyZAW-ZJ+-8Lijj_s1rqqxgU7VQ@mail.gmail.com>
<CAJowKg+UaMsY_nL6SBfb20Ltki+LdhXOwwvG_mAsUq_ww3Tesg@mail.gmail.com>
<CALqxMTHYaspkn8JupaHBeLDxLOfZbnwcne2AVeFZe2ADOefktA@mail.gmail.com>
<CAJowKg+rC9rmv--NxtrFQ=ea4B20u0ozkmA5hARpA4wLinnVQg@mail.gmail.com>
<CAJowKg+QxcU0ECpZrvUckXQfBpn6Qri=gWzLA7+Y2mvTAq_mSw@mail.gmail.com>
<CAMZUoK=iNgsZVb89gYRDUdZu0AkTGQ8cXqqbk3NXHEONBpO5ow@mail.gmail.com>
<CAJowKgJBVdJbRvf5Y6dV4o5Jf1XyELNsT+vCrp4b-86ZYr+LYQ@mail.gmail.com>
<CAJowKgKB1GDxvpQt1JjPr+cgyM8yztLtgJ_mZ8vsoCHyBdqkVA@mail.gmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Fri, 20 Jul 2018 16:18:47 -0400
X-Google-Sender-Auth: mpqCRoOux2jiH-ZCrOhoF7ZYCXE
Message-ID: <CAJowKgJXzgQuxt3YMjUfOQRp4T_QybpWKpLq=x-EAif4HLNMcQ@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000dedb5505717400eb"
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: Sun, 22 Jul 2018 12:50:59 +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: Fri, 20 Jul 2018 20:18:51 -0000
--000000000000dedb5505717400eb
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Sorry there were typos:
- Using MuSig's solution for the blinding factor (e)
- Using interpolation to enhance MuSig to be M of N instead of M of M
References:
- MuSig https://blockstream.com/2018/01/23/musig-key-aggregation-
schnorr-signatures.html
- HomPrf http://crypto.stanford.edu/~dabo/papers/homprf.pdf (sections 7.1
and 7.4)
Each party:
1. Publishes public key G*xi, G*ki, where ki is a random nonce
3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, for the purposes of
interpolation
3. R =3D G*k =3D via interpolation of r1=3DGk1, r2=3DGk2... (see HomPrf)
4. L =3D H(X1,X2,=E2=80=A6) (see MuSig)
5. X =3D sum of all H(L,Xi)Xi (see MuSig)
6. Computes e =3D H(R | M | X) .... standard schnorr e... not a share
7. Computes si =3D ki *e+ xi * e ... where si is a "share" of the sig, and =
xi
is the private data, and e is the blinding factor
8. Publishes (si, e) as the share sig
If an attacker has multiple devices, e is safe, because of the musig
construction.
But what protects k from the same multiparty birthday attack?
If an attacker has multiple devices, by carefully controlling the selection
of private keys, the attacker can try to solve
the polynomial equation to force the selection of a "known k".
A "known k" would allow an attacker to sign messages on his own.
To fix this, we need to somehow "blind k as well".
Does this work?
The revision below seems to solve this problem.
1. Publishes public key G*xi, G*ki, where ki is a random nonce
3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, for the purposes of
interpolation
3. R =3D G*k =3D via interpolation of r1=3DGk1, r2=3DGk2... (see HomPrf)
4. L =3D H(X1,X2,=E2=80=A6) (see MuSig)
5. L2 =3D H2(XN,XN-1,=E2=80=A6) (see MuSig... H2 is a "second hash")
6. X =3D sum of all H(L,Xi)Xi (see MuSig)
7. Computes e =3D H(R | M | X) .... standard schnorr e... not a share
8. Computes e2 =3D H(R | M | X2) ... a second blinding factor
9. Computes si =3D ki *e2 + xi * e ... where si is a "share" of the sig, an=
d
xi is the private data, and e, e2 are blinding factors
10. Publishes (si, e, e2) as the share sig
The final signature is computed via interpolation, and e2 is can be
subtracted to recover a "normal" schnor sig for the set of participants.
Now there's no mechanism for a birthday attack on k.
On Fri, Jul 20, 2018 at 1:34 PM, Erik Aronesty <erik@q32.com> wrote:
> Hi, thanks for all the help. I'm going to summarize again, and see if
> we've arrived at the correct solution for an M of N "single sig" extensio=
n
> of MuSig, which I think we have.
>
> - Using MuSig's solution for the blinding to solve the Wagner attack
> - Using interpolation to enhance MuSig to be M of N instead of M of M
>
> References:
>
> - MuSig https://blockstream.com/2018/01/23/musig-key-aggregation-
> schnorr-signatures.html
> - HomPrf http://crypto.stanford.edu/~dabo/papers/homprf.pdf (sections
> 7.1 and 7.4)
>
> Each party:
>
> 1. Publishes public key G*xi
> 3. Xi =3D H(G*xi) ... Xi is the parties x coordinate, for the purposes of
> interpolation
> 3. r =3D G*x =3D via interpolation of Gx1, Gx2... (see HomPrf)
> 4. L =3D H(X1,X2,=E2=80=A6) (see MuSig)
> 5. X =3D sum of all H(L,Xi)Xi (see MuSig)
> 6. Computes e =3D H(r | M | X) .... standard schnorr e... not a share
> 7. Computes si =3D xi - xe ... where si is a "share" of the sig, and xi i=
s
> the private data
> 8. Publishes (si, e, G*Xi)
>
> Any party can then derive s from m of n shares, by interpolating, not
> adding.
>
>
>
>
--000000000000dedb5505717400eb
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>
<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
-color:initial">Sorry there were typos:</div><div style=3D"font-size:small;=
text-decoration-style:initial;text-decoration-color:initial"><br></div></di=
v><div style=3D"font-size:small;text-decoration-style:initial;text-decorati=
on-color:initial">- Using MuSig's solution for the blinding factor (e)<=
br></div><div style=3D"font-size:small;text-decoration-style:initial;text-d=
ecoration-color:initial">- Using interpolation to enhance MuSig to be M of =
N instead of M of M</div><div style=3D"font-size:small;text-decoration-styl=
e:initial;text-decoration-color:initial"></div><div style=3D"font-size:smal=
l;text-decoration-style:initial;text-decoration-color:initial"><br></div><d=
iv style=3D"font-size:small;text-decoration-style:initial;text-decoration-c=
olor:initial">References:</div><div style=3D"font-size:small;text-decoratio=
n-style:initial;text-decoration-color:initial"><br></div><div style=3D"font=
-size:small;text-decoration-style:initial;text-decoration-color:initial">=
=C2=A0- MuSig <a href=3D"https://blockstream.com/2018/01/23/musig-key-aggre=
gation-schnorr-signatures.html" target=3D"_blank">https://blockstream.com/2=
018/<wbr>01/23/musig-key-aggregation-<wbr>schnorr-signatures.html</a><br></=
div><div style=3D"font-size:small;text-decoration-style:initial;text-decora=
tion-color:initial">=C2=A0- HomPrf <a href=3D"http://crypto.stanford.edu/~d=
abo/papers/homprf.pdf" target=3D"_blank">http://crypto.stanford.edu/~<wbr>d=
abo/papers/homprf.pdf</a> (sections 7.1 and 7.4)</div><div style=3D"font-si=
ze:small;text-decoration-style:initial;text-decoration-color:initial"><br><=
/div><div style=3D"font-size:small;text-decoration-style:initial;text-decor=
ation-color:initial">Each <span class=3D"gmail-il">party</span>:</div><div =
style=3D"font-size:small;text-decoration-style:initial;text-decoration-colo=
r:initial"><br></div><div style=3D"font-size:small;text-decoration-style:in=
itial;text-decoration-color:initial">1. Publishes public key G*xi, G*ki, wh=
ere ki is a random nonce<br></div><div style=3D"font-size:small;text-decora=
tion-style:initial;text-decoration-color:initial">3. Xi =3D H(G*xi) ... Xi =
is the parties x coordinate, for the purposes of interpolation</div><div st=
yle=3D"font-size:small;text-decoration-style:initial;text-decoration-color:=
initial">3. R =3D G*k =3D via interpolation of r1=3DGk1, r2=3DGk2... (see=
=C2=A0<span style=3D"background-color:rgb(255,255,255);text-decoration-styl=
e:initial;text-decoration-color:initial;float:none;display:inline">HomPrf</=
span>)</div><div style=3D"font-size:small;text-decoration-style:initial;tex=
t-decoration-color:initial">4. L =3D H(X1,X2,=E2=80=A6) (see MuSig)<br></di=
v><div style=3D"font-size:small;text-decoration-style:initial;text-decorati=
on-color:initial">5. X =3D sum of all H(L,Xi)Xi (<span style=3D"background-=
color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:=
initial;float:none;display:inline">see MuSig</span>)</div><div style=3D"fon=
t-size:small;text-decoration-style:initial;text-decoration-color:initial">6=
. Computes e =3D H(R | M | X) .... standard schnorr e... not a share</div><=
div style=3D"font-size:small;text-decoration-style:initial;text-decoration-=
color:initial">7. Computes si =3D ki *e+ xi * e ... where si is a "sha=
re" of the sig, and xi is the private data, and e is the blinding fact=
or<br></div><div style=3D"font-size:small;text-decoration-style:initial;tex=
t-decoration-color:initial">8. Publishes (si, e) as the share sig<br></div>=
<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
-color:initial"><br></div><div>If an attacker has multiple devices, e is sa=
fe, because of the musig construction.</div><div><br></div><div>
<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
-color:initial">But what protects k from the same multiparty birthday attac=
k?=C2=A0=C2=A0</div><div style=3D"font-size:small;text-decoration-style:ini=
tial;text-decoration-color:initial"><br></div><div style=3D"font-size:small=
;text-decoration-style:initial;text-decoration-color:initial"></div></div><=
div style=3D"font-size:small;text-decoration-style:initial;text-decoration-=
color:initial">
<div style=3D"text-decoration-style:initial;text-decoration-color:initial">=
If an attacker has multiple devices, by carefully controlling the selection=
of private keys, the attacker can try to solve <br></div><div style=3D"tex=
t-decoration-style:initial;text-decoration-color:initial">the polynomial eq=
uation to force the selection of a "known k".<br><br></div><div s=
tyle=3D"text-decoration-style:initial;text-decoration-color:initial">A &quo=
t;known k" would allow an attacker to sign messages on his own.</div><=
div style=3D"text-decoration-style:initial;text-decoration-color:initial"><=
br></div><div style=3D"text-decoration-style:initial;text-decoration-color:=
initial">To fix this, we need to somehow "blind k as well".</div>=
<div style=3D"text-decoration-style:initial;text-decoration-color:initial">=
<br></div><div style=3D"text-decoration-style:initial;text-decoration-color=
:initial">Does this work?</div><div style=3D"text-decoration-style:initial;=
text-decoration-color:initial"><br></div><div style=3D"text-decoration-styl=
e:initial;text-decoration-color:initial">The revision below seems to solve =
this problem.<br></div><div style=3D"text-decoration-style:initial;text-dec=
oration-color:initial"><br></div><div style=3D"text-decoration-style:initia=
l;text-decoration-color:initial"></div><div style=3D"text-decoration-style:=
initial;text-decoration-color:initial">
<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
-color:initial">1. Publishes public key G*xi, G*ki, where ki is a random no=
nce<br></div><div style=3D"font-size:small;text-decoration-style:initial;te=
xt-decoration-color:initial">3. Xi =3D H(G*xi) ... Xi is the parties x coor=
dinate, for the purposes of interpolation</div><div style=3D"font-size:smal=
l;text-decoration-style:initial;text-decoration-color:initial">3. R =3D G*k=
=3D via interpolation of r1=3DGk1, r2=3DGk2... (see=C2=A0<span style=3D"ba=
ckground-color:rgb(255,255,255);text-decoration-style:initial;text-decorati=
on-color:initial;float:none;display:inline">HomPrf</span>)</div><div style=
=3D"font-size:small;text-decoration-style:initial;text-decoration-color:ini=
tial">4. L =3D H(X1,X2,=E2=80=A6) (see MuSig)<br></div><div style=3D"font-s=
ize:small;text-decoration-style:initial;text-decoration-color:initial">
<div style=3D"text-decoration-style:initial;text-decoration-color:initial">=
5. L2 =3D H2(XN,XN-1,=E2=80=A6) (see MuSig... H2 is a "second hash&quo=
t;)<br></div><div style=3D"text-decoration-style:initial;text-decoration-co=
lor:initial"></div>
6. X =3D sum of all H(L,Xi)Xi (<span style=3D"background-color:rgb(255,255,=
255);text-decoration-style:initial;text-decoration-color:initial;float:none=
;display:inline">see MuSig</span>)</div>7. Computes e =3D H(R | M | X) ....=
standard schnorr e... not a share<div style=3D"font-size:small;text-decora=
tion-style:initial;text-decoration-color:initial">
<div style=3D"text-decoration-style:initial;text-decoration-color:initial">=
8. Computes e2 =3D H(R | M | X2) ... a second blinding factor<br></div><div=
style=3D"text-decoration-style:initial;text-decoration-color:initial"></di=
v>
9. Computes si =3D ki *e2 + xi * e ... where si is a "share" of t=
he sig, and xi is the private data, and e, e2 are blinding factors<br></div=
><div style=3D"font-size:small;text-decoration-style:initial;text-decoratio=
n-color:initial">10. Publishes (si, e, e2) as the share sig<br></div><div s=
tyle=3D"font-size:small;text-decoration-style:initial;text-decoration-color=
:initial"><br></div><div style=3D"font-size:small;text-decoration-style:ini=
tial;text-decoration-color:initial">The final signature is computed via int=
erpolation, and e2 is can be subtracted to recover a "normal" sch=
nor sig for the set of participants.<br><br></div><div style=3D"font-size:s=
mall;text-decoration-style:initial;text-decoration-color:initial">Now there=
's no mechanism for a birthday attack on k.<br></div><div style=3D"font=
-size:small;text-decoration-style:initial;text-decoration-color:initial"><b=
r></div>
</div></div><br></div><div class=3D"gmail_extra"><br><div class=3D"gmail_qu=
ote">On Fri, Jul 20, 2018 at 1:34 PM, Erik Aronesty <span dir=3D"ltr"><<=
a href=3D"mailto:erik@q32.com" target=3D"_blank">erik@q32.com</a>></span=
> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bo=
rder-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"g=
mail_extra">
<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
-color:initial">Hi, thanks for all the help.=C2=A0 =C2=A0I'm going to s=
ummarize again, and see if we've arrived at the correct solution for an=
M of N "single sig" extension of MuSig, which I think we have.</=
div><div style=3D"font-size:small;text-decoration-style:initial;text-decora=
tion-color:initial"><br></div><div style=3D"font-size:small;text-decoration=
-style:initial;text-decoration-color:initial">- Using MuSig's solution =
for the blinding to solve the Wagner attack</div><div style=3D"font-size:sm=
all;text-decoration-style:initial;text-decoration-color:initial">- Using in=
terpolation to enhance MuSig to be M of N instead of M of M</div><div style=
=3D"font-size:small;text-decoration-style:initial;text-decoration-color:ini=
tial"><br></div><div style=3D"font-size:small;text-decoration-style:initial=
;text-decoration-color:initial">References:</div><div style=3D"font-size:sm=
all;text-decoration-style:initial;text-decoration-color:initial"><br></div>=
<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
-color:initial">=C2=A0- MuSig <a href=3D"https://blockstream.com/2018/01/23=
/musig-key-aggregation-schnorr-signatures.html" target=3D"_blank">https://b=
lockstream.com/2018/<wbr>01/23/musig-key-aggregation-<wbr>schnorr-signature=
s.html</a><br></div><div style=3D"font-size:small;text-decoration-style:ini=
tial;text-decoration-color:initial">=C2=A0- HomPrf <a href=3D"http://crypto=
.stanford.edu/~dabo/papers/homprf.pdf" target=3D"_blank">http://crypto.stan=
ford.edu/~<wbr>dabo/papers/homprf.pdf</a> (sections 7.1 and 7.4)</div><div =
style=3D"font-size:small;text-decoration-style:initial;text-decoration-colo=
r:initial"><br></div><div style=3D"font-size:small;text-decoration-style:in=
itial;text-decoration-color:initial">Each party:</div><div style=3D"font-si=
ze:small;text-decoration-style:initial;text-decoration-color:initial"><br><=
/div><div style=3D"font-size:small;text-decoration-style:initial;text-decor=
ation-color:initial">1. Publishes public key G*xi</div><div style=3D"font-s=
ize:small;text-decoration-style:initial;text-decoration-color:initial">3. X=
i =3D H(G*xi) ... Xi is the parties x coordinate, for the purposes of inter=
polation</div><div style=3D"font-size:small;text-decoration-style:initial;t=
ext-decoration-color:initial">3. r =3D G*x =3D via interpolation of Gx1, Gx=
2... (see=C2=A0<span style=3D"background-color:rgb(255,255,255);text-decora=
tion-style:initial;text-decoration-color:initial;float:none;display:inline"=
>HomPrf</span>)</div><div style=3D"font-size:small;text-decoration-style:in=
itial;text-decoration-color:initial">4. L =3D H(X1,X2,=E2=80=A6) (see MuSig=
)<br></div><div style=3D"font-size:small;text-decoration-style:initial;text=
-decoration-color:initial">5. X =3D sum of all H(L,Xi)Xi (<span style=3D"ba=
ckground-color:rgb(255,255,255);text-decoration-style:initial;text-decorati=
on-color:initial;float:none;display:inline">see MuSig</span>)</div><div sty=
le=3D"font-size:small;text-decoration-style:initial;text-decoration-color:i=
nitial">6. Computes e =3D H(r | M | X) .... standard schnorr e... not a sha=
re</div><div style=3D"font-size:small;text-decoration-style:initial;text-de=
coration-color:initial">7. Computes si =3D xi - xe ... where si is a "=
share" of the sig, and xi is the private data</div><div style=3D"font-=
size:small;text-decoration-style:initial;text-decoration-color:initial">8. =
Publishes (si, e, G*Xi)</div><div style=3D"font-size:small;text-decoration-=
style:initial;text-decoration-color:initial"><br></div><div style=3D"font-s=
ize:small;text-decoration-style:initial;text-decoration-color:initial">Any =
party can then derive s from m of n shares, by interpolating, not adding.</=
div><div style=3D"font-size:small;text-decoration-style:initial;text-decora=
tion-color:initial"><br></div><br class=3D"m_-4832618653516637091gmail-Appl=
e-interchange-newline">
<br></div></div>
</blockquote></div><br></div>
--000000000000dedb5505717400eb--
|