path: root/2e/3e48e601f22d3110c249cfd2598e99748d0359

Delivery-date: Thu, 29 May 2025 16:45:43 -0700
Received: from mail-yb1-f189.google.com ([209.85.219.189])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDHJDC5244MRBG7D4PAQMGQEEK4XDAQ@googlegroups.com>)
	id 1uKmwP-0000T5-Tt
	for bitcoindev@gnusha.org; Thu, 29 May 2025 16:45:43 -0700
Received: by mail-yb1-f189.google.com with SMTP id 3f1490d57ef6-e7dabc0305dsf2188218276.2
        for <bitcoindev@gnusha.org>; Thu, 29 May 2025 16:45:41 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1748562336; x=1749167136; 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=6Swc/KavlkYZW8y69GNwnuadTNgh5ENbyLzmHnHEW0s=;
        b=lnbHyZE72hCsFTSFMvAE0B+TQz5g+BXHJCOgmBTyct91CJ4VbTmZIAlxtAwicuTrJi
         Or0JLTm7T4QM6DpmFNXvasDb9m2DGi8nD9VnZlz58X8qQa46Pt6qsSa+BGC0W3TGmckO
         d8MGS8kVGI0zvwWH28ZDOB1+L9SW9wWBDRPhoKRhRTAFMcN8uxhTpb9wkvUOlhOePKPi
         CaRWDD9CpbKK7Hdz5n9oGCxNVNz7WJPcjfySY3SjQUTi4igo6WVKtH7H01E7tL5hQqAW
         +2qEJ0PRbeIdD8YiaYh3NHqXVTDgEPARXtH1wKpGN3Kh5EzLMI2nNtJiLycltaSO3jk4
         7ywg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1748562336; x=1749167136; 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=6Swc/KavlkYZW8y69GNwnuadTNgh5ENbyLzmHnHEW0s=;
        b=U8hToM2bhWwOBUqTu59TfPGJHqusYNTZ9Y5JUn9kIHX+HgX8l00JXygD8mH+47OsrD
         a9zd5oQiA3dN5HNlMBugZyDhXCR90u2nGqLllStzKrq7jbtOU5gsTZGRZ2kB1TZG2lhk
         ZwTdbSk4/y1kmTVml5Mq12HaDqq3CVe3Fsf6KjJgFbNHLyv44qjMmf499XmJcqV+4tCw
         9RTkck5pu+3laus6GutyqvMn9Yh9QyeLooRuKcE6huiwjKu7GvotEjUzNd0lalrZy/5X
         7gjiWQbkVyQQlhdtbXUuPs9KjfjcLewvbxbd6Q81EsdJkwo7NESUKXs5qJRmmaODHXyk
         /dZQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1748562336; x=1749167136;
        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=6Swc/KavlkYZW8y69GNwnuadTNgh5ENbyLzmHnHEW0s=;
        b=Pl/kUFLELZEMKmO2oHcI6jrnqm3i2K0PYDRkyrZ48THJoW4MHMt/n7B6bx3TlG4xk2
         gB4fRilYM9aoj9Y/pYoJFMbxtbHTy0AORbReRCbHqQ9j4yPAldZVSSKys7UjY2BB7T2p
         m+TrxNRedzQkGeTM/Zkm+KKwk90kbjVIB+qu43+4tYtKsLwm57Qq9vXlakI4zSRIU2UN
         pOwAwvJddkomaZKmXg3c2NShZtMh2Ke7TXHwmZtWwUXen+VMnRBUe6SSVKGshsgOchaR
         LtjcmeLAeUoeh5kT+izWHSL09owTE/SuODEUFwX6/Krd4SADIbOnnh9slqVd8jBHEdKH
         vCSQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCXpzF9iHHM2+P3P4QeQdvFm1wO8hYwT/6Xxf6TIPtmziqAASDSYPk6emax0zCKfCLRraKQ6g33lmIXF@gnusha.org
X-Gm-Message-State: AOJu0YwCcxumXZNvBX2wwkB9X8pVofqjZa3d2a0NCdz43RzzF3/GE3Oq
	TwRRDtDnp4YWFjkuJYKgdR0VYe3SvRevBHMX3oyUYaDGMYaikBuxQjwo
X-Google-Smtp-Source: AGHT+IHQpwVeLkvNta72Te960Wl46TNaMny8wxi7i//KAu018uLG/lT3/EKy1D7tO/DHovaf4Vxxhg==
X-Received: by 2002:a05:6902:150b:b0:e7d:7264:6bc3 with SMTP id 3f1490d57ef6-e7f81ddf54emr2249643276.13.1748562335686;
        Thu, 29 May 2025 16:45:35 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZcO5xhrgJ4vEuHSvJxOsdsuztZDwFpOGmI4ncod+qGMVw==
Received: by 2002:a25:b288:0:b0:e7d:622d:9dd6 with SMTP id 3f1490d57ef6-e7f6f6a178fls1408873276.0.-pod-prod-06-us;
 Thu, 29 May 2025 16:45:30 -0700 (PDT)
X-Received: by 2002:a05:690c:4907:b0:6d4:4a0c:fcf0 with SMTP id 00721157ae682-71057cf454dmr2748377b3.20.1748562330701;
        Thu, 29 May 2025 16:45:30 -0700 (PDT)
Received: by 2002:a05:690c:6083:b0:70e:2cf8:9db8 with SMTP id 00721157ae682-70f980e43fams7b3;
        Thu, 29 May 2025 16:20:19 -0700 (PDT)
X-Received: by 2002:a05:690c:3507:b0:70f:8883:ce60 with SMTP id 00721157ae682-71057d235b9mr1922597b3.26.1748560818220;
        Thu, 29 May 2025 16:20:18 -0700 (PDT)
Date: Thu, 29 May 2025 16:20:17 -0700 (PDT)
From: Q C <dogeprotocol1@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <14874ca7-853c-4468-a357-a76759e50bben@googlegroups.com>
In-Reply-To: <e812604c-94a5-4f5f-87e8-71d178963d62n@googlegroups.com>
References: <CAMjbhoU=PCUwbhWFbqCbOdZc+ybmREJmmt1K1TuHrCTncKH6VA@mail.gmail.com>
 <8a2c8743-dd0b-422c-85f9-f0350eec1162n@googlegroups.com>
 <e812604c-94a5-4f5f-87e8-71d178963d62n@googlegroups.com>
