path: root/2f/0e217edeec2b6bce56035fa106e3f97706b4bd

Delivery-date: Sat, 19 Apr 2025 09:35:43 -0700
Received: from mail-yb1-f185.google.com ([209.85.219.185])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDI23FE35EIBBUVBR7AAMGQEOBA74XY@googlegroups.com>)
	id 1u6BAM-0005hf-PI
	for bitcoindev@gnusha.org; Sat, 19 Apr 2025 09:35:43 -0700
Received: by mail-yb1-f185.google.com with SMTP id 3f1490d57ef6-e72874a21c0sf3358404276.1
        for <bitcoindev@gnusha.org>; Sat, 19 Apr 2025 09:35:42 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1745080536; x=1745685336; 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=A6cNtjuRrjosHufHbEtTgxprcVwC93rdsyqws9ut+ws=;
        b=bjBqQzLZQ8alM/MgFta4Rtc/B1hXPf0/mNYO5VkxmgR0lDf8ty83bXqtxFrMLRyZi5
         AR/WCQb2vrhFdSnNpNbQUUc+wkA7oCULt0UsOoGVdbcoVBhlTcOjpK0dYfJjgMwnwt7m
         m2NLrRViH8wR9HqgXgQqTpRgjUBR0xLzJ4MvwJn6CbKN58zLf+lvOF5fuhG2kY9VlCvm
         sOLjMYgPT9OrGbJMSgzYVuVsh8HYB2BYFQJ9fJnZ9nYt2Ztyo+cpxwEXwW+G2rTonAkB
         IFlNQJmB1b6B5/G3Uvs8sqovmUSq+tUSOMAfIWtGA/h59BiD+U1dwZX7jnI4T4HEvlu8
         YyyQ==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1745080536; x=1745685336; 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=A6cNtjuRrjosHufHbEtTgxprcVwC93rdsyqws9ut+ws=;
        b=BMeFimVUsdGrh8uxD5oj3fTquNhJNczRbyXC3Zt0MM+CUzlmBPLwUWjvBPcPRS1JJU
         djR4j8ps0iB3Tt64Ofh4kMxRTflAtAva6z10x0ft5EbC+F1YrYiPJu7t0qz4CPAxojWQ
         PbgLPZVTMpM+G+h1aY5rnNyHFOkcZVSH3b8795ME0MO5xTh5wuWQ9kQY17xHA3qGN9vH
         jwy7Ky+lNRAVWma82dud6nqGhFgMKR39YP173djnlqI5kpQkabGacFuErZeMtEc5A4mt
         qOJUCZdfcip5lxbKZA/lTKG4O65Q1gm/4DXfXbTxN/guFqBQ7tUMeWL9zybnkGN8cE5I
         KOQg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1745080536; x=1745685336;
        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=A6cNtjuRrjosHufHbEtTgxprcVwC93rdsyqws9ut+ws=;
        b=TA9r2Tbnjfkzz79ALnOB5+SONZBuGOAXxjjgcM51Zey7+MiwNcejULccdxMO93dWh4
         m+Gsvjti5DQxhlNvq7aHkSTuwFPKH2MVeXlZZEiO6xySUQMMl/u1s/M1QxMNWC4NArQv
         +fv5lh6/J9E5mscX13lHDULnlYbC7IX0m0ZSt/rAFmXpo9wtZSxCbDXQzwzS82MhUm4C
         vrLJYGL/IhHj+mAdNHunB3G1l/V2hEP+3I5k0WSnewYq3Yg4fY1XQAUcpy6oVSz6k8yu
         dsikdItC5r2kOR3BfC3p/e5QBPCsaEbbrobRyGKeCjDGJKQSPTXlu5j7d4BcBvEnqrep
         ieMg==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCXZ5g0Fh94M2IldalI8DBgRfA2d+kL1ug5zjStwwN3NyTvrC7Gt1cU+IteFGnwERWotzTNTUoL4aSpO@gnusha.org
X-Gm-Message-State: AOJu0YwbK/uB/uEshDme0lpyyVjiGt5ooVIeg5auLPk9K2+a+yuKIatp
	AZSRGd58gJJ6jcac0eIj+kGbtSTjS5vYhO+gxARe0T/QBZBKsjsb
X-Google-Smtp-Source: AGHT+IEK61QDhakiE5wQvfj8aXvXa1CASryuDFfcHmYSLHt8RyM/c3pE8Wux+WiRXJ75nsLFNJ1OPw==
X-Received: by 2002:a05:6902:2849:b0:e6d:ee8e:876a with SMTP id 3f1490d57ef6-e7297dc9ee7mr7757746276.15.1745080536492;
        Sat, 19 Apr 2025 09:35:36 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAJepbn4kI2VujA5iSotDDl8iMba45Tafch4wqbt4yXyWg==
