📅 Original date posted:2023-05-03
🗒️ Summary of this message: A new paper by Wei Dai, Okamoto, and Yamamoto highlights the insufficiency of the aEUF-CMA definition of the Aumayr paper, which doesn't address the possibility of multiple adaptors on the same message at once. The paper has a lot of meat in terms of security definitions, but it is not attempting to rewrite reductions.
📝 Original message:Hi Lloyd and list,
While on the road and re-downloading the papers, I realised there is a "new" paper published December 2022 by Wei Dai, Okamoto and Yamamoto on this same topic:
https://eprint.iacr.org/2022/1687
and, strikingly, it focuses on the exact same point I made here in Section 3 - namely that the aEUF-CMA definition of the Aumayr paper doesn't address the possibility of multiple-adaptors-on-the-same-message-at-once.
A pretty big facepalm moment that I didn't bother to search carefully enough to find that!
Also it's cool that such renowned cryptographers are turning their heads towards this subject :)
It does have a nice illustration of why that definition (which as you know has been reused by other researchers) is insufficient, by making up a malicious version of the "preSign" (i.e. adaptor-sign) algorithm which leaks an arbitrary signature after two calls, while it still fits the definition of aEUF-CMA!
The paper has a *lot* of meat in terms of security definitions (only had a brief chance to read parts of it, as I'm on the road, so this is high level vague perspective), but afaict it is not actually attempting to rewrite reductions(?), so perhaps more work is needed on that(?).
Cheers,Adam
Sent with [Proton Mail](https://proton.me/) secure email.
------- Original Message -------
On Monday, May 1st, 2023 at 12:37, AdamISZ via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
> Hi Lloyd,
> thanks for taking a look.
>
>> I think your view of the uselessness of single signer adaptors is too pessimistic. The claim you make is that they "don't provide a way to create enforcement that the publication of signature on a pre-defined message will reveal a secret'' and so are useless. I think this is wrong. If I hold a secret key for X and create a signature adaptor with some encryption key Y with message m and do not create any further signatures (adaptor or otherwise) on m, then any signature on m that is published necessarily reveals the secret on Y to me. This is very useful and has already been used for years by DLCs in production.
>
> I'm struggling with this one - say I hold privkey x for pubkey X. And I publish adaptor for a point Y (DL y) for message m, like: s' = k - y + H(R|X|m)x with k the nonce and R the nonce point.
>
> And to get the basics clear first, if I publish s = k + H(R|X|m)x then of course the secret y is revealed.
>
> What do you mean in saying "any signature on m that is published reveals y"? Clearly you don't mean any signature on any key (i.e. not the key X). But I also can't parse it if you mean "any signature on m using key X", because if I go ahead and publish s = k_2 + H(R_2|X|m)x, it has no algebraic relationship to the adaptor s' as defined above, right?
>
> I think the point of confusion is maybe about the DLC construct? I referenced that in Section 4.2, parenthetically, because it's analogous in one sense - in MuSig(2) you're fixing R via a negotiation, whereas in Dryja's construct you're fixing R "by definition". When I was talking about single key Schnorr, I was saying that's what's missing, and thereby making them useless.
>
> I think I must have missed some implicit concept in your argument otherwise?
>
>> I haven't read the proofs in detail but I am optimistic about your approach
>
> Appreciate it, but I fear the optimism is misplaced; as you can see from some notes I made in Issue 1, I think I had a pretty substantially invalid line of reasoning in those proof. Probably I need to revert to the forking lemma style arguments that you and Aumayr et al (and some others) took. I also am revisiting a clearer definition of what security threats need to be addressed. It all seems very nuanced.
>
> But hey, that's why I published it and asked for feedback - if nothing else it made *me* think more carefully :)
>
>> One thing I was considering while reading is that you could make a general proof against all secure Schnorr signing scheme in the ROM by simply extending the ROM forwarding approach from Aumayer et al to all "tweak" operations on the elements that go into the Schnorr challenge hash i.e. the public key and the nonce. After all whether it's MuSig2, MuSig, FROST they all must call some RO. I think we can prove that if we apply any bijective map to the (X,R) tuple before they go into the challenge hash function then any Schnorr-like scheme that was secure before will be secure when bip32/TR tweaking (i.e. tweaking X) and adaptor tweaking (tweaking R) is applied to it. This would be cool because then we could prove all these variants secure for all schemes past and present in one go. I haven't got a concrete approach but the proofs I've looked at all seem to share this structure.
> Appreciate these thoughts. In particular your point about "generalization of tweaking" is clearly important, I bet other people have thought about it before me. Btw are there any papers on tweaking in general? I'm suddenly reminded of Poelstra's paper on taproot itself, which istr was an entirely different approach.
>
> Sent with [Proton Mail](https://proton.me/) secure email.
>
> ------- Original Message -------
> On Sunday, April 30th, 2023 at 22:23, Lloyd Fournier via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>> Hi waxwing,
>>
>> I think your view of the uselessness of single signer adaptors is too pessimistic. The claim you make is that they "don't provide a way to create enforcement that the publication of signature on a pre-defined message will reveal a secret'' and so are useless. I think this is wrong. If I hold a secret key for X and create a signature adaptor with some encryption key Y with message m and do not create any further signatures (adaptor or otherwise) on m, then any signature on m that is published necessarily reveals the secret on Y to me. This is very useful and has already been used for years by DLCs in production.
>>
>> I haven't read the proofs in detail but I am optimistic about your approach. One thing I was considering while reading is that you could make a general proof against all secure Schnorr signing scheme in the ROM by simply extending the ROM forwarding approach from Aumayer et al to all "tweak" operations on the elements that go into the Schnorr challenge hash i.e. the public key and the nonce. After all whether it's MuSig2, MuSig, FROST they all must call some RO. I think we can prove that if we apply any bijective map to the (X,R) tuple before they go into the challenge hash function then any Schnorr-like scheme that was secure before will be secure when bip32/TR tweaking (i.e. tweaking X) and adaptor tweaking (tweaking R) is applied to it. This would be cool because then we could prove all these variants secure for all schemes past and present in one go. I haven't got a concrete approach but the proofs I've looked at all seem to share this structure.
>>
>> Cheers,
>>
>> LL
>>
>> On Sun, 30 Apr 2023 at 00:20, AdamISZ via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
>>
>>> Hi list,
>>> I was motivated to look more carefully at the question of the security of using signature adaptors after recently getting quite enthused about the idea of using adaptors across N signing sessions to do a kind of multiparty swap. But of course security analysis is also much more important for the base case of 2 party swapping, which is of .. some considerable practical importance :)
>>>
>>> There is work (referenced in Section 3 here) that's pretty substantial on "how secure are adaptors" (think in terms of security reductions) already from I guess the 2019-2021 period. But I wanted to get into scenarios of multiple adaptors at once or multiple signing sessions at once with the *same* adaptor (as mentioned above, probably this is the most important scenario).
>>>
>>> To be clear this is the work of an amateur and is currently unreviewed - hence (a) me posting it here and (b) putting the paper on github so people can easily add specific corrections or comments if they like:
>>>
>>> https://github.com/AdamISZ/AdaptorSecurityDoc/blob/main/adaptorsecurity.pdf
>>>
>>> I'll note that I did the analysis only around MuSig, not MuSig2.
>>>
>>> The penultimate ("third case"), that as mentioned, of "multiple signing sessions, same adaptor" proved to be the most interesting: in trying to reduce this to ECDLP I found an issue around sequencing. It may just be irrelevant but I'd be curious to hear what others think about that.
>>>
>>> If nothing else, I'd be very interested to hear what experts in the field have to say about security reductions for this primitive in the case of multiple concurrent signing sessions (which of course has been analyzed very carefully already for base MuSig(2)).
>>>
>>> Cheers,
>>> AdamISZ/waxwing
>>>
>>> Sent with Proton Mail secure email.
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev at lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230503/549203d7/attachment-0001.html>;
AdamISZ [ARCHIVE] /
npub1nv…kqw2t
2023-06-07 23:21:02
in reply to nevent1q…5ra2
Author Public Key
npub1nv7tjpn2g8tvt8qfq5ccyl00ucfcu98ch998sq4g5xp65vy6fc4sykqw2tPublished at
2023-06-07 23:21:02Event JSON
{
"id": "8eb074bd64952f26efa55eebe2efdbdcffd11319466db7a5308890c66570d9bc",
"pubkey": "9b3cb9066a41d6c59c090531827defe6138e14f8b94a7802a8a183aa309a4e2b",
"created_at": 1686180062,
"kind": 1,
"tags": [
[
"e",
"133df61ab9b4424d0555ee25d8e7699e138772505ef669b2f377570d0f54ea6b",
"",
"root"
],
[
"e",
"2a42b37602b36f5f0e02579b41c02d4e02a5d333a81de3c0e1c528171459d030",
"",
"reply"
],
[
"p",
"9b3cb9066a41d6c59c090531827defe6138e14f8b94a7802a8a183aa309a4e2b"
]
],
"content": "📅 Original date posted:2023-05-03\n🗒️ Summary of this message: A new paper by Wei Dai, Okamoto, and Yamamoto highlights the insufficiency of the aEUF-CMA definition of the Aumayr paper, which doesn't address the possibility of multiple adaptors on the same message at once. The paper has a lot of meat in terms of security definitions, but it is not attempting to rewrite reductions.\n📝 Original message:Hi Lloyd and list,\n\nWhile on the road and re-downloading the papers, I realised there is a \"new\" paper published December 2022 by Wei Dai, Okamoto and Yamamoto on this same topic:\n\nhttps://eprint.iacr.org/2022/1687\n\nand, strikingly, it focuses on the exact same point I made here in Section 3 - namely that the aEUF-CMA definition of the Aumayr paper doesn't address the possibility of multiple-adaptors-on-the-same-message-at-once.\n\nA pretty big facepalm moment that I didn't bother to search carefully enough to find that!\n\nAlso it's cool that such renowned cryptographers are turning their heads towards this subject :)\n\nIt does have a nice illustration of why that definition (which as you know has been reused by other researchers) is insufficient, by making up a malicious version of the \"preSign\" (i.e. adaptor-sign) algorithm which leaks an arbitrary signature after two calls, while it still fits the definition of aEUF-CMA!\n\nThe paper has a *lot* of meat in terms of security definitions (only had a brief chance to read parts of it, as I'm on the road, so this is high level vague perspective), but afaict it is not actually attempting to rewrite reductions(?), so perhaps more work is needed on that(?).\n\nCheers,Adam\n\nSent with [Proton Mail](https://proton.me/) secure email.\n\n------- Original Message -------\nOn Monday, May 1st, 2023 at 12:37, AdamISZ via bitcoin-dev \u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\n\u003e Hi Lloyd,\n\u003e thanks for taking a look.\n\u003e\n\u003e\u003e I think your view of the uselessness of single signer adaptors is too pessimistic. The claim you make is that they \"don't provide a way to create enforcement that the publication of signature on a pre-defined message will reveal a secret'' and so are useless. I think this is wrong. If I hold a secret key for X and create a signature adaptor with some encryption key Y with message m and do not create any further signatures (adaptor or otherwise) on m, then any signature on m that is published necessarily reveals the secret on Y to me. This is very useful and has already been used for years by DLCs in production.\n\u003e\n\u003e I'm struggling with this one - say I hold privkey x for pubkey X. And I publish adaptor for a point Y (DL y) for message m, like: s' = k - y + H(R|X|m)x with k the nonce and R the nonce point.\n\u003e\n\u003e And to get the basics clear first, if I publish s = k + H(R|X|m)x then of course the secret y is revealed.\n\u003e\n\u003e What do you mean in saying \"any signature on m that is published reveals y\"? Clearly you don't mean any signature on any key (i.e. not the key X). But I also can't parse it if you mean \"any signature on m using key X\", because if I go ahead and publish s = k_2 + H(R_2|X|m)x, it has no algebraic relationship to the adaptor s' as defined above, right?\n\u003e\n\u003e I think the point of confusion is maybe about the DLC construct? I referenced that in Section 4.2, parenthetically, because it's analogous in one sense - in MuSig(2) you're fixing R via a negotiation, whereas in Dryja's construct you're fixing R \"by definition\". When I was talking about single key Schnorr, I was saying that's what's missing, and thereby making them useless.\n\u003e\n\u003e I think I must have missed some implicit concept in your argument otherwise?\n\u003e\n\u003e\u003e I haven't read the proofs in detail but I am optimistic about your approach\n\u003e\n\u003e Appreciate it, but I fear the optimism is misplaced; as you can see from some notes I made in Issue 1, I think I had a pretty substantially invalid line of reasoning in those proof. Probably I need to revert to the forking lemma style arguments that you and Aumayr et al (and some others) took. I also am revisiting a clearer definition of what security threats need to be addressed. It all seems very nuanced.\n\u003e\n\u003e But hey, that's why I published it and asked for feedback - if nothing else it made *me* think more carefully :)\n\u003e\n\u003e\u003e One thing I was considering while reading is that you could make a general proof against all secure Schnorr signing scheme in the ROM by simply extending the ROM forwarding approach from Aumayer et al to all \"tweak\" operations on the elements that go into the Schnorr challenge hash i.e. the public key and the nonce. After all whether it's MuSig2, MuSig, FROST they all must call some RO. I think we can prove that if we apply any bijective map to the (X,R) tuple before they go into the challenge hash function then any Schnorr-like scheme that was secure before will be secure when bip32/TR tweaking (i.e. tweaking X) and adaptor tweaking (tweaking R) is applied to it. This would be cool because then we could prove all these variants secure for all schemes past and present in one go. I haven't got a concrete approach but the proofs I've looked at all seem to share this structure.\n\u003e Appreciate these thoughts. In particular your point about \"generalization of tweaking\" is clearly important, I bet other people have thought about it before me. Btw are there any papers on tweaking in general? I'm suddenly reminded of Poelstra's paper on taproot itself, which istr was an entirely different approach.\n\u003e\n\u003e Sent with [Proton Mail](https://proton.me/) secure email.\n\u003e\n\u003e ------- Original Message -------\n\u003e On Sunday, April 30th, 2023 at 22:23, Lloyd Fournier via bitcoin-dev \u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\n\u003e\u003e Hi waxwing,\n\u003e\u003e\n\u003e\u003e I think your view of the uselessness of single signer adaptors is too pessimistic. The claim you make is that they \"don't provide a way to create enforcement that the publication of signature on a pre-defined message will reveal a secret'' and so are useless. I think this is wrong. If I hold a secret key for X and create a signature adaptor with some encryption key Y with message m and do not create any further signatures (adaptor or otherwise) on m, then any signature on m that is published necessarily reveals the secret on Y to me. This is very useful and has already been used for years by DLCs in production.\n\u003e\u003e\n\u003e\u003e I haven't read the proofs in detail but I am optimistic about your approach. One thing I was considering while reading is that you could make a general proof against all secure Schnorr signing scheme in the ROM by simply extending the ROM forwarding approach from Aumayer et al to all \"tweak\" operations on the elements that go into the Schnorr challenge hash i.e. the public key and the nonce. After all whether it's MuSig2, MuSig, FROST they all must call some RO. I think we can prove that if we apply any bijective map to the (X,R) tuple before they go into the challenge hash function then any Schnorr-like scheme that was secure before will be secure when bip32/TR tweaking (i.e. tweaking X) and adaptor tweaking (tweaking R) is applied to it. This would be cool because then we could prove all these variants secure for all schemes past and present in one go. I haven't got a concrete approach but the proofs I've looked at all seem to share this structure.\n\u003e\u003e\n\u003e\u003e Cheers,\n\u003e\u003e\n\u003e\u003e LL\n\u003e\u003e\n\u003e\u003e On Sun, 30 Apr 2023 at 00:20, AdamISZ via bitcoin-dev \u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\u003e\n\u003e\u003e\u003e Hi list,\n\u003e\u003e\u003e I was motivated to look more carefully at the question of the security of using signature adaptors after recently getting quite enthused about the idea of using adaptors across N signing sessions to do a kind of multiparty swap. But of course security analysis is also much more important for the base case of 2 party swapping, which is of .. some considerable practical importance :)\n\u003e\u003e\u003e\n\u003e\u003e\u003e There is work (referenced in Section 3 here) that's pretty substantial on \"how secure are adaptors\" (think in terms of security reductions) already from I guess the 2019-2021 period. But I wanted to get into scenarios of multiple adaptors at once or multiple signing sessions at once with the *same* adaptor (as mentioned above, probably this is the most important scenario).\n\u003e\u003e\u003e\n\u003e\u003e\u003e To be clear this is the work of an amateur and is currently unreviewed - hence (a) me posting it here and (b) putting the paper on github so people can easily add specific corrections or comments if they like:\n\u003e\u003e\u003e\n\u003e\u003e\u003e https://github.com/AdamISZ/AdaptorSecurityDoc/blob/main/adaptorsecurity.pdf\n\u003e\u003e\u003e\n\u003e\u003e\u003e I'll note that I did the analysis only around MuSig, not MuSig2.\n\u003e\u003e\u003e\n\u003e\u003e\u003e The penultimate (\"third case\"), that as mentioned, of \"multiple signing sessions, same adaptor\" proved to be the most interesting: in trying to reduce this to ECDLP I found an issue around sequencing. It may just be irrelevant but I'd be curious to hear what others think about that.\n\u003e\u003e\u003e\n\u003e\u003e\u003e If nothing else, I'd be very interested to hear what experts in the field have to say about security reductions for this primitive in the case of multiple concurrent signing sessions (which of course has been analyzed very carefully already for base MuSig(2)).\n\u003e\u003e\u003e\n\u003e\u003e\u003e Cheers,\n\u003e\u003e\u003e AdamISZ/waxwing\n\u003e\u003e\u003e\n\u003e\u003e\u003e Sent with Proton Mail secure email.\n\u003e\u003e\u003e _______________________________________________\n\u003e\u003e\u003e bitcoin-dev mailing list\n\u003e\u003e\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e\u003e\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230503/549203d7/attachment-0001.html\u003e",
"sig": "254bbf67269afcfe570104dca1e02eeaf03b2b724c5e95d129a23fad20cf5e4b8869329531aa6099e4ef57cef76d59d26d6937c0cb02ebb5d8de85f15b5b43fe"
}