From: waxwing/ AdamISZ <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] On (in)ability to embed data into Schnorr
Date: Fri, 31 Oct 2025 06:09:14 -0700 (PDT) [thread overview]
Message-ID: <61eb9abe-3e26-495d-9d00-dbda69fe018bn@googlegroups.com> (raw)
In-Reply-To: <5c15c2c265c92d5527fe3da510ac76c2a6e8e0e4.camel@real-or-random.org>
[-- Attachment #1.1: Type: text/plain, Size: 5873 bytes --]
Hi Tim,
First, thanks for the considered reply! That is a very interesting point
for sure.
I guess I have 2 or 3 responses:
First, my "theorem 1" was deliberately specific about BIP340. I am aware of
the impact of Pohlig-Hellman on non prime order groups.
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.
> 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.
Nice reference, thanks! I definitely wouldn't have found that. As per
above, I just assumed this without justifying it; so my end conclusion that
there is a reduction to hash preimage resistance is I guess incomplete.
[1] so .. k -> kG is kind of a pseudorandom function, or generator, right?
If this is a DDH assumption, then perhaps that's what we should really
reduce to (well, plus hash preimage resistance)?
Cheers,
Adam
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
> > .
>
--
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/61eb9abe-3e26-495d-9d00-dbda69fe018bn%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 7906 bytes --]
next prev parent reply other threads:[~2025-10-31 13:25 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-10-01 14:24 waxwing/ AdamISZ
2025-10-01 22:10 ` Greg Maxwell
2025-10-01 23:11 ` Andrew Poelstra
2025-10-02 0:25 ` waxwing/ AdamISZ
2025-10-02 15:56 ` waxwing/ AdamISZ
2025-10-02 19:49 ` Greg Maxwell
2025-10-06 13:04 ` waxwing/ AdamISZ
2025-10-03 13:24 ` Peter Todd
2025-10-04 2:39 ` waxwing/ AdamISZ
2025-10-07 8:22 ` Anthony Towns
2025-10-07 12:05 ` waxwing/ AdamISZ
2025-10-08 5:12 ` Anthony Towns
2025-10-08 12:55 ` waxwing/ AdamISZ
2025-10-31 9:10 ` Tim Ruffing
2025-10-31 13:09 ` waxwing/ AdamISZ [this message]
2025-10-31 13:19 ` Garlo Nicon
2025-11-01 14:49 ` waxwing/ AdamISZ
2025-11-02 9:11 ` Garlo Nicon
2025-11-02 13:30 ` waxwing/ AdamISZ
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=61eb9abe-3e26-495d-9d00-dbda69fe018bn@googlegroups.com \
--to=ekaggata@gmail.com \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox