* [bitcoindev] DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures
@ 2025-04-17 16:27 Jonas Nick
2025-04-19 16:28 ` [bitcoindev] " waxwing/ AdamISZ
0 siblings, 1 reply; 3+ messages in thread
From: Jonas Nick @ 2025-04-17 16:27 UTC (permalink / raw)
To: bitcoindev
Hi list,
Cross-Input Signature Aggregation (CISA) has been a recurring topic here, aiming
to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yannick
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 their own
message, which distinguishes it from multi- and threshold signatures, where all
signers sign the same message. This makes aggregate signature schemes the
natural cryptographic primitive for cross-input signature aggregation 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 logarithm
problem on secp256k1 currently used in Bitcoin signatures (e.g., groups with
efficient pairings).
- Were "folklore" constructions, lacking detailed descriptions 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 key
tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover, we show
that there exists a concrete attack against a folklore aggregate signature
scheme derived from MuSig2 when key tweaking is used.
In contrast, DahLIAS is proven to be compatible with key tweaking. Moreover, 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 signatures
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 "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/be3813bf-467d-4880-9383-2a0b0223e7e5%40gmail.com.
^ permalink raw reply [flat|nested] 3+ messages in thread
* [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures
2025-04-17 16:27 [bitcoindev] DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures Jonas Nick
@ 2025-04-19 16:28 ` waxwing/ AdamISZ
2025-04-22 15:29 ` Jonas Nick
0 siblings, 1 reply; 3+ messages in thread
From: waxwing/ AdamISZ @ 2025-04-19 16:28 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 3624 bytes --]
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:
Appendix 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 this same attack cannot be applied to MuSig2 itself?
the multisig-to-IAS "translation" makes sense, given the caveat of the
weakness identified in the 2018 paper and explained here in detail, other
than that it's basically about the message being a concat of the individual
messages (and keys). But surely that doesn't change the structure of the
attack? (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 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 AM UTC-6 Jonas Nick wrote:
> Hi list,
>
> Cross-Input Signature Aggregation (CISA) has been a recurring topic here,
> aiming
> to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yannick
> 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
> their own
> message, which distinguishes it from multi- and threshold signatures,
> where all
> signers sign the same message. This makes aggregate signature schemes the
> natural cryptographic primitive for cross-input signature aggregation
> 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
> logarithm
> problem on secp256k1 currently used in Bitcoin signatures (e.g., groups
> with
> efficient pairings).
> - Were "folklore" constructions, lacking detailed descriptions 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 key
> tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover, we
> show
> that there exists a concrete attack against a folklore aggregate signature
> scheme derived from MuSig2 when key tweaking is used.
>
> In contrast, DahLIAS is proven to be compatible with key tweaking.
> Moreover, 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
> signatures
> 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 "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/242c6fdd-f629-4a2a-900c-7b1d770eedbbn%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 4787 bytes --]
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures
2025-04-19 16:28 ` [bitcoindev] " waxwing/ AdamISZ
@ 2025-04-22 15:29 ` Jonas Nick
0 siblings, 0 replies; 3+ messages in thread
From: Jonas Nick @ 2025-04-22 15:29 UTC (permalink / raw)
To: bitcoindev
Thanks for bringing this up. It's an interesting question and it made us realize
that we should clarify this section of the paper, as there are indeed some
subtleties here that are currently unmentioned.
> I don't understand why this same attack cannot be applied to MuSig2 itself?
There are nuances, but I think it's fair to say that the same attack cannot be
applied to MuSig2 itself. During the attack, the adversary requests a partial
signature for public key X and message m from the honest signer. Using this, the
adversary is able to create a partial signature for public key X' = TweakPK(X,
t), where t is some tweak chosen by the adversary, and message m'. When applying
the attack to MuSig2, we have that m' = m, and when applying it to MuSig2-IAS,
we may have m != m'.
So, using the attack, the adversary is able to produce a signature sigma_1 for
MuSig2 and sigma_2 for MuSig2-IAS such that
- MuSig2.Verify(KeyAgg(X, X'), m, sigma_1) = 1, and
- MuSig2-IAS.Verify((X, m), (X', m'), sigma_2) = 1.
sigma_2 is clearly a forgery under the EUF-CMA-TK security model defined in the
DahLIAS paper because it is a signature for a message m' that the honest signer
hasn't signed. In contrast, sigma_1 only covers the message that the honest
signer actually signed. Whether sigma_1 counts as a forgery depends on the
abstract security notion that you consider for multisignature tweaking. We
didn't provide such a model in the MuSig2 paper and I am not aware of a standard
one. It would be easy to design a security model where sigma_1 constitutes a
forgery and one where it doesn't.
More importantly, could this be a problem for MuSig2 in practice? I can only
come up with contrived scenarios, but it may still be worth mentioning in the
BIP, for example.
--
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 email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/2ede88e8-2570-442f-a073-730f7de70eca%40gmail.com.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2025-04-22 17:02 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2025-04-17 16:27 [bitcoindev] DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures Jonas Nick
2025-04-19 16:28 ` [bitcoindev] " waxwing/ AdamISZ
2025-04-22 15:29 ` Jonas Nick
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox