From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Fri, 31 Oct 2025 06:25:20 -0700 Received: from mail-oo1-f62.google.com ([209.85.161.62]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vEp83-0005Oe-Gh for bitcoindev@gnusha.org; Fri, 31 Oct 2025 06:25:20 -0700 Received: by mail-oo1-f62.google.com with SMTP id 006d021491bc7-656828a8ba5sf3081519eaf.1 for ; Fri, 31 Oct 2025 06:25:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1761917113; x=1762521913; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=f4NoWjP6zLrSonH5BtveLfhLVyyqNWUaw+6nqWpAjXU=; b=q6q60Oc5a1p+BkZJpKFduZZuQJtB1tW3mm+3lZlM4ZEztFadwgZI33usUv9xMDUCov ok9JO7oqEcbulabIu77kGGi4jqgaKf8ge9G3V+NLvNtRrGVt/E5fyTMRUekycc6ET+Ot 7SoCyLPdz1tDtlOri5jwJXT4Bp6iun1Z36UPGj2ellw85JjQ9WtxpNelDRe0ThknqCgy B1CcKj1lLWzkvjW/xYiZ3h9nPXcrZ+/hBZ6bxN1XfS3dMEUnyyiyXgAJedksnhrjIrvJ wOO5k2WpM96qS84Ipv6CB6jMR6yjlX9cEElMfo5xC0hjTgsk/YFciAyAQJ+twZ8rV4wt Zpvg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1761917113; x=1762521913; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=f4NoWjP6zLrSonH5BtveLfhLVyyqNWUaw+6nqWpAjXU=; b=ITHQNTpUVIT3oU+9EvQOQIap2LI/otNNcwDm5ar5KF3Iac/A/jjhWlnKyKOYXBfVv6 7EwDFXYKF+04kpZ6nNAMMsr1XPnaUIFQ7I12MR50lYURcpZq2z2AT2E8SS7H7oNEVOOm 7aCFuSjiBaXxL0iNF4F52pO37zLB2WBjwkft8CyV1hXUzJeum+RWpe/wlPD/D3aTSz+G xvFeJH7JwPqUyFpUxMUSjGeDHrLVcLMzIQeyWYkQFkzHbxGZnooa9UEmkKc0KhIZBe7L sCB+P+MioH0wYkqx4KPLlqx54QWpUGmLc73PR07KwEpzB38/Q1TywFldXKMWzxJHLX6N rY5Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761917113; x=1762521913; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=f4NoWjP6zLrSonH5BtveLfhLVyyqNWUaw+6nqWpAjXU=; b=IUgMkUurfLMzQQIErzLcsdButFAEe28uXwXULgCjYVb39pvIRSrZJypsqEZ9F/oZxB lh+fbaIRs4rM/nfq2n6wrLBChwypVXvYJIMET/gcnqOJbvfV8Kjx4cseL5do0fq9Ves1 DmRlSOiEvtm4N9r3FcW0jbunk8+AyNDRHyY9XRPJppyQoAWI4WdxzQql+inGXZV/ovF9 1qC8Y0IDGBrGIM/TBbWwD+OOaKwAsixPmWZ3aolUwM7iCbGTEln/74Y8yj2+sGQyfpvp gT1QqRO80JuurW9eEnYZDq1gUBxs9/4VZFUtjG4o1thmXRX54P5mDVAbHcr25uUbRvmt l+gA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCXTwwsXj/VdvevI45J1GaH6ShwS6w/SJdyNn0EpdXCGsjOCpLINtj5oRQYbsp7c8jX6Kk53jiO0SVqC@gnusha.org X-Gm-Message-State: AOJu0YwCW3h6j64fTKkCr9PeJ20hkod+V5LvcdwtXSr0YG3Lo6HSmpBE ZviHNM9arT7y94UAhUepHCcqwfDbPVJ/WfWgckIf78CloQ/sgkP/aF8j X-Google-Smtp-Source: AGHT+IE04kB3N5YhxDu0RchqvV5XeTX/zxO1ewepb371xhB2XxZ2JIjnvCKvf9kUhzrx12H0017jxw== X-Received: by 2002:a05:6820:994:b0:656:84e7:8fde with SMTP id 006d021491bc7-6568a6bbfa5mr1634277eaf.3.1761917113356; Fri, 31 Oct 2025 06:25:13 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="Ae8XA+Ygj8UVjkm2eve4U14zt51LFrGIQB4G/Th5yqWU9jHxzA==" Received: by 2002:a05:6820:2d0a:b0:656:7cf6:9258 with SMTP id 006d021491bc7-656824a6568ls1194660eaf.2.-pod-prod-05-us; Fri, 31 Oct 2025 06:25:09 -0700 (PDT) X-Received: by 2002:a05:6808:c18a:b0:441:7c61:7f8b with SMTP id 5614622812f47-44f95ecef88mr1373601b6e.29.1761917108947; Fri, 31 Oct 2025 06:25:08 -0700 (PDT) Received: by 2002:a05:690c:dc1:b0:785:e55d:2dfd with SMTP id 00721157ae682-78649982b58ms7b3; Fri, 31 Oct 2025 06:09:15 -0700 (PDT) X-Received: by 2002:a05:690c:b03:b0:785:c08c:d39d with SMTP id 00721157ae682-7864856b0d4mr25761987b3.57.1761916154909; Fri, 31 Oct 2025 06:09:14 -0700 (PDT) Date: Fri, 31 Oct 2025 06:09:14 -0700 (PDT) From: waxwing/ AdamISZ To: Bitcoin Development Mailing List Message-Id: <61eb9abe-3e26-495d-9d00-dbda69fe018bn@googlegroups.com> In-Reply-To: <5c15c2c265c92d5527fe3da510ac76c2a6e8e0e4.camel@real-or-random.org> References: <0f6c92cc-e922-4d9f-9fdf-69384dcc4086n@googlegroups.com> <5c15c2c265c92d5527fe3da510ac76c2a6e8e0e4.camel@real-or-random.org> Subject: Re: [bitcoindev] On (in)ability to embed data into Schnorr MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_82358_1012136241.1761916154320" X-Original-Sender: ekaggata@gmail.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) ------=_Part_82358_1012136241.1761916154320 Content-Type: multipart/alternative; boundary="----=_Part_82359_1869745723.1761916154320" ------=_Part_82359_1869745723.1761916154320 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Tim, First, thanks for the considered reply! That is a very interesting point=20 for sure. I guess I have 2 or 3 responses: First, my "theorem 1" was deliberately specific about BIP340. I am aware of= =20 the impact of Pohlig-Hellman on non prime order groups. However despite me being able to "defend the thesis" in that literal sense,= =20 I still think your overall critique is valid. I think the "framework" (at= =20 least in the updated version of the paper; the first couple of drafts were= =20 a bit incoherent) makes sense, but it's too vague in the most important=20 part of the reasoning, namely the invertibility of the functions described.= =20 But w.r.t. the values P and R, throughout, I was assuming pseudorandomness= =20 (uncontrollable output-ness) [1] of the mappings x -> P =3D xG and k -> R= =3DkG.=20 That assumption was both explicit and implicit in several steps (or perhaps= =20 leaps) I took (see e.g. how I refer to the function f(P, R, s) and in at=20 least one place basically "ignore" the P, R dependency because they are=20 uncontrollable); in my head , that was justifiable based on it being a=20 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=C3=A5stad-N=C3=A4slund 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=20 above, I just assumed this without justifying it; so my end conclusion that= =20 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?= =20 If this is a DDH assumption, then perhaps that's what we should really=20 reduce to (well, plus hash preimage resistance)? Cheers, Adam On Friday, October 31, 2025 at 7:51:48=E2=80=AFAM UTC-3 Tim Ruffing wrote: > Hey Adam, > > I think something is wrong here.=20 > > Assume a group of order n=3Dp*2^t where p is a large enough prime such > that the DL problem is hard. For example, Curve25519 has t=3D3 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.=20 > > 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=3D0, 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=C3=A5stad-N=C3=A4slund 20= 03 [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, > >=20 > > https://github.com/AdamISZ/schnorr-unembeddability/ > >=20 > > 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". > >=20 > > See the abstract for a slightly more fleshed out context. > >=20 > > 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. > >=20 > > (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*). > >=20 > > However I still am probably in the large majority that thinks it's > > appalling to imagine a sig attached to every pubkey onchain. > >=20 > > Either way, I found it very interesting! Perhaps others will find the > > analysis valuable. > >=20 > > Feedback (especially of the "that's wrong/that's not meaningful" > > variety) appreciated. > >=20 > > Regards, > > AdamISZ/waxwing > >=20 > > --=20 > > 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 > >=20 > https://groups.google.com/d/msgid/bitcoindev/0f6c92cc-e922-4d9f-9fdf-6938= 4dcc4086n%40googlegroups.com > > . > --=20 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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= 61eb9abe-3e26-495d-9d00-dbda69fe018bn%40googlegroups.com. ------=_Part_82359_1869745723.1761916154320 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Tim,

First, thanks for the considered reply! That i= s a very interesting point for sure.

I guess I h= ave 2 or 3 responses:

First, my "theorem 1" was = deliberately specific about BIP340. I am aware of the impact of Pohlig-Hell= man on non prime order groups.

However despite m= e being able to "defend the thesis" in that literal sense, I still think yo= ur overall critique is valid. I think the "framework" (at least in the upda= ted 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 reasonin= g, namely the invertibility of the functions described. But w.r.t. the valu= es P and R, throughout, I was assuming pseudorandomness (uncontrollable out= put-ness) [1] of the mappings x -> P =3D xG and k -> R=3DkG. That ass= umption 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 uncontrollab= le); in my head=C2=A0, 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 mu= st somehow exploit the fact that all bits of k
are hard to compute fro= m R; see Section 10 in H=C3=A5stad-N=C3=A4slund 2003 [1]
for a proof t= hat this is the case for prime-order groups.

Nic= e 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 i= s a reduction to hash preimage resistance is I guess incomplete.
=
[1] so .. k -> kG is kind of a pseudorandom function, o= r generator, right? If this is a DDH assumption, then perhaps that's what w= e should really reduce to (well, plus hash preimage resistance)?
=
Cheers,
Adam

On Friday, October 31, 2025= at 7:51:48=E2=80=AFAM UTC-3 Tim Ruffing wrote:
Hey Adam,

I think something is wrong here.=C2=A0

Assume a group of order n=3Dp*2^t where p is a large enough prime such
that the DL problem is hard. For example, Curve25519 has t=3D3 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 f= or
sufficiently large values of t.=C2=A0

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=3D0, 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=C3=A5stad-N=C3=A4slund = 2003 [1]
for a proof that this is the case for prime-order groups.

Best,
Tim

[1] http= s://www.csc.kth.se/~johanh/hnrsaacm.pdf



On Wed, 2025-10-01 at 07:24 -0700, waxwing/ AdamISZ wrote:
> Hi all,
>=20
> https://github.com/AdamISZ/schnorr-unembeddability/
>=20
> Here I'm analyzing whether the following statement is true: &q= uot;if you
> can embed data into a (P, R, s) tuple (Schnorr pubkey and signatur= e,
> BIP340 style), without grinding or using a sidechannel to "in= form"
> the reader, you must be leaking your private key".
>=20
> See the abstract for a slightly more fleshed out context.
>=20
> I'm curious about the case of P, R, s published in utxos to pr= event
> usage of utxos as data. I think this answers in the half-affirmati= ve:
> you can only embed data by leaking the privkey so that it (can)
> immediately fall out of the utxo set.
>=20
> (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 i= s *no
> other way*).
>=20
> However I still am probably in the large majority that thinks it&#= 39;s
> appalling to imagine a sig attached to every pubkey onchain.
>=20
> Either way, I found it very interesting! Perhaps others will find = the
> analysis valuable.
>=20
> Feedback (especially of the "that's wrong/that's not = meaningful"
> variety) appreciated.
>=20
> Regards,
> AdamISZ/waxwing
>=20
> --=20
> 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 bitcoi= ndev+...@googlegroups.com.
> To view this discussion visit
> https://groups.google.com/d/msgid/b= itcoindev/0f6c92cc-e922-4d9f-9fdf-69384dcc4086n%40googlegroups.com
> .

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/61eb9abe-3e26-495d-9d00-dbda69fe018bn%40googlegroups.com.
------=_Part_82359_1869745723.1761916154320-- ------=_Part_82358_1012136241.1761916154320--