path: root/7c/acca4fe58766dc6ff57a35ea50bf773698f548

Delivery-date: Tue, 17 Jun 2025 11:58:03 -0700
Received: from mail-yw1-f190.google.com ([209.85.128.190])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDHJDC5244MRBL7VY3BAMGQEQMAF6LA@googlegroups.com>)
	id 1uRbVR-0005Mu-L0
	for bitcoindev@gnusha.org; Tue, 17 Jun 2025 11:58:03 -0700
Received: by mail-yw1-f190.google.com with SMTP id 00721157ae682-70e7d6fef9csf13244467b3.3
        for <bitcoindev@gnusha.org>; Tue, 17 Jun 2025 11:58:01 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1750186676; x=1750791476; 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=jYwDqIhzETvffD/BBwvuXYz+wUneBkH11pVZn0GKff4=;
        b=nhgkdpxsO9zGQg9WvPauOXzLXboTZ8Et3O46AezVd7US8uXoyEiSu0bJCNSCDj8O9C
         O8y+KXDq4cQOmJHRp73UdISsXP+31VDT2TMDXcdUM7tTfNIHgUTUdy/U0KZlWsuzzzw1
         EurYEE3qREWjb9gSSi/le8letuzRXSZtT+nGp+nao3Xasoz0OhzN3IsJxinukWY3GEzE
         i+L3QeHi+dtXkJ4l0NPdJ1/E4ZAu4YbT44H1nuZvT5OomYbydFEya5+DO22esN8r04YK
         d48LLX991B04N1XSwBjXWWHWjCIBfYHcN4WkqyFVDJipZZOOjyhj0DylvPqN53Co7qJa
         +Dlw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1750186676; x=1750791476; 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=jYwDqIhzETvffD/BBwvuXYz+wUneBkH11pVZn0GKff4=;
        b=dofewaXF2vquXKmlAQUcmzcp2fashb6DIAVUJ4aT4Jslmrn5knmaYsZj9E5ZvY3uZk
         RLcPoTSRNToBPFbH/IcOpinZpdzXQQKFNAHc3Y44YwBIs59tDRGnRnZMD/W2XWpGu5FC
         N06C9F9LzRCFZXdbosjupKQTem4i8zjQUniLcYZ/DX4q7nvCm1U7BEL897nza+5BuLOp
         SWkHH0k7vxHtospX9/V82wE7qCtTvm5vKkvoftU7b7GAf7Y66lRlD5xvcX7isV/+4+LL
         TNDH9pz6GxEryXwKUKqgpyx30QqK4dN/l3ZhZtFnyv4Jn4czlEjz09HVqV6STk5UuAXg
         WLIA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1750186676; x=1750791476;
        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=jYwDqIhzETvffD/BBwvuXYz+wUneBkH11pVZn0GKff4=;
        b=o8QjnIGNebuGdHHWi5g5mC8WsIZPV4+eGE+mUo13rHcH3lIGIwbdY997V5cxw+bukO
         V0w+W1rAp3slrmc5sowR/VTUY0BKPCYqFQgXWJPauGN79/x2h1RCOVsfSTCg6JRsHWYA
         XK8QohrH9L1gVp5mx92XWlT+FpRalUltSc9EbgTf5gjq2i1Wma0FSHHLaFfTYftsh7Be
         zgveb1WIVbNqLBbqCqiEcYwuxUgvQ9h/u5BwdADpBxuOlLymOKVFIpvU9V4z7Ef1A9G8
         l5/RTZNX8S0ARnfDQi4aPR6jYHh6oposEFYbHIb9z0CPheTpKg+siozn4qE0ujdDNX2f
         wnMQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCVGeeidl5tT2DUzQ10ItMhjfL8w9wRXDeWUVd5rS1iSJIPLXueqHPMhUWFfuF7gyMt9gc7KVP+pr9wy@gnusha.org
X-Gm-Message-State: AOJu0Yz9ly7QAgi1GoThH7sjTjvM/niAoIR8QPVxeoJTCzsJhatjexbx
	okxRit/s4hXQP0MuslAUc6jVw/hO1hCupfsEtRy1fhefJMDTMyhdZGOC
X-Google-Smtp-Source: AGHT+IFqRSvwF7dh1kp9DR3Y/9833+59MdNZCzYV4hPrI06qWohkIMpw9NHJaeCj7GkeipKCVxOhPA==
X-Received: by 2002:a05:6902:991:b0:e81:dd9d:d45c with SMTP id 3f1490d57ef6-e8266526e66mr2868523276.10.1750186675801;
        Tue, 17 Jun 2025 11:57:55 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZdRYbnC2xMEU+5YloLP2sVDwiYPqeI3HP15O8kOrIOk+w==
Received: by 2002:a25:d897:0:b0:e7d:cab1:1366 with SMTP id 3f1490d57ef6-e820daa0182ls5274442276.1.-pod-prod-08-us;
 Tue, 17 Jun 2025 11:57:51 -0700 (PDT)
X-Received: by 2002:a05:690c:28f:b0:70d:ffaf:48df with SMTP id 00721157ae682-71175383003mr213681457b3.3.1750186671298;
        Tue, 17 Jun 2025 11:57:51 -0700 (PDT)
Received: by 2002:a05:690c:340c:b0:6ef:590d:3213 with SMTP id 00721157ae682-712a53b9560ms7b3;
        Tue, 17 Jun 2025 10:42:20 -0700 (PDT)
X-Received: by 2002:a05:690c:6f86:b0:710:d81a:b345 with SMTP id 00721157ae682-7117544cfccmr194311367b3.29.1750182139591;
        Tue, 17 Jun 2025 10:42:19 -0700 (PDT)
Date: Tue, 17 Jun 2025 10:42:19 -0700 (PDT)
From: Q C <dogeprotocol1@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <05cea2fb-45f1-4bbd-beda-96e20e67bb0en@googlegroups.com>
In-Reply-To: <14874ca7-853c-4468-a357-a76759e50bben@googlegroups.com>
References: <CAMjbhoU=PCUwbhWFbqCbOdZc+ybmREJmmt1K1TuHrCTncKH6VA@mail.gmail.com>
 <8a2c8743-dd0b-422c-85f9-f0350eec1162n@googlegroups.com>
 <e812604c-94a5-4f5f-87e8-71d178963d62n@googlegroups.com>
 <14874ca7-853c-4468-a357-a76759e50bben@googlegroups.com>
Subject: [bitcoindev] Re: jpeg resistance of various post-quantum signature schemes
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_321694_81375724.1750182139002"
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_321694_81375724.1750182139002
Content-Type: multipart/alternative; 
	boundary="----=_Part_321695_1062724607.1750182139002"

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

Actually, one of the proposed parameter sets (*G-7*) for SLH-DSA (which is=
=20
currently in discussion at the NIST pqc forum) offers a good alternative to=
=20
ML-DSA (if lattice security is a concern). The pubKey+sig sizes are still=
=20
many tens of orders of magnitude larger than secp256k1 though.

Below snippet from the NIST forum:

Parameter Set      Limit       Sig Size         Verify      Overuse Safety

AAA-1                        20           3072                4767         =
=20
 1722

AAA-3                        20           3280                452         =
=20
    19

G-1                             30           3568                7085     =
=20
      205

G-7                             30           3888                736       =
=20
       22

G-8                             30           4000                743       =
=20
       53

G-7 (128-bit security, 2^30 signatures). 3888-byte signatures; 9% longer=20
signatures than G-1 (shortest candidate), but 9x faster signature=20
verification.=20

On Thursday, May 29, 2025 at 4:45:35=E2=80=AFPM UTC-7 Q C wrote:

> *>>>  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,=20
> storage size, ML-DSA sounds like the a good option.  As a safety hedge ti=
ll=20
> quantum computers capable of breaking classical cryptography become=20
> available, a hybrid option with ML-DSA+ed25519 or FN-DSA+ed25519 seems a=
=20
> good bet (at risk of higher complexity and implementation risk).=20
>
>
> On Thursday, May 22, 2025 at 6:01:18=E2=80=AFAM UTC-7 Bas Westerbaan wrot=
e:
>
>> On Wednesday, May 21, 2025 at 10:58:00=E2=80=AFPM UTC+2 Hunter Beast wro=
te:
>>
>> Thank you for this! It's definitely informing how we approach developmen=
t=20
>> of BIP-360. SLH-DSA is concering, in that 7/8 arbitrary data would make =
it=20
>> about on par with the de facto witness discount. I don't want to sacrifi=
ce=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 =
are=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 Bitco=
in=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 y=
ou=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 tr=
ack=20
>> of the last leaf that was used for each public key. If you see a public =
key=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 apar=
t,=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 orde=
r=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 signat=
ure=20
>> size, verification time, and signing time. There is some momentum betwee=
n=20
>> standardising new variants of SLH-DSA. See also this paper [2]. If XMSS =
is=20
>> too scary, you might want to consider a Bitcoin tailored variant of SLH-=
DSA.
>> =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 abou=
t=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=20
>> means, perhaps with BitZip, which is what I'm calling Ethan's proposal a=
=20
>> couple weeks back for block-wide transaction compression scaling PQC=20
>> signatures 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 wr=
ote:
>>
>> Hi all,
>>
>> My colleague Ethan asked me the fun question which post-quantum signatur=
e=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 comple=
ted=20
>> signature verifies under the public key.
>>
>> A naive hash-based signature is not jpeg resistant. Schoolbook Winternit=
z=20
>> one-time signatures, forest-of-trees few-time signatures, and Merkle tre=
es=20
>> all validate signatures (/authentication paths) by recomputing the publi=
c=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 me=
ans=20
>> we can pick anything for the signature, and just set the public key to t=
he=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 f=
irst=20
>> hashes in (among others) the public key. Basically the best we can do fo=
r=20
>> XMSS (except for setting the signature randomizer) is to guess the publi=
c=20
>> key. Thus it=E2=80=99s pretty much jpeg resistant.
>>
>> The situation is different again for RFC 8391 XMSSMT. XMSSMT is=20
>> basically a certificate chain of XMSS signatures. An XMSSMT public key=
=20
>> is an XMSS public key. An XMSSMT signature is a chain of XMSS=20
>> signatures: the XMSSMT public key signs another XMSS public key; which=
=20
>> signs another public XMSS public key; =E2=80=A6; which signs the message=
. Again the=20
>> top XMSSMT public key is hashed into the message signed, but that only=
=20
>> binds the first XMSS signature. We can=E2=80=99t mess with the first sig=
nature, but=20
>> the other signatures we can choose freely, as those roots are not bound.=
=20
>> Thus XMSSMT with two subtrees is only half jpeg resistant and it gets=20
>> worse with more subtrees.
>>
>> Similarly SLH-DSA (FIPS 205, n=C3=A9e SPHINCS+) is a certificate chain o=
f (a=20
>> variant of) XMSS signing another XMSS public key, which signs another XM=
SS=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 hy=
per=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, b=
ut=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 =
and=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 prov=
er=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=
=93Shamir,=20
>> in ML-DSA the challenge c is the hash of the commitment, message, and=20
>> public key. The scheme has commitment recovery, so the signature itself=
=20
>> consists of the response z and the challenge c. (There is also a hint h,=
=20
>> but that=E2=80=99s small and we can ignore it.) If we set s1 to zero, th=
en z=3Dy,=20
>> which is free to choose. So we can freely choose z, which is by far the=
=20
>> largest part of the signature. Such a public key t is easy to detect, as=
 it=20
>> has small coefficients. Instead we can set s1 to zero on only a few=20
>> components. That allows us to choose z arbitrarily for those components,=
=20
>> still breaking jpeg resistance, while being hard to detect. There could=
=20
>> well be other approaches here.
>>
>> Falcon. A Falcon private key are small polynomials f,g. Its public key=
=20
>> is h =3D g f-1. With the private key, for any polynomial c, we can compu=
te=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 t=
o 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=20
>> will likely yield a sufficiently small s2. Now, I thought about using=20
>> this s2 as a new g and construct a signature that way by finding s=E2=80=
=991 and=20
>> s=E2=80=992 with s=E2=80=991 + s=E2=80=992s1f-1 =3D H(r,m), but my broth=
er suggested a simpler=20
>> approach. s2 is likely invertible and we can set h =3D H(r, m)/s2. Both=
=20
>> approaches would be thwarted by using H(H(h), r, m) instead of H(r, m). =
I=20
>> do not know if 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/=
05cea2fb-45f1-4bbd-beda-96e20e67bb0en%40googlegroups.com.

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