Subject: [bitcoindev] Re: jpeg resistance of various post-quantum signature schemes
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_31338_2014820662.1748560817651"
X-Original-Sender: dogeprotocol1@gmail.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: 3.1 (+++)

------=_Part_31338_2014820662.1748560817651
Content-Type: multipart/alternative; 
	boundary="----=_Part_31339_1368722702.1748560817651"

------=_Part_31339_1368722702.1748560817651
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

 *>>>  If XMSS is too scary,*

Hi Bas, it is scary like you said; it is too risky to use XMSS in a=20
distributed system like Bitcoin, especially when there are a multitude of=
=20
developers/implementers/users worldwide who might not necessarily=20
understand the nuances of a stateful scheme.=20

At the cost of larger block payload sizes due to sig+pub key sizes, storage=
=20
size, ML-DSA sounds like the a good option.  As a safety hedge till quantum=
=20
computers capable of breaking classical cryptography become available, a=20
hybrid option with ML-DSA+ed25519 or FN-DSA+ed25519 seems a good bet (at=20
risk of higher complexity and implementation risk).=20


On Thursday, May 22, 2025 at 6:01:18=E2=80=AFAM UTC-7 Bas Westerbaan wrote:

> On Wednesday, May 21, 2025 at 10:58:00=E2=80=AFPM UTC+2 Hunter Beast wrot=
e:
>
> Thank you for this! It's definitely informing how we approach development=
=20
> of BIP-360. SLH-DSA is concering, in that 7/8 arbitrary data would make i=
t=20
> about on par with the de facto witness discount. I don't want to sacrific=
e=20
> SLH-DSA because it's favored due to hash-based signatures having more=20
> confidence due to not introducing as many novel security assumptions as a=
re=20
> introduced with lattice cryptography.
>
>
> At present, lattices are the only viable approach to post-quantum key=20
> agreement in TLS. If come Q-day they're broken, then it's not just Bitcoi=
n=20
> that's in big trouble. If you do want the certainty of hashes, you might=
=20
> want to consider XMSS: that's JPEG resistant. With parameters n=3D16, h=
=3D20,=20
> d=3D1, w=3D16 it has 32 byte public key and 880 byte signature can sign a=
=20
> million messages, and only requires 3,000 hashes for verification [1]=20
> (which can actually be reduced threefold.) The big downside is that if yo=
u=20
> use the same OTS leaf twice, probably anyone can forge another signature =
on=20
> that leaf. In this case you might make this mistake harder by keeping tra=
ck=20
> of the last leaf that was used for each public key. If you see a public k=
ey=20
> sign using the same leaf a second time, you simply ignore the second=20
> signature. This helps against an oopsie that's at least a few hours apart=
,=20
> but not if you're using the same leaf twice in short succession.
> =20
>
> Another concern regarding SLH-DSA might be its performance, it's an order=
=20
> of magnitude more costly to run than FALCON, which itself is an order of=
=20
> magnitude more costly to run than secp256k1 Schnorr...
>
>
> I assume you're talking about signature size? Falcon-512 requires fewer=
=20
> cycles to verify than secp256k1. SLH-DSA's verification is a bit slower.=
=20
> There is some flexibility: SLH-DSA today assumes that a signer will make=
=20
> 2^64 signatures. If you drop that to say one million, then you can get=20
> smaller parameters. You can also vary parameters to smoothly vary signatu=
re=20
> size, verification time, and signing time. There is some momentum between=
=20
> standardising new variants of SLH-DSA. See also this paper [2]. If XMSS i=
s=20
> too scary, you might want to consider a Bitcoin tailored variant of SLH-D=
SA.
> =20
>
> We'll also be deprecating ML-DSA because it's too similar to FALCON in=20
> terms of performance and size.
>
>
> Falcon has great signature size and verification performance. Its=20
> verification routine is also simple to implement. I do have to warn about=
=20
> it's signing routine: it's quite complicated and tricky to implement=20
> securily, especially if you want it to be fast. I don't think speed is=20
> critical here, so I would stay away from implementations that use=20
> floating-point accelerators. Another thing to note is that if lattice=20
> cryptanalysis improves, the first step above Falcon-512 is Falcon-1024. A=
=20
> Falcon-768 is possible (and used to be specified), but it's quite a bit=
=20
> more complex.
>
> Best,
>
>  Bas
> =20
>
> JPEG resistance and scaling will need to be solved through separate means=
,=20
> perhaps with BitZip, which is what I'm calling Ethan's proposal a couple=
=20
> weeks back for block-wide transaction compression scaling PQC signatures=
=20
> through STARK proofs.
>
> Will be making those changes to the BIP soon. Feedback is always welcome!
>
> On Wednesday, May 21, 2025 at 5:20:02=E2=80=AFAM UTC-6 Bas Westerbaan wro=
te:
>
> Hi all,
>
> My colleague Ethan asked me the fun question which post-quantum signature=
=20
> schemes have the following security property, which he called jpeg=20
> resistance.
>
> Attacker wins if for a (partially specified) signature and full message,=
=20
> they can find a completed signature and public key, such that the complet=
ed=20
> signature verifies under the public key.
>
> A naive hash-based signature is not jpeg resistant. Schoolbook Winternitz=
=20
> one-time signatures, forest-of-trees few-time signatures, and Merkle tree=
s=20
> all validate signatures (/authentication paths) by recomputing the public=
=20
> key (/Merkle tree root) from the signature and the message, and checking=
=20
> whether the recomputed public key matches the actual public key. That mea=
ns=20
> we can pick anything for the signature, and just set the public key to th=
e=20
> recomputed public key.
>
> The situation is more subtle for actual standardized hash-based=20
> signatures. RFC 8391 XMSS doesn=E2=80=99t sign the message itself, but fi=
rst=20
> hashes in (among others) the public key. Basically the best we can do for=
=20
> XMSS (except for setting the signature randomizer) is to guess the public=
=20
> key. Thus it=E2=80=99s pretty much jpeg resistant.
>
> The situation is different again for RFC 8391 XMSSMT. XMSSMT is basically=
=20
> a certificate chain of XMSS signatures. An XMSSMT public key is an XMSS=
=20
> public key. An XMSSMT signature is a chain of XMSS signatures: the XMSSMT=
=20
> public key signs another XMSS public key; which signs another public XMSS=
=20
> public key; =E2=80=A6; which signs the message. Again the top XMSSMT publ=
ic key=20
> is hashed into the message signed, but that only binds the first XMSS=20
> signature. We can=E2=80=99t mess with the first signature, but the other =
signatures=20
> we can choose freely, as those roots are not bound. Thus XMSSMT with two=
=20
> subtrees is only half jpeg resistant and it gets worse with more subtrees=
.
>
> Similarly SLH-DSA (FIPS 205, n=C3=A9e SPHINCS+) is a certificate chain of=
 (a=20
> variant of) XMSS signing another XMSS public key, which signs another XMS=
S=20
> public key, etc, which signs a FORS public key, which signs the final=20
> message. The SLH-DSA public key is the first XMSS public key. From the=20
> message and the public key it derives the FORS key pair (leaf) in the hyp=
er=20
> tree to use to sign, and the message to actually sign. This means we can=
=E2=80=99t=20
> mess with the first XMSS keypair. Thus to attack SLH-DSA we honestly=20
> generate the first XMSS keypair. Then given a message, we just pick the=
=20
> signature arbitrarily for all but the first XMSS signature. We run the=20
> verification routine to recompute the root to sign by the first XMSS=20
> keypair. Then we sign it honestly. It depends a bit on the parameters, bu=
t=20
> basically we get to pick roughly =E2=85=9E of the signature for free.
>
> ML-DSA (FIPS 204, n=C3=A9e Dilithium) is a Fiat=E2=80=93Shamir transform =
of a=20
> (module-)lattice identification scheme. In the identification scheme the=
=20
> prover picks a nonce y, and sends the commitment w1 =3D HighBits(A y) to=
=20
> the verifier, where A is a matrix that=E2=80=99s part of the public key a=
nd=20
> HighBits drops the lower bits (of the coefficients of the polynomials in=
=20
> the vector). The verifier responds with a challenge c, to which the prove=
r=20
> returns the response z =3D y + c s1, where s1 is part of the private key.=
=20
> The verifier checks, among other things, whether HighBits(Az-ct) =3D w1,=
=20
> where t =3D As1+s2 is part of the public key. As usual with Fiat=E2=80=93=
Shamir, in=20
> ML-DSA the challenge c is the hash of the commitment, message, and public=
=20
> key. The scheme has commitment recovery, so the signature itself consists=
=20
> of the response z and the challenge c. (There is also a hint h, but that=
=E2=80=99s=20
> small and we can ignore it.) If we set s1 to zero, then z=3Dy, which is=
=20
> free to choose. So we can freely choose z, which is by far the largest pa=
rt=20
> of the signature. Such a public key t is easy to detect, as it has small=
=20
> coefficients. Instead we can set s1 to zero on only a few components.=20
> That allows us to choose z arbitrarily for those components, still breaki=
ng=20
> jpeg resistance, while being hard to detect. There could well be other=20
> approaches here.
>
> Falcon. A Falcon private key are small polynomials f,g. Its public key is=
=20
> h =3D g f-1. With the private key, for any polynomial c, we can compute=
=20
> small s1 and s2 with s1 + s2h =3D c. A Falcon signature is a pair r, s2=
=20
> where s1 =3D H(r, m) - s2 h is small. s2 is Guassian distributed, and is=
=20
> encoded using an Elias=E2=80=93Fano approach. It=E2=80=99s then padded to=
 make signatures=20