Received: by 2002:a25:6908:0:b0:e6d:e6df:b3b3 with SMTP id 3f1490d57ef6-e72804b6b2els515719276.1.-pod-prod-06-us;
 Sat, 19 Apr 2025 09:35:30 -0700 (PDT)
X-Received: by 2002:a05:690c:3609:b0:702:52fb:462d with SMTP id 00721157ae682-706ccdbcfa7mr97843037b3.29.1745080530209;
        Sat, 19 Apr 2025 09:35:30 -0700 (PDT)
Received: by 2002:a81:a805:0:b0:6fe:b496:fc0e with SMTP id 00721157ae682-706cb24f9d4ms7b3;
        Sat, 19 Apr 2025 09:28:53 -0700 (PDT)
X-Received: by 2002:a05:690c:6a09:b0:706:ca86:d79e with SMTP id 00721157ae682-706ccd276d8mr90482957b3.19.1745080132663;
        Sat, 19 Apr 2025 09:28:52 -0700 (PDT)
Date: Sat, 19 Apr 2025 09:28:52 -0700 (PDT)
From: waxwing/ AdamISZ <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <242c6fdd-f629-4a2a-900c-7b1d770eedbbn@googlegroups.com>
In-Reply-To: <be3813bf-467d-4880-9383-2a0b0223e7e5@gmail.com>
References: <be3813bf-467d-4880-9383-2a0b0223e7e5@gmail.com>
Subject: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive
 Aggregate Signatures
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_248680_1152894813.1745080132326"
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_248680_1152894813.1745080132326
Content-Type: multipart/alternative; 
	boundary="----=_Part_248681_1673172462.1745080132326"

------=_Part_248681_1673172462.1745080132326
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Jonas and list.

So I'm reading the paper and it's very interesting. I have other questions=
=20
but this one seems more important so I'll just stick with this one:

Appendix A2 explains an attack on Musig2-IAS, in which you can forge a=20
partial signature on a tweaked key of the honest signer. I don't understand=
=20
why this same attack cannot be applied to MuSig2 itself?

the multisig-to-IAS "translation" makes sense, given the caveat of the=20
weakness identified in the 2018 paper and explained here in detail, other=
=20
than that it's basically about the message being a concat of the individual=
=20
messages (and keys). But surely that doesn't change the structure of the=20
attack? (i.e. multiply your R-vals by a2/a1, then take partial sig and=20
multiply by a2/a1 and add the tweak). I note that 3 round musig is not=20
vulnerable to it, nor would some PoK of R be.

Obviously I missed something.

Cheers,
AdamISZ/waxwing

On Thursday, April 17, 2025 at 10:38:46=E2=80=AFAM UTC-6 Jonas Nick wrote:

> Hi list,
>
> Cross-Input Signature Aggregation (CISA) has been a recurring topic here,=
=20
> aiming
> to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yanni=
ck
> Seurin and I recently published DahLIAS, the first interactive aggregate
> signature scheme with constant-size signatures (64 bytes) compatible with
> secp256k1.
>
> https://eprint.iacr.org/2025/692.pdf
>
> Recall that in an aggregate signature scheme, each signer contributes=20
> their own
> message, which distinguishes it from multi- and threshold signatures,=20
> where all
> signers sign the same message. This makes aggregate signature schemes the
> natural cryptographic primitive for cross-input signature aggregation=20
> because
> each transaction input typically requires signing a different message.
>
> Previous candidates for constant-size aggregate signatures either:
> - Required cryptographic assumptions quite different from the discrete=20
> logarithm
> problem on secp256k1 currently used in Bitcoin signatures (e.g., groups=
=20
> with
> efficient pairings).
> - Were "folklore" constructions, lacking detailed descriptions and securi=
ty
> proofs.
>
> Besides presenting DahLIAS, the paper provides a proof that a class of=20
> these
> folklore constructions are indeed secure if the signer does _not_ use key
> tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover, w=
e=20
> show
> that there exists a concrete attack against a folklore aggregate signatur=
e
> scheme derived from MuSig2 when key tweaking is used.
>
> In contrast, DahLIAS is proven to be compatible with key tweaking.=20
> Moreover, it
> requires two rounds of communication for signing, where the first round=
=20
> can be
> run before the messages to be signed are known. Verification of DahLIAS
> signatures is asymptotically twice as fast as half-aggregate Schnorr=20
> signatures
> and as batch verification of individual Schnorr signatures.
>
> We believe DahLIAS offers an attractive building block for a potential CI=
SA
> proposal and welcome any feedback or discussion.
>
> Jonas Nick, Tim Ruffing, Yannick Seurin
>
>
> [0] See, e.g., https://cisaresearch.org/ for a summary of various CISA
> discussions.
>