Actually, one of the proposed parameter sets (<b>G-7</b>) for SLH-DSA (whic=
h is currently in discussion at the NIST pqc forum) offers a good alternati=
ve to ML-DSA (if lattice security is a concern). The pubKey+sig sizes are s=
till many tens of orders of magnitude larger than secp256k1 though.<br /><b=
r />Below snippet from the NIST forum:<p><span style=3D"font-size: 11pt;">P=
arameter Set=C2=A0 =C2=A0 =C2=A0 Limit=C2=A0 =C2=A0 =C2=A0 =C2=A0Sig Size=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Verify=C2=A0 =C2=A0 =C2=A0 Overuse Safety=
</span></p>
<p><span style=3D"font-size: 11pt;">AAA-1=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 20=C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A03072=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 4767=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A01722</span></p>
<p><span style=3D"font-size: 11pt;">AAA-3=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 20=C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A03280=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 452=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 19</span>=
</p>
<p><span style=3D"font-size: 11pt;">G-1=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0 30=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A03568=C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 7085=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 205</span></p>
<p><span style=3D"font-size: 11pt;">G-7=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 =
=C2=A030=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A03888=C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 736=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A022</span></p>
<p><span style=3D"font-size: 11pt;">G-8=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 =
=C2=A030=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A04000=C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 743=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A053</span></p><br /><span style=3D"color: rgb(0, 0, 0);"=
>G-7 (128-bit security, 2^30 signatures). 3888-byte=20
signatures; 9% longer signatures than G-1 (shortest candidate), but 9x=20
faster signature verification.=C2=A0</span><i><span style=3D"color: rgb(0, =
0, 0);"><br /></span></i><br /><div class=3D"gmail_quote"><div dir=3D"auto"=
 class=3D"gmail_attr">On Thursday, May 29, 2025 at 4:45:35=E2=80=AFPM UTC-7=
 Q C wrote:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 =
0 0 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

<i style=3D"color:rgba(0,0,0,0.87);font-family:Roboto,RobotoDraft,Helvetica=
,Arial,sans-serif;font-size:14px;font-variant-ligatures:normal;font-variant=
-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-in=
dent:0px;text-transform:none;word-spacing:0px;white-space:normal;background=
-color:rgb(255,255,255);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,Helvetica,A=
rial,sans-serif;font-size:14px;font-style:normal;font-variant-ligatures:nor=
mal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-ali=
gn:start;text-indent:0px;text-transform:none;word-spacing:0px;white-space:n=
ormal;background-color:rgb(255,255,255);text-decoration-style:initial;text-=
decoration-color:initial"><br style=3D"color:rgba(0,0,0,0.87);font-family:R=
oboto,RobotoDraft,Helvetica,Arial,sans-serif;font-size:14px;font-style:norm=
al;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;l=
etter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;w=
ord-spacing:0px;white-space:normal;background-color:rgb(255,255,255);text-d=
ecoration-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-ligatures:normal;font-varian=
t-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-i=
ndent:0px;text-transform:none;word-spacing:0px;white-space:normal;backgroun=
d-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-colo=
r:initial;display:inline;float:none">Hi Bas, it is scary like you said; it =
is too risky to use XMSS in a distributed system like Bitcoin, especially w=
hen there are a multitude of developers/implementers/users worldwide who mi=
ght not necessarily understand the nuances of a stateful scheme.=C2=A0</spa=
n><br style=3D"color:rgba(0,0,0,0.87);font-family:Roboto,RobotoDraft,Helvet=
ica,Arial,sans-serif;font-size:14px;font-style:normal;font-variant-ligature=
s:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;tex=
t-align:start;text-indent:0px;text-transform:none;word-spacing:0px;white-sp=
ace:normal;background-color:rgb(255,255,255);text-decoration-style:initial;=
text-decoration-color:initial"><br style=3D"color:rgba(0,0,0,0.87);font-fam=
ily:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;font-size:14px;font-style=
:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:=
400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:n=
one;word-spacing:0px;white-space:normal;background-color:rgb(255,255,255);t=
ext-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-ligatures:normal;font-v=
ariant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;t=
ext-indent:0px;text-transform:none;word-spacing:0px;white-space:normal;back=
ground-color:rgb(255,255,255);text-decoration-style:initial;text-decoration=
-color:initial;display:inline;float:none">At the cost of larger block paylo=
ad sizes due to sig+pub key sizes, storage size, ML-DSA sounds like the a g=
ood option.=C2=A0 As a safety hedge till quantum computers capable of break=
ing classical cryptography become available, a hybrid option with ML-DSA+ed=
25519 or FN-DSA+ed25519 seems a good bet (at risk of higher complexity and =
implementation risk).=C2=A0</span><br style=3D"color:rgba(0,0,0,0.87);font-=
family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;font-size:14px;font-st=
yle:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weig=
ht:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transfor=
m:none;word-spacing:0px;white-space:normal;background-color:rgb(255,255,255=
);text-decoration-style:initial;text-decoration-color:initial">