> fixed-length. Clearly the randomizer r can be set arbitrarily, but it=E2=
=80=99s=20
> only 40 bytes. Putting arbitrary bytes in most of the encoding of s2 will=
=20
> likely yield a sufficiently small s2. Now, I thought about using this s2=
=20
> as a new g and construct a signature that way by finding s=E2=80=991 and =
s=E2=80=992 with=20
> s=E2=80=991 + s=E2=80=992s1f-1 =3D H(r,m), but my brother suggested a sim=
pler approach. s2=20
> is likely invertible and we can set h =3D H(r, m)/s2. Both approaches wou=
ld=20
> be thwarted by using H(H(h), r, m) instead of H(r, m). I do not know if=
=20
> there is still another attack.
>
> Best,
>
>  Bas
>
>
>
> [1] https://westerbaan.name/~bas/hashcalc/=20
> [2] https://eprint.iacr.org/2024/018.pdf
>

--=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/=
14874ca7-853c-4468-a357-a76759e50bben%40googlegroups.com.

------=_Part_31339_1368722702.1748560817651
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable



<i style=3D"color: rgba(0, 0, 0, 0.87); font-family: Roboto, RobotoDraft, H=
elvetica, Arial, sans-serif; font-size: 14px; font-variant-ligatures: norma=
l; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; tex=
t-align: start; text-indent: 0px; text-transform: none; word-spacing: 0px; =
white-space: normal; background-color: rgb(255, 255, 255); text-decoration-=
thickness: initial; text-decoration-style: initial; text-decoration-color: =
initial;">&gt;&gt;&gt;<span>=C2=A0</span>=C2=A0If XMSS is too scary,</i><br=
 style=3D"color: rgba(0, 0, 0, 0.87); font-family: Roboto, RobotoDraft, Hel=
