From: Tim Ruffing <me@real-or-random.org>
To: waxwing/ AdamISZ <ekaggata@gmail.com>,
Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] On (in)ability to embed data into Schnorr
Date: Fri, 31 Oct 2025 10:10:51 +0100 [thread overview]
Message-ID: <5c15c2c265c92d5527fe3da510ac76c2a6e8e0e4.camel@real-or-random.org> (raw)
In-Reply-To: <0f6c92cc-e922-4d9f-9fdf-69384dcc4086n@googlegroups.com>
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+unsubscribe@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/5c15c2c265c92d5527fe3da510ac76c2a6e8e0e4.camel%40real-or-random.org.
next prev parent reply other threads:[~2025-10-31 10:51 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 [this message]
2025-10-31 13:09 ` waxwing/ AdamISZ
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=5c15c2c265c92d5527fe3da510ac76c2a6e8e0e4.camel@real-or-random.org \
--to=me@real-or-random.org \
--cc=bitcoindev@googlegroups.com \
--cc=ekaggata@gmail.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