<br><br><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">O=
n Thursday, May 22, 2025 at 6:01:18=E2=80=AFAM UTC-7 Bas Westerbaan wrote:<=
br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 0.8ex;bord=
er-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 Hunter Beast wrote=
:<br></div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px so=
lid rgb(204,204,204);padding-left:1ex">Thank you for this! It&#39;s definit=
ely 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 the de facto wi=
tness discount. I don&#39;t want to sacrifice SLH-DSA because it&#39;s favo=
red due to hash-based signatures having more confidence due to not introduc=
ing as many novel security assumptions as are introduced with lattice crypt=
ography.</blockquote><div><br></div></div><div><div>At present, lattices ar=
e the only viable approach to post-quantum key agreement in TLS. If come Q-=
day they&#39;re broken, then it&#39;s not just Bitcoin that&#39;s in big tr=
ouble. If you do want the certainty of hashes, you might want to consider X=
MSS: that&#39;s JPEG resistant. With parameters n=3D16, h=3D20, d=3D1, w=3D=
16 it has 32 byte public key and 880 byte signature can sign a million mess=
ages, and only requires 3,000 hashes for verification [1] (which can actual=
ly be reduced threefold.) The big downside is that if you use the same OTS =
leaf twice, probably anyone can forge another signature on that leaf. In th=
is case you might make this mistake harder by keeping track of the last lea=
f that was used for each public key. If you see a public key sign using the=
 same leaf a second time, you simply ignore the second signature. This help=
s 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></div><div><div>=
=C2=A0</div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px s=
olid rgb(204,204,204);padding-left:1ex"><div>Another concern regarding SLH-=
DSA might be its performance, it&#39;s an order of magnitude more costly to=
 run than FALCON, which itself is an order of magnitude more costly to run =
than secp256k1 Schnorr...</div></blockquote><div><br></div></div><div><div>=
I assume you&#39;re talking about signature size? Falcon-512 requires fewer=
 cycles to verify than secp256k1. SLH-DSA&#39;s verification is a bit slowe=
r. There is some flexibility: SLH-DSA today assumes that a signer will make=
 2^64 signatures. If you drop that to say one million, then you can get sma=
ller parameters. You can also vary parameters to smoothly vary signature si=
ze, verification time, and signing time. There is some momentum between sta=
ndardising new variants of SLH-DSA. See also this paper [2]. If XMSS is too=
 scary, you might want to consider a Bitcoin tailored variant of SLH-DSA.</=
div></div><div><div>=C2=A0</div><blockquote style=3D"margin:0px 0px 0px 0.8=
ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>We&#39;ll =
also be deprecating ML-DSA because it&#39;s too similar to FALCON in terms =
of performance and size.</div></blockquote><div><br></div></div><div><div>F=
alcon has great signature size and verification performance. Its verificati=
on routine is also simple to implement. I do have to warn about it&#39;s si=
gning routine: it&#39;s quite complicated and tricky to implement 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 floating-point acc=
elerators. Another thing to note is that if lattice cryptanalysis improves,=
 the first step above Falcon-512 is Falcon-1024. A Falcon-768 is possible (=
and used to be specified), but it&#39;s quite a bit more complex.</div><div=
><br></div><div>Best,</div><div><br></div><div>=C2=A0Bas</div></div><div><d=
iv>=C2=A0</div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1p=
x solid rgb(204,204,204);padding-left:1ex"><div>JPEG resistance and scaling=
 will need to be solved through separate means, perhaps with BitZip, which =
