From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Sat, 01 Nov 2025 08:47:45 -0700 Received: from mail-oo1-f59.google.com ([209.85.161.59]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vFDpQ-0007Q0-Oq for bitcoindev@gnusha.org; Sat, 01 Nov 2025 08:47:45 -0700 Received: by mail-oo1-f59.google.com with SMTP id 006d021491bc7-654dbf83af6sf1804792eaf.2 for ; Sat, 01 Nov 2025 08:47:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1762012058; x=1762616858; 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=hFJ3fSIPYe1NNVvSMFXxc9ttRWXHuLVT/i6/pAD27ME=; b=UOm4NOXTs9vhokrCLF48/VspGIop06RYP4rG4YZI5ZmNeTlrmwdm0OyTK5rJ0LAZbh betXj+Jh0L/REs87EzH6f05gvGYQtxfmyRsF/RJrBa9aS+bmXqVdatMPYLS9cQsZfjJw 1DhC8vgzkVeSBE13wDbX3a1Oli4VAnjN0rgkbiYmGqhLhCaLc/tuL2vk8/LsYv/FuqFr c8dYtY0X9D21jyDpl5JFzBErs/mfRiGoHgQm2RCP05wiy5Ny22o5bNHvs8YiwTLnqpZk S3l6ctjUmumuxwyBKfueI6cP5z63hcBDmqfMLgB54CGby9PyE73AXggGuZpDefyVQ6Be wgJA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762012058; x=1762616858; 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=hFJ3fSIPYe1NNVvSMFXxc9ttRWXHuLVT/i6/pAD27ME=; b=NwRhqYOUrmLw93emXH2hed0MtPrOE2HD/5DjyCNuhV+V2/DR7Ua371VBJ8pZ8DC1om yAdNOI5pchQ/FIra0IkbY6pLSW5VSbYA4mlojsHgvwK9Wnh3hJkk+yGDXZEHR6VS7DXf Q8XGYqPJNHlIyzYmBwjTrpZwuYTlaSkh6vtxeyn7IQIdLZ10UKUwqHmYnp1Gik4eG5VL bK90QENKfkW27LGCKFdJft/nBC/QddgjtC+vkp4k3+4yxYSciTXDkUUA+KKUUYit19Yz hWQkWb/TSyphPmtxEVE7rWHBwry0hZbo3Im5NtPxMiTNKkyb3ayTF6C1pbylnnnV+oh0 aGEA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762012058; x=1762616858; 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=hFJ3fSIPYe1NNVvSMFXxc9ttRWXHuLVT/i6/pAD27ME=; b=qvAsOCMCIAq2PuqUAZFzq17B63GbiyKnZsCWefL3xKtk/c2ajdCrMyPKgTYt9fe9j1 8cv+bpfLCOOk81YcTIYuLRqlNLgrqIBxX955MHoBgHeH0Dyr8wr5ePVJKR9lQ7tb+YjV hu8D3fZDBckaoFSc+9+1fSTmN+MnqoXryNafMABAmhF61YK03QiPweBkAioqiepv3oH5 OgsQPcJ3bCdPEvVTh/85JakvVMRWNWytXDtOjo+gW/h2zDQCyUz69vzPOca0u++VoXyZ keqbCn7j/hWv/JT4QvzB1mlmD+n0mnAHQ2Z2RxEgb1vk4ZAqL2TFBlj31UZNk9Q5K+/4 GIoA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCUq6NXLPpF/c6nn20G+Iz0btyUXL4zHzTpWANj5bUIk06HlKSQcNX01wYl2Q9rTEv6OxAXiPbIbiNm5@gnusha.org X-Gm-Message-State: AOJu0YwPhtMdzqzqEA59k5A2+7O/3wa0rS+hPZ7WJrVglmgm5dZQ7c1s 1AdIxyonpH8VKZfi9pzynV7BUD4OsxALdvcIIIyXtTDYIAUKh/LKYVKI X-Google-Smtp-Source: AGHT+IHqbhUrKtwVTYzlnwzNPPSeQHlsEtcRmjKYRzvb2oVgv7rpAvj8smoW11hFleeqr2/+8h74og== X-Received: by 2002:a05:6871:870e:10b0:3db:d2f2:5de5 with SMTP id 586e51a60fabf-3dbd2f2a45cmr1981483fac.39.1762012058373; Sat, 01 Nov 2025 08:47:38 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="Ae8XA+YC5cKs3QeICbdhj1DoVidAI1euv20O2X69Vpx/Vq0mYQ==" Received: by 2002:a05:6870:7052:10b0:3d2:c10b:cb41 with SMTP id 586e51a60fabf-3d8bc1edb61ls971214fac.2.-pod-prod-09-us; Sat, 01 Nov 2025 08:47:34 -0700 (PDT) X-Received: by 2002:a05:6808:4f4e:b0:43f:87ca:403b with SMTP id 5614622812f47-44f95f24cc9mr3829273b6e.26.1762012054738; Sat, 01 Nov 2025 08:47:34 -0700 (PDT) Received: by 2002:a05:690c:ea:b0:780:f7eb:fdf with SMTP id 00721157ae682-7865fb1b7c5ms7b3; Sat, 1 Nov 2025 07:49:06 -0700 (PDT) X-Received: by 2002:a05:690c:7605:b0:786:4f0d:46ae with SMTP id 00721157ae682-7864f0d5f81mr43219497b3.1.1762008545735; Sat, 01 Nov 2025 07:49:05 -0700 (PDT) Date: Sat, 1 Nov 2025 07:49:05 -0700 (PDT) From: waxwing/ AdamISZ To: Bitcoin Development Mailing List Message-Id: <781840dd-b633-4d87-b05d-d389c6374d63n@googlegroups.com> In-Reply-To: References: <0f6c92cc-e922-4d9f-9fdf-69384dcc4086n@googlegroups.com> Subject: Re: [bitcoindev] On (in)ability to embed data into Schnorr MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_123614_69604575.1762008545394" 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_123614_69604575.1762008545394 Content-Type: multipart/alternative; boundary="----=_Part_123615_791249138.1762008545394" ------=_Part_123615_791249138.1762008545394 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Garlo Nicon, Before I answer your point I want to mention (to readers): probably some=20 things remained tacit in this thread but are worth emphasizing: 1. It's always trivial to get a 100% embedding rate if it's OK to assume=20 the embedder is choosing to share data off-blockchain with others (just xor= =20 the real signature with their chosen data and call that the key). This is= =20 of course is a bit silly (though not entirely silly); if the purpose is to= =20 *communicate* then they can use the communication channel for the data,=20 instead of the xor value, and forget about the blockchain. On the other=20 hand if their purpose is to publish data, and rely on the immutability and= =20 persistence of the blockchain, then there is the problem that the xor key= =20 can be lost; it's that offchain data that represents the actual semantics= =20 of what they published, and so they're in rather the same position as they= =20 would have been without the blockchain existing at all. (insert=20 finesses/caveats but, basically). 2. All of the above theoretical analysis doesn't work for ECDSA *as an=20 algorithm outside of Bitcoin*. You get 32 bytes of embedding without=20 leaking the private key, there. (the s-value can literally be made to say= =20 "hello world" 3 times or whatever). this is the non-pubkey-committing=20 nature of standard ECDSA. I *think* you can make it behave the same as=20 Schnorr in terms of pubkey-unembeddability-without-key-leakage by putting= =20 the pubkey in the message, but it's even harder to analyze than Schnorr=20 (which is already hard). 3. In contrast to 2., the pubkey is in fact embedded in the message=20 (indirectly), at least usually, in Bitcoin (except sighash_noinput type=20 stuff which isn't live), so you can't put hello world in the signatures for= =20 now, at least AFAIK. Still even then you're stuck at a 33% rate if we=20 include all of P, R, s, which seems reasonable (in fact, that's a generous= =20 measure). Again, I am ignoring grinding which always adds a bit more. Anyway, you say: > So, I guess it is a spectrum: something like 70% efficiency means, that= =20 you need "known plaintext attack" to get the data. And then, you can use=20 less and less bits per public key, to make it arbitrarily weaker. Then,=20 instead of relying on a timelock, you can rely on computation difficulty=20 for the reader, for example: "how many bits I need to leak, to make it=20 breakable by lattice attack". I think it's an interesting idea to use lattice attacks but I can't find a= =20 way to agree with 66 or 70%. Here's why: We assume a "few" signatures are all on the same private key. If there are= =20 N such signatures, then once LLL or similar lattice method is successful,= =20 you retrieve the 1 private key (32 bytes) and the N * 27 bytes (or so;=20 imagining 5 bytes are biased; it *can* go lower, requiring more signatures;= =20 doesn't change the situation). So you embedded successfully 27N+32 (all the nonces and the private key)=20 into 64N + 32N [1] for a ratio that is a bit less than 33%. Compare with=20 just using a repeated nonce in 2 equations, where you get 64 bytes (nonce,= =20 privkey) from 2*P + 2*(R,s) or so a total of 196, i.e. 33% exactly.=20 Basically, at least in a bitcoin context, there is no gain in doing a=20 partial exposure of the nonce; you may as well just reveal all of it,=20 either by repetition or as noted in the pdf, by using something public like= =20 a block hash. Notice that if my note [1] did not apply, then all the above= =20 isn't correct, the ratios work differently. Can you let me know how you're getting 66%+? I'm guessing you're just=20 saying "the k and the d values" but as per above I don't see it. Maybe=20 write out concretely what the data-reader would be doing? [1] It's easy to slip up here - I know I did - when considering publication= =20 *on bitcoin* compared with just publishing signatures. In the latter case,= =20 I can publish 100 signatures with the tacit assumption that they all refer= =20 to the same key (or, you can verify, to check). In bitcoin the pubkey is=20 never tacit, it's always published in the scriptPubKey or scriptSig or=20 whatever, so you can't gain efficiency from repeated uses of the same key= =20 (i.e. you can't write 64N + 32, it must be 64N + 32N for (P, R, s) tuples). Cheers, Adam On Friday, October 31, 2025 at 10:25:30=E2=80=AFAM UTC-3 Garlo Nicon wrote: > if you can embed data into a (P, R, s) tuple (Schnorr pubkey and=20 signature, BIP340 style), without grinding or using a sidechannel to=20 "inform" the reader, you must be leaking your private key You can embed data into a valid signature. For example: R=3Dk*G P=3Dd*G k=3Dfirst_chunk_of_data d=3Dsecond_chunk_of_data And then, keys are "weak", because people can use "known plaintext attack",= =20 to get them. However, if you want to push random data, that is unknown to= =20 the reader, then it is known only by the holder of the data. Which means, that the efficiency of this encoding is somewhere around 66%,= =20 by grinding SHA-256 hashes, it could probably reach around 70% in practice.= =20 Only s-value is something, that needs any grinding, for k-value and=20 d-value, you need only the data, and nothing else. So, I guess it is a spectrum: something like 70% efficiency means, that you= =20 need "known plaintext attack" to get the data. And then, you can use less= =20 and less bits per public key, to make it arbitrarily weaker. Then, instead= =20 of relying on a timelock, you can rely on computation difficulty for the=20 reader, for example: "how many bits I need to leak, to make it breakable by= =20 lattice attack". --=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/= 781840dd-b633-4d87-b05d-d389c6374d63n%40googlegroups.com. ------=_Part_123615_791249138.1762008545394 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Garlo Nicon,

Before I answer your point I want= to mention (to readers): probably some things remained tacit in this threa= d but are worth emphasizing:

1. It's always triv= ial to get a 100% embedding rate if it's OK to assume the embedder is choos= ing to share data off-blockchain with others (just xor the real signature w= ith their chosen data and call that the key). This is of course is a bit si= lly (though not entirely silly); if the purpose is to *communicate* then th= ey can use the communication channel for the data, instead of the xor value= , and forget about the blockchain. On the other hand if their purpose is to= publish data, and rely on the immutability and persistence of the blockcha= in, then there is the problem that the xor key can be lost; it's that offch= ain data that represents the actual semantics of what they published, and s= o they're in rather the same position as they would have been without the b= lockchain existing at all. (insert finesses/caveats but, basically).
<= div>
2. All of the above theoretical analysis doesn't work = for ECDSA *as an algorithm outside of Bitcoin*. You get 32 bytes of embeddi= ng without leaking the private key, there. (the s-value can literally be ma= de to say "hello world" 3 times or whatever). this is the non-pubkey-commit= ting nature of standard ECDSA. I *think* you can make it behave the same as= Schnorr in terms of pubkey-unembeddability-without-key-leakage by putting = the pubkey in the message, but it's even harder to analyze than Schnorr (wh= ich is already hard).

3. In contrast to 2., the = pubkey is in fact embedded in the message (indirectly), at least usually, i= n Bitcoin (except sighash_noinput type stuff which isn't live), so you can'= t put hello world in the signatures for now, at least AFAIK. Still even the= n you're stuck at a 33% rate if we include all of P, R, s, which seems reas= onable (in fact, that's a generous measure). Again, I am ignoring grinding = which always adds a bit more.

Anyway, you say:
<= /div>

> So, I guess it is a spectrum: something lik= e 70% efficiency means, that you need "known plaintext attack" to get the d= ata. And then, you can use less and less bits per public key, to make it ar= bitrarily weaker. Then, instead of relying on a timelock, you can rely on c= omputation difficulty for the reader, for example: "how many bits I need to= leak, to make it breakable by lattice attack".

= I think it's an interesting idea to use lattice attacks but I can't find a = way to agree with 66 or 70%. Here's why:

We assu= me a "few" signatures are all on the same private key. If there are N such = signatures, then once LLL or similar lattice method is successful, you retr= ieve the 1 private key (32 bytes) and the N * 27 bytes (or so; imagining 5 = bytes are biased; it *can* go lower, requiring more signatures; doesn't cha= nge the situation).

So you embedded successfully= 27N+32 (all the nonces and the private key) into 64N + 32N [1] for a ratio= that is a bit less than 33%. Compare with just using a repeated nonce in 2= equations, where you get 64 bytes (nonce, privkey) from 2*P + 2*(R,s) or s= o a total of 196, i.e. 33% exactly. Basically, at least in a bitcoin contex= t, there is no gain in doing a partial exposure of the nonce; you may as we= ll just reveal all of it, either by repetition or as noted in the pdf, by u= sing something public like a block hash. Notice that if my note [1] did not= apply, then all the above isn't correct, the ratios work differently.

Can you let me know how you're getting 66%+? I'm gue= ssing you're just saying "the k and the d values" but as per above I don't = see it. Maybe write out concretely what the data-reader would be doing?

[1] It's easy to slip up here - I know I did - when= considering publication *on bitcoin* compared with just publishing signatu= res. In the latter case, I can publish 100 signatures with the tacit assump= tion that they all refer to the same key (or, you can verify, to check). In= bitcoin the pubkey is never tacit, it's always published in the scriptPubK= ey or scriptSig or whatever, so you can't gain efficiency from repeated use= s of the same key (i.e. you can't write 64N + 32, it must be 64N + 32N for = (P, R, s) tuples).

Cheers,
Adam
<= br />
On Friday, October 31, 2025 at 10:25:30= =E2=80=AFAM UTC-3 Garlo Nicon wrote:
> 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
You can embed data into a valid signature. = For example:

R=3Dk*G
P=3Dd*G
k=3Dfirst_chunk_of_data
d=3Dsecond_chunk_of_data=

And then, keys are "weak", because people can use "known plaint= ext attack", to get them. However, if you want to push random data, that is= unknown to the reader, then it is known only by the holder of the data.
Which means, that the efficiency of this encoding is somewhere aro= und 66%, by grinding SHA-256 hashes, it could probably reach around 70% in = practice. Only s-value is something, that needs any grinding, for k-value a= nd d-value, you need only the data, and nothing else.

So, I gues= s it is a spectrum: something like 70% efficiency means, that you need "kno= wn plaintext attack" to get the data. And then, you can use less and less b= its per public key, to make it arbitrarily weaker. Then, instead of relying= on a timelock, you can rely on computation difficulty for the reader, for = example: "how many bits I need to leak, to make it breakable by lattice att= ack".

--
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/781840dd-b633-4d87-b05d-d389c6374d63n%40googlegroups.com.
------=_Part_123615_791249138.1762008545394-- ------=_Part_123614_69604575.1762008545394--