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
|
Delivery-date: Wed, 02 Jul 2025 04:41:58 -0700
Received: from mail-qt1-f183.google.com ([209.85.160.183])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBDWIFPUA4ICRB6VVSTBQMGQEVGQRLJQ@googlegroups.com>)
id 1uWvqf-0001Cs-IY
for bitcoindev@gnusha.org; Wed, 02 Jul 2025 04:41:58 -0700
Received: by mail-qt1-f183.google.com with SMTP id d75a77b69052e-4a43ae0dcf7sf142040691cf.1
for <bitcoindev@gnusha.org>; Wed, 02 Jul 2025 04:41:57 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1751456511; cv=pass;
d=google.com; s=arc-20240605;
b=ft3h/Vc/eWnxe63Tecjd2CWoJCyofeQYIM48Zg/X90R9LHLD8kS8WwkMeJhPhcEe4m
JyfoDMFFzSix49ofdruG2paszSQ6KPGvBKEsi5tJse0yQ4t0yn8xHQaQ4KnxrMKcK/xX
Dzo8EuiL4MMNyKJNGYNj5i3Vb/uV7c521Ebxd63RByfbykoq6UyfbArM+eIs71E9FVbz
MSl4hObPMd+XIwsmNQyH1LPr0TcsUDDgH/s44oVAeD43tdv7aOBXV4mZZ23DX9nPkv7C
BNzv0hhfbapLWI3AowAy8Ve4gizIITbeKxSxGzfy/FX8NMBl2pTpLgbiA039L7SIkmwb
p4jA==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:mime-version:references:in-reply-to
:date:to:from:subject:message-id:sender:dkim-signature;
bh=3Iq3cs3vfQHquHNf0yKQltoY7Gneg7rhgEXsE2X1ntw=;
fh=biQLkhsAtMTvm2vEEvTaYmt154icElPyBY6rwZKmMPI=;
b=kKc4lKKnbRCOYnEGKetbUim7b/door/x1IEgIRs/xetQ1y2UXf8oIIsyYB9AtJpfG9
Ex3+E8e/26pLJhqlQI1uMvsCxVyYRBGC9U2jwIbHc3WCEv1ekE4F9qD7gUITodSK9TAN
/207aRmUtTyqS4P6Cv49ZPyDGI4WYlB5S31HXiaskcuyFItF67Wgl2VR81fbBJFXjZy4
eEy3Efrb38qTP7RM6w2Tdaxfc7YzO2jdUmZ/tPlAz+H5vtjaeNZ5Z2+UvrVdoV24mSQF
q7V7HD60CP+x+hgPg9KNkASP1WKboHq/Rr/EEpFfeOsylaL6QOIbd7tJnIhIUaeF81L1
pxOQ==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@timruffing.de header.s=MBO0001 header.b=TV008ajg;
spf=pass (google.com: domain of crypto@timruffing.de designates 2001:67c:2050:0:465::101 as permitted sender) smtp.mailfrom=crypto@timruffing.de;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=timruffing.de
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1751456511; x=1752061311; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:mime-version:references:in-reply-to:date:to:from
:subject:message-id:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=3Iq3cs3vfQHquHNf0yKQltoY7Gneg7rhgEXsE2X1ntw=;
b=QCsS8TmvtC1o5xqix+LhS1Jv3v2n1xt9bB1oQ4KGF65e27zgqqpLj03JifMh7vS2jY
zpWxfoLH8aGDH8mD1+3+ggKugOWFFz8ICraSl3lLUUp7KGXOTl6vOPGoh7EPgYuFwq5u
HT/3ewjPSZ6Maf2Fhwn3SjKQ/y/eyfPIwVxb7oQe7gK7hNq5FSoUBjAE8lLPXlIbNTsH
hPbBYpZDvuNYFc5HC2TjqJvAfzOiEVt08N6DwrjLe80VW09zfV49NrlK37ZeQmVI9DRP
3mZmcO4c7ZieQNhxaT4OxDGRqq7fN4lwNa4UdyntGOVYFqDKBZN44uTvBlJ3kMGwdhmJ
FwWw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1751456511; x=1752061311;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:mime-version:references:in-reply-to:date:to:from
:subject:message-id:x-beenthere:x-gm-message-state:sender:from:to:cc
:subject:date:message-id:reply-to;
bh=3Iq3cs3vfQHquHNf0yKQltoY7Gneg7rhgEXsE2X1ntw=;
b=iXUOBsZGQ7G7HJ66/c663jFmsM5tf1aye+tfvEBCNOyMt1gcrNFF7t9xKB3WRQSEYj
oARGznkn767mE435HswVc47IAxkwcc3LxAYtVgWSw2v11iVrWHAbHamnTSb//4kONhf4
tp6PTv1md0MGTIE9WaEbBhWTuqiEp/o06X05gvKdB/cZ4w0kW7t7xWuGoWXKJkLVN8uj
q5ldVg7xcnO7UjpzFsViuT+2iS/QRdOxAL52ZClFTUxJ/QxhpuawwaEfk8W3a0TVtda6
xtAL6cHdLMSjU+ulfvzFuZvt7b0o+g/pQz3tGTylaOCSogf4/VN+vDl1VYbZhaNDsW7/
wE+w==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCUsSMsx8vmb2V6tTzg26CW7cQqYglDs1dOuIBHsH57gSJSaMEp/LxekVMlCLB2Q9gfPlrewkdv2D/Es@gnusha.org
X-Gm-Message-State: AOJu0YyT+sBHoq3FJw5X61VaDIzxXuPz3E9SUKkLS/fY/a0YrlKk8aJ3
vCCwqK1Xfb9PFdtPQKWzmZxtPt3PPifeCo+Rxi19s6066nzt2R2hTSyC
X-Google-Smtp-Source: AGHT+IF+y9vqcAL64BPYL5dmtdJcsXJoHEt3Ms5cI3XJjkgq9rEGt3pdqQogRRzQ5jSxGrg1IopvQA==
X-Received: by 2002:ac8:5e0a:0:b0:494:b1f9:d683 with SMTP id d75a77b69052e-4a976ab1db3mr42900881cf.49.1751456510829;
Wed, 02 Jul 2025 04:41:50 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZeLf6JUFdq307nzx2fXWRHWrbBcWHa+L7RRszXi4Gz5zw==
Received: by 2002:ac8:5803:0:b0:477:78b2:dc08 with SMTP id d75a77b69052e-4a82ee59498ls34139261cf.0.-pod-prod-01-us;
Wed, 02 Jul 2025 04:41:46 -0700 (PDT)
X-Forwarded-Encrypted: i=2; AJvYcCXVV+pWchaw5z7EnEK9pvaNP6t8GlESksYrFH0iirjedSzT6LFpuhEZ/MO7/+WjnwyX16AjrxjplylQ@googlegroups.com
X-Received: by 2002:a05:620a:6844:b0:7c7:739d:5cea with SMTP id af79cd13be357-7d5c4798c57mr330969185a.35.1751456506363;
Wed, 02 Jul 2025 04:41:46 -0700 (PDT)
Received: by 2002:a05:6504:d91:b0:2b1:9626:e73d with SMTP id a1c4a302cd1d6-2b5fb63a227msc7a;
Wed, 2 Jul 2025 04:36:15 -0700 (PDT)
X-Forwarded-Encrypted: i=2; AJvYcCXRfAn01xfvOe/uhpzU/ibhQQbw6E5FdsfbIPgfqyWYAMU+Tx8+8zGnVIi02AdUnBL1mWIPbregj9i4@googlegroups.com
X-Received: by 2002:a05:651c:487:b0:31e:261a:f3e2 with SMTP id 38308e7fff4ca-32dfff68830mr6761991fa.1.1751456172813;
Wed, 02 Jul 2025 04:36:12 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1751456172; cv=none;
d=google.com; s=arc-20240605;
b=SNx1q22r3q9K6jOj0X9UUgD2w+qzXu9JXYYWnG/UDrGR8BCs0e+x7kVtgl+nZop2hf
talK/aFPQLpOqC7sRL/u8GVmdcK5jQMU3C1NfIV05wLeUD0XQekTeUR9wbNPOiWo2+6u
rwiraPlqm3oJoZ3RW7zsJ9Nydk8EVw+4MSLqz7OL0S6EbNuqpJv2MsDYaK7EJ+h9Excj
btlIR3CJ51cn+sB1GbkPSSDRGcA/8yYbp2ptVizm1RdfhOIZe0+zfpMkKtay4q7UJd7o
t6A06+HPhzsSfVuw1aD9ZKvYQl++ioayCvjuuyVIGtpvayHJhwknS952lsufqVpNZoa0
oPAg==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=mime-version:content-transfer-encoding:references:in-reply-to:date
:to:from:subject:message-id:dkim-signature;
bh=FzUnWzrZaG9QFzBmunDMZD7KFHeuHbSl5Krz/MxCN0c=;
fh=2EV9HtMw1QTzGSfUm2X/O0xVoxxmy5vUj8s0Z9ARrDA=;
b=Wv0OKXTdKGEDWucGEfQHuE0bs8aIXeMFV1aW1f9+UHOKgDxpv695u05C5dBrWDnpJj
b/7fkAL+aa3C4BJsZ66esISsoFE9RA+cM6aTuKuBleSv8GZ7NrjNFWd6VDQFX04/PkxI
Ru9tCko/qHri782ZJZUkwTJ3r2aR/mAaNG0dLt4kuKq8iEXJAAlPDPecFEMLLamIDGwl
it7L07qQ8NrmXidz88CEEoO6Q+w89fWwlllyIz3g+JOjTVV+TpXMlWVHN/IzbCfW6GFh
AQQfXRQdcDR/1OvD53hqQ9OguSz6yQOf+knxMSYb6dgf5y+VKK9RkMNRyYRcNbzmI3AZ
+jpw==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@timruffing.de header.s=MBO0001 header.b=TV008ajg;
spf=pass (google.com: domain of crypto@timruffing.de designates 2001:67c:2050:0:465::101 as permitted sender) smtp.mailfrom=crypto@timruffing.de;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=timruffing.de
Received: from mout-p-101.mailbox.org (mout-p-101.mailbox.org. [2001:67c:2050:0:465::101])
by gmr-mx.google.com with ESMTPS id 38308e7fff4ca-32cd2c4275fsi5556341fa.0.2025.07.02.04.36.12
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
Wed, 02 Jul 2025 04:36:12 -0700 (PDT)
Received-SPF: pass (google.com: domain of crypto@timruffing.de designates 2001:67c:2050:0:465::101 as permitted sender) client-ip=2001:67c:2050:0:465::101;
Received: from smtp202.mailbox.org (smtp202.mailbox.org [IPv6:2001:67c:2050:b231:465::202])
(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256)
(No client certificate requested)
by mout-p-101.mailbox.org (Postfix) with ESMTPS id 4bXHsQ00ZVz9tK1;
Wed, 2 Jul 2025 13:36:10 +0200 (CEST)
Message-ID: <437237c5f0debe352aafd0a184d6266c14d6e142.camel@timruffing.de>
Subject: Re: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive
Aggregate Signatures
From: Tim Ruffing <crypto@timruffing.de>
To: waxwing/ AdamISZ <ekaggata@gmail.com>, Bitcoin Development Mailing List
<bitcoindev@googlegroups.com>
Date: Wed, 02 Jul 2025 13:36:08 +0200
In-Reply-To: <3f23ebaa-02c7-45d1-bf57-9baf48c133a3n@googlegroups.com>
References: <be3813bf-467d-4880-9383-2a0b0223e7e5@gmail.com>
<039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com>
<604ca4d2-48c6-4fa0-baa6-329a78a02201n@googlegroups.com>
<f9e082e3-4079-40b6-aa49-5d1b9b3b1e29@gmail.com>
<a9f133ff-1d8e-45a3-8186-79fb52bbd467n@googlegroups.com>
<3f23ebaa-02c7-45d1-bf57-9baf48c133a3n@googlegroups.com>
Content-Type: text/plain; charset="UTF-8"
MIME-Version: 1.0
X-Rspamd-Queue-Id: 4bXHsQ00ZVz9tK1
X-Original-Sender: crypto@timruffing.de
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@timruffing.de header.s=MBO0001 header.b=TV008ajg; spf=pass
(google.com: domain of crypto@timruffing.de designates 2001:67c:2050:0:465::101
as permitted sender) smtp.mailfrom=crypto@timruffing.de; dmarc=pass
(p=NONE sp=NONE dis=NONE) header.from=timruffing.de
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
<https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.8 (/)
First of all, again great to see that you look so carefully at the
paper.
Your observation is right: If each participant has a distinct b_i as
you've sketched, then the duplicate checks can be omitted. And I tend
to agree that this is more natural scheme. In fact, this is where we
started, and we had a security proof of this (though without tweaking
worked out) in an earlier unpublished draft of the paper, and only
afterwards we found a scheme with a single b.
The reason we why prefer the scheme with a single b is simply
efficiency. The current signing protocol needs 3 group exponentiations
(i.e., scalar-point multiplications). With separate b values, one of
those becomes a multi-exponentiation of size n-1, which is much slower
and needs O(n/log n) time instead of O(1).
Another, very minor and optional efficiency benefit is that the
coordinator can take care of the computation of the final R2 and send
it to the participants. (But that's really minor, because the
coordinator needs to send the individual R_{2,i} values anyway.)
Intuitively, we manage to get away with a single b by (ab)using the R_i
values as ephemeral identifiers for the participants, which makes it
possible to distinguish them even if they happen to have the same
public key (or, in other words, if it's the same participant that joins
the session more than once). This is why we need the uniqueness check,
to make sure that the identifiers are unique.
And yes, the uniqueness check looks a bit strange at first glance, but
(as the proof shows) there should be nothing wrong with it. One could
argue that the uniqueness check is a potential footgun in practice
because an implementation could omit it by accident, and would still
"work" and produce signatures. But we find this not really convincing
because it's possible to create a failing test vector for this case.
We didn't talk about identifying disruptive participants in the paper
at all, but one could also argue that the uniqueness check creates a
problem if the honest participants want to figure out who disrupted a
session: if malicious participant i copies from honest participant j,
then how the others tell who of them to exclude?
But if you think about it, that's not a real issue. In any case,
identifying disruptive participants will work reliably only if the
coordinator is honest, so let's assume this. And then, if additionally
the participants have secure channels to the coordinator, then no
malicious can steal the R_{2,j} of an honest participant j. So, if the
coordinator sees that R_{2,i} = R_{2,j}, the right conclusion is that
they are colluding and both malicious.
On Mon, 2025-06-16 at 12:35 -0700, waxwing/ AdamISZ wrote:
> So here's my question: why does the signing context, represented by
> "b", in the aggregate R-value, need to be a fixed value across
> signing indices? Clearly if we have one b-value, H-non(ctx), where
> ctx is ((P1, m1), (P2, m2),..) [1], then it is easy to sum all the
> R1,i = R1 and then sum all the R2,i values = R2 and then R = R1 +
> bR2, exploiting the linearity. But why do we have to? If coefficient
> b were different per participant, i.e. b_i = H(ctx, m_i, P_i) then it
> makes that sum "harder" but still trivial for all participants to
> create/calculate. All participants can still agree on the correct
> aggregate "R" before making their second stage output s_i.
>
> If I am right that that is possible, then the gain is clear (I
> claim!): the attacks previously described, involving "attacker uses
> same key with different message" fail. The first thing I'd note is
> that the basic thwarting of ROS/Wagner style attacks still exists,
> because the b_i values still include the whole context, meaning
> grinding your nonce doesn't allow you to control the victim's
> effective nonce. But because in this case, you cannot create
> scenarios like in Appendix B, i.e. in the notation there:
> F(X1, m1(0), out1, ctx) = F(X1, m1(1), out1, ctx) is no longer true
> because b no longer only depends on global ctx, but also on m1 (b_1 =
> Hnon(ctx, m1, P1) is my proposal),
>
> then the "Property 3" does not apply and so (maybe? I haven't thought
> it through properly) the duplication checks as currently described,
> would not be needed.
>
> I feel like this alternate version is more intuitive: I see it as
> analogous to (though not the same) as Fiat-Shamir hashing, where the
> main idea is to fix the actual context of the proof; but the context
> of *my* partial signature for this aggregate, is not only ((P1, m1),
> (P2, m2),..) but also my particular entry in that list.
>
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/437237c5f0debe352aafd0a184d6266c14d6e142.camel%40timruffing.de.
|
