From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 30 Apr 2025 20:14:37 -0700 Received: from mail-yw1-f189.google.com ([209.85.128.189]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uAKNg-0003LO-Ay for bitcoindev@gnusha.org; Wed, 30 Apr 2025 20:14:37 -0700 Received: by mail-yw1-f189.google.com with SMTP id 00721157ae682-703ad0aaeebsf8271097b3.3 for ; Wed, 30 Apr 2025 20:14:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1746069270; x=1746674070; 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=rPT4tsWJ6PB3r77sqzsX3eJsNfz4SFwrIF+xBH6NIto=; b=HSUmZJ7zImoFlnsuUkMpLG3dz63g0Z7yvL5t30ncjnNnCr7xlw0KsqhbFH1fDxZK5y D1eQ7poTQVzf/5oi0CFKRC3xssxMGcgZ2820sTMyxXNg/OVtg7IdkbVJ58abwiox+lNA lcbmTld1zV1PgNO4spLZept6GJgPvQK4DdPDbflaP2CTe5zdaFfP4dFoU2/RoarOUeXH lMJCGbbKnX07WNVT+kkT8leGdhdAaSO+cnsZHqZ+iJoCvPm5o3Q3E9gIH4ir+veAHfMP qCNs6munsWfB1SmCowJ63a2qsflH42mtu6102ZRl11qwzvIa3rTAPbfyYR7NppKiJGOz b/Fg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1746069270; x=1746674070; 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=rPT4tsWJ6PB3r77sqzsX3eJsNfz4SFwrIF+xBH6NIto=; b=GU+wCforUgcWyy92Mh6eC4Z8q0Qw+opGU/wTfluZ2JIIkfWK/li83Hs6PsQo8Qf2Ac I/tXlKRaSo/l6XhpTNvNyOvfYhFY7iMj0Z7XczWq6aTN7VpA7ZOx/EdxsRN13Hu8Lufp gBD1wgXvgLQm5ahCbxI2s1f6v0iETuudVtowWT5VJQGnIC0dAAOHUuI8vR5ZyqPW6bw1 IWkh370MGNZ4BDmIoH3gaw8656/tIdEVYyp8RX6vC30Q67xWzqCKoRbFwYIk4aWqzxXQ 8NFZSCb21WmcuAfGiKWuYJeEN3WvnNjN0IgRXrpxMu7gm9JtPu8h+vIyksg9HfGUADXo AGkw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1746069270; x=1746674070; 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=rPT4tsWJ6PB3r77sqzsX3eJsNfz4SFwrIF+xBH6NIto=; b=r88KQkudPxct3QzRZ8uvcAZc5KuNNQ/VrrE9QAZpzVRYZlNCtWCQJfZEsPOZChFEKT 6ZQhpIaZx44wkYDIlFFSRMEJFa5yt7MBILza357cgJZyXwlkB1RDP/AzJvT5gL6yhCXw 05Fe2QjjwCp2Q8pdztWvLdrHkAoXnNISdvYoyjPKlEAsLsESmr1gkrzFL1dmUSyeT2Sy 4hVW8MHqdEDsD2CL/2XuJ8vU7iKb58QlDbUO3AZsDw2xUr4X30wr39kiErBd9FaMrD1M FAaa+4pErr1waobjY4hvONNnGEi3K1LUJF+rLIUI//9LpDFOTtzHilblzstHjGyNsK4h JyAQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCXXTL+fDuBwKi5e59QR4KFFfHJyS7bHVInWrZgYEapwr7v1s+50eNDL5VCjN40iqJAG+OeTyK7+aPTD@gnusha.org X-Gm-Message-State: AOJu0Yyp2LAgp4GbiTp1ieHab6RWsx6j3t7KSJBnSMJR2FDwiG+PSMj3 CUe7t8RWtoVF7lZFvC4B6sJjddPBnVGK1dcYoxHaYuiKqTutMPBA X-Google-Smtp-Source: AGHT+IELrm+H+i4u9JkI2/Cl8fadF9gBzHnUaTsnOI8FADhQZK6Une3U3XX6cwSVMSSfZINFuplRIw== X-Received: by 2002:a05:6902:2746:b0:e6d:fb0f:fcbf with SMTP id 3f1490d57ef6-e7405b8b8b5mr7133769276.39.1746069269845; Wed, 30 Apr 2025 20:14:29 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBGMpA+Tc6oLwgWrH50Lwq0Kkx+uuAbgu430LbcErVo6bg== Received: by 2002:a25:2d20:0:b0:e74:32a2:edc6 with SMTP id 3f1490d57ef6-e74dc9b9c8dls720446276.2.-pod-prod-02-us; Wed, 30 Apr 2025 20:14:26 -0700 (PDT) X-Received: by 2002:a05:690c:6e01:b0:6ef:5097:5daa with SMTP id 00721157ae682-708abe4b425mr86730577b3.34.1746069266518; Wed, 30 Apr 2025 20:14:26 -0700 (PDT) Received: by 2002:a05:690c:b9b:b0:708:1ea1:3cd5 with SMTP id 00721157ae682-708ab132065ms7b3; Wed, 30 Apr 2025 08:54:47 -0700 (PDT) X-Received: by 2002:a05:690c:3344:b0:6fb:8461:e828 with SMTP id 00721157ae682-708abe247eemr56898667b3.30.1746028487023; Wed, 30 Apr 2025 08:54:47 -0700 (PDT) Date: Wed, 30 Apr 2025 08:54:46 -0700 (PDT) From: waxwing/ AdamISZ To: Bitcoin Development Mailing List Message-Id: 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_81236_1169592386.1746028486685" 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_81236_1169592386.1746028486685 Content-Type: multipart/alternative; boundary="----=_Part_81237_1392290992.1746028486685" ------=_Part_81237_1392290992.1746028486685 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable > 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, 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 the= =20 HVZK property of the Schnorr ID scheme, which "kinda" carries over into the= =20 FS transformed version with a simulator (maybe? kinda?). Anyway this is a= =20 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 the= =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 to= =20 make a judgement as to whether it's safe or not, given that these protocols= =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. > > > That side note reminds me of my first question: would it not be=20 > appropriate > > to include a proof of the zero knowledgeness property of the scheme, an= d > > not only the soundness? I can kind of accept the answer "it's trivial" > > based on the structure of the partial sig components (s_k =3D r_k1 + br= _k2=20 > + > > 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, t= he > adversary could use that to win the unforgeability game. However, the=20 > adversary > 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=20 > explicitly > > write down ways in which the usage of the scheme/structure can, and=20 > 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,=20 > ..., 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 suddenly realised > > it's not a viable suggestion: of course it defends against key=20 > 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 "Wagner-styl= e" > vulnerabilities. Roughly speaking, it shows that schemes where the=20 > adversary can > ask the signer to produce a partial signature s =3D r + c*x or s' =3D r += c'*x=20 > such > that c !=3D c' then the scheme is vulnerable. In your "proof of knowledge= of=20 > 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 being used be= =20 > the > signer but different challenges c and c'. > --=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/= a9f133ff-1d8e-45a3-8186-79fb52bbd467n%40googlegroups.com. ------=_Part_81237_1392290992.1746028486685 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
> That partial signatures do not leak information about the secret= key x_k is
implied by the security theorem for DahLIAS: If information would lea= k, the
adversary could use that to win the unforgeability game. However, the= adversary
doesn't win the game unless the adversary solves the DL problem or fi= nds a
collision in hash function Hnon.

OK, = so that's maybe a theoretical confusion on my part, I'm thinking of the HVZ= K property of the Schnorr ID scheme, which "kinda" carries over into the FS= transformed version with a simulator (maybe? kinda?). Anyway this is a sid= etrack 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
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*x= 1 + ... +
cn*xn. So this would only require a single group multiplication.

I feel bad for saying so, but I absolutely do believ= e 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 an ul= tra-simple optimisation ... I guess that's entirely correct!), then it shou= ld be included there and not elsewhere. Why? Because it's exactly 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, given that these protoc= ols are such a minefield. I'd say even if there is *no* such optimisation p= ossible it's worth saying so.

I guess the counte= rargument 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 wo= rk.

On Wednesday, April 30, 2025 at 9:03:34=E2=80=AFAM UTC-6 J= onas 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/a9f133ff-1d8e-45a3-8186-79fb52bbd467n%40googlegroups.com.
------=_Part_81237_1392290992.1746028486685-- ------=_Part_81236_1169592386.1746028486685--