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 ) 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 ; 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 To: Bitcoin Development Mailing List Message-Id: <05cea2fb-45f1-4bbd-beda-96e20e67bb0en@googlegroups.com> In-Reply-To: <14874ca7-853c-4468-a357-a76759e50bben@googlegroups.com> References: <8a2c8743-dd0b-422c-85f9-f0350eec1162n@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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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 (G-7) 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.
Below snippet from the NIST forum:

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=

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

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=

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

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

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


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

On Thursday, May 29, 2025 at 4:45:35=E2=80=AFPM UTC-7= Q C wrote:
>>>=C2=A0=C2=A0If XMSS is too scary,
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

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


O= n Thursday, May 22, 2025 at 6:01:18=E2=80=AFAM UTC-7 Bas Westerbaan wrote:<= br>
On Wednesday, May 21, 2025 at 10:58:00=E2=80=AFPM UTC+2 Hunter Beast wrote= :
Thank you for this! It'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't want to sacrifice SLH-DSA because it'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.

At present, lattices ar= e the only viable approach to post-quantum key agreement in TLS. If come Q-= day they're broken, then it's not just Bitcoin that's in big tr= ouble. If you do want the certainty of hashes, you might want to consider X= MSS: that'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's at least a few hours apart, but not if you&#= 39;re using the same leaf twice in short succession.
= =C2=A0
Another concern regarding SLH-= DSA might be its performance, it'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...

= I assume you're talking about signature size? Falcon-512 requires fewer= cycles to verify than secp256k1. SLH-DSA'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.
=C2=A0
We'll = also be deprecating ML-DSA because it's too similar to FALCON in terms = of performance and size.

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's si= gning routine: it's quite complicated and tricky to implement securily,= especially if you want it to be fast. I don'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's quite a bit more complex.

Best,

=C2=A0Bas
=C2=A0
JPEG resistance and scaling= will need to be solved through separate means, perhaps with BitZip, which = is what I'm calling Ethan's proposal a couple weeks back for block-= wide transaction compression scaling PQC signatures through STARK proofs.

Will be making those changes to the BIP soon. Feedb= ack is always welcome!

On Wednesday, May 21= , 2025 at 5:20:02=E2=80=AFAM UTC-6 Bas Westerbaan wrote:

Hi all,


My colleague Ethan as= ked me the fun question which post-quantum signature schemes have the follo= wing security property, which he called jpeg resistance= .


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.


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.


The situation is more subtle for actual st= andardized hash-based signatures. RFC 8391 XMSS 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.


The situation is different again for RFC 8391 = XMSSMT. XMSSMT is basically a certificate chain of XMSS signatu= res. An XMSSMT public key is an XMSS public key. An XMSSMT signature is a chain of XMSS signature= s: the XMSSMT= 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= MT 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 XMSSMT with two subtrees is = only half jpeg resistant and it gets worse with more subtrees.

Sim= ilarly SLH-DSA (FIPS 205, n=C3=A9e SPHINCS+) 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.


ML-DSA (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 w1 =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 s1, where s1 is part of the private key. The verifier checks, among othe= r things, whether HighBits(Az-ct) =3D w1, where t =3D As1+s2 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 s1 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 s1 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.=


Falcon. A Falcon private key are small polynomi= als f,g. Its public key is h =3D g f-1. With the private key, for any polynomial c, we= can compute small s1<= /span> and s2= with s1 + = s2h =3D c. A = Falcon signature is a pair r, s2 where s1 =3D H(r, m) - s2 h is small. s2 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 s2 will likely yield a = sufficiently small s2<= /span>. Now, I thought about using this s2 as a new g and construct a signature that w= ay by finding s=E2=80=991 and s=E2=80=992 with s=E2=80=991 + s=E2=80=992s1= f-1<= /span> =3D H(r,m), but my brother suggested a simpler approach. s2 is likely invertible and= we can set h =3D H(r, m)/s2. 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.

Best,


=C2=A0Bas



--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/05cea2fb-45f1-4bbd-beda-96e20e67bb0en%40googlegroups.com.
------=_Part_321695_1062724607.1750182139002-- ------=_Part_321694_81375724.1750182139002--