diff options
-rw-r--r-- | e3/52c960f6d71b1e0b254d1d9791b85b2e74d4c3 | 241 |
1 files changed, 241 insertions, 0 deletions
diff --git a/e3/52c960f6d71b1e0b254d1d9791b85b2e74d4c3 b/e3/52c960f6d71b1e0b254d1d9791b85b2e74d4c3 new file mode 100644 index 000000000..43d1166a4 --- /dev/null +++ b/e3/52c960f6d71b1e0b254d1d9791b85b2e74d4c3 @@ -0,0 +1,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. + |