From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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 To: Bitcoin Development Mailing List Message-Id: <242c6fdd-f629-4a2a-900c-7b1d770eedbbn@googlegroups.com> In-Reply-To: References: 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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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
Hi Jonas and list.

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:

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?

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.

Obviously I mi= ssed something.

Cheers,
AdamISZ/waxwin= g

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

Cross-Input Signature Aggregation (CISA) has been a recurring topic her= e, aiming
to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yan= nick
Seurin and I recently published DahLIAS, the first interactive aggregat= e
signature scheme with constant-size signatures (64 bytes) compatible wi= th
secp256k1.

https://eprint.iacr.o= rg/2025/692.pdf

Recall that in an aggregate signature scheme, each signer contributes t= heir own
message, which distinguishes it from multi- and threshold signatures, w= here all
signers sign the same message. This makes aggregate signature schemes t= he
natural cryptographic primitive for cross-input signature aggregation b= ecause
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 = logarithm
problem on secp256k1 currently used in Bitcoin signatures (e.g., gro= ups with
efficient pairings).
- Were "folklore" constructions, lacking detailed description= s and security
proofs.

Besides presenting DahLIAS, the paper provides a proof that a class of = these
folklore constructions are indeed secure if the signer does _not_ use k= ey
tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover,= we show
that there exists a concrete attack against a folklore aggregate signat= ure
scheme derived from MuSig2 when key tweaking is used.

In contrast, DahLIAS is proven to be compatible with key tweaking. More= over, it
requires two rounds of communication for signing, where the first round= can be
run before the messages to be signed are known. Verification of DahLIAS
signatures is asymptotically twice as fast as half-aggregate Schnorr si= gnatures
and as batch verification of individual Schnorr signatures.

We believe DahLIAS offers an attractive building block for a potential = CISA
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.

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