From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Fri, 31 Oct 2025 03:51:54 -0700 Received: from mail-oa1-f61.google.com ([209.85.160.61]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vEmja-0003pd-8K for bitcoindev@gnusha.org; Fri, 31 Oct 2025 03:51:54 -0700 Received: by mail-oa1-f61.google.com with SMTP id 586e51a60fabf-3c976cde530sf3396082fac.3 for ; Fri, 31 Oct 2025 03:51:54 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1761907908; cv=pass; d=google.com; s=arc-20240605; b=RHjc1swfIkigRIUGBStkCkApHB4nKavdm9N+pxXzqNUfzFtygVAV43r1ZiN52PYHii 3Uj2VHu0JZpKu4HIcQy9cSAqTKOsDI+43mRq2KO2M+FNtoiOniIqf9US/bIGD/qyxOPP UtOMGEa6BBlFBWnhd13Kjhnyc/SOPqP9zpOc8u8QO7sD7gzNGnXApieoqXivDPkHS6t2 ZjsZL3PnzTymqGIQl+In3dk4810wRLkAMZcTp3S9Tt3AgA28xe2FvSe1zKsS4YQRLQhB kAsMu0jj8e4r+DmPFVkXnPOqUl8+iTow0PQQzg4SAK09DtWaczEtIgcM217W/nMN/hFN yozw== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:mime-version :content-transfer-encoding:references:in-reply-to:date:to:from :subject:message-id:sender:dkim-signature; bh=jsSolHBj8pxJmJM675WXguTq2JHKC4U2hldHIKTAgyk=; fh=Cl0WPsjTkWXX4LE0yty4D3Dgq/Q0VzggjAdBImpLjHA=; b=WdLa1XzYbm8xjqs65gHgQZts3H7Dz3R/CVcEZAwYLNiOpU9D5ipvOqZImyV36Ajni5 4BrGtvbN4hGoYLlHbjtXO+w9hIcfA4WG4MrRW+UtQCeRl4fQ8hRtyobooe5aacu2Qy8a LIR+wNx791Fs1yog5TiUwuFtdznnpM+B0fTu4iJTw8UbZIJlKTFvxO5+IhvbQnXIxrO2 jLmthhq3yRRD4G95a02DZGC9Ar1axsP6hV/nmjbco49GlBEi18hHZNttyPDqGFwUBEkK A0my/s0edaQIKPQyiqOG6LowOJJD2zohgTcPycNYWkNFlKG8/JnoqlKP4gna2lzTd0OC 849Q==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@real-or-random.org header.s=MBO0001 header.b=RWzgv9G6; spf=pass (google.com: domain of me@real-or-random.org designates 80.241.56.152 as permitted sender) smtp.mailfrom=me@real-or-random.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=real-or-random.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1761907908; x=1762512708; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:mime-version:content-transfer-encoding:references :in-reply-to:date:to:from:subject:message-id:sender:from:to:cc :subject:date:message-id:reply-to; bh=jsSolHBj8pxJmJM675WXguTq2JHKC4U2hldHIKTAgyk=; b=WypBNetVnr5fTNH3SGttBdMyi/uUORymWdufX7paAxWUEyPB6JyUGLBJLBn4/0Vup5 sASjYMoUx6deNGSwWPpdB/erqNy07EQi5lXbsqXEAhmu4TO+xwx/as2/6/PZ4tCoj/T6 rcLnKWRRWpuUsKkqsP+DPhmIAkKKAtCflM8msBreiUZYsnCvmi2FsQHAF7kmDK8AR0Po h54RAtuJZLuIvbbsVkeRYtTGVjnDeF6GyTHBYTSK3YL5O6ATo5nfv4cz8Oljy3ibzYCo RyyfeoeM2gipbQ7onLVOHRlz3rpw19t5FJ3PMA597PskmB41HZgmKbpjhT1YpfwDoaH1 PsYA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761907908; x=1762512708; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:mime-version:content-transfer-encoding:references :in-reply-to:date:to:from:subject:message-id:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=jsSolHBj8pxJmJM675WXguTq2JHKC4U2hldHIKTAgyk=; b=h+Gz3jczYhD1jj0eEIbiLUinqwKJC0UMkzJjSop3MU6I6E1PSjoOtL9xftIuG0tep9 ZrjnEoCHj3gFhFJzWAh66nAv54y0C7Bp462VphV8C/Moq61L2OY1cr1ESE3nT0rhzvDV RgqFNVzNmpIn7aNTmVjIzByiKYLhjtKSLKPldN8GDyZs92W63/RLiYgcj/fbseCUAhLj VkqsNwcOJvJ4A40+96MfRuXoyqm4tOx1yQW4GgtwI2QUIftffN2AYaGRaVmmONubIQ3I EEc+3MQDPzMMnvpv33r2fzVPxbKrFAmeaNoCTvRcZgA95+lRc70WbqSKONdoURU2hOGU g0YA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCW0qSm6VtrEHS11NLAgnjmRLUXFIweFwnpLGQjZIHFzTKtiXVdjdlErh4lRW4MWGNlftkosWbrvbyjn@gnusha.org X-Gm-Message-State: AOJu0Yz+xJ+3zFT15e3G38LnZ+2TNEieT73VcmaOYp77A/ZWPrJF9m6y BJQb8sq6+Kg/JtmA+uCqG8MjlVZVQbi4t4RELxO2V6Umyj2ueWDcichY X-Google-Smtp-Source: AGHT+IEAsCIim/R72ZzhfrYI6360OXsTr5PM4ImCHnPhh1eJ4vKPBYYoS9984INGU5VP9tqTp9f3ew== X-Received: by 2002:a05:6870:84c5:b0:3d2:be9c:6b1c with SMTP id 586e51a60fabf-3daca106e1bmr1052534fac.8.1761907907890; Fri, 31 Oct 2025 03:51:47 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="Ae8XA+YWN5nYZaN9tgjXsraRC4oCq5rJGGV9u6Q3BpepdfPGPA==" Received: by 2002:a05:6870:a093:b0:35a:ce0a:d0a3 with SMTP id 586e51a60fabf-3d8b946c526ls901798fac.0.-pod-prod-08-us; Fri, 31 Oct 2025 03:51:43 -0700 (PDT) X-Forwarded-Encrypted: i=2; AJvYcCWQn6zYErUOn0y3JkSVbb2zTW8p8A+b+7WPRV5RKwILWyDtFSbS1NjgqY0noL4v0q7KAGBRbqAdzl5z@googlegroups.com X-Received: by 2002:a05:6808:3206:b0:44f:8bff:4354 with SMTP id 5614622812f47-44f95e78c2dmr1327543b6e.6.1761907903318; Fri, 31 Oct 2025 03:51:43 -0700 (PDT) Received: by 2002:a50:a699:0:b0:637:23ea:b3e2 with SMTP id 4fb4d7f45d1cf-6407925d796msa12; Fri, 31 Oct 2025 02:10:58 -0700 (PDT) X-Forwarded-Encrypted: i=2; AJvYcCU64jlcMTRBaarIAZfCHITb3Az22DTsTGV6QQ1oxj+BkDYy+2BvWf9cOBn7SRT9ZsaGbw5IuAu7DcMI@googlegroups.com X-Received: by 2002:a05:6402:42c4:b0:633:7017:fcbc with SMTP id 4fb4d7f45d1cf-64076faddecmr2318294a12.15.1761901856053; Fri, 31 Oct 2025 02:10:56 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1761901856; cv=none; d=google.com; s=arc-20240605; b=g/EXqUNAHF9vEEODDb6YMh1PjwSqtakd+K3ClwOAzjnGDnjevFcRgfnnRpoCmnLCpi wfYmJ57pjxNjC88s/iN4st3M73DLq/RrN5e2/qUwuDtwKSMovGV1WX4ZRBvqRtHytCNn EU0k5aEcg7L80RgrKzsMX31+sakfz+TiNwHX8siUsx+jjCBIia2do4ZRBm5ivJfj3/NF ZEV/SYCKcJyhj0NtGhJyqoWR016NW6gSGV0q/8bo/GWmzBgNZOKI9JpLZYKL4smeHyz2 YEkH6AUNGS8Gaiw8ZHDPleAqGCfJ22ygEl7VEw1oG03hNFELXyH89TgNZpLLebOWTArA hH9A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=mime-version:content-transfer-encoding:references:in-reply-to:date :to:from:subject:message-id:dkim-signature; bh=6GOSeQiWKjRs8qwsH+0cDuZ6139MilVK6IS5VlZUKRM=; fh=2EV9HtMw1QTzGSfUm2X/O0xVoxxmy5vUj8s0Z9ARrDA=; b=hY89rfA9DDsdF5Q1QftQ25Ng3hnLm14mNq5G6coz9jzT/cDRv0vdIeAvccMOE368ze dy1nGEAKu37wrgGOoQYCMxjXaXfLtfkRkmXke5h0ljdf1V0PISi7y1Pc1wf8qQpGUGLk TyoULoAcMyYedMQV0WJ5RUvzXWd1t8p0q42FXpLcwSnaxK2MibShYmRSvWmdEf0KDYhu dlAr/sD8XHMqkC9rt03bxwVHSMx14/t47zX2ySEh1U/U6gOzZIDrUqw/7rAI9iRUkc2y QPFMqEkxANTIAYChU8fwABEDnW3FkPHDx1Q93SCyXxdeyL7oOFJMqZPptv6STUx3+Xdl KX4Q==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@real-or-random.org header.s=MBO0001 header.b=RWzgv9G6; spf=pass (google.com: domain of me@real-or-random.org designates 80.241.56.152 as permitted sender) smtp.mailfrom=me@real-or-random.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=real-or-random.org Received: from mout-p-102.mailbox.org (mout-p-102.mailbox.org. [80.241.56.152]) by gmr-mx.google.com with ESMTPS id 4fb4d7f45d1cf-6407b349cb0si137760a12.1.2025.10.31.02.10.55 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 31 Oct 2025 02:10:55 -0700 (PDT) Received-SPF: pass (google.com: domain of me@real-or-random.org designates 80.241.56.152 as permitted sender) client-ip=80.241.56.152; Received: from smtp202.mailbox.org (smtp202.mailbox.org [IPv6:2001:67c:2050:b231:465::202]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by mout-p-102.mailbox.org (Postfix) with ESMTPS id 4cyZvx3v4Wz9tyC; Fri, 31 Oct 2025 10:10:53 +0100 (CET) Message-ID: <5c15c2c265c92d5527fe3da510ac76c2a6e8e0e4.camel@real-or-random.org> Subject: Re: [bitcoindev] On (in)ability to embed data into Schnorr From: Tim Ruffing To: waxwing/ AdamISZ , Bitcoin Development Mailing List Date: Fri, 31 Oct 2025 10:10:51 +0100 In-Reply-To: <0f6c92cc-e922-4d9f-9fdf-69384dcc4086n@googlegroups.com> References: <0f6c92cc-e922-4d9f-9fdf-69384dcc4086n@googlegroups.com> Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Rspamd-Queue-Id: 4cyZvx3v4Wz9tyC X-Original-Sender: me@real-or-random.org X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@real-or-random.org header.s=MBO0001 header.b=RWzgv9G6; spf=pass (google.com: domain of me@real-or-random.org designates 80.241.56.152 as permitted sender) smtp.mailfrom=me@real-or-random.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=real-or-random.org 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.8 (/) 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 for 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] 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+unsubscribe@googlegroups.com. > To view this discussion visit > 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/= 5c15c2c265c92d5527fe3da510ac76c2a6e8e0e4.camel%40real-or-random.org.