However despite me being able to "defend the thesis" in that literal sense, I still think your overall critique is valid. I think the "framework" (at least in the updated version of the paper; the first couple of drafts were a bit incoherent) makes sense, but it's too vague in the most important part of the reasoning, namely the invertibility of the functions described. But w.r.t. the values P and R, throughout, I was assuming pseudorandomness (uncontrollable output-ness) [1] of the mappings x -> P = xG and k -> R=kG. That assumption was both explicit and implicit in several steps (or perhaps leaps) I took (see e.g. how I refer to the function f(P, R, s) and in at least one place basically "ignore" the P, R dependency because they are uncontrollable); in my head , that was justifiable based on it being a prime order group, but at the very least, I should have been explicit.

On Friday, October 31, 2025 at 7:51:48 AM UTC-3 Tim Ruffing wrote:

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 bitcoindev+...@googlegroups.com.
> To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/0f6c92cc-e922-4d9f-9fdf-69384dcc4086n%40googlegroups.com
> .