--=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/=
242c6fdd-f629-4a2a-900c-7b1d770eedbbn%40googlegroups.com.

------=_Part_248681_1673172462.1745080132326
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div>Hi Jonas and list.</div><div><br /></div><div>So I'm reading the paper=
 and it's very interesting. I have other questions but this one seems more =
important so I'll just stick with this one:</div><div><br /></div><div>Appe=
ndix A2 explains an attack on Musig2-IAS, in which you can forge a partial =
signature on a tweaked key of the honest signer. I don't understand why thi=
s same attack cannot be applied to MuSig2 itself?</div><div><br /></div><di=
v>the multisig-to-IAS "translation" makes sense, given the caveat of the we=
akness identified in the 2018 paper and explained here in detail, other tha=
n that it's basically about the message being a concat of the individual me=
ssages (and keys). But surely that doesn't change the structure of the atta=
ck? (i.e. multiply your R-vals by a2/a1, then take partial sig and multiply=
 by a2/a1 and add the tweak). I note that 3 round musig is not vulnerable t=
o it, nor would some PoK of R be.</div><div><br /></div><div>Obviously I mi=
ssed something.</div><div><br /></div><div>Cheers,</div><div>AdamISZ/waxwin=
g</div><br /><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_at=
tr">On Thursday, April 17, 2025 at 10:38:46=E2=80=AFAM UTC-6 Jonas Nick wro=
te:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8e=
x; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Hi list,
<br>
<br>Cross-Input Signature Aggregation (CISA) has been a recurring topic her=
e, aiming
<br>to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yan=
nick
<br>Seurin and I recently published DahLIAS, the first interactive aggregat=
e
<br>signature scheme with constant-size signatures (64 bytes) compatible wi=
th
<br>secp256k1.
<br>
<br><a href=3D"https://eprint.iacr.org/2025/692.pdf" target=3D"_blank" rel=
=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&am=
p;q=3Dhttps://eprint.iacr.org/2025/692.pdf&amp;source=3Dgmail&amp;ust=3D174=
5074524571000&amp;usg=3DAOvVaw1AzPa85akwxSdsZ7eqJ1lx">https://eprint.iacr.o=
rg/2025/692.pdf</a>
<br>
<br>Recall that in an aggregate signature scheme, each signer contributes t=
heir own
<br>message, which distinguishes it from multi- and threshold signatures, w=
here all
<br>signers sign the same message. This makes aggregate signature schemes t=
he
<br>natural cryptographic primitive for cross-input signature aggregation b=
ecause
<br>each transaction input typically requires signing a different message.
<br>
<br>Previous candidates for constant-size aggregate signatures either:
<br>- Required cryptographic assumptions quite different from the discrete =
logarithm
<br>   problem on secp256k1 currently used in Bitcoin signatures (e.g., gro=
ups with
<br>   efficient pairings).
<br>- Were &quot;folklore&quot; constructions, lacking detailed description=
s and security
<br>   proofs.
<br>
<br>Besides presenting DahLIAS, the paper provides a proof that a class of =
these
<br>folklore constructions are indeed secure if the signer does _not_ use k=
ey
<br>tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover,=
 we show
<br>that there exists a concrete attack against a folklore aggregate signat=
ure
<br>scheme derived from MuSig2 when key tweaking is used.
<br>
<br>In contrast, DahLIAS is proven to be compatible with key tweaking. More=
over, it
<br>requires two rounds of communication for signing, where the first round=
 can be
<br>run before the messages to be signed are known. Verification of DahLIAS
<br>signatures is asymptotically twice as fast as half-aggregate Schnorr si=
gnatures
<br>and as batch verification of individual Schnorr signatures.
<br>
<br>We believe DahLIAS offers an attractive building block for a potential =
CISA
<br>proposal and welcome any feedback or discussion.
<br>
<br>Jonas Nick, Tim Ruffing, Yannick Seurin
<br>
<br>
<br>[0] See, e.g., <a href=3D"https://cisaresearch.org/" target=3D"_blank" =
rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den=
&amp;q=3Dhttps://cisaresearch.org/&amp;source=3Dgmail&amp;ust=3D17450745245=
71000&amp;usg=3DAOvVaw1LWnw33pHTpUBKyfInkRLm">https://cisaresearch.org/</a>=
 for a summary of various CISA
<br>     discussions.
<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/242c6fdd-f629-4a2a-900c-7b1d770eedbbn%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/242c6fdd-f629-4a2a-900c-7b1d770eedbbn%40googlegroups.com</a>.<br />

------=_Part_248681_1673172462.1745080132326--

------=_Part_248680_1152894813.1745080132326--