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
|
Return-Path: <jonasdnick@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 811A69F0
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 28 Nov 2018 16:43:17 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wr1-f41.google.com (mail-wr1-f41.google.com
[209.85.221.41])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1E8AE762
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 28 Nov 2018 16:43:16 +0000 (UTC)
Received: by mail-wr1-f41.google.com with SMTP id v13so23529113wrw.5
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 28 Nov 2018 08:43:15 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=from:subject:to:references:openpgp:autocrypt:message-id:date
:user-agent:mime-version:in-reply-to:content-language
:content-transfer-encoding;
bh=r3di/8RuGDDXXMH+CkUmm4Dcl/tAMnvQ/wq44jxyhUc=;
b=R7lraY8+q3elVGPvflHknkTlb/7iyEiJZAIireSiLnw8qUafvPGdWDGTBScjPlpsgA
+xSbhzYdlSGJLjApDJoHzh7lE3Amdt4IECmgzp6RsgUIkcxgZTtVry2svqUk8x3MmPcA
Gi6O8VJbI8igkKsFNm0703Wldc/IvVC9aU+w2fqy1Ful8sqSWy5DqfSPOwUZRH7RDOq6
zjEBlTB+KH65IuPbllKY0O/iGdBzS3z5zfsFIN9oDB14IUzuE9xapdeT3IVuNOELu0gi
6seuAJy15Ecjh0GEWH9SYuPD3A5t18jSDtsQmg0lrl0Z0db7N1f5qa2SAgp8f+JkpJPi
9rjw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:from:subject:to:references:openpgp:autocrypt
:message-id:date:user-agent:mime-version:in-reply-to
:content-language:content-transfer-encoding;
bh=r3di/8RuGDDXXMH+CkUmm4Dcl/tAMnvQ/wq44jxyhUc=;
b=ktf3Gm1kTXHFZ1vxt0hKvQswYoe9DfD7W7ZB5tHPkEJx2LbFgXGRb77QvH3hjSCcFl
sQk+QAFwocOXB5auKM8aTXBs9Wh0b/o0vYq04FP6M31C919dL3P65iwD2zlhfn5ZomBL
op+PriNu5GD2w0gpyr7DZQa7/X207Vw4gXEJmzpbtm/c/bbC0rLuTshpzN9KYpwx75F1
V8nkoH0xwdKSV13HhmhhA8V22e4ISQ7blxqH3TzOZmfJiUYAt6za33j+aoP7weOSu5Cl
a4T19uauqyJ70FfvXpnyzMVkbM6siODNOWHn1pD+xzstdOABRGacqQTDWeG3B+/umGjD
C4FQ==
X-Gm-Message-State: AA+aEWaS9VIwQKZq923U2os8DBxiqnSpRab09bWt5gY98dK72IYHwH9g
wz3pC4AwMDjYoQPkuSftKYvbnBad
X-Google-Smtp-Source: AFSGD/X0HIlrVdXTfAfDdBKEb6yKF036iFKNH0pWSnrj6uisCugUTTGDAjGgAlbhcRWkv6Drs6Yj8Q==
X-Received: by 2002:a05:6000:110f:: with SMTP id
z15mr30703685wrw.136.1543423393993;
Wed, 28 Nov 2018 08:43:13 -0800 (PST)
Received: from [192.168.178.36] (i59F76689.versanet.de. [89.247.102.137])
by smtp.googlemail.com with ESMTPSA id
i16sm4038060wmd.28.2018.11.28.08.43.12
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Wed, 28 Nov 2018 08:43:13 -0800 (PST)
From: Jonas Nick <jonasdnick@gmail.com>
X-Google-Original-From: Jonas Nick <jonasd.nick@gmail.com>
To: Anthony Towns <aj@erisian.com.au>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
References: <CALhDas2W5QEPmw8JEgak0zf7y3N0UFTiMVk-djR8x9_WYZiyfQ@mail.gmail.com>
<CAB0O3SVjhXVV4PKYPh+2O4xZomcyT-T2Mis1A8riTtrnUUigig@mail.gmail.com>
<20181128104946.bftgbclno6gzzji4@erisian.com.au>
Openpgp: preference=signencrypt
Autocrypt: addr=jonasd.nick@gmail.com; prefer-encrypt=mutual; keydata=
xsFNBFQ2o3oBEACv5N5WajlYk+i/4B8FmniipCB4biIKg38spMNt1EYM6RzTu+hbOrVOlJW8
fq/ih+dvlpreGxRPQlX4jr75kwoJCykd3geywTUl3KPLeJ/JRQJ8fVkine4Wr5qB5Jwo3+wt
inDVooaaF32Y0HolNacXVzT1x9uwn83Bz/ifg+iGATn/e1Si3ga/ytY5wYDzFz6aUDRW8ulu
DcG8ARMAgtzmi66EuyQyIWwSyoWFU8wJ98slU9LKuTu23r6HdxFuV+P2H1omJm+z8cd4QBMj
I23uHst0Wx1MyTeVhZCnQAghyasA3oopwzqRf5wwECAui1oZhr59R4R1DHJjn0PeWZXBSnOo
XPQ1ERjz4nQrODiIDEabD5DClPHZ1bte0tswm1aYBtD8/me9ck+SJdoH5r0DJrXCTtNl1XG1
9TTUINQe0eaQUOTakZmVaneCeSrw/pKOknkzudOCNCbmngKa2oJQOynrdsBuoigIYY+NQdot
fk1nJljrBzyTh4sFktbHyA24x/hCykMX6FnIQxDnsGR+S3I+vzADBLBBMQQtZsUA+xnvPu4l
6You5SZMVhgprQy38bKybeIGxSZtmPNtBf8ouKhAUpbIfOaq6BoP4EtueXk/vyieFxXiIkbF
N6b3pjhkG7wVG17HqCqeVeHz1ZAQJUPcqDQAPaelBf38RXPbeQARAQABzSJKb25hcyBOaWNr
IDxqb25hc2Qubmlja0BnbWFpbC5jb20+wsF/BBMBAgApAhsDBwsJCAcDAgEGFQgCCQoLBBYC
AwECHgECF4AFAlu1I0QFCQtA5soACgkQsacOT43NA2Y5zA/9G1kt1ECa6zPhpEBV5iqD1omt
ABdrZSxD8gBsZOMt2nLE1f4J0Oqy9LfMzKFzC8Kyd7usu6HVA8XM3fjVgqi+cDlEhaE+RqFi
FVJjai7Fo1EqQGoD8QKTHDpGMNAmkfiQI7yc7OOxJ7X/nRpI8EnUsHG0slw3ieG6krrwLMfi
rdJz5xA3P0tjdz/gRsG1IkwaB1bWnrIyh4oS9MiTSO1GZzHdRrhYZPFnJa7XiQsDWTvtTf4o
fkbDAxqsKSqJhh99Gl79dXjJ1X9c6YfmxdOWuHZwtpJRgTFXSavaojkjPdnx4/f8lsgQg0tI
BEaZnfroAvJCkYCqxNAPS5pSCaRaZbm+eoBl9848eFQztds/xfG3xIpn6VaOSdDNCD0+kSiO
LrqghKLN3nPWOfCU0zPlkFuNsWX0ALvAJj6UKGbvMRfR6uj5NPZuHbA2FK9/1pOfKLjm6bHI
2HtXeS5B0+eoAjHzoF9w/2DM4+DLU8Qbn63CpDZ3dodqK3Z7PHLv9oiiCVUFxia0J9YUZJru
1jFHc3BA/Ado4LSxjyUbG0kDQjddvBEmQIkW5c2VrkczYv8gCOLwiUF+RPqc8PxGRs5I5SqJ
RzcEN9nIaFcP5MTPrabbkXKLw6ZhHqc3J85qMOLoxThP5SCWM7I1SwLYIGgcWGFtL27U9IXe
/wzNH4aerKfOwU0EWVEx3gEQAMH7dVvWR+idYEe3OVDY/SVV80wjfOe1zTDTOQ+qB8D5Fin8
7v3Rpt8y0RxW3Y4Fbljoi635jhJo3/MoTHvZSes61LbnPzUjReYmIqMYprJ5HSF+IkskW9E5
P078G6wI2hxwjRXXg4y+Z+oYk3C8GBH1Ejjs2i3lmYIPACMUKDba26ZIuxkjK5OB3tZHmTOu
YRJ9eP5KltSD4P6Y6ZTgDlvUpQeJa0w52A4dOQARmyKDiGJ5z+x8gSeCK3IrYWyt79et364R
SWZG4pFj34fnHIcHPebwOMX6gMZdPIyKNxaTwA62gnQp5loJoJJUTsgSTSOW1Dzvjjxm/4iW
M2HlS6NT0f80fSw1GnfIxSSPrx2F4Iwg8ckAWzy/EYcGr7+pHJ28AVVN4q0EG/9WvTsL9iM9
Zqbw9cI9faDTDuJfYtcxIorMgkmDF4u14GFdzSsx5loTO+/7VFZhFDLLCC1eHCzOvLjHFg+9
XpR0N7eArpDiYBWPFWBVthHtb6JuXqAWyZ+0LZZw2JGM4/gzUdFr+1FznJX1MqtlwtrAggM4
xrPlnIf4qwL6B074tr00vzr4YIzl0FUGti9Qx+xozqeO2NmKltXmfBYfBJZdnfanVHp8XMDS
+z7CVKCzMkmnuyJ0QrY0jJVAxOvlwLQy363Nk5pRprrHna2R2+ZsTqf8Cw3dABEBAAHCwXwE
GAEIACYWIQQ2xxo3ydmIveglCNmxpw5Pjc0DZgUCWVEx3gIbDAUJA8JnAAAKCRCxpw5Pjc0D
ZgeWEACfP52WfyPUWMg8mZax834TW/RGBaUi9KQZc0tRX8lDrsD42aunTF+8va8t4/vw4Cfy
kloL+5mcz9orWzp+9YVO98U0O2s76zDTxBIJC5pp8ZRoqCZbRhD2w7DBNxgazeChCmsSmADn
/3ktkAztTI99I/xa/i7/PhVKn/MQJZ/vzFOwdvxaVar8W7jsWnzw43DFMVIVyWrwXeBaKVFe
vBwvnltvbmNyvx8L+3W0dPP4biVsCbT6Fteki++c3XoAooCut7ld9wP0oNiYUUFMSd2rEErd
QHPnaTGil/KAO2BMQEbcCXbDX7L9PX6rjonPwQIbaP3zNbuRfZj8LRKzz7ih+gOJRMPGGYX1
eMUVXwoi8EQeofLM7wmOQikXlDbVR0a3+kKj/g6yKsBFvRbtSx73DeLg2Zp4EodoUnF/0W3V
JqZCWeI794kfk6NFvKKn1GLfxdyj82wiqzzCNFnYe6H4l78kGCZ7E0yg0u0M0kCjtDfBlxHJ
r1FDbWf3e4yX76QwxsQwR5yiY9mpWWo6Z6XFDT2Jz6HQX7y9oJhV/cLyAMzVz3Y7BSLm9tX5
/pX1TjOC7jsEBBPYFk1XyLQ+Ip6ZT0TZx7nXNoF08GhTXFLLx7tSNzx1IE+Go0FXcA0vmYUy
Ex981QeJInExpznDYCvx7pHU1PzImXcSLzWzqR8Anw==
Message-ID: <dd9988c0-2635-88d7-21e4-ebd42e202990@gmail.com>
Date: Wed, 28 Nov 2018 16:43:12 +0000
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
Thunderbird/60.3.1
MIME-Version: 1.0
In-Reply-To: <20181128104946.bftgbclno6gzzji4@erisian.com.au>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US-large
Content-Transfer-Encoding: 8bit
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM,
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: Wed, 28 Nov 2018 23:33:04 +0000
Subject: Re: [bitcoin-dev] Multi party Schnorr Rust implementation
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: Wed, 28 Nov 2018 16:43:17 -0000
> For deterministic nonces, you generate r=H(p,m) based on the message
> being signed and your private key, so can only start this process when
> you start signing, and the sharing rounds mean interactivity.
It's not your point but it should be noted that this is not secure unless all
other signers give you zero knowledge proof that they've generated their nonce
in the same way. Otherwise, if your asked to sign the same message you'll use
the same nonce for two different challenges. In your example you'd compute
s=r+H(R',P',m)*p and s'=r+H(R'',P',m)*p from which an observer can compute the
secret key p.
On 11/28/18 10:49 AM, Anthony Towns via bitcoin-dev wrote:
> On Tue, Nov 27, 2018 at 10:33:30PM -0800, Devrandom via bitcoin-dev wrote:
>> Are there any candidates for non-interactive threshold signatures? Interactive
>> signatures are not very suitable for air-gapped use cases.
>
> I think you can work around this to some extent by "batching" signing
> requests.
>
> (Background:
>
> For interactive multisignatures (threshold or not), the protocol is:
>
> produce secret nonce r, calculate public nonce R=r*G
> everyone shares H(R)
> everyone shares R, checks received values match received hashes
> everyone calculates s=r+H(R',P',m)*p, shares s
>
> For deterministic nonces, you generate r=H(p,m) based on the message
> being signed and your private key, so can only start this process when
> you start signing, and the sharing rounds mean interactivity.
>
> )
>
> But you don't strictly need deterministic nonces, you just have to never
> use the same nonce with a different message. If you arrange to do that
> by keeping some state instead, you can calculate nonces in advance:
>
> phase 1:
> produce secret nonces r1..r1024, calculate R1..R1024
> share H(R1)..H(R1024)
>
> phase 2:
> store other parties hashes, eg as H1..H1024
> share R1..R1024
>
> phase 3:
> check received nonces match, ie H(R1)=H1, etc
>
> phase 4:
> request to sign msg m, with nonce n
> if nonce n has already been used, abort
> mark nonce n as having being used
> lookup other signer's nonces n and sum them to get R'
> calculate s = rn + H(R',P',m)*p
> share s
>
> That way you could do phases 1-3 once, and then do 1024 signatures during
> the month on whatever your current timetable is.
>
> You could also combine these phases, so when you get a signing request you:
>
> * receive msg to sign m, n=4; everyone else's R4, H(R5)
>
> * check H(R4) = previously received "H(R4)"
> * calculate R4' by summing up your and everyone's R4s
> * bump state to n=5
> * do the signature...
>
> * send sig=(s,R4), R5, H(R6)
>
> which would let you have an untrusted app that does the coordination and
> shares the nonces and nonce-hashes, and getting all the needed air-gapped
> communication in a single round. (This is effectively doing phase 3 and
> 4 for the current signature, phase 2 for the next signature, and phase
> 1 for the signature after that all in one round of communication)
>
> That seems almost as good as true non-interactivity to me, if your signing
> hardware is capable of securely storing (and updating) a few kB of state
> (which is probably not quite as easy as it sounds).
>
> Cheers,
> aj
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
|
