Hey Adam, I think something is wrong here.
Assume a group of order n=p*2^t where p is a large enough prime such that the DL problem is hard. For example, Curve25519 has t=3 but the DL problem still hard. Or, assuming n+1 is also prime, work in the multiplicative group of integers modulo n+1 (which has group order n then). I'm not aware of any obstacles to constructing such groups for sufficiently large values of t. The crucial point is that, in these groups, the Pohlig-Hellman algorithm can be used to compute the t least significant bits of the discrete logarithm k of a group element R efficiently. So to embed t bits in a Schnorr signature (R, s), simply pick k such that its t least significant bits t are exactly these bits. Of course, this does not work in BIP340 because it uses the secp256k1 group for which t=0, i.e., the group has prime order. But it appears that the reasoning in your write up is not specific to prime-order groups. Thus I conclude that something must be wrong or insufficient in your argument. Let me clarify that I do not claim that data can be embedded in a BIP340 signature. I only claim that your arguments for why data can't be embedded do not appear to be sound. I believe any proof that data cannot be embedded in a Schnorr signature (or in a group element R) in a prime-order group must somehow exploit the fact that all bits of k are hard to compute from R; see Section 10 in Håstad-Näslund 2003 [1] for a proof that this is the case for prime-order groups. Best, Tim [1] https://www.csc.kth.se/~johanh/hnrsaacm.pdf On Wed, 2025-10-01 at 07:24 -0700, waxwing/ AdamISZ wrote: > Hi all, > > https://github.com/AdamISZ/schnorr-unembeddability/ > > Here I'm analyzing whether the following statement is true: "if you > can embed data into a (P, R, s) tuple (Schnorr pubkey and signature, > BIP340 style), without grinding or using a sidechannel to "inform" > the reader, you must be leaking your private key". > > See the abstract for a slightly more fleshed out context. > > I'm curious about the case of P, R, s published in utxos to prevent > usage of utxos as data. I think this answers in the half-affirmative: > you can only embed data by leaking the privkey so that it (can) > immediately fall out of the utxo set. > > (To emphasize, this is different to the earlier observations > (including by me!) that just say it is *possible* to leak data by > leaking the private key; here I'm trying to prove that there is *no > other way*). > > However I still am probably in the large majority that thinks it's > appalling to imagine a sig attached to every pubkey onchain. > > Either way, I found it very interesting! Perhaps others will find the > analysis valuable. > > Feedback (especially of the "that's wrong/that's not meaningful" > variety) appreciated. > > Regards, > AdamISZ/waxwing > > -- > 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 [email protected]. > To view this discussion visit > https://groups.google.com/d/msgid/bitcoindev/0f6c92cc-e922-4d9f-9fdf-69384dcc4086n%40googlegroups.com > . -- 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 [email protected]. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/5c15c2c265c92d5527fe3da510ac76c2a6e8e0e4.camel%40real-or-random.org.