vetica, Arial, sans-serif; font-size: 14px; font-style: normal; font-varian=
t-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-sp=
acing: normal; text-align: start; text-indent: 0px; text-transform: none; w=
ord-spacing: 0px; white-space: normal; background-color: rgb(255, 255, 255)=
; text-decoration-thickness: initial; text-decoration-style: initial; text-=
decoration-color: initial;" /><br style=3D"color: rgba(0, 0, 0, 0.87); font=
-family: Roboto, RobotoDraft, Helvetica, Arial, sans-serif; font-size: 14px=
; font-style: normal; font-variant-ligatures: normal; font-variant-caps: no=
rmal; font-weight: 400; letter-spacing: normal; text-align: start; text-ind=
ent: 0px; text-transform: none; word-spacing: 0px; white-space: normal; bac=
kground-color: rgb(255, 255, 255); text-decoration-thickness: initial; text=
-decoration-style: initial; text-decoration-color: initial;" /><span style=
=3D"color: rgba(0, 0, 0, 0.87); font-family: Roboto, RobotoDraft, Helvetica=
, Arial, sans-serif; font-size: 14px; font-style: normal; font-variant-liga=
tures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing:=
 normal; text-align: start; text-indent: 0px; text-transform: none; word-sp=
acing: 0px; white-space: normal; background-color: rgb(255, 255, 255); text=
-decoration-thickness: initial; text-decoration-style: initial; text-decora=
tion-color: initial; display: inline; float: none;">Hi Bas, it is scary lik=
e you said; it is too risky to use XMSS in a distributed system like Bitcoi=
n, especially when there are a multitude of developers/implementers/users w=
orldwide who might not necessarily understand the nuances of a stateful sch=
eme.=C2=A0</span><br style=3D"color: rgba(0, 0, 0, 0.87); font-family: Robo=
to, RobotoDraft, Helvetica, Arial, sans-serif; font-size: 14px; font-style:=
 normal; font-variant-ligatures: normal; font-variant-caps: normal; font-we=
ight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; tex=
t-transform: none; word-spacing: 0px; white-space: normal; background-color=
: rgb(255, 255, 255); text-decoration-thickness: initial; text-decoration-s=
tyle: initial; text-decoration-color: initial;" /><br style=3D"color: rgba(=
0, 0, 0, 0.87); font-family: Roboto, RobotoDraft, Helvetica, Arial, sans-se=
rif; font-size: 14px; font-style: normal; font-variant-ligatures: normal; f=
ont-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-al=
ign: start; text-indent: 0px; text-transform: none; word-spacing: 0px; whit=
e-space: normal; background-color: rgb(255, 255, 255); text-decoration-thic=
kness: initial; text-decoration-style: initial; text-decoration-color: init=
ial;" /><span style=3D"color: rgba(0, 0, 0, 0.87); font-family: Roboto, Rob=
otoDraft, Helvetica, Arial, sans-serif; font-size: 14px; font-style: normal=
; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 4=
00; letter-spacing: normal; text-align: start; text-indent: 0px; text-trans=
form: none; word-spacing: 0px; white-space: normal; background-color: rgb(2=
55, 255, 255); text-decoration-thickness: initial; text-decoration-style: i=
nitial; text-decoration-color: initial; display: inline; float: none;">At t=
he cost of larger block payload sizes due to sig+pub key sizes, storage siz=
e, ML-DSA sounds like the a good option.=C2=A0 As a safety hedge till quant=
um computers capable of breaking classical cryptography become available, a=
 hybrid option with ML-DSA+ed25519 or FN-DSA+ed25519 seems a good bet (at r=
isk of higher complexity and implementation risk).=C2=A0</span><br style=3D=
"color: rgba(0, 0, 0, 0.87); font-family: Roboto, RobotoDraft, Helvetica, A=
rial, sans-serif; font-size: 14px; font-style: normal; font-variant-ligatur=
es: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: no=
rmal; text-align: start; text-indent: 0px; text-transform: none; word-spaci=
ng: 0px; white-space: normal; background-color: rgb(255, 255, 255); text-de=
coration-thickness: initial; text-decoration-style: initial; text-decoratio=
n-color: initial;" />

<br /><br /><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_att=
r">On Thursday, May 22, 2025 at 6:01:18=E2=80=AFAM UTC-7 Bas Westerbaan wro=
te:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8e=
x; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div=
 dir=3D"auto">On Wednesday, May 21, 2025 at 10:58:00=E2=80=AFPM UTC+2 Hunte=
r Beast wrote:<br></div><blockquote style=3D"margin:0px 0px 0px 0.8ex;borde=
r-left:1px solid rgb(204,204,204);padding-left:1ex">Thank you for this! It&=
#39;s definitely informing how we approach development of BIP-360. SLH-DSA =
is concering, in that 7/8 arbitrary data would make it about on par with th=
e de facto witness discount. I don&#39;t want to sacrifice SLH-DSA because =
it&#39;s favored due to hash-based signatures having more confidence due to=
 not introducing as many novel security assumptions as are introduced with =
lattice cryptography.</blockquote><div><br></div></div><div><div>At present=
, lattices are the only viable approach to post-quantum key agreement in TL=
S. If come Q-day they&#39;re broken, then it&#39;s not just Bitcoin that&#3=
9;s in big trouble. If you do want the certainty of hashes, you might want =
to consider XMSS: that&#39;s JPEG resistant. With parameters n=3D16, h=3D20=
, d=3D1, w=3D16 it has 32 byte public key and 880 byte signature can sign a=
 million messages, and only requires 3,000 hashes for verification [1] (whi=
ch can actually be reduced threefold.) The big downside is that if you use =
the same OTS leaf twice, probably anyone can forge another signature on tha=
t leaf. In this case you might make this mistake harder by keeping track of=
 the last leaf that was used for each public key. If you see a public key s=
ign using the same leaf a second time, you simply ignore the second signatu=
re. This helps against an oopsie that&#39;s at least a few hours apart, but=
 not if you&#39;re using the same leaf twice in short succession.</div></di=
v><div><div>=C2=A0</div><blockquote style=3D"margin:0px 0px 0px 0.8ex;borde=
r-left:1px solid rgb(204,204,204);padding-left:1ex"><div>Another concern re=
garding SLH-DSA might be its performance, it&#39;s an order of magnitude mo=
re costly to run than FALCON, which itself is an order of magnitude more co=
stly to run than secp256k1 Schnorr...</div></blockquote><div><br></div></di=
v><div><div>I assume you&#39;re talking about signature size? Falcon-512 re=
quires fewer cycles to verify than secp256k1. SLH-DSA&#39;s verification is=
 a bit slower. There is some flexibility: SLH-DSA today assumes that a sign=
