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
|
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 562A6C3A
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 19 Jul 2018 12:24:54 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f44.google.com (mail-wm0-f44.google.com [74.125.82.44])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5B3FC784
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 19 Jul 2018 12:24:53 +0000 (UTC)
Received: by mail-wm0-f44.google.com with SMTP id h20-v6so6166631wmb.4
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 19 Jul 2018 05:24:53 -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=WZxiYH8jkzpvNaSbv7q4mXieujmKQpM3gu/v0djgsKU=;
b=Pl3/6CCwmQXbKJnrU2ZibKrku+QXgG/nKcY0x8iq9f/Vb9wcz5o06Z/9T80ibGsIyx
CzazOX7gdPjVCk7eK6RShj8nW8hLAtXQUIQolKCl8/5zrlUv2txMCk+wpmjIHyNr9CWi
zZySJ6xshI8v0JHqZJiD8zdz1BGRDnMkCFYJUVGvLSU7zBf+y7rM+/ez/JvDln1GaXN0
I7IgUUiwerGUnrnwjGAmRG+q7uE2PEobXonphc+5OE0aB0RPdiK6alLYmErGyVPEwPYf
VdnTgTdq0zwBpaXaigzf51GUTxfeKdYOlzkry4HKI24mIwJt5wd0vBFLrfS6+TQ0hMPm
OsTg==
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=WZxiYH8jkzpvNaSbv7q4mXieujmKQpM3gu/v0djgsKU=;
b=IX5SDwvy3plII3/M7QcDJfs+8Z7zWN/YGznhFqfdiJ8MHTtTrdtfZ8HVu3QAHfyfmp
oZL32uENAziPSRNuw1mzBUHUi0ZdzClgQbN46Cmaq3r7xv5Mor8V7IyQw7nGB5mWHc7X
RONqwGUW/K170m5k8UyrZDgEa4gWl4iWtb1udN5aCtz8Os2vh6wuM3Sgoj49GATP9gPi
bNYVfTqhk7D3THt6JFc8BKzKk4GYEQdGVLoAFWgEeJq/q83LjlownOk9d+lBAXjjALqE
7ZRH0aoKoq0Lm6ENmW97Yrl7PEVHz5TcrnHXVjNx7JwwWIbZ6eN6iQ3cS5rQIL1ScTOo
XzZw==
X-Gm-Message-State: AOUpUlHk3R7LutO4FtXYHERR/VQdBV9LSmfHokvUM8XiloeIjvpaZv6S
VkCcyKdVhPOQwxi2OJbarmEvjXKxpF/sT3LZFfUFVBVC1Q==
X-Google-Smtp-Source: AAOMgpdmOrazoIs0C/iQ2x0OxvF6sF2rtPkQGBdYQ/dAUDRtTFiULENgJir46qJr2l6R4GgzdLbTnOJ2iRmnv7piQtQ=
X-Received: by 2002:a1c:8952:: with SMTP id l79-v6mr3904764wmd.7.1532003091836;
Thu, 19 Jul 2018 05:24:51 -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>
<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>
In-Reply-To: <CAJowKg+QxcU0ECpZrvUckXQfBpn6Qri=gWzLA7+Y2mvTAq_mSw@mail.gmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Thu, 19 Jul 2018 08:24:39 -0400
Message-ID: <CAJowKgJO8o4coqsB_jpBiQKMQOggq9gG+Bde+EbymhUauK94mA@mail.gmail.com>
To: adam@cypherspace.org
Content-Type: multipart/alternative; boundary="000000000000157453057159441b"
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: Thu, 19 Jul 2018 12:51:32 +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: Thu, 19 Jul 2018 12:24:54 -0000
--000000000000157453057159441b
Content-Type: text/plain; charset="UTF-8"
Probably because my descriptions are a bit vague and rambling.
but I can't help but think that a SMC of a bitcoin private key, followed by
a secure multiparty computation of a signature is going to be more secure
overall.
I couldn't figure out how to do it offline. But one round of exchange
seems to work.
It comes down to the blinding factor (k). All parties need to agree to it
... which creates the second round.
On Thu, Jul 19, 2018, 8:16 AM Erik Aronesty <erik@q32.com> wrote:
> Also Wagner's algorithm shouldn't be applicable for a number of reasons.
> you can't birthday attack something where there's only a single variable
> that you can modify. And when you change the equation from additive you
> now have a multi-dimensional equation we're partitioning won't function.
> this is the basis of the perfect security of Shamir secret sharing.
>
> On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty <erik@q32.com> wrote:
>
>> OK, so you're going with this scenario:
>>
>> 1. I know Apub and Bpub,
>> 2. I know M is 3
>> 3. I'm choosing a random number for C's private key
>>
>> Cpub is g^C
>>
>> The equation I am solving for .. and trying to factor myself out of is
>> g^Ax + g^B*2 + g^C*3
>>
>> I don't know A or B... I only know their public keys.
>>
>> I don't think it's possible to adaptively choose C for an attack on the
>> multisig construction, when using hash of the public key as the X
>> coordinate in the polynomial, because in order to satisfy the equation and
>> factor out C, you would need to be able to break the hash.
>>
>> With an additive construction, yes... adaptive attacks are possible.
>> But in a shamir secret sharing interpolation, you need a public X
>> coordinate as well as a secret share. Choosing hash(pub) as X, prevents
>> this attack.
>>
>>
>> On Wed, Jul 11, 2018 at 6:35 AM, Adam Back <adam.back@gmail.com> wrote:
>>
>>> On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev <
>>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>> > Basically you're just replacing addition with interpolation everywhere
>>> in the musig construction
>>>
>>> Yes, but you can't do that without a delinearization mechanism to
>>> prevent adaptive public key choice being used to break the scheme using
>>> Wagner's attack. It is not specific to addition, it is a generalized
>>> birthday attack.
>>>
>>> Look at the delinearization mechanism for an intuition, all public keys
>>> are hashed along with per value hash, so that pre-commits and forces the
>>> public keys to be non-adaptively chosen.
>>>
>>> Adaptively chosen public keys are dangerous and simple to exploit for
>>> example pub keys A+B, add party C' he chooses C=C'-A-B, now we can sign for
>>> A+B+C using adaptively chose public key C.
>>>
>>> Btw Wagner also breaks this earlier delinearization scheme
>>> S=H(A)*A+H(B)*B+H(C)*C
>>>
>>> Adam
>>>
>>
>>
--000000000000157453057159441b
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"auto">Probably because my descriptions are a bit vague and ramb=
ling.<div dir=3D"auto"><br></div><div dir=3D"auto">but I can't help but=
think that a SMC of a bitcoin private key, followed by a secure multiparty=
computation of a signature is going to be more secure overall.</div><div d=
ir=3D"auto"><br></div><div dir=3D"auto">I couldn't figure out how to do=
it offline.=C2=A0 But one round of exchange seems to work.</div><div dir=
=3D"auto"><br></div><div dir=3D"auto">It comes down to the blinding factor =
(k).=C2=A0 All parties need to agree to it ... which creates the second rou=
nd.</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Thu, Jul =
19, 2018, 8:16 AM Erik Aronesty <<a href=3D"mailto:erik@q32.com">erik@q3=
2.com</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"au=
to">Also Wagner's algorithm shouldn't be applicable for a number of=
reasons.=C2=A0 you can't birthday attack something where there's o=
nly a single variable that you can modify.=C2=A0 =C2=A0 And when you change=
the equation from additive you now have a multi-dimensional equation we=
9;re partitioning won't function.=C2=A0 this is the basis of the perfec=
t security of Shamir secret sharing.</div><br><div class=3D"gmail_quote"><d=
iv dir=3D"ltr">On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty <<a href=3D"=
mailto:erik@q32.com" target=3D"_blank" rel=3D"noreferrer">erik@q32.com</a>&=
gt; 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"ltr">OK, so =
you're going with this scenario:<br><div><br></div><div>1. I know Apub =
and Bpub,</div><div>2. I know M is 3</div><div>3. I'm choosing a random=
number for C's private key</div><div><br></div><div>Cpub is g^C</div><=
div><br></div><div>The equation I am solving for .. and trying to factor my=
self out of is g^Ax + g^B*2 + g^C*3</div><div><br></div><div>I don't kn=
ow A or B... I only know their public keys.</div><div><br></div><div>I don&=
#39;t think it's possible to adaptively choose C for an attack on the m=
ultisig construction, when using=C2=A0hash of the public key as the X coord=
inate in the polynomial, because in order to satisfy the equation and facto=
r out C, you would need to be able to break the hash.</div><div><br></div><=
div>With an additive construction, yes... adaptive attacks are possible.=C2=
=A0 =C2=A0But in a shamir secret sharing interpolation, you need a public X=
coordinate as well as a secret share.=C2=A0 =C2=A0Choosing hash(pub) as X,=
prevents this attack.</div><div><br></div></div><div class=3D"gmail_extra"=
><br><div class=3D"gmail_quote">On Wed, Jul 11, 2018 at 6:35 AM, Adam Back =
<span dir=3D"ltr"><<a href=3D"mailto:adam.back@gmail.com" rel=3D"norefer=
rer noreferrer" target=3D"_blank">adam.back@gmail.com</a>></span> wrote:=
<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-lef=
t:1px #ccc solid;padding-left:1ex"><div dir=3D"auto"><span><div dir=3D"ltr"=
style=3D"font-family:sans-serif">On Wed, Jul 11, 2018, 02:42 Erik Aronesty=
via bitcoin-dev <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.or=
g" rel=3D"noreferrer noreferrer" target=3D"_blank">bitcoin-dev@lists.linuxf=
oundation.org</a>> wrote:<br></div><span style=3D"font-family:sans-serif=
">> Basically you're just replacing addition with interpolation ever=
ywhere in the musig construction</span>=C2=A0<div dir=3D"auto"><br></div></=
span><div dir=3D"auto">Yes, but you can't do that without a delineariza=
tion mechanism to prevent adaptive public key choice being used to break th=
e scheme using Wagner's attack. It is not specific to addition, it is a=
generalized birthday attack.</div><div dir=3D"auto"><br></div><div dir=3D"=
auto">Look at the delinearization mechanism for an intuition, all public ke=
ys are hashed along with per value hash, so that pre-commits and forces the=
public keys to be non-adaptively chosen.=C2=A0</div><div dir=3D"auto"><br>=
</div><div dir=3D"auto">Adaptively chosen public keys are dangerous and sim=
ple to exploit for example pub keys A+B, add party C' he chooses C=3DC&=
#39;-A-B, now we can sign for A+B+C using adaptively chose public key C.</d=
iv><div dir=3D"auto"><br></div><div dir=3D"auto">Btw Wagner also breaks thi=
s earlier delinearization scheme S=3DH(A)*A+H(B)*B+H(C)*C</div><span class=
=3D"m_5467970328507897024m_-2119242826565656256HOEnZb"><font color=3D"#8888=
88"><div dir=3D"auto"><br></div><div dir=3D"auto">Adam</div></font></span><=
/div>
</blockquote></div><br></div>
</blockquote></div>
</blockquote></div>
--000000000000157453057159441b--
|
