From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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 (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 To: waxwing/ AdamISZ , Bitcoin Development Mailing List Date: Wed, 02 Jul 2025 13:36:08 +0200 In-Reply-To: <3f23ebaa-02c7-45d1-bf57-9baf48c133a3n@googlegroups.com> References: <039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com> <604ca4d2-48c6-4fa0-baa6-329a78a02201n@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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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.