Delivery-date: Thu, 29 May 2025 16:45:43 -0700 Received: from mail-yb1-f189.google.com ([209.85.219.189]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uKmwP-0000T5-Tt for bitcoindev@gnusha.org; Thu, 29 May 2025 16:45:43 -0700 Received: by mail-yb1-f189.google.com with SMTP id 3f1490d57ef6-e7dabc0305dsf2188218276.2 for ; Thu, 29 May 2025 16:45:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1748562336; x=1749167136; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=6Swc/KavlkYZW8y69GNwnuadTNgh5ENbyLzmHnHEW0s=; b=lnbHyZE72hCsFTSFMvAE0B+TQz5g+BXHJCOgmBTyct91CJ4VbTmZIAlxtAwicuTrJi Or0JLTm7T4QM6DpmFNXvasDb9m2DGi8nD9VnZlz58X8qQa46Pt6qsSa+BGC0W3TGmckO d8MGS8kVGI0zvwWH28ZDOB1+L9SW9wWBDRPhoKRhRTAFMcN8uxhTpb9wkvUOlhOePKPi CaRWDD9CpbKK7Hdz5n9oGCxNVNz7WJPcjfySY3SjQUTi4igo6WVKtH7H01E7tL5hQqAW +2qEJ0PRbeIdD8YiaYh3NHqXVTDgEPARXtH1wKpGN3Kh5EzLMI2nNtJiLycltaSO3jk4 7ywg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1748562336; x=1749167136; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=6Swc/KavlkYZW8y69GNwnuadTNgh5ENbyLzmHnHEW0s=; b=U8hToM2bhWwOBUqTu59TfPGJHqusYNTZ9Y5JUn9kIHX+HgX8l00JXygD8mH+47OsrD a9zd5oQiA3dN5HNlMBugZyDhXCR90u2nGqLllStzKrq7jbtOU5gsTZGRZ2kB1TZG2lhk ZwTdbSk4/y1kmTVml5Mq12HaDqq3CVe3Fsf6KjJgFbNHLyv44qjMmf499XmJcqV+4tCw 9RTkck5pu+3laus6GutyqvMn9Yh9QyeLooRuKcE6huiwjKu7GvotEjUzNd0lalrZy/5X 7gjiWQbkVyQQlhdtbXUuPs9KjfjcLewvbxbd6Q81EsdJkwo7NESUKXs5qJRmmaODHXyk /dZQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1748562336; x=1749167136; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=6Swc/KavlkYZW8y69GNwnuadTNgh5ENbyLzmHnHEW0s=; b=Pl/kUFLELZEMKmO2oHcI6jrnqm3i2K0PYDRkyrZ48THJoW4MHMt/n7B6bx3TlG4xk2 gB4fRilYM9aoj9Y/pYoJFMbxtbHTy0AORbReRCbHqQ9j4yPAldZVSSKys7UjY2BB7T2p m+TrxNRedzQkGeTM/Zkm+KKwk90kbjVIB+qu43+4tYtKsLwm57Qq9vXlakI4zSRIU2UN pOwAwvJddkomaZKmXg3c2NShZtMh2Ke7TXHwmZtWwUXen+VMnRBUe6SSVKGshsgOchaR LtjcmeLAeUoeh5kT+izWHSL09owTE/SuODEUFwX6/Krd4SADIbOnnh9slqVd8jBHEdKH vCSQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCXpzF9iHHM2+P3P4QeQdvFm1wO8hYwT/6Xxf6TIPtmziqAASDSYPk6emax0zCKfCLRraKQ6g33lmIXF@gnusha.org X-Gm-Message-State: AOJu0YwCcxumXZNvBX2wwkB9X8pVofqjZa3d2a0NCdz43RzzF3/GE3Oq TwRRDtDnp4YWFjkuJYKgdR0VYe3SvRevBHMX3oyUYaDGMYaikBuxQjwo X-Google-Smtp-Source: AGHT+IHQpwVeLkvNta72Te960Wl46TNaMny8wxi7i//KAu018uLG/lT3/EKy1D7tO/DHovaf4Vxxhg== X-Received: by 2002:a05:6902:150b:b0:e7d:7264:6bc3 with SMTP id 3f1490d57ef6-e7f81ddf54emr2249643276.13.1748562335686; Thu, 29 May 2025 16:45:35 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZcO5xhrgJ4vEuHSvJxOsdsuztZDwFpOGmI4ncod+qGMVw== Received: by 2002:a25:b288:0:b0:e7d:622d:9dd6 with SMTP id 3f1490d57ef6-e7f6f6a178fls1408873276.0.-pod-prod-06-us; Thu, 29 May 2025 16:45:30 -0700 (PDT) X-Received: by 2002:a05:690c:4907:b0:6d4:4a0c:fcf0 with SMTP id 00721157ae682-71057cf454dmr2748377b3.20.1748562330701; Thu, 29 May 2025 16:45:30 -0700 (PDT) Received: by 2002:a05:690c:6083:b0:70e:2cf8:9db8 with SMTP id 00721157ae682-70f980e43fams7b3; Thu, 29 May 2025 16:20:19 -0700 (PDT) X-Received: by 2002:a05:690c:3507:b0:70f:8883:ce60 with SMTP id 00721157ae682-71057d235b9mr1922597b3.26.1748560818220; Thu, 29 May 2025 16:20:18 -0700 (PDT) Date: Thu, 29 May 2025 16:20:17 -0700 (PDT) From: Q C To: Bitcoin Development Mailing List Message-Id: <14874ca7-853c-4468-a357-a76759e50bben@googlegroups.com> In-Reply-To: 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_31338_2014820662.1748560817651" 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_31338_2014820662.1748560817651 Content-Type: multipart/alternative; boundary="----=_Part_31339_1368722702.1748560817651" ------=_Part_31339_1368722702.1748560817651 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable *>>> If XMSS is too scary,* Hi Bas, it is scary like you said; it is too risky to use XMSS in a=20 distributed system like Bitcoin, especially when there are a multitude of= =20 developers/implementers/users worldwide who might not necessarily=20 understand the nuances of a stateful scheme.=20 At the cost of larger block payload sizes due to sig+pub key sizes, storage= =20 size, ML-DSA sounds like the a good option. As a safety hedge till quantum= =20 computers capable of breaking classical cryptography become available, a=20 hybrid option with ML-DSA+ed25519 or FN-DSA+ed25519 seems a good bet (at=20 risk of higher complexity and implementation risk).=20 On Thursday, May 22, 2025 at 6:01:18=E2=80=AFAM UTC-7 Bas Westerbaan wrote: > On Wednesday, May 21, 2025 at 10:58:00=E2=80=AFPM UTC+2 Hunter Beast wrot= e: > > Thank you for this! It's definitely informing how we approach development= =20 > of BIP-360. SLH-DSA is concering, in that 7/8 arbitrary data would make i= t=20 > about on par with the de facto witness discount. I don't want to sacrific= e=20 > SLH-DSA because it's favored due to hash-based signatures having more=20 > confidence due to not introducing as many novel security assumptions as a= re=20 > introduced with lattice cryptography. > > > At present, lattices are the only viable approach to post-quantum key=20 > agreement in TLS. If come Q-day they're broken, then it's not just Bitcoi= n=20 > that's in big trouble. If you do want the certainty of hashes, you might= =20 > want to consider XMSS: that's JPEG resistant. With parameters n=3D16, h= =3D20,=20 > d=3D1, w=3D16 it has 32 byte public key and 880 byte signature can sign a= =20 > million messages, and only requires 3,000 hashes for verification [1]=20 > (which can actually be reduced threefold.) The big downside is that if yo= u=20 > use the same OTS leaf twice, probably anyone can forge another signature = on=20 > that leaf. In this case you might make this mistake harder by keeping tra= ck=20 > of the last leaf that was used for each public key. If you see a public k= ey=20 > sign using the same leaf a second time, you simply ignore the second=20 > signature. This helps against an oopsie that's at least a few hours apart= ,=20 > but not if you're using the same leaf twice in short succession. > =20 > > Another concern regarding SLH-DSA might be its performance, it's an order= =20 > of magnitude more costly to run than FALCON, which itself is an order of= =20 > magnitude more costly to run than secp256k1 Schnorr... > > > I assume you're talking about signature size? Falcon-512 requires fewer= =20 > cycles to verify than secp256k1. SLH-DSA's verification is a bit slower.= =20 > There is some flexibility: SLH-DSA today assumes that a signer will make= =20 > 2^64 signatures. If you drop that to say one million, then you can get=20 > smaller parameters. You can also vary parameters to smoothly vary signatu= re=20 > size, verification time, and signing time. There is some momentum between= =20 > standardising new variants of SLH-DSA. See also this paper [2]. If XMSS i= s=20 > too scary, you might want to consider a Bitcoin tailored variant of SLH-D= SA. > =20 > > We'll also be deprecating ML-DSA because it's too similar to FALCON in=20 > terms of performance and size. > > > Falcon has great signature size and verification performance. Its=20 > verification routine is also simple to implement. I do have to warn about= =20 > it's signing routine: it's quite complicated and tricky to implement=20 > securily, especially if you want it to be fast. I don't think speed is=20 > critical here, so I would stay away from implementations that use=20 > floating-point accelerators. Another thing to note is that if lattice=20 > cryptanalysis improves, the first step above Falcon-512 is Falcon-1024. A= =20 > Falcon-768 is possible (and used to be specified), but it's quite a bit= =20 > more complex. > > Best, > > Bas > =20 > > JPEG resistance and scaling will need to be solved through separate means= ,=20 > perhaps with BitZip, which is what I'm calling Ethan's proposal a couple= =20 > weeks back for block-wide transaction compression scaling PQC signatures= =20 > through STARK proofs. > > Will be making those changes to the BIP soon. Feedback is always welcome! > > On Wednesday, May 21, 2025 at 5:20:02=E2=80=AFAM UTC-6 Bas Westerbaan wro= te: > > Hi all, > > My colleague Ethan asked me the fun question which post-quantum signature= =20 > schemes have the following security property, which he called jpeg=20 > resistance. > > Attacker wins if for a (partially specified) signature and full message,= =20 > they can find a completed signature and public key, such that the complet= ed=20 > signature verifies under the public key. > > A naive hash-based signature is not jpeg resistant. Schoolbook Winternitz= =20 > one-time signatures, forest-of-trees few-time signatures, and Merkle tree= s=20 > all validate signatures (/authentication paths) by recomputing the public= =20 > key (/Merkle tree root) from the signature and the message, and checking= =20 > whether the recomputed public key matches the actual public key. That mea= ns=20 > we can pick anything for the signature, and just set the public key to th= e=20 > recomputed public key. > > The situation is more subtle for actual standardized hash-based=20 > signatures. RFC 8391 XMSS doesn=E2=80=99t sign the message itself, but fi= rst=20 > hashes in (among others) the public key. Basically the best we can do for= =20 > XMSS (except for setting the signature randomizer) is to guess the public= =20 > key. Thus it=E2=80=99s pretty much jpeg resistant. > > The situation is different again for RFC 8391 XMSSMT. XMSSMT is basically= =20 > a certificate chain of XMSS signatures. An XMSSMT public key is an XMSS= =20 > public key. An XMSSMT signature is a chain of XMSS signatures: the XMSSMT= =20 > public key signs another XMSS public key; which signs another public XMSS= =20 > public key; =E2=80=A6; which signs the message. Again the top XMSSMT publ= ic key=20 > is hashed into the message signed, but that only binds the first XMSS=20 > signature. We can=E2=80=99t mess with the first signature, but the other = signatures=20 > we can choose freely, as those roots are not bound. Thus XMSSMT with two= =20 > subtrees is only half jpeg resistant and it gets worse with more subtrees= . > > Similarly SLH-DSA (FIPS 205, n=C3=A9e SPHINCS+) is a certificate chain of= (a=20 > variant of) XMSS signing another XMSS public key, which signs another XMS= S=20 > public key, etc, which signs a FORS public key, which signs the final=20 > message. The SLH-DSA public key is the first XMSS public key. From the=20 > message and the public key it derives the FORS key pair (leaf) in the hyp= er=20 > tree to use to sign, and the message to actually sign. This means we can= =E2=80=99t=20 > mess with the first XMSS keypair. Thus to attack SLH-DSA we honestly=20 > generate the first XMSS keypair. Then given a message, we just pick the= =20 > signature arbitrarily for all but the first XMSS signature. We run the=20 > verification routine to recompute the root to sign by the first XMSS=20 > keypair. Then we sign it honestly. It depends a bit on the parameters, bu= t=20 > basically we get to pick roughly =E2=85=9E of the signature for free. > > ML-DSA (FIPS 204, n=C3=A9e Dilithium) is a Fiat=E2=80=93Shamir transform = of a=20 > (module-)lattice identification scheme. In the identification scheme the= =20 > prover picks a nonce y, and sends the commitment w1 =3D HighBits(A y) to= =20 > the verifier, where A is a matrix that=E2=80=99s part of the public key a= nd=20 > HighBits drops the lower bits (of the coefficients of the polynomials in= =20 > the vector). The verifier responds with a challenge c, to which the prove= r=20 > returns the response z =3D y + c s1, where s1 is part of the private key.= =20 > The verifier checks, among other things, whether HighBits(Az-ct) =3D w1,= =20 > where t =3D As1+s2 is part of the public key. As usual with Fiat=E2=80=93= Shamir, in=20 > ML-DSA the challenge c is the hash of the commitment, message, and public= =20 > key. The scheme has commitment recovery, so the signature itself consists= =20 > of the response z and the challenge c. (There is also a hint h, but that= =E2=80=99s=20 > small and we can ignore it.) If we set s1 to zero, then z=3Dy, which is= =20 > free to choose. So we can freely choose z, which is by far the largest pa= rt=20 > of the signature. Such a public key t is easy to detect, as it has small= =20 > coefficients. Instead we can set s1 to zero on only a few components.=20 > That allows us to choose z arbitrarily for those components, still breaki= ng=20 > jpeg resistance, while being hard to detect. There could well be other=20 > approaches here. > > Falcon. A Falcon private key are small polynomials f,g. Its public key is= =20 > h =3D g f-1. With the private key, for any polynomial c, we can compute= =20 > small s1 and s2 with s1 + s2h =3D c. A Falcon signature is a pair r, s2= =20 > where s1 =3D H(r, m) - s2 h is small. s2 is Guassian distributed, and is= =20 > encoded using an Elias=E2=80=93Fano approach. It=E2=80=99s then padded to= make signatures=20 > fixed-length. Clearly the randomizer r can be set arbitrarily, but it=E2= =80=99s=20 > only 40 bytes. Putting arbitrary bytes in most of the encoding of s2 will= =20 > likely yield a sufficiently small s2. Now, I thought about using this s2= =20 > as a new g and construct a signature that way by finding s=E2=80=991 and = s=E2=80=992 with=20 > s=E2=80=991 + s=E2=80=992s1f-1 =3D H(r,m), but my brother suggested a sim= pler approach. s2=20 > is likely invertible and we can set h =3D H(r, m)/s2. Both approaches wou= ld=20 > be thwarted by using H(H(h), r, m) instead of H(r, m). I do not know if= =20 > there is still another attack. > > Best, > > Bas > > > > [1] https://westerbaan.name/~bas/hashcalc/=20 > [2] https://eprint.iacr.org/2024/018.pdf > --=20 You received this message because you are subscribed to the Google Groups "= Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= 14874ca7-853c-4468-a357-a76759e50bben%40googlegroups.com. ------=_Part_31339_1368722702.1748560817651 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable >>>=C2=A0=C2=A0If XMSS is too scary,
Hi Bas, it is scary lik= e you said; it is too risky to use XMSS in a distributed system like Bitcoi= n, especially when there are a multitude of developers/implementers/users w= orldwide who might not necessarily understand the nuances of a stateful sch= eme.=C2=A0

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


On Thursday, May 22, 2025 at 6:01:18=E2=80=AFAM UTC-7 Bas Westerbaan wro= te:
On Wednesday, May 21, 2025 at 10:58:00=E2=80=AFPM UTC+2 Hunte= r Beast wrote:
Thank you for this! It&= #39;s definitely informing how we approach development of BIP-360. SLH-DSA = is concering, in that 7/8 arbitrary data would make it about on par with th= e de facto witness discount. I don't want to sacrifice SLH-DSA because = it's favored due to hash-based signatures having more confidence due to= not introducing as many novel security assumptions as are introduced with = lattice cryptography.

At present= , lattices are the only viable approach to post-quantum key agreement in TL= S. If come Q-day they're broken, then it's not just Bitcoin that= 9;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= million messages, and only requires 3,000 hashes for verification [1] (whi= ch can actually be reduced threefold.) The big downside is that if you use = the same OTS leaf twice, probably anyone can forge another signature on tha= t leaf. In this case you might make this mistake harder by keeping track of= the last leaf that was used for each public key. If you see a public key s= ign using the same leaf a second time, you simply ignore the second signatu= re. This helps against an oopsie that's at least a few hours apart, but= not if you're using the same leaf twice in short succession.
=C2=A0
Another concern re= garding SLH-DSA might be its performance, it's an order of magnitude mo= re costly to run than FALCON, which itself is an order of magnitude more co= stly to run than secp256k1 Schnorr...

I assume you're talking about signature size? Falcon-512 re= quires fewer cycles to verify than secp256k1. SLH-DSA's verification is= a bit slower. There is some flexibility: SLH-DSA today assumes that a sign= er will make 2^64 signatures. If you drop that to say one million, then you= can get smaller parameters. You can also vary parameters to smoothly vary = signature size, verification time, and signing time. There is some momentum= between standardising new variants of SLH-DSA. See also this paper [2]. If= XMSS is too scary, you might want to consider a Bitcoin tailored variant o= f SLH-DSA.
=C2=A0
We'll also be deprecating ML-DSA because it's too similar to FALC= ON in terms of performance and size.

Falcon has great signature size and verification performance. It= s verification routine is also simple to implement. I do have to warn about= it's signing routine: it's quite complicated and tricky to impleme= nt 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 floati= ng-point accelerators. Another thing to note is that if lattice cryptanalys= is improves, the first step above Falcon-512 is Falcon-1024. A Falcon-768 i= s possible (and used to be specified), but it's quite a bit more comple= x.

Best,

=C2=A0Bas
<= /div>
=C2=A0
JPEG resistance= and scaling will need to be solved through separate means, perhaps with Bi= tZip, which is what I'm calling Ethan's proposal a couple weeks bac= k for block-wide transaction compression scaling PQC signatures through STA= RK proofs.

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

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

Hi all,


My colle= ague Ethan asked me the fun question which post-quantum signature schemes h= ave the following security property, which he called jp= eg resistance.


Attacker wins if for a (partiall= y specified) signature and full message, they can find a completed signatur= e and public key, such that the completed signature verifies under the publ= ic key.


A naive hash-based signature is not jpeg resistant. School= book Winternitz one-time signatures, forest-of-trees few-time signatures, a= nd Merkle trees all validate signatures (/authentication paths) by recomput= ing the public key (/Merkle tree root) from the signature and the message, = and checking whether the recomputed public key matches the actual public ke= y. That means we can pick anything for the signature, and just set the publ= ic key to the recomputed public key.


The situation is more subtle = for actual standardized 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 s= etting the signature randomizer) is to guess the public key. Thus it=E2=80= =99s pretty much jpeg resistant.


The situation 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 X= MSS signatures: the XMSSMT public key signs another XMSS public key; which signs anoth= er public XMSS public key; =E2=80=A6; which signs the message. Again the to= p XMSSMT pu= blic key is hashed into the message signed, but that only binds the first X= MSS signature. We can=E2=80=99t mess with the first signature, but the othe= r signatures we can choose freely, as those roots are not bound. Thus XMSS<= /span>MT with two = subtrees is only half jpeg resistant and it gets worse with more subtrees.<= /span>


Similarly SLH-DSA (FIPS 205, n=C3=A9e SPHINCS<= /span>+) is a cert= ificate chain of (a variant of) XMSS signing another XMSS public key, which= signs another XMSS public key, etc, which signs a FORS public key, which s= igns the final message. The SLH-DSA public key is the first XMSS public key= . From the message and the public key it derives the FORS key pair (leaf) i= n the hyper tree to use to sign, and the message to actually sign. This mea= ns we can=E2=80=99t mess with the first XMSS keypair. Thus to attack SLH-DS= A we honestly generate the first XMSS keypair. Then given a message, we jus= t pick the signature arbitrarily for all but the first XMSS signature. We r= un the verification routine to recompute the root to sign by the first XMSS= keypair. Then we sign it honestly. It depends a bit on the parameters, but= basically we get to pick roughly =E2=85=9E of the signature for free.


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 = w1 =3D HighBi= ts(A y) to the verifier, where A is a matrix that=E2=80=99s part of the pub= lic key and HighBits drops the lower bits (of the coefficients of the polyn= omials in the vector). The verifier responds with a challenge c, to which t= he prover returns the response z =3D y + c s1, where s1 is part of the private key. The verifier chec= ks, among other things, whether HighBits(Az-ct) =3D w1, where t =3D As1+s2 is part of the public key. As usual wit= h Fiat=E2=80=93Shamir, in ML-DSA the challenge c is the hash of the commitm= ent, message, and public key. The scheme has commitment recovery, so the si= gnature itself consists of the response z and the challenge c. (There is al= so a hint h, but that=E2=80=99s small and we can ignore it.) If we set s<= span style=3D"font-size:0.6em;vertical-align:sub">1 to zero, then = z=3Dy, which is free to choose. So we can freely choose z, which is by far = the largest part of the signature. Such a public key t is easy to detect, a= s it has small coefficients. Instead we can set s1 to zero on only a few components. Tha= t allows us to choose z arbitrarily for those components, still breaking jp= eg resistance, while being hard to detect. There could well be other approa= ches here.


Falcon. A Falcon private key are smal= l polynomials f,g. Its public key is h =3D g f-1. With the private key, for any polyno= mial c, we can compute small s1 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 usi= ng an Elias=E2=80=93Fano approach. It=E2=80=99s then padded to make signatu= res fixed-length. Clearly the randomizer r can be set arbitrarily, but it= =E2=80=99s only 40 bytes. Putting arbitrary bytes in most of the encoding o= f s2 will lik= ely yield a sufficiently small s2. Now, I thought about using this s2 as a new g and construct a si= gnature that way by finding s=E2=80=991 and s=E2=80=992 with s=E2=80=991 + s=E2=80=992s1f-1 =3D H(r,m), but my brother suggested a simpler approach. s<= /span>2 is likely in= vertible 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 atta= ck.


Best,


=C2=A0Bas

<= /div>


[1]=C2=A0https://westerbaan.nam= e/~bas/hashcalc/=C2=A0

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