er will make 2^64 signatures. If you drop that to say one million, then you=
 can get smaller parameters. You can also vary parameters to smoothly vary =
signature size, verification time, and signing time. There is some momentum=
 between standardising new variants of SLH-DSA. See also this paper [2]. If=
 XMSS is too scary, you might want to consider a Bitcoin tailored variant o=
f SLH-DSA.</div></div><div><div>=C2=A0</div><blockquote style=3D"margin:0px=
 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><di=
v>We&#39;ll also be deprecating ML-DSA because it&#39;s too similar to FALC=
ON in terms of performance and size.</div></blockquote><div><br></div></div=
><div><div>Falcon has great signature size and verification performance. It=
s verification routine is also simple to implement. I do have to warn about=
 it&#39;s signing routine: it&#39;s quite complicated and tricky to impleme=
nt securily, especially if you want it to be fast. I don&#39;t think speed =
is critical here, so I would stay away from implementations that use floati=
ng-point accelerators. Another thing to note is that if lattice cryptanalys=
is improves, the first step above Falcon-512 is Falcon-1024. A Falcon-768 i=
s possible (and used to be specified), but it&#39;s quite a bit more comple=
x.</div><div><br></div><div>Best,</div><div><br></div><div>=C2=A0Bas</div><=
/div><div><div>=C2=A0</div><blockquote style=3D"margin:0px 0px 0px 0.8ex;bo=
rder-left:1px solid rgb(204,204,204);padding-left:1ex"><div>JPEG resistance=
 and scaling will need to be solved through separate means, perhaps with Bi=
tZip, which is what I&#39;m calling Ethan&#39;s proposal a couple weeks bac=
k for block-wide transaction compression scaling PQC signatures through STA=
RK proofs.</div><div><br></div><div>Will be making those changes to the BIP=
 soon. Feedback is always welcome!</div><br><div><div dir=3D"auto">On Wedne=
sday, May 21, 2025 at 5:20:02=E2=80=AFAM UTC-6 Bas Westerbaan wrote:<br></d=
iv><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(=
204,204,204);padding-left:1ex"><div dir=3D"ltr"><span><p dir=3D"ltr" style=
=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-=
size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:tr=
ansparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-v=
ariant-alternates:normal;vertical-align:baseline">Hi all,</span></p><br><p =
dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><sp=
an style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);ba=
ckground-color:transparent;font-variant-numeric:normal;font-variant-east-as=
ian:normal;font-variant-alternates:normal;vertical-align:baseline">My colle=
ague Ethan asked me the fun question which post-quantum signature schemes h=
ave the following security property, which he called </span><span style=3D"=
font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-col=
or:transparent;font-style:italic;font-variant-numeric:normal;font-variant-e=
ast-asian:normal;font-variant-alternates:normal;vertical-align:baseline">jp=
eg resistance</span><span style=3D"font-size:11pt;font-family:Arial,sans-se=
rif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:norm=
al;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-a=
lign:baseline">.</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;mar=
gin-left:36pt;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11=
pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpare=
nt;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-=
alternates:normal;vertical-align:baseline">Attacker wins if for a (partiall=
y specified) signature and full message, they can find a completed signatur=
e and public key, such that the completed signature verifies under the publ=
ic key.</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0=
pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-family:Arial,sans-=
serif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:no=
rmal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical=
-align:baseline">A naive hash-based signature is not jpeg resistant. School=
book Winternitz one-time signatures, forest-of-trees few-time signatures, a=
nd Merkle trees all validate signatures (/authentication paths) by recomput=
ing the public key (/Merkle tree root) from the signature and the message, =
and checking whether the recomputed public key matches the actual public ke=
y. That means we can pick anything for the signature, and just set the publ=
ic key to the recomputed public key.</span></p><br><p dir=3D"ltr" style=3D"=
line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size=
:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transp=
arent;font-variant-numeric:normal;font-variant-east-asian:normal;font-varia=
nt-alternates:normal;vertical-align:baseline">The situation is more subtle =
for actual standardized hash-based signatures. RFC 8391 </span><span style=
=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background=
-color:transparent;font-weight:700;font-variant-numeric:normal;font-variant=
-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline">=
XMSS</span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color=
:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-v=
ariant-east-asian:normal;font-variant-alternates:normal;vertical-align:base=
line"> doesn=E2=80=99t sign the message itself, but first hashes in (among =
others) the public key. Basically the best we can do for XMSS (except for s=
etting the signature randomizer) is to guess the public key. Thus it=E2=80=
=99s pretty much jpeg resistant.</span></p><br><p dir=3D"ltr" style=3D"line=
-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11p=
t;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparen=
t;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-a=
lternates:normal;vertical-align:baseline">The situation is different again =
for RFC 8391 </span><span style=3D"font-size:11pt;font-family:Arial,sans-se=
rif;color:rgb(0,0,0);background-color:transparent;font-weight:700;font-vari=
ant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:n=
ormal;vertical-align:baseline">XMSS</span><span style=3D"font-size:11pt;fon=
t-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;fon=
t-weight:700;font-variant-numeric:normal;font-variant-east-asian:normal;fon=
t-variant-alternates:normal;vertical-align:baseline"><span style=3D"font-si=
ze:0.6em;vertical-align:super">MT</span></span><span style=3D"font-size:11p=
t;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparen=
t;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-a=
lternates:normal;vertical-align:baseline">. XMSS</span><span style=3D"font-=
size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:tr=
ansparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-v=
ariant-alternates:normal;vertical-align:baseline"><span style=3D"font-size:=
0.6em;vertical-align:super">MT</span></span><span style=3D"font-size:11pt;f=
ont-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;f=
ont-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alte=
rnates:normal;vertical-align:baseline"> is basically a certificate chain of=
 XMSS signatures. An XMSS</span><span style=3D"font-size:11pt;font-family:A=