is what I&#39;m calling Ethan&#39;s proposal a couple weeks back for block-=
wide transaction compression scaling PQC signatures through STARK proofs.</=
div><div><br></div><div>Will be making those changes to the BIP soon. Feedb=
ack is always welcome!</div><br><div><div dir=3D"auto">On Wednesday, May 21=
, 2025 at 5:20:02=E2=80=AFAM UTC-6 Bas Westerbaan wrote:<br></div><blockquo=
te 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-heig=
ht:1.38;margin-top:0pt;margin-bottom:0pt"><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">Hi all,</span></p><br><p dir=3D"ltr" s=
tyle=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"f=
ont-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-colo=
r:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;fo=
nt-variant-alternates:normal;vertical-align:baseline">My colleague Ethan as=
ked me the fun question which post-quantum signature schemes have the follo=
wing security property, which he called </span><span style=3D"font-size:11p=
t;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparen=
t;font-style:italic;font-variant-numeric:normal;font-variant-east-asian:nor=
mal;font-variant-alternates:normal;vertical-align:baseline">jpeg resistance=
</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-varia=
nt-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline=
">.</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-left:36pt=
;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-famil=
y:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-varia=
nt-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:no=
rmal;vertical-align:baseline">Attacker wins if for a (partially specified) =
signature and full message, they can find a completed signature and public =
key, such that the completed signature verifies under the public key.</span=
></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margin-bot=
tom:0pt"><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:r=
gb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-var=
iant-east-asian:normal;font-variant-alternates:normal;vertical-align:baseli=
ne">A naive hash-based signature is not jpeg resistant. Schoolbook Winterni=
tz one-time signatures, forest-of-trees few-time signatures, and Merkle tre=
es all validate signatures (/authentication paths) by recomputing the publi=
c key (/Merkle tree root) from the signature and the message, and checking =
whether the recomputed public key matches the actual public key. That means=
 we can pick anything for the signature, and just set the public 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-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">The situation is more subtle for actual st=
andardized hash-based signatures. RFC 8391 </span><span style=3D"font-size:=
11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpa=
rent;font-weight:700;font-variant-numeric:normal;font-variant-east-asian:no=
rmal;font-variant-alternates:normal;vertical-align:baseline">XMSS</span><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"> 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 setting the s=
ignature randomizer) is to guess the public key. Thus it=E2=80=99s pretty m=
uch 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: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">The situation is different again for 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:n=
ormal;font-variant-east-asian:normal;font-variant-alternates:normal;vertica=
l-align:baseline">XMSS</span><span style=3D"font-size:11pt;font-family:Aria=
l,sans-serif;color:rgb(0,0,0);background-color:transparent;font-weight:700;=
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:super">MT</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">. XMSS</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:super">MT</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"> is basically a certificate chain of XMSS signatu=
res. An XMSS</span><span style=3D"font-size:11pt;font-family:Arial,sans-ser=
if;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:norma=
l;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-al=
ign: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: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"> public key is an XMSS public key. An XMSS</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:super">MT</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-alterna=
tes:normal;vertical-align:baseline"> signature is a chain of XMSS signature=
s: the XMSS</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:super">MT</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-varia=
nt-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline=
"> public key signs another XMSS public key; which signs another public XMS=
S public key; =E2=80=A6; which signs the message. Again the top 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-variant-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);background=
-color:transparent;font-variant-numeric:normal;font-variant-east-asian:norm=
al;font-variant-alternates:normal;vertical-align:baseline"> public key is h=
ashed into the message signed, but that only binds the first XMSS signature=
. We can=E2=80=99t mess with the first signature, but the other signatures =
we can choose freely, as those roots are not bound. Thus XMSS</span><span s=
tyle=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);backgr=
ound-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:super">MT</span></span><span style=3D"fo=
nt-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color=
:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;fon=
t-variant-alternates:normal;vertical-align:baseline"> with two subtrees is =
only half jpeg resistant and it gets worse with more subtrees.</span></p><b=
r><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:transparent;font-variant-numeric:normal;font-variant-ea=
st-asian:normal;font-variant-alternates:normal;vertical-align:baseline">Sim=
ilarly </span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;co=
lor:rgb(0,0,0);background-color:transparent;font-weight:700;font-variant-nu=
meric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;=
vertical-align:baseline">SLH-DSA</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"> (FIPS 205, n=C3=A9e SPHINCS</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"><span style=
=3D"font-size:0.6em;vertical-align:super">+</span></span><span style=3D"fon=
t-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">) is a certificate chai=
n of (a variant of) XMSS signing another XMSS public key, which signs anoth=
er XMSS public key, etc, which signs a FORS public key, which signs the fin=
al message. The SLH-DSA public key is the first XMSS public key. From the m=
essage and the public key it derives the FORS key pair (leaf) in the hyper =
tree to use to sign, and the message to actually sign. This means we can=E2=
=80=99t mess with the first XMSS keypair. Thus to attack SLH-DSA we honestl=
y generate the first XMSS keypair. Then given a message, we just pick the s=
ignature arbitrarily for all but the first XMSS signature. We run the verif=
ication routine to recompute the root to sign by the first XMSS keypair. Th=
en we sign it honestly. It depends a bit on the parameters, but basically w=
e get to pick roughly =E2=85=9E of the signature for free.</span></p><br><p=
 dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><s=
pan style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);b=
ackground-color:transparent;font-weight:700;font-variant-numeric:normal;fon=
t-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:b=
aseline">ML-DSA</span><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"> (FIPS 204, n=C3=A9e Dilithium) is a Fiat=E2=80=93Shamir t=
ransform 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:rgb(0,0,0);backg=
round-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 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"> =3D HighBits(A y) to the=
 verifier, where A is a matrix that=E2=80=99s part of the public key and Hi=
ghBits drops the lower bits (of the coefficients of the polynomials in the =
vector). The verifier responds with a challenge c, to which the prover retu=
rns the response z =3D y + c 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">, where s</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"><span style=3D"font-size:0.6em;vertical-align:=
sub">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"> is part of the private key. The verifier checks, among othe=
r 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-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">1</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">, where t =3D As</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">1</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">+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-alternat=
es: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,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"> is part of the public key. As usual with Fiat=E2=80=
=93Shamir, in ML-DSA the challenge c is the hash of the commitment, message=
, and public key. The scheme has commitment recovery, so the signature itse=
lf consists of the response z and the challenge c. (There is also a hint h,=
 but that=E2=80=99s small and we can ignore it.) If we set s</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"><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:t=
ransparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-=
variant-alternates:normal;vertical-align:baseline">to zero, then z=3Dy, whi=
ch is free to choose. So we can freely choose z, which is by far the larges=
t part of the signature. Such a public key t is easy to detect, as it has s=
mall 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: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">1</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"> to zero on only a few components. That allows u=
s to choose z arbitrarily for those components, still breaking jpeg resista=
nce, while being hard to detect. There could well be other approaches here.=
</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;marg=
in-bottom:0pt"><span style=3D"font-size:11pt;font-family:Arial,sans-serif;c=
olor:rgb(0,0,0);background-color:transparent;font-weight:700;font-variant-n=
umeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal=
;vertical-align:baseline">Falcon</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">. A Falcon private key are small polynomi=
als f,g. Its public key is h =3D g f</span><span style=3D"font-size:11pt;fo=
nt-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;fo=
nt-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alter=
nates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;vertic=
al-align:super">-1</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">. With the private key, for any polynomial c, we=
 can compute small s</span><span style=3D"font-size:11pt;font-family:Arial,=
sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-numer=
ic:normal;font-variant-east-asian:normal;font-variant-alternates:normal;ver=
tical-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;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"> and s</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"><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-varia=
nt-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline=
"> with 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;f=
ont-variant-east-asian:normal;font-variant-alternates:normal;vertical-align=
:baseline"><span style=3D"font-size:0.6em;vertical-align:sub">1</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"> + =
s</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">2</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">h =3D c. A =
Falcon signature is a pair r, s</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"><span style=3D"font-size:0.6em;vertical-al=
ign:sub">2</span></span><span style=3D"font-size:11pt;font-family:Arial,san=
s-serif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:=
normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertic=
al-align:baseline"> where s</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"><span style=3D"font-size:0.6em;vertical-align:=
sub">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) - s</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"><span style=3D"font-size:0.6em;vertical-al=
ign:sub">2</span></span><span style=3D"font-size:11pt;font-family:Arial,san=
s-serif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:=
normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertic=
al-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:transparent;font-=
variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternat=
es: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,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"> is Guassian distributed, and is encoded using an Elia=
s=E2=80=93Fano approach. It=E2=80=99s then padded to make signatures fixed-=
length. Clearly the randomizer r can be set arbitrarily, but it=E2=80=99s o=
nly 40 bytes. Putting arbitrary bytes in most of the encoding of s</span><s=
pan style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);b=
ackground-color:transparent;font-variant-numeric:normal;font-variant-east-a=
sian:normal;font-variant-alternates:normal;vertical-align:baseline"><span s=
tyle=3D"font-size:0.6em;vertical-align:sub">2</span></span><span style=3D"f=
ont-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-colo=
r:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;fo=
nt-variant-alternates:normal;vertical-align:baseline"> will likely yield a =
sufficiently small s</span><span style=3D"font-size:11pt;font-family:Arial,=
sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-numer=
ic:normal;font-variant-east-asian:normal;font-variant-alternates:normal;ver=
tical-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;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">. 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: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"> as a new g and construct a signature that w=
ay by finding s=E2=80=99</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=
">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-alternates:normal;vertical-alig=
n:baseline"> and 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-varian=
t-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:nor=
mal;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-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"> with s=E2=80=99</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"><span style=3D"font-size:0.6em;vertical-al=
ign:sub">1</span></span><span style=3D"font-size:11pt;font-family:Arial,san=
s-serif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:=
normal;font-variant-east-asian:normal;font-variant-alternates:normal;vertic=
al-align:baseline"> + s=E2=80=99</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">s</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"><span style=3D"font-size:0.6em;vertical-align:sub">1=
</span></span><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">f</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"><span style=3D"font-size:0.6em;vertical-align:super">-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-varian=
t-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"=
> =3D H(r,m), but my brother suggested a simpler approach. s</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"><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:tr=
ansparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-v=
ariant-alternates:normal;vertical-align:baseline"> is likely invertible 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-varian=
t-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:nor=
mal;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-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">. Both approaches would be thwarted by using H(H(h), r, m) i=
nstead of H(r, m). I do not know if there is still another attack.</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:transparent;font-variant-numeric:normal;font-varian=
t-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"=
>Best,</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0p=
t;margin-bottom:0pt"><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">=C2=A0Bas</span></p></span></div></blockquote></div></block=
quote><div><br></div><div><br></div></div><div><div>[1]=C2=A0<a href=3D"htt=
ps://westerbaan.name/~bas/hashcalc/" rel=3D"nofollow" target=3D"_blank" dat=
a-saferedirecturl=3D"https://www.google.com/url?hl=3Den&amp;q=3Dhttps://wes=
terbaan.name/~bas/hashcalc/&amp;source=3Dgmail&amp;ust=3D1750268203431000&a=
mp;usg=3DAOvVaw0SZuCW_dCeJU9CsCKxCyI2">https://westerbaan.name/~bas/hashcal=
c/</a>=C2=A0</div><div>[2]=C2=A0<a href=3D"https://eprint.iacr.org/2024/018=
.pdf" rel=3D"nofollow" target=3D"_blank" data-saferedirecturl=3D"https://ww=
w.google.com/url?hl=3Den&amp;q=3Dhttps://eprint.iacr.org/2024/018.pdf&amp;s=
ource=3Dgmail&amp;ust=3D1750268203431000&amp;usg=3DAOvVaw39DLwzWYAcWs2zILu5=
ORSO">https://eprint.iacr.org/2024/018.pdf</a></div></div></blockquote></di=
v></blockquote></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/05cea2fb-45f1-4bbd-beda-96e20e67bb0en%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/05cea2fb-45f1-4bbd-beda-96e20e67bb0en%40googlegroups.com</a>.<br />

------=_Part_321695_1062724607.1750182139002--

------=_Part_321694_81375724.1750182139002--