path: root/1f/d0c159273b5d882d5211f7e9fca9ca6811e910

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 <bitcoindev+bncBDI23FE35EIBBEWOZPAAMGQEDRIZG7A@googlegroups.com>)
	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 <bitcoindev@gnusha.org>; 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 <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <a9f133ff-1d8e-45a3-8186-79fb52bbd467n@googlegroups.com>
In-Reply-To: <f9e082e3-4079-40b6-aa49-5d1b9b3b1e29@gmail.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>
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: <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.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

<br />&gt; That partial signatures do not leak information about the secret=
 key x_k is
<br />implied by the security theorem for DahLIAS: If information would lea=
k, the
<br />adversary could use that to win the unforgeability game. However, the=
 adversary
<br />doesn't win the game unless the adversary solves the DL problem or fi=
nds a
<br /><div>collision in hash function Hnon.</div><div><br /></div><div>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.</div><br /><div=
>&gt; This is a very interesting point, probably out of scope for the paper=
. A
<br />single-party signer, given secret keys xi, ..., xn for public keys X1=
, ..., Xn
<br />can draw r at random, compute R :=3D r*G and then set s :=3D r + c1*x=
1 + ... +
<br />cn*xn. So this would only require a single group multiplication.</div=
><div><br /></div><div>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.</div><div><br /></div><div>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.</div><div><br /></div><div>On the third =
paragraph, yeah, as per earlier email, I realised that that just doesn't wo=
rk.</div><div><br /></div><div class=3D"gmail_quote"><div dir=3D"auto" clas=
s=3D"gmail_attr">On Wednesday, April 30, 2025 at 9:03:34=E2=80=AFAM UTC-6 J=
onas Nick wrote:<br/></div><blockquote class=3D"gmail_quote" style=3D"margi=
n: 0 0 0 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1e=
x;">Thanks for your comments.
<br>
<br> &gt; That side note reminds me of my first question: would it not be a=
ppropriate
<br> &gt; to include a proof of the zero knowledgeness property of the sche=
me, and
<br> &gt; not only the soundness? I can kind of accept the answer &quot;it&=
#39;s trivial&quot;
<br> &gt; based on the structure of the partial sig components (s_k =3D r_k=
1 + br_k2 +
<br> &gt; c_k x_k) being &quot;identical&quot; to baseline Schnorr?
<br>
<br>That partial signatures do not leak information about the secret key x_=
k is
<br>implied by the security theorem for DahLIAS: If information would leak,=
 the
<br>adversary could use that to win the unforgeability game. However, the a=
dversary
<br>doesn&#39;t win the game unless the adversary solves the DL problem or =
finds a
<br>collision in hash function Hnon.
<br>
<br> &gt; The side note also raises this point: would it be a good idea to =
explicitly
<br> &gt; write down ways in which the usage of the scheme/structure can, a=
nd cannot,
<br> &gt; be optimised for the single-party case?
<br>
<br>This is a very interesting point, probably out of scope for the paper. =
A
<br>single-party signer, given secret keys xi, ..., xn for public keys X1, =
..., Xn
<br>can draw r at random, compute R :=3D r*G and then set s :=3D r + c1*x1 =
+ ... +
<br>cn*xn. So this would only require a single group multiplication.
<br>
<br> &gt; On that last point about &quot;proof of knowledge of R&quot;, I s=
uddenly realised
<br> &gt; it&#39;s not a viable suggestion: of course it defends against ke=
y subtraction
<br> &gt; attacks, but does not defend at all against the ability to grind =
nonces
<br> &gt; adversarially in a Wagner type attack
<br>
<br>We believe Appendix B provides a helpful characterization of &quot;Wagn=
er-style&quot;
<br>vulnerabilities. Roughly speaking, it shows that schemes where the adve=
rsary can
<br>ask the signer to produce a partial signature s =3D r + c*x or s&#39; =
=3D r + c&#39;*x such
<br>that c !=3D c&#39; then the scheme is vulnerable. In your &quot;proof o=
f knowledge of R
<br>idea&quot;, the adversary can choose to provide either R2 or R2&#39; in=
 a signing
<br>request, which would result in the same &quot;effective nonce&quot; r b=
eing used be the
<br>signer but different challenges c and c&#39;.
<br></blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/a9f133ff-1d8e-45a3-8186-79fb52bbd467n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/a9f133ff-1d8e-45a3-8186-79fb52bbd467n%40googlegroups.com</a>.<br />

------=_Part_81237_1392290992.1746028486685--

------=_Part_81236_1169592386.1746028486685--