From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Mon, 16 Jun 2025 15:06:53 -0700 Received: from mail-yb1-f183.google.com ([209.85.219.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 1uRHyd-00033R-K4 for bitcoindev@gnusha.org; Mon, 16 Jun 2025 15:06:53 -0700 Received: by mail-yb1-f183.google.com with SMTP id 3f1490d57ef6-e819e8eb985sf5507944276.2 for ; Mon, 16 Jun 2025 15:06:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1750111606; x=1750716406; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=r30avzEhb39NMrftJNAbfdbGVt5G9Cx0yO3WRok8rvg=; b=mfyjUGbk7uRSC+/g/nnfXqzkLitmviJ5SehWIT1m0/Yu1i1HmOT6iIxZeI8UkATX1y 5MVYRcwE8o16e7KZLMilrGqyXz759m0lcL0j01H0fmnbrTx8cYmwVIS3WhtbRSHxIAae U2+FYAwJIph0gBMP/7w4x1pl9j2eqa98lO4gNx4OCpLpkKJrK+iLGRsfL+MSk9dhlI8k p5XnM0ZFsFzVSW7pzAF67yiCuM6SEhsPWMQFz7Q4fCxvo1HBPBH02VTu3+ozvZOpAOSu J+raUOYwcdfM5n7Hhl0+FeS+umdYrvIOuEIkQ+bLaNZ40/ziY1UGfa6mbLe4HOGrJSOO 1JKg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1750111606; x=1750716406; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=r30avzEhb39NMrftJNAbfdbGVt5G9Cx0yO3WRok8rvg=; b=fSyUA8CEuNMNmy6qaA4GMTq9kBh8xT4j81abi2b5Ng5EgFxwBh3fY82FgQIkTBC4RO fgT17JqZqZ0GVktgAr/er/XDbdsXvupoShDBdEGORi60r2zIk8LFNXJG0YSEwKDbYZEy zyGAaxHzMJs7IYOq340m1G4r1e7jNenL2w3+rBcBPr/FYBbokMbnaCSgmyQBalBTyvEc cVQkLZXFT42NCisNmsTHKtS+RwJulI3nEqTyU1TBdL/i+mkTirUvgFL02g2Lmjhz3nwG yhqWRv4imq9XpEObmq6zt2Tiv0BbFmIsFNMuS8M22K02iLyPDiq5BCPLjKESDO7KKn3e t51w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1750111606; x=1750716406; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=r30avzEhb39NMrftJNAbfdbGVt5G9Cx0yO3WRok8rvg=; b=YL1DH+O3rPyyzGeviMkR6Cqv/hWljHDdxUpzBSKfmTHeCeimA/MNxPcFFTggSlL3jJ ny4BMGnQQmvJr/a98/FFk/4eFkwLeTvDxEkXrvGSE8MToz/NLB8g2afgi6REQpxhr8SD NWnV0DgbKHmXWjxfx/SMtYwO98rFFtjs8V8wTmfjqSse/A6th4MxoCx0AuwCa6SMpSWY vBs3MKsGYVJFVdZyX2UE++JNQOn6kwcxjGg3BHBXAAe1ycwpNECR2YQDHtWunRnsWvdV z2TwN4arKDez/MPLdYuRGuWr+ByU0I7bQYmB2D3LpOGjUvam6L2JrThI42w1RBtPX2Ga PIFw== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCWrwWm0YCsu+m/K4XY5RwUcQ8IymIRFbfQfAjOYA5aK2+rBhP6WGAo3IEEDSUaDsdAca2JTm1+zuG9p@gnusha.org X-Gm-Message-State: AOJu0YzDeUtft3s+cNDZhsSzfpx5N0PK/70V0nr7K28EDulCpWXG07lG Uy0rNcrcNnBiYQMSBrzSe5avMpuZLL39otkYiMNuCnu3BtsfFseKMae/ X-Google-Smtp-Source: AGHT+IETZBFE0iolNc7rfQ2dw0oyMP5DS/3z8iLPUnolOs8pFCBuNsK9LHyAB6BRp95/veFGUnve3Q== X-Received: by 2002:a05:6902:2493:b0:e82:1c5f:5069 with SMTP id 3f1490d57ef6-e822acaced0mr15689480276.4.1750111605839; Mon, 16 Jun 2025 15:06:45 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZesqtCTEX4vjozuqDxsbw3u+x7O7811ttELfVMnFqLQMg== Received: by 2002:a25:c881:0:b0:e81:7ebb:b7ba with SMTP id 3f1490d57ef6-e8261f93642ls739252276.1.-pod-prod-09-us; Mon, 16 Jun 2025 15:06:41 -0700 (PDT) X-Received: by 2002:a05:690c:906:b0:70e:29d2:fb7b with SMTP id 00721157ae682-71175498c04mr155769407b3.33.1750111601134; Mon, 16 Jun 2025 15:06:41 -0700 (PDT) Received: by 2002:a05:690c:2706:b0:6ef:590d:3213 with SMTP id 00721157ae682-71162a564f0ms7b3; Mon, 16 Jun 2025 12:35:44 -0700 (PDT) X-Received: by 2002:a05:690c:4b09:b0:70e:7ae4:5a3e with SMTP id 00721157ae682-711753bfad3mr158125887b3.11.1750102543716; Mon, 16 Jun 2025 12:35:43 -0700 (PDT) Date: Mon, 16 Jun 2025 12:35:43 -0700 (PDT) From: waxwing/ AdamISZ To: Bitcoin Development Mailing List Message-Id: <3f23ebaa-02c7-45d1-bf57-9baf48c133a3n@googlegroups.com> In-Reply-To: References: <039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com> <604ca4d2-48c6-4fa0-baa6-329a78a02201n@googlegroups.com> Subject: Re: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_331584_750040566.1750102543362" X-Original-Sender: ekaggata@gmail.com 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.5 (/) ------=_Part_331584_750040566.1750102543362 Content-Type: multipart/alternative; boundary="----=_Part_331585_1313770776.1750102543362" ------=_Part_331585_1313770776.1750102543362 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On the very important argument laid out in Appendix B: (for readers, this part of the paper deals with this problem: if the scheme= =20 can allow a scenario where the output "effective nonce" of an honest signer= =20 is the same for two different contexts and thus have two difference=20 signature hashes (in DahLIAS the sighash is H(L, R, X_i, m_i)), then with= =20 some deft mathematical footwork, we can extract a forgery on some other=20 message by that signer, as long as we can do a bunch of parallel signing=20 sessions; you can think of this as a sophisticated extension of the=20 fundamental idea of "nonce reuse is insecure"). ... I find myself stepping back through the arguments for this structure R1= =20 + bR2 in MuSig2. In that case, it is vital that we end with a verification= =20 that looks like : sG =3D?=3D R + H(R,P,m)P, precisely, because we need MuSi= g2=20 verification to be indistinguishable from single-key Schnorr verification. In DahLIAS we have (obviously, reasonably) relaxed that restriction. The=20 verification now allows for multiple pubkeys and messages to be inputs;=20 that's the whole point, we're publically verifying authorization of a bunch= =20 of (pubkey, message) pairs, so it would be incoherent or at least=20 unnecessary to *require* some kind of aggregate pubkey as input. (though as= =20 the paper discussed, you can *try* to build the IAS from an IMS, which=20 would mean actually doing that, but as demonstrated, it doesn't really seem= =20 to work, anyway). So when we look at the R component, which, distinct from the pubkeys, *must= =20 actually be published*, we do need to have an aggregated R value (to get a= =20 short signature), so at the end, we publish (R, s) and can do a=20 verification with the implied pubkey message pairs ((P1, m1), (P2, m2),..)= =20 like: sG =3D?=3D R + sigma (sighash(Pn,mn) * Pn). So here's my question: why does the signing context, represented by "b", in= =20 the aggregate R-value, need to be a fixed value across signing indices?=20 Clearly if we have one b-value, H-non(ctx), where ctx is ((P1, m1), (P2,=20 m2),..) [1], then it is easy to sum all the R1,i =3D R1 and then sum all th= e=20 R2,i values =3D R2 and then R =3D R1 + bR2, exploiting the linearity. But w= hy=20 do we have to? If coefficient b were different per participant, i.e. b_i = =3D=20 H(ctx, m_i, P_i) then it makes that sum "harder" but still trivial for all= =20 participants to create/calculate. All participants can still agree on the= =20 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= =20 attacks previously described, involving "attacker uses same key with=20 different message" fail. The first thing I'd note is that the basic=20 thwarting of ROS/Wagner style attacks still exists, because the b_i values= =20 still include the whole context, meaning grinding your nonce doesn't allow= =20 you to control the victim's effective nonce. But because in this case, you= =20 cannot create scenarios like in Appendix B, i.e. in the notation there: F(X1, m1(0), out1, ctx) =3D F(X1, m1(1), out1, ctx) is no longer true becau= se=20 b no longer only depends on global ctx, but also on m1 (b_1 =3D Hnon(ctx, m= 1,=20 P1) is my proposal), then the "Property 3" does not apply and so (maybe? I haven't thought it=20 through properly) the duplication checks as currently described, would not= =20 be needed. I feel like this alternate version is more intuitive: I see it as analogous= =20 to (though not the same) as Fiat-Shamir hashing, where the main idea is to= =20 fix the actual context of the proof; but the context of *my* partial=20 signature for this aggregate, is not only ((P1, m1), (P2, m2),..) but also= =20 my particular entry in that list. [1] Here I am ignoring that actual DahLIAS uses ctx including R2 values=20 because I understand that that is part of the checking procedure that I am= =20 (somewhat vaguely) here trying to argue might be omitted. Cheers, AdamISZ/waxwing On Thursday, May 1, 2025 at 12:14:30=E2=80=AFAM UTC-3 waxwing/ AdamISZ wrot= e: > > > That partial signatures do not leak information about the secret key x_= k=20 > is=20 > implied by the security theorem for DahLIAS: If information would leak,= =20 > the=20 > adversary could use that to win the unforgeability game. However, the=20 > adversary=20 > doesn't win the game unless the adversary solves the DL problem or finds = a=20 > collision in hash function Hnon. > > OK, so that's maybe a theoretical confusion on my part, I'm thinking of= =20 > the HVZK property of the Schnorr ID scheme, which "kinda" carries over in= to=20 > the FS transformed version with a simulator (maybe? kinda?). Anyway this = is=20 > a sidetrack and not relevant to the paper, so I'll stop on that. > > > This is a very interesting point, probably out of scope for the paper. = A=20 > single-party signer, given secret keys xi, ..., xn for public keys X1,=20 > ..., Xn=20 > can draw r at random, compute R :=3D r*G and then set s :=3D r + c1*x1 + = ... +=20 > cn*xn. So this would only require a single group multiplication. > > I feel bad for saying so, but I absolutely do believe it's in scope of th= e=20 > paper :) If there is a concrete, meaningful optimisation that's both=20 > possible and sensible (and as you say, there is such an ultra-simple=20 > optimisation ... I guess that's entirely correct!), then it should be=20 > included there and not elsewhere. Why? Because it's exactly the kind of= =20 > thing an engineer might want to do, but it's definitely not their place t= o=20 > make a judgement as to whether it's safe or not, given that these protoco= ls=20 > are such a minefield. I'd say even if there is *no* such optimisation=20 > possible it's worth saying so. > > I guess the counterargument is that it's suitable for a BIP not the paper= ?=20 > But I'd disagree, this isn't purely a bitcoin thing. > > On the third paragraph, yeah, as per earlier email, I realised that that= =20 > just doesn't work. > > On Wednesday, April 30, 2025 at 9:03:34=E2=80=AFAM UTC-6 Jonas Nick wrote= : > >> Thanks for your comments.=20 >> >> > That side note reminds me of my first question: would it not be=20 >> appropriate=20 >> > to include a proof of the zero knowledgeness property of the scheme,= =20 >> and=20 >> > not only the soundness? I can kind of accept the answer "it's trivial"= =20 >> > based on the structure of the partial sig components (s_k =3D r_k1 += =20 >> br_k2 +=20 >> > c_k x_k) being "identical" to baseline Schnorr?=20 >> >> That partial signatures do not leak information about the secret key x_k= =20 >> is=20 >> implied by the security theorem for DahLIAS: If information would leak,= =20 >> the=20 >> adversary could use that to win the unforgeability game. However, the=20 >> adversary=20 >> doesn't win the game unless the adversary solves the DL problem or finds= =20 >> a=20 >> collision in hash function Hnon.=20 >> >> > The side note also raises this point: would it be a good idea to=20 >> explicitly=20 >> > write down ways in which the usage of the scheme/structure can, and=20 >> cannot,=20 >> > be optimised for the single-party case?=20 >> >> This is a very interesting point, probably out of scope for the paper. A= =20 >> single-party signer, given secret keys xi, ..., xn for public keys X1,= =20 >> ..., Xn=20 >> can draw r at random, compute R :=3D r*G and then set s :=3D r + c1*x1 += ...=20 >> +=20 >> cn*xn. So this would only require a single group multiplication.=20 >> >> > On that last point about "proof of knowledge of R", I suddenly realise= d=20 >> > it's not a viable suggestion: of course it defends against key=20 >> subtraction=20 >> > attacks, but does not defend at all against the ability to grind nonce= s=20 >> > adversarially in a Wagner type attack=20 >> >> We believe Appendix B provides a helpful characterization of=20 >> "Wagner-style"=20 >> vulnerabilities. Roughly speaking, it shows that schemes where the=20 >> adversary can=20 >> ask the signer to produce a partial signature s =3D r + c*x or s' =3D r = +=20 >> c'*x such=20 >> that c !=3D c' then the scheme is vulnerable. In your "proof of knowledg= e=20 >> of R=20 >> idea", the adversary can choose to provide either R2 or R2' in a signing= =20 >> request, which would result in the same "effective nonce" r being used b= e=20 >> the=20 >> signer but different challenges c and c'.=20 >> > --=20 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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= 3f23ebaa-02c7-45d1-bf57-9baf48c133a3n%40googlegroups.com. ------=_Part_331585_1313770776.1750102543362 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On the very important argument laid out in Appendix B:

(for readers, this part of the paper deals with this problem: i= f the scheme can allow a scenario where the output "effective nonce" of an = honest signer is the same for two different contexts and thus have two diff= erence signature hashes (in DahLIAS the sighash is H(L, R, X_i, m_i)), then= with some deft mathematical footwork, we can extract a forgery on some oth= er message by that signer, as long as we can do a bunch of parallel signing= sessions; you can think of this as a sophisticated extension of the fundam= ental idea of "nonce reuse is insecure").

... I = find myself stepping back through the arguments for this structure R1 + bR2= in MuSig2. In that case, it is vital that we end with a verification that = looks like : sG =3D?=3D R + H(R,P,m)P, precisely, because we need MuSig2 ve= rification to be indistinguishable from single-key Schnorr verification.

In DahLIAS we have (obviously, reasonably) relaxed= that restriction. The verification now allows for multiple pubkeys and mes= sages to be inputs; that's the whole point, we're publically verifying auth= orization of a bunch of (pubkey, message) pairs, so it would be incoherent = or at least unnecessary to *require* some kind of aggregate pubkey as input= . (though as the paper discussed, you can *try* to build the IAS from an IM= S, which would mean actually doing that, but as demonstrated, it doesn't re= ally seem to work, anyway).

So when we look at t= he R component, which, distinct from the pubkeys, *must actually be publish= ed*, we do need to have an aggregated R value (to get a short signature), s= o at the end, we publish (R, s) and can do a verification with the implied = pubkey message pairs ((P1, m1), (P2, m2),..) like: sG =3D?=3D R + sigma (si= ghash(Pn,mn) * Pn).

So here's my question: why d= oes 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 =3D R1 and then sum all the R2,i values =3D R2 and then R = =3D R1 + bR2, exploiting the linearity. But why do we have to? If coefficie= nt b were different per participant, i.e. b_i =3D H(ctx, m_i, P_i) then it = makes that sum "harder" but still trivial for all participants to create/ca= lculate. All participants can still agree on the correct aggregate "R" befo= re making their second stage output s_i.

If I am= right that that is possible, then the gain is clear (I claim!): the attack= s previously described, involving "attacker uses same key with different me= ssage" fail. The first thing I'd note is that the basic thwarting of ROS/Wa= gner style attacks still exists, because the b_i values still include the w= hole context, meaning grinding your nonce doesn't allow you to control the = victim's effective nonce. But because in this case, you cannot create scena= rios like in Appendix B, i.e. in the notation there:
F(X1, m1(0),= out1, ctx) =3D F(X1, m1(1), out1, ctx) is no longer true because b no long= er only depends on global ctx, but also on m1 (b_1 =3D Hnon(ctx, m1, P1) is= my proposal),

then the "Property 3" does not ap= ply and so (maybe? I haven't thought it through properly) the duplication c= hecks as currently described, would not be needed.

I feel like this alternate version is more intuitive: I see it as analog= ous 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 si= gnature for this aggregate, is not only ((P1, m1), (P2, m2),..) but also my= particular entry in that list.

[1] Here I am ig= noring that actual DahLIAS uses ctx including R2 values because I understan= d that that is part of the checking procedure that I am (somewhat vaguely) = here trying to argue might be omitted.

Cheers,AdamISZ/waxwing



On Thursday, May 1,= 2025 at 12:14:30=E2=80=AFAM UTC-3 waxwing/ AdamISZ wrote:

> That partial signatu= res do not leak information about the secret key x_k is
implied by the security theorem for DahLIAS: If information would leak,= the
adversary could use that to win the unforgeability game. However, the a= dversary
doesn't win the game unless the adversary solves the DL problem or = finds a
collision in hash function Hnon.

OK, so t= hat's maybe a theoretical confusion on my part, I'm thinking of the= HVZK property of the Schnorr ID scheme, which "kinda" carries ov= er into the FS transformed version with a simulator (maybe? kinda?). Anyway= this is a sidetrack and not relevant to the paper, so I'll stop on tha= t.

> This is a very interesting point, probably out of sco= pe for the paper. A
single-party signer, given secret keys xi, ..., xn for public keys X1, = ..., Xn
can draw r at random, compute R :=3D r*G and then set s :=3D r + c1*x1 = + ... +
cn*xn. So this would only require a single group multiplication.
<= div>
I feel bad for saying so, but I absolutely do believe it= 's in scope of the paper :) If there is a concrete, meaningful optimisa= tion that's both possible and sensible (and as you say, there is such a= n ultra-simple optimisation ... I guess that's entirely correct!), then= it should be included there and not elsewhere. Why? Because it's exact= ly the kind of thing an engineer might want to do, but it's definitely = not their place to make a judgement as to whether it's safe or not, giv= en that these protocols are such a minefield. I'd say even if there is = *no* such optimisation possible it's worth saying so.

I guess the counterargument is that it's suitable for a BIP not= the paper? But I'd disagree, this isn't purely a bitcoin thing.

On the third paragraph, yeah, as per earlier email, = I realised that that just doesn't work.

On Wednesday, April= 30, 2025 at 9:03:34=E2=80=AFAM UTC-6 Jonas Nick wrote:
Thanks for your comments.

> That side note reminds me of my first question: would it not be a= ppropriate
> to include a proof of the zero knowledgeness property of the sche= me, and
> not only the soundness? I can kind of accept the answer "it&= #39;s trivial"
> based on the structure of the partial sig components (s_k =3D r_k= 1 + br_k2 +
> c_k x_k) being "identical" to baseline Schnorr?

That partial signatures do not leak information about the secret key x_= k is
implied by the security theorem for DahLIAS: If information would leak,= the
adversary could use that to win the unforgeability game. However, the a= dversary
doesn't win the game unless the adversary solves the DL problem or = finds a
collision in hash function Hnon.

> The side note also raises this point: would it be a good idea to = explicitly
> write down ways in which the usage of the scheme/structure can, a= nd cannot,
> be optimised for the single-party case?

This is a very interesting point, probably out of scope for the paper. = A
single-party signer, given secret keys xi, ..., xn for public keys X1, = ..., Xn
can draw r at random, compute R :=3D r*G and then set s :=3D r + c1*x1 = + ... +
cn*xn. So this would only require a single group multiplication.

> On that last point about "proof of knowledge of R", I s= uddenly realised
> it's not a viable suggestion: of course it defends against ke= y subtraction
> attacks, but does not defend at all against the ability to grind = nonces
> adversarially in a Wagner type attack

We believe Appendix B provides a helpful characterization of "Wagn= er-style"
vulnerabilities. Roughly speaking, it shows that schemes where the adve= rsary can
ask the signer to produce a partial signature s =3D r + c*x or s' = =3D r + c'*x such
that c !=3D c' then the scheme is vulnerable. In your "proof o= f knowledge of R
idea", the adversary can choose to provide either R2 or R2' in= a signing
request, which would result in the same "effective nonce" r b= eing used be the
signer but different challenges c and c'.

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/3f23ebaa-02c7-45d1-bf57-9baf48c133a3n%40googlegroups.com.
------=_Part_331585_1313770776.1750102543362-- ------=_Part_331584_750040566.1750102543362--