rial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-=
numeric:normal;font-variant-east-asian:normal;font-variant-alternates:norma=
l;vertical-align:baseline"><span style=3D"font-size:0.6em;vertical-align:su=
per">MT</span></span><span style=3D"font-size:11pt;font-family:Arial,sans-s=
erif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:nor=
mal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-=
align:baseline"> public key is an XMSS public key. An XMSS</span><span styl=
e=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);backgroun=
d-color:transparent;font-variant-numeric:normal;font-variant-east-asian:nor=
mal;font-variant-alternates:normal;vertical-align:baseline"><span style=3D"=
font-size:0.6em;vertical-align:super">MT</span></span><span style=3D"font-s=
ize:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:tra=
nsparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-va=
riant-alternates:normal;vertical-align:baseline"> signature is a chain of X=
MSS signatures: the XMSS</span><span style=3D"font-size:11pt;font-family:Ar=
ial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-n=
umeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal=
;vertical-align:baseline"><span style=3D"font-size:0.6em;vertical-align:sup=
er">MT</span></span><span style=3D"font-size:11pt;font-family:Arial,sans-se=
rif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:norm=
al;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-a=
lign:baseline"> public key signs another XMSS public key; which signs anoth=
er public XMSS public key; =E2=80=A6; which signs the message. Again the to=
p XMSS</span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;col=
or:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font=
-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:ba=
seline"><span style=3D"font-size:0.6em;vertical-align:super">MT</span></spa=
n><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,=
0);background-color:transparent;font-variant-numeric:normal;font-variant-ea=
st-asian:normal;font-variant-alternates:normal;vertical-align:baseline"> pu=
blic key is hashed into the message signed, but that only binds the first X=
MSS signature. We can=E2=80=99t mess with the first signature, but the othe=
r signatures we can choose freely, as those roots are not bound. Thus XMSS<=
/span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(=
0,0,0);background-color:transparent;font-variant-numeric:normal;font-varian=
t-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"=
><span style=3D"font-size:0.6em;vertical-align:super">MT</span></span><span=
 style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);back=
ground-color:transparent;font-variant-numeric:normal;font-variant-east-asia=
n:normal;font-variant-alternates:normal;vertical-align:baseline"> with two =
subtrees is only half jpeg resistant and it gets worse with more subtrees.<=
/span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margi=
n-bottom:0pt"><span style=3D"font-size:11pt;font-family:Arial,sans-serif;co=
lor:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;fon=
t-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:b=
aseline">Similarly </span><span style=3D"font-size:11pt;font-family:Arial,s=
ans-serif;color:rgb(0,0,0);background-color:transparent;font-weight:700;fon=
t-variant-numeric:normal;font-variant-east-asian:normal;font-variant-altern=
ates:normal;vertical-align:baseline">SLH-DSA</span><span style=3D"font-size=
:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transp=
arent;font-variant-numeric:normal;font-variant-east-asian:normal;font-varia=
nt-alternates:normal;vertical-align:baseline"> (FIPS 205, n=C3=A9e SPHINCS<=
/span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(=
0,0,0);background-color:transparent;font-variant-numeric:normal;font-varian=
t-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"=
><span style=3D"font-size:0.6em;vertical-align:super">+</span></span><span =
style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);backg=
round-color:transparent;font-variant-numeric:normal;font-variant-east-asian=
:normal;font-variant-alternates:normal;vertical-align:baseline">) is a cert=
ificate chain of (a variant of) XMSS signing another XMSS public key, which=
 signs another XMSS public key, etc, which signs a FORS public key, which s=
igns the final message. The SLH-DSA public key is the first XMSS public key=
. From the message and the public key it derives the FORS key pair (leaf) i=
n the hyper tree to use to sign, and the message to actually sign. This mea=
ns we can=E2=80=99t mess with the first XMSS keypair. Thus to attack SLH-DS=
A we honestly generate the first XMSS keypair. Then given a message, we jus=
t pick the signature arbitrarily for all but the first XMSS signature. We r=
un the verification routine to recompute the root to sign by the first XMSS=
 keypair. Then we sign it honestly. It depends a bit on the parameters, but=
 basically we get to pick roughly =E2=85=9E of the signature for free.</spa=
n></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margin-bo=
ttom:0pt"><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:=
rgb(0,0,0);background-color:transparent;font-weight:700;font-variant-numeri=
c:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vert=
ical-align:baseline">ML-DSA</span><span style=3D"font-size:11pt;font-family=
:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-varian=
t-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:nor=
mal;vertical-align:baseline"> (FIPS 204, n=C3=A9e Dilithium) is a Fiat=E2=
=80=93Shamir transform of a (module-)lattice identification scheme. In the =
identification scheme the prover picks a nonce y, and sends the commitment =
w</span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rg=
b(0,0,0);background-color:transparent;font-variant-numeric:normal;font-vari=
ant-east-asian:normal;font-variant-alternates:normal;vertical-align:baselin=
e"><span style=3D"font-size:0.6em;vertical-align:sub">1</span></span><span =
style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);backg=
round-color:transparent;font-variant-numeric:normal;font-variant-east-asian=
:normal;font-variant-alternates:normal;vertical-align:baseline"> =3D HighBi=
ts(A y) to the verifier, where A is a matrix that=E2=80=99s part of the pub=
lic key and HighBits drops the lower bits (of the coefficients of the polyn=
omials in the vector). The verifier responds with a challenge c, to which t=
he prover returns the response z =3D y + c s</span><span style=3D"font-size=
:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transp=
arent;font-variant-numeric:normal;font-variant-east-asian:normal;font-varia=
nt-alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6e=
m;vertical-align:sub">1</span></span><span style=3D"font-size:11pt;font-fam=
ily:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-var=
iant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:=
normal;vertical-align:baseline">, where s</span><span style=3D"font-size:11=
pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpare=
nt;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-=
alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;v=
ertical-align:sub">1</span></span><span style=3D"font-size:11pt;font-family=
:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-varian=
t-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:nor=
mal;vertical-align:baseline"> is part of the private key. The verifier chec=
ks, among other things, whether HighBits(Az-ct) =3D w</span><span style=3D"=
font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-col=
or:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;f=
ont-variant-alternates:normal;vertical-align:baseline"><span style=3D"font-=
size:0.6em;vertical-align:sub">1</span></span><span style=3D"font-size:11pt=
;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent=
;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-al=
ternates:normal;vertical-align:baseline">, where t =3D As</span><span style=
=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background=
-color:transparent;font-variant-numeric:normal;font-variant-east-asian:norm=
al;font-variant-alternates:normal;vertical-align:baseline"><span style=3D"f=
ont-size:0.6em;vertical-align:sub">1</span></span><span style=3D"font-size:=
11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpa=
rent;font-variant-numeric:normal;font-variant-east-asian:normal;font-varian=
t-alternates:normal;vertical-align:baseline">+s</span><span style=3D"font-s=
ize:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:tra=
nsparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-va=
riant-alternates:normal;vertical-align:baseline"><span style=3D"font-size:0=
.6em;vertical-align:sub">2</span></span><span style=3D"font-size:11pt;font-=
family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-=
variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternat=
es:normal;vertical-align:baseline"> is part of the public key. As usual wit=
h Fiat=E2=80=93Shamir, in ML-DSA the challenge c is the hash of the commitm=
ent, message, and public key. The scheme has commitment recovery, so the si=
gnature itself consists of the response z and the challenge c. (There is al=
so a hint h, but that=E2=80=99s small and we can ignore it.) If we set s</s=
pan><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,=
0,0);background-color:transparent;font-variant-numeric:normal;font-variant-=
east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"><=
span style=3D"font-size:0.6em;vertical-align:sub">1 </span></span><span sty=
le=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);backgrou=
nd-color:transparent;font-variant-numeric:normal;font-variant-east-asian:no=
rmal;font-variant-alternates:normal;vertical-align:baseline">to zero, then =
z=3Dy, which is free to choose. So we can freely choose z, which is by far =
the largest part of the signature. Such a public key t is easy to detect, a=
s it has small coefficients. Instead we can set s</span><span style=3D"font=
-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:t=
ransparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-=
variant-alternates:normal;vertical-align:baseline"><span style=3D"font-size=
:0.6em;vertical-align:sub">1</span></span><span style=3D"font-size:11pt;fon=
t-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;fon=
t-variant-numeric:normal;font-variant-east-asian:normal;font-variant-altern=
ates:normal;vertical-align:baseline"> to zero on only a few components. Tha=
t allows us to choose z arbitrarily for those components, still breaking jp=
eg resistance, while being hard to detect. There could well be other approa=
ches here.</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-to=
p:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-family:Arial,sa=
ns-serif;color:rgb(0,0,0);background-color:transparent;font-weight:700;font=
-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alterna=
tes:normal;vertical-align:baseline">Falcon</span><span style=3D"font-size:1=
1pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpar=
ent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant=
-alternates:normal;vertical-align:baseline">. A Falcon private key are smal=
l polynomials f,g. Its public key is h =3D g f</span><span style=3D"font-si=
ze:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:tran=
sparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-var=
iant-alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.=
6em;vertical-align:super">-1</span></span><span style=3D"font-size:11pt;fon=
t-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;fon=
t-variant-numeric:normal;font-variant-east-asian:normal;font-variant-altern=
ates:normal;vertical-align:baseline">. With the private key, for any polyno=
mial c, we can compute small s</span><span style=3D"font-size:11pt;font-fam=
ily:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-var=
iant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:=
normal;vertical-align:baseline"><span style=3D"font-size:0.6em;vertical-ali=
gn:sub">1</span></span><span style=3D"font-size:11pt;font-family:Arial,sans=
-serif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:n=
ormal;font-variant-east-asian:normal;font-variant-alternates:normal;vertica=
l-align:baseline"> and s</span><span style=3D"font-size:11pt;font-family:Ar=
ial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-n=
umeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal=
;vertical-align:baseline"><span style=3D"font-size:0.6em;vertical-align:sub=
">2</span></span><span style=3D"font-size:11pt;font-family:Arial,sans-serif=
;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;=
font-variant-east-asian:normal;font-variant-alternates:normal;vertical-alig=
n:baseline"> with s</span><span style=3D"font-size:11pt;font-family:Arial,s=
ans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-numeri=
c:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vert=
ical-align:baseline"><span style=3D"font-size:0.6em;vertical-align:sub">1</=
span></span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;colo=
r:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-=
variant-east-asian:normal;font-variant-alternates:normal;vertical-align:bas=
eline"> + s</span><span style=3D"font-size:11pt;font-family:Arial,sans-seri=
f;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal=
;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-ali=
gn:baseline"><span style=3D"font-size:0.6em;vertical-align:sub">2</span></s=
pan><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,=
0,0);background-color:transparent;font-variant-numeric:normal;font-variant-=
east-asian:normal;font-variant-alternates:normal;vertical-align:baseline">h=
 =3D c. A Falcon signature is a pair r, s</span><span style=3D"font-size:11=
pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpare=
nt;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-=
alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;v=
ertical-align:sub">2</span></span><span style=3D"font-size:11pt;font-family=
:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-varian=
t-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:nor=
mal;vertical-align:baseline"> where s</span><span style=3D"font-size:11pt;f=
ont-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;f=
ont-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alte=
rnates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;verti=
cal-align:sub">1</span></span><span style=3D"font-size:11pt;font-family:Ari=
al,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-nu=
meric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;=
vertical-align:baseline"> =3D H(r, m) - s</span><span style=3D"font-size:11=
pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpare=
nt;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-=
alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;v=
ertical-align:sub">2</span></span><span style=3D"font-size:11pt;font-family=
:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-varian=
t-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:nor=
mal;vertical-align:baseline"> h is small. s</span><span style=3D"font-size:=
11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpa=
rent;font-variant-numeric:normal;font-variant-east-asian:normal;font-varian=
t-alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em=
;vertical-align:sub">2</span></span><span style=3D"font-size:11pt;font-fami=
ly:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-vari=
ant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:n=
ormal;vertical-align:baseline"> is Guassian distributed, and is encoded usi=
ng an Elias=E2=80=93Fano approach. It=E2=80=99s then padded to make signatu=
res fixed-length. Clearly the randomizer r can be set arbitrarily, but it=
=E2=80=99s only 40 bytes. Putting arbitrary bytes in most of the encoding o=
f s</span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:=
rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-va=
riant-east-asian:normal;font-variant-alternates:normal;vertical-align:basel=
ine"><span style=3D"font-size:0.6em;vertical-align:sub">2</span></span><spa=
n style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);bac=
kground-color:transparent;font-variant-numeric:normal;font-variant-east-asi=
an:normal;font-variant-alternates:normal;vertical-align:baseline"> will lik=
ely yield a sufficiently small s</span><span style=3D"font-size:11pt;font-f=
amily:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-v=
ariant-numeric:normal;font-variant-east-asian:normal;font-variant-alternate=
s:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;vertical-a=
lign:sub">2</span></span><span style=3D"font-size:11pt;font-family:Arial,sa=
ns-serif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric=
:normal;font-variant-east-asian:normal;font-variant-alternates:normal;verti=
cal-align:baseline">. Now, I thought about using this s</span><span style=
=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background=
-color:transparent;font-variant-numeric:normal;font-variant-east-asian:norm=
al;font-variant-alternates:normal;vertical-align:baseline"><span style=3D"f=
ont-size:0.6em;vertical-align:sub">2</span></span><span style=3D"font-size:=
11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpa=
rent;font-variant-numeric:normal;font-variant-east-asian:normal;font-varian=
t-alternates:normal;vertical-align:baseline"> as a new g and construct a si=
gnature that way by finding s=E2=80=99</span><span style=3D"font-size:11pt;=
font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;=
font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alt=
ernates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;vert=
ical-align:sub">1</span></span><span style=3D"font-size:11pt;font-family:Ar=
ial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-n=
umeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal=
;vertical-align:baseline"> and s=E2=80=99</span><span style=3D"font-size:11=
pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpare=
nt;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-=
alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;v=
ertical-align:sub">2</span></span><span style=3D"font-size:11pt;font-family=
:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-varian=
t-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:nor=
mal;vertical-align:baseline"> with s=E2=80=99</span><span style=3D"font-siz=
e:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:trans=
parent;font-variant-numeric:normal;font-variant-east-asian:normal;font-vari=
ant-alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6=
em;vertical-align:sub">1</span></span><span style=3D"font-size:11pt;font-fa=
mily:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-va=
riant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates=
:normal;vertical-align:baseline"> + s=E2=80=99</span><span style=3D"font-si=
ze:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:tran=
sparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-var=
iant-alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.=
6em;vertical-align:sub">2</span></span><span style=3D"font-size:11pt;font-f=
amily:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-v=
ariant-numeric:normal;font-variant-east-asian:normal;font-variant-alternate=
s:normal;vertical-align:baseline">s</span><span style=3D"font-size:11pt;fon=
t-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;fon=
t-variant-numeric:normal;font-variant-east-asian:normal;font-variant-altern=
ates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;vertica=
l-align:sub">1</span></span><span style=3D"font-size:11pt;font-family:Arial=
,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-nume=
ric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;ve=
rtical-align:baseline">f</span><span style=3D"font-size:11pt;font-family:Ar=
ial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-n=
umeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal=
;vertical-align:baseline"><span style=3D"font-size:0.6em;vertical-align:sup=
er">-1</span></span><span style=3D"font-size:11pt;font-family:Arial,sans-se=
rif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:norm=
al;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-a=
lign:baseline"> =3D H(r,m), but my brother suggested a simpler approach. s<=
/span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(=
0,0,0);background-color:transparent;font-variant-numeric:normal;font-varian=
t-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"=
><span style=3D"font-size:0.6em;vertical-align:sub">2</span></span><span st=
yle=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);backgro=
und-color:transparent;font-variant-numeric:normal;font-variant-east-asian:n=
ormal;font-variant-alternates:normal;vertical-align:baseline"> is likely in=
vertible and we can set h =3D H(r, m)/s</span><span style=3D"font-size:11pt=
;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent=
;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-al=
ternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;ver=
tical-align:sub">2</span></span><span style=3D"font-size:11pt;font-family:A=
rial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-=
numeric:normal;font-variant-east-asian:normal;font-variant-alternates:norma=
l;vertical-align:baseline">. Both approaches would be thwarted by using H(H=
(h), r, m) instead of H(r, m). I do not know if there is still another atta=
ck.</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;m=
argin-bottom:0pt"><span style=3D"font-size:11pt;font-family:Arial,sans-seri=
f;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal=
;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-ali=
gn:baseline">Best,</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;m=
argin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-family:=
Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant=
-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:norm=
al;vertical-align:baseline">=C2=A0Bas</span></p></span></div></blockquote><=
/div></blockquote><div><br></div><div><br></div></div><div><div>[1]=C2=A0<a=
 href=3D"https://westerbaan.name/~bas/hashcalc/" target=3D"_blank" rel=3D"n=
ofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&amp;q=
=3Dhttps://westerbaan.name/~bas/hashcalc/&amp;source=3Dgmail&amp;ust=3D1748=
647163266000&amp;usg=3DAOvVaw3D5aR4eXDZy3GxBdLVojJn">https://westerbaan.nam=
e/~bas/hashcalc/</a>=C2=A0</div><div>[2]=C2=A0<a href=3D"https://eprint.iac=
r.org/2024/018.pdf" target=3D"_blank" rel=3D"nofollow" data-saferedirecturl=
=3D"https://www.google.com/url?hl=3Den&amp;q=3Dhttps://eprint.iacr.org/2024=
/018.pdf&amp;source=3Dgmail&amp;ust=3D1748647163266000&amp;usg=3DAOvVaw3TzC=
VcaWykEcdEJKYDKxqJ">https://eprint.iacr.org/2024/018.pdf</a></div></div></b=
lockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/14874ca7-853c-4468-a357-a76759e50bben%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/14874ca7-853c-4468-a357-a76759e50bben%40googlegroups.com</a>.<br />

------=_Part_31339_1368722702.1748560817651--

------=_Part_31338_2014820662.1748560817651--