From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Thu, 22 May 2025 06:01:26 -0700 Received: from mail-yb1-f192.google.com ([209.85.219.192]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uI5Y4-0002qe-Gs for bitcoindev@gnusha.org; Thu, 22 May 2025 06:01:26 -0700 Received: by mail-yb1-f192.google.com with SMTP id 3f1490d57ef6-e7b6bc95500sf9289097276.1 for ; Thu, 22 May 2025 06:01:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1747918878; x=1748523678; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to: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=dpMdW1nNNkVu9T7n9eBus9o68Ts3Vnfn7tgkBKHDho8=; b=e91T3H49fKF4sNB+w7LCmgrWENKBwd/EP0oludjESiverZbL0UZQlqU7wNELmsUfLW 9cYShbU++rLuwltnmDc5QCM5pIIhEV0gKS3VM01WYDkzvs5KHBh1EFPS2Lcod3WDNeaU oN0UdRp8dnyxP6vqBaGtTs0fjN926xtzIPYOhgO2idZTyqdhtH/zyFnqUNIqlFCSvJrK +8jj8XSfketjCFr7hgr7n/R7pTCa0Xd9ntTC+AG1R8i+gnv8VRHkBJNpqLKQH8He494H 9b0A2o3qFyzTSPTYP1Quxx0yFpqiUxNYHzEL890iwW9BeM9Kot8g+5qSzKqzp/0dmkkJ KOcQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1747918878; x=1748523678; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:x-original-sender :mime-version:subject:references:in-reply-to:message-id:to:from:date :x-beenthere:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=dpMdW1nNNkVu9T7n9eBus9o68Ts3Vnfn7tgkBKHDho8=; b=FN1Eet2wpUDtg3ocaRJuWC3iDq4JUqHvEpW4Uq5ne7SnC9zlMP9kTmW04I4pECjVyQ IvmM+D9o5deNFk82PZgg6CS7Uvo2m8WNT4bs7Po38N1iFb43owktPaqNOWgaciUa6UQi mHvPzKco/OavRcUPV/VX+zADSxThr096oJyUopy3vUi8R2gtPi13jILxEsXV9jGs+EJt 1ODQVuEuwHA/auGKqkPF+mppzOvKh3Y21r3D/lztPBJTSbqWaZgqF4OtIIK3bysO88Wo pU7WcQjlfU/2aEUZ60xT8GB9WXEtE1J4Xu2MnbE4ANdhlB6oX8mqN/0qgzPmke7t/VuO Xtcw== X-Forwarded-Encrypted: i=1; AJvYcCUwMj07zL2y6KE6+99dnRouj27xr/WbxmXutYmIzkcX89V5vtVDW9u0dCKFwc/sz0xi5BNfvI3E7yuu@gnusha.org X-Gm-Message-State: AOJu0Yw6CJW5p1yffOgisDszo7smNr8hMF9bjkNMwVE7h3HYKre4Hcxh 0PJ9OmuxqVGpPwyCuLg0dojx/L0hYhXbNmk7gYCyvK8FeWxhqG+8DX6N X-Google-Smtp-Source: AGHT+IFV10uZW2GdveXhw4kJGn5auucrYK52yVo/O172DeP+FOheOdNAGfGSxmfYYb+MuU5XfhXfuA== X-Received: by 2002:a05:6902:2d06:b0:e7d:6cd4:8540 with SMTP id 3f1490d57ef6-e7d6cd488ccmr3548850276.47.1747918877951; Thu, 22 May 2025 06:01:17 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBEHvS0qOwJUNRNS6UbQ/+PMt9OzJsXPq5F2WSunwZ+2rQ== Received: by 2002:a5b:912:0:b0:e7d:6a62:1e8a with SMTP id 3f1490d57ef6-e7d6a622575ls991559276.2.-pod-prod-09-us; Thu, 22 May 2025 06:01:13 -0700 (PDT) X-Received: by 2002:a05:690c:319:b0:6fd:4072:2c5b with SMTP id 00721157ae682-70ca7b88383mr338291427b3.24.1747918872945; Thu, 22 May 2025 06:01:12 -0700 (PDT) Received: by 2002:a81:c949:0:b0:6ef:590d:3213 with SMTP id 00721157ae682-70ca9c0bd38ms7b3; Thu, 22 May 2025 05:57:35 -0700 (PDT) X-Received: by 2002:a05:690c:b8e:b0:702:d85:59b5 with SMTP id 00721157ae682-70ca7bade9bmr345666177b3.33.1747918654113; Thu, 22 May 2025 05:57:34 -0700 (PDT) Date: Thu, 22 May 2025 05:57:33 -0700 (PDT) From: "'Bas Westerbaan' via Bitcoin Development Mailing List" To: Bitcoin Development Mailing List Message-Id: In-Reply-To: <8a2c8743-dd0b-422c-85f9-f0350eec1162n@googlegroups.com> References: <8a2c8743-dd0b-422c-85f9-f0350eec1162n@googlegroups.com> Subject: [bitcoindev] Re: jpeg resistance of various post-quantum signature schemes MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_222008_2078022066.1747918653500" X-Original-Sender: bas@cloudflare.com X-Original-From: Bas Westerbaan Reply-To: Bas Westerbaan 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: 2.6 (++) ------=_Part_222008_2078022066.1747918653500 Content-Type: multipart/alternative; boundary="----=_Part_222009_1304167791.1747918653500" ------=_Part_222009_1304167791.1747918653500 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Wednesday, May 21, 2025 at 10:58:00=E2=80=AFPM UTC+2 Hunter Beast wrote: 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 it= =20 about on par with the de facto witness discount. I don't want to sacrifice= =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 Bitcoin= =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=3D2= 0,=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 you= =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 track= =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 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 signature= =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 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 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 wrote= : 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 completed= =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 trees= =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 means= =20 we can pick anything for the signature, and just set the public key to the= =20 recomputed public key. The situation is more subtle for actual standardized hash-based signatures.= =20 RFC 8391 XMSS doesn=E2=80=99t sign the message itself, but first hashes in = (among=20 others) the public key. Basically the best we can do for XMSS (except for= =20 setting the signature randomizer) is to guess the public key. Thus it=E2=80= =99s=20 pretty much jpeg resistant. The situation is different again for RFC 8391 XMSSMT. XMSSMT is basically a= =20 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 public= key is=20 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 si= gnatures=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 XMSS= =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 hyper= =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, but= =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 th= e=20 verifier, where A is a matrix that=E2=80=99s part of the public key and Hig= hBits=20 drops the lower bits (of the coefficients of the polynomials in the=20 vector). The verifier responds with a challenge c, to which the prover=20 returns the response z =3D y + c s1, where s1 is part of the private key. T= he=20 verifier checks, among other things, whether HighBits(Az-ct) =3D w1, where = t=20 =3D As1+s2 is part of the public key. As usual with Fiat=E2=80=93Shamir, in= ML-DSA=20 the challenge c is the hash of the commitment, message, and public key. The= =20 scheme has commitment recovery, so the signature itself consists of the=20 response z and the challenge c. (There is also a hint h, but that=E2=80=99s= small=20 and we can ignore it.) If we set s1 to zero, then z=3Dy, which is free to= =20 choose. So we can freely choose z, which is by far the largest part of the= =20 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. That= =20 allows us to choose z arbitrarily for those components, still breaking jpeg= =20 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 h= =20 =3D g f-1. With the private key, for any polynomial c, we can compute small= s1=20 and s2 with s1 + s2h =3D c. A Falcon signature is a pair r, s2 where s1 =3D= =20 H(r, m) - s2 h is small. s2 is Guassian distributed, and is encoded using= =20 an Elias=E2=80=93Fano approach. It=E2=80=99s then padded to make signatures= fixed-length.=20 Clearly the randomizer r can be set arbitrarily, but it=E2=80=99s only 40 b= ytes.=20 Putting arbitrary bytes in most of the encoding of s2 will likely yield a= =20 sufficiently small s2. Now, I thought about using this s2 as a new g and=20 construct a signature that way by finding s=E2=80=991 and s=E2=80=992 with = s=E2=80=991 + s=E2=80=992s1f-1 =3D=20 H(r,m), but my brother suggested a simpler approach. s2 is likely=20 invertible and we can set h =3D H(r, m)/s2. Both approaches would be thwart= ed=20 by using H(H(h), r, m) instead of H(r, m). I do not know if there is still= =20 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/= e812604c-94a5-4f5f-87e8-71d178963d62n%40googlegroups.com. ------=_Part_222009_1304167791.1747918653500 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

On Wednesday, May 21, 2025 at 10:58:00= =E2=80=AFPM UTC+2 Hunter Beast wrote:
Thank you for this! It's definitely informing how we approach dev= elopment of BIP-360. SLH-DSA is concering, in that 7/8 arbitrary data would= make it about on par with the de facto witness discount. I don't want to s= acrifice SLH-DSA because it's favored due to hash-based signatures having m= ore confidence due to not introducing as many novel security assumptions as= are introduced with lattice cryptography.

At present, lattices are the only viable approach to post-quantum key agr= eement in TLS. If come Q-day they're broken, then it's not just Bitcoin tha= t's in big trouble. If you do want the certainty of hashes, you might want = to consider XMSS: that'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 mi= llion messages, and only requires 3,000 hashes for verification [1] (which = 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 that l= eaf. In this case you might make this mistake harder by keeping track of th= e last leaf 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 helps against an oopsie that's at least a few hours apart, but not if= you're using the same leaf twice in short succession.
=C2=A0
Another concern regarding SLH-DS= A might be its performance, it's an order of magnitude more costly to run t= han FALCON, which itself is an order of magnitude more costly to run than s= ecp256k1 Schnorr...

I assume you're= talking about signature size? Falcon-512 requires fewer cycles to verify t= han secp256k1. SLH-DSA's verification is a bit slower. There is some flexib= ility: SLH-DSA today assumes that a signer will make 2^64 signatures. If yo= u drop that to say one million, then you can get smaller parameters. You ca= n 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 of SLH-DSA.
=C2=A0
We'll also be deprecating ML-DSA bec= ause it's too similar to FALCON in terms of performance and size.

Falcon has great signature size and verifica= tion performance. Its verification routine is also simple to implement. I d= o have to warn about it's signing routine: it's quite complicated and trick= y to implement securily, especially if you want it to be fast. I don't thin= k speed is critical here, so I would stay away from implementations that us= e floating-point accelerators. Another thing to note is that if lattice cry= ptanalysis improves, the first step above Falcon-512 is Falcon-1024. A Falc= on-768 is possible (and used to be specified), but it's quite a bit more co= mplex.

Best,

=C2=A0Ba= s
=C2=A0
JPEG resis= tance and scaling will need to be solved through separate means, perhaps wi= th BitZip, which is what I'm calling Ethan's proposal a couple weeks back f= or block-wide transaction compression scaling PQC signatures through STARK = proofs.

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

On Wedn= esday, 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) signat= ure and full message, they can find a completed signature and public key, s= uch that the completed signature verifies under the public key.

<= br />

A naive hash-based signature is not jpeg resistant= . Schoolbook Winternitz one-time signatures, forest-of-trees few-time signa= tures, and Merkle trees all validate signatures (/authentication paths) by = recomputing the public key (/Merkle tree root) from the signature and the m= essage, and checking whether the recomputed public key matches the actual p= ublic 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 standardized hash-based signa= tures. RFC 8391 XMSS doesn=E2=80=99t sign the message itself, but first hashes in (among o= thers) the public key. Basically the best we can do for XMSS (except for se= tting the signature randomizer) is to guess the public key. Thus it=E2=80= =99s pretty much jpeg resistant.


The si= tuation is different again for RFC 8391 XMSSMT. XMSSMT is basically a certificate chain of XMSS signatures= . An XMSSMT public key is an XMSS public key= . An XMSSMT signature is a chain of XMSS sig= natures: the XMSSMT public key signs another= XMSS public key; which signs another public XMSS public key; =E2=80=A6; wh= ich signs the message. Again the top XMSSMT public key is hashed into the message signed, but that only binds the f= irst XMSS signature. We can=E2=80=99t mess with the first signature, but th= e 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.


Similarly SLH-DSA (FIPS 205, n=C3=A9e SPHINCS+) is= a certificate 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 signs the final message. The SLH-DSA public key is the first XMSS pub= lic key. From the message 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. T= his means we can=E2=80=99t mess with the first XMSS keypair. Thus to attack= SLH-DSA we honestly generate the first XMSS keypair. Then given a message,= we just pick the signature arbitrarily for all but the first XMSS signatur= e. We run the verification routine to recompute the root to sign by the fir= st XMSS keypair. Then we sign it honestly. It depends a bit on the paramete= rs, but basically we get to pick roughly =E2=85=9E of the signature for fre= e.


ML-DSA (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= 1 =3D HighBits(A y) to the verifier, where A is a matrix that=E2=80= =99s part of the public key and HighBits drops the lower bits (of the coeff= icients of the polynomials in the vector). The verifier responds with a cha= llenge c, to which the prover returns the response z =3D y + c s1, where s1 is part of the p= rivate key. The verifier checks, among other things, whether HighBits(Az-ct= ) =3D w1, where t =3D As<= span style=3D"font-size: 0.6em; vertical-align: sub;">1+s2 is part of the public key. As usua= l with Fiat=E2=80=93Shamir, in ML-DSA the challenge c is the hash of the co= mmitment, message, and public key. The scheme has commitment recovery, so t= he signature itself 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, which is free to choo= se. So we can freely choose z, which is by far the largest part of the sign= ature. Such a public key t is easy to detect, as it has small coefficients.= Instead we can set s1 to zero on only a few c= omponents. That allows us to choose z arbitrarily for those components, sti= ll breaking jpeg resistance, while being hard to detect. There could well b= e other approaches here.


Falcon. A Falcon private key are small polynomials= f,g. Its public key is h =3D g f-1. With th= e private key, for any polynomial c, we can compute small s1= and s2 with s1 + s2h =3D c. A Falcon signature i= s 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. Now, I thought about using this s2 as a new g and construct a signature that way by finding s=E2=80=99= 1 and s=E2=80=992= with s=E2=80=991 + s=E2=80=992= s1f-1 =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) instead of H(r, m). I do not know if there is still another attack= .


Best,


=C2=A0Bas

=

[1]=C2=A0https://westerbaan.name/~bas/has= hcalc/=C2=A0
[2]=C2=A0https://eprint.iacr.org/2024/018.pdf
<= /div>

--
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/e812604c-94a5-4f5f-87e8-71d178963d62n%40googlegroups.com.
------=_Part_222009_1304167791.1747918653500-- ------=_Part_222008_2078022066.1747918653500--