Delivery-date: Thu, 29 May 2025 16:45:43 -0700 Received: from mail-yb1-f189.google.com ([209.85.219.189]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from <bitcoindev+bncBDHJDC5244MRBG7D4PAQMGQEEK4XDAQ@googlegroups.com>) id 1uKmwP-0000T5-Tt for bitcoindev@gnusha.org; Thu, 29 May 2025 16:45:43 -0700 Received: by mail-yb1-f189.google.com with SMTP id 3f1490d57ef6-e7dabc0305dsf2188218276.2 for <bitcoindev@gnusha.org>; Thu, 29 May 2025 16:45:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1748562336; x=1749167136; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=6Swc/KavlkYZW8y69GNwnuadTNgh5ENbyLzmHnHEW0s=; b=lnbHyZE72hCsFTSFMvAE0B+TQz5g+BXHJCOgmBTyct91CJ4VbTmZIAlxtAwicuTrJi Or0JLTm7T4QM6DpmFNXvasDb9m2DGi8nD9VnZlz58X8qQa46Pt6qsSa+BGC0W3TGmckO d8MGS8kVGI0zvwWH28ZDOB1+L9SW9wWBDRPhoKRhRTAFMcN8uxhTpb9wkvUOlhOePKPi CaRWDD9CpbKK7Hdz5n9oGCxNVNz7WJPcjfySY3SjQUTi4igo6WVKtH7H01E7tL5hQqAW +2qEJ0PRbeIdD8YiaYh3NHqXVTDgEPARXtH1wKpGN3Kh5EzLMI2nNtJiLycltaSO3jk4 7ywg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1748562336; x=1749167136; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=6Swc/KavlkYZW8y69GNwnuadTNgh5ENbyLzmHnHEW0s=; b=U8hToM2bhWwOBUqTu59TfPGJHqusYNTZ9Y5JUn9kIHX+HgX8l00JXygD8mH+47OsrD a9zd5oQiA3dN5HNlMBugZyDhXCR90u2nGqLllStzKrq7jbtOU5gsTZGRZ2kB1TZG2lhk ZwTdbSk4/y1kmTVml5Mq12HaDqq3CVe3Fsf6KjJgFbNHLyv44qjMmf499XmJcqV+4tCw 9RTkck5pu+3laus6GutyqvMn9Yh9QyeLooRuKcE6huiwjKu7GvotEjUzNd0lalrZy/5X 7gjiWQbkVyQQlhdtbXUuPs9KjfjcLewvbxbd6Q81EsdJkwo7NESUKXs5qJRmmaODHXyk /dZQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1748562336; x=1749167136; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=6Swc/KavlkYZW8y69GNwnuadTNgh5ENbyLzmHnHEW0s=; b=Pl/kUFLELZEMKmO2oHcI6jrnqm3i2K0PYDRkyrZ48THJoW4MHMt/n7B6bx3TlG4xk2 gB4fRilYM9aoj9Y/pYoJFMbxtbHTy0AORbReRCbHqQ9j4yPAldZVSSKys7UjY2BB7T2p m+TrxNRedzQkGeTM/Zkm+KKwk90kbjVIB+qu43+4tYtKsLwm57Qq9vXlakI4zSRIU2UN pOwAwvJddkomaZKmXg3c2NShZtMh2Ke7TXHwmZtWwUXen+VMnRBUe6SSVKGshsgOchaR LtjcmeLAeUoeh5kT+izWHSL09owTE/SuODEUFwX6/Krd4SADIbOnnh9slqVd8jBHEdKH vCSQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCXpzF9iHHM2+P3P4QeQdvFm1wO8hYwT/6Xxf6TIPtmziqAASDSYPk6emax0zCKfCLRraKQ6g33lmIXF@gnusha.org X-Gm-Message-State: AOJu0YwCcxumXZNvBX2wwkB9X8pVofqjZa3d2a0NCdz43RzzF3/GE3Oq TwRRDtDnp4YWFjkuJYKgdR0VYe3SvRevBHMX3oyUYaDGMYaikBuxQjwo X-Google-Smtp-Source: AGHT+IHQpwVeLkvNta72Te960Wl46TNaMny8wxi7i//KAu018uLG/lT3/EKy1D7tO/DHovaf4Vxxhg== X-Received: by 2002:a05:6902:150b:b0:e7d:7264:6bc3 with SMTP id 3f1490d57ef6-e7f81ddf54emr2249643276.13.1748562335686; Thu, 29 May 2025 16:45:35 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZcO5xhrgJ4vEuHSvJxOsdsuztZDwFpOGmI4ncod+qGMVw== Received: by 2002:a25:b288:0:b0:e7d:622d:9dd6 with SMTP id 3f1490d57ef6-e7f6f6a178fls1408873276.0.-pod-prod-06-us; Thu, 29 May 2025 16:45:30 -0700 (PDT) X-Received: by 2002:a05:690c:4907:b0:6d4:4a0c:fcf0 with SMTP id 00721157ae682-71057cf454dmr2748377b3.20.1748562330701; Thu, 29 May 2025 16:45:30 -0700 (PDT) Received: by 2002:a05:690c:6083:b0:70e:2cf8:9db8 with SMTP id 00721157ae682-70f980e43fams7b3; Thu, 29 May 2025 16:20:19 -0700 (PDT) X-Received: by 2002:a05:690c:3507:b0:70f:8883:ce60 with SMTP id 00721157ae682-71057d235b9mr1922597b3.26.1748560818220; Thu, 29 May 2025 16:20:18 -0700 (PDT) Date: Thu, 29 May 2025 16:20:17 -0700 (PDT) From: Q C <dogeprotocol1@gmail.com> To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com> Message-Id: <14874ca7-853c-4468-a357-a76759e50bben@googlegroups.com> In-Reply-To: <e812604c-94a5-4f5f-87e8-71d178963d62n@googlegroups.com> References: <CAMjbhoU=PCUwbhWFbqCbOdZc+ybmREJmmt1K1TuHrCTncKH6VA@mail.gmail.com> <8a2c8743-dd0b-422c-85f9-f0350eec1162n@googlegroups.com> <e812604c-94a5-4f5f-87e8-71d178963d62n@googlegroups.com> Subject: [bitcoindev] Re: jpeg resistance of various post-quantum signature schemes MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_31338_2014820662.1748560817651" X-Original-Sender: dogeprotocol1@gmail.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: <bitcoindev.googlegroups.com> X-Google-Group-Id: 786775582512 List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com> List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com> List-Archive: <https://groups.google.com/group/bitcoindev List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com> List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>, <https://groups.google.com/group/bitcoindev/subscribe> X-Spam-Score: 3.1 (+++) ------=_Part_31338_2014820662.1748560817651 Content-Type: multipart/alternative; boundary="----=_Part_31339_1368722702.1748560817651" ------=_Part_31339_1368722702.1748560817651 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable *>>> If XMSS is too scary,* Hi Bas, it is scary like you said; it is too risky to use XMSS in a=20 distributed system like Bitcoin, especially when there are a multitude of= =20 developers/implementers/users worldwide who might not necessarily=20 understand the nuances of a stateful scheme.=20 At the cost of larger block payload sizes due to sig+pub key sizes, storage= =20 size, ML-DSA sounds like the a good option. As a safety hedge till quantum= =20 computers capable of breaking classical cryptography become available, a=20 hybrid option with ML-DSA+ed25519 or FN-DSA+ed25519 seems a good bet (at=20 risk of higher complexity and implementation risk).=20 On Thursday, May 22, 2025 at 6:01:18=E2=80=AFAM UTC-7 Bas Westerbaan wrote: > On Wednesday, May 21, 2025 at 10:58:00=E2=80=AFPM UTC+2 Hunter Beast wrot= e: > > Thank you for this! It's definitely informing how we approach development= =20 > of BIP-360. SLH-DSA is concering, in that 7/8 arbitrary data would make i= t=20 > about on par with the de facto witness discount. I don't want to sacrific= e=20 > SLH-DSA because it's favored due to hash-based signatures having more=20 > confidence due to not introducing as many novel security assumptions as a= re=20 > introduced with lattice cryptography. > > > At present, lattices are the only viable approach to post-quantum key=20 > agreement in TLS. If come Q-day they're broken, then it's not just Bitcoi= n=20 > that's in big trouble. If you do want the certainty of hashes, you might= =20 > want to consider XMSS: that's JPEG resistant. With parameters n=3D16, h= =3D20,=20 > d=3D1, w=3D16 it has 32 byte public key and 880 byte signature can sign a= =20 > million messages, and only requires 3,000 hashes for verification [1]=20 > (which can actually be reduced threefold.) The big downside is that if yo= u=20 > use the same OTS leaf twice, probably anyone can forge another signature = on=20 > that leaf. In this case you might make this mistake harder by keeping tra= ck=20 > of the last leaf that was used for each public key. If you see a public k= ey=20 > sign using the same leaf a second time, you simply ignore the second=20 > signature. This helps against an oopsie that's at least a few hours apart= ,=20 > but not if you're using the same leaf twice in short succession. > =20 > > Another concern regarding SLH-DSA might be its performance, it's an order= =20 > of magnitude more costly to run than FALCON, which itself is an order of= =20 > magnitude more costly to run than secp256k1 Schnorr... > > > I assume you're talking about signature size? Falcon-512 requires fewer= =20 > cycles to verify than secp256k1. SLH-DSA's verification is a bit slower.= =20 > There is some flexibility: SLH-DSA today assumes that a signer will make= =20 > 2^64 signatures. If you drop that to say one million, then you can get=20 > smaller parameters. You can also vary parameters to smoothly vary signatu= re=20 > size, verification time, and signing time. There is some momentum between= =20 > standardising new variants of SLH-DSA. See also this paper [2]. If XMSS i= s=20 > too scary, you might want to consider a Bitcoin tailored variant of SLH-D= SA. > =20 > > We'll also be deprecating ML-DSA because it's too similar to FALCON in=20 > terms of performance and size. > > > Falcon has great signature size and verification performance. Its=20 > verification routine is also simple to implement. I do have to warn about= =20 > it's signing routine: it's quite complicated and tricky to implement=20 > securily, especially if you want it to be fast. I don't think speed is=20 > critical here, so I would stay away from implementations that use=20 > floating-point accelerators. Another thing to note is that if lattice=20 > cryptanalysis improves, the first step above Falcon-512 is Falcon-1024. A= =20 > Falcon-768 is possible (and used to be specified), but it's quite a bit= =20 > more complex. > > Best, > > Bas > =20 > > JPEG resistance and scaling will need to be solved through separate means= ,=20 > perhaps with BitZip, which is what I'm calling Ethan's proposal a couple= =20 > weeks back for block-wide transaction compression scaling PQC signatures= =20 > through STARK proofs. > > Will be making those changes to the BIP soon. Feedback is always welcome! > > On Wednesday, May 21, 2025 at 5:20:02=E2=80=AFAM UTC-6 Bas Westerbaan wro= te: > > Hi all, > > My colleague Ethan asked me the fun question which post-quantum signature= =20 > schemes have the following security property, which he called jpeg=20 > resistance. > > Attacker wins if for a (partially specified) signature and full message,= =20 > they can find a completed signature and public key, such that the complet= ed=20 > signature verifies under the public key. > > A naive hash-based signature is not jpeg resistant. Schoolbook Winternitz= =20 > one-time signatures, forest-of-trees few-time signatures, and Merkle tree= s=20 > all validate signatures (/authentication paths) by recomputing the public= =20 > key (/Merkle tree root) from the signature and the message, and checking= =20 > whether the recomputed public key matches the actual public key. That mea= ns=20 > we can pick anything for the signature, and just set the public key to th= e=20 > recomputed public key. > > The situation is more subtle for actual standardized hash-based=20 > signatures. RFC 8391 XMSS doesn=E2=80=99t sign the message itself, but fi= rst=20 > hashes in (among others) the public key. Basically the best we can do for= =20 > XMSS (except for setting the signature randomizer) is to guess the public= =20 > key. Thus it=E2=80=99s pretty much jpeg resistant. > > The situation is different again for RFC 8391 XMSSMT. XMSSMT is basically= =20 > a certificate chain of XMSS signatures. An XMSSMT public key is an XMSS= =20 > public key. An XMSSMT signature is a chain of XMSS signatures: the XMSSMT= =20 > public key signs another XMSS public key; which signs another public XMSS= =20 > public key; =E2=80=A6; which signs the message. Again the top XMSSMT publ= ic key=20 > is hashed into the message signed, but that only binds the first XMSS=20 > signature. We can=E2=80=99t mess with the first signature, but the other = signatures=20 > we can choose freely, as those roots are not bound. Thus XMSSMT with two= =20 > subtrees is only half jpeg resistant and it gets worse with more subtrees= . > > Similarly SLH-DSA (FIPS 205, n=C3=A9e SPHINCS+) is a certificate chain of= (a=20 > variant of) XMSS signing another XMSS public key, which signs another XMS= S=20 > public key, etc, which signs a FORS public key, which signs the final=20 > message. The SLH-DSA public key is the first XMSS public key. From the=20 > message and the public key it derives the FORS key pair (leaf) in the hyp= er=20 > tree to use to sign, and the message to actually sign. This means we can= =E2=80=99t=20 > mess with the first XMSS keypair. Thus to attack SLH-DSA we honestly=20 > generate the first XMSS keypair. Then given a message, we just pick the= =20 > signature arbitrarily for all but the first XMSS signature. We run the=20 > verification routine to recompute the root to sign by the first XMSS=20 > keypair. Then we sign it honestly. It depends a bit on the parameters, bu= t=20 > basically we get to pick roughly =E2=85=9E of the signature for free. > > ML-DSA (FIPS 204, n=C3=A9e Dilithium) is a Fiat=E2=80=93Shamir transform = of a=20 > (module-)lattice identification scheme. In the identification scheme the= =20 > prover picks a nonce y, and sends the commitment w1 =3D HighBits(A y) to= =20 > the verifier, where A is a matrix that=E2=80=99s part of the public key a= nd=20 > HighBits drops the lower bits (of the coefficients of the polynomials in= =20 > the vector). The verifier responds with a challenge c, to which the prove= r=20 > returns the response z =3D y + c s1, where s1 is part of the private key.= =20 > The verifier checks, among other things, whether HighBits(Az-ct) =3D w1,= =20 > where t =3D As1+s2 is part of the public key. As usual with Fiat=E2=80=93= Shamir, in=20 > ML-DSA the challenge c is the hash of the commitment, message, and public= =20 > key. The scheme has commitment recovery, so the signature itself consists= =20 > of the response z and the challenge c. (There is also a hint h, but that= =E2=80=99s=20 > small and we can ignore it.) If we set s1 to zero, then z=3Dy, which is= =20 > free to choose. So we can freely choose z, which is by far the largest pa= rt=20 > of the signature. Such a public key t is easy to detect, as it has small= =20 > coefficients. Instead we can set s1 to zero on only a few components.=20 > That allows us to choose z arbitrarily for those components, still breaki= ng=20 > jpeg resistance, while being hard to detect. There could well be other=20 > approaches here. > > Falcon. A Falcon private key are small polynomials f,g. Its public key is= =20 > h =3D g f-1. With the private key, for any polynomial c, we can compute= =20 > small s1 and s2 with s1 + s2h =3D c. A Falcon signature is a pair r, s2= =20 > where s1 =3D H(r, m) - s2 h is small. s2 is Guassian distributed, and is= =20 > encoded using an Elias=E2=80=93Fano approach. It=E2=80=99s then padded to= make signatures=20 > fixed-length. Clearly the randomizer r can be set arbitrarily, but it=E2= =80=99s=20 > only 40 bytes. Putting arbitrary bytes in most of the encoding of s2 will= =20 > likely yield a sufficiently small s2. Now, I thought about using this s2= =20 > as a new g and construct a signature that way by finding s=E2=80=991 and = s=E2=80=992 with=20 > s=E2=80=991 + s=E2=80=992s1f-1 =3D H(r,m), but my brother suggested a sim= pler approach. s2=20 > is likely invertible and we can set h =3D H(r, m)/s2. Both approaches wou= ld=20 > be thwarted by using H(H(h), r, m) instead of H(r, m). I do not know if= =20 > there is still another attack. > > Best, > > Bas > > > > [1] https://westerbaan.name/~bas/hashcalc/=20 > [2] https://eprint.iacr.org/2024/018.pdf > --=20 You received this message because you are subscribed to the Google Groups "= Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= 14874ca7-853c-4468-a357-a76759e50bben%40googlegroups.com. ------=_Part_31339_1368722702.1748560817651 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <i style=3D"color: rgba(0, 0, 0, 0.87); font-family: Roboto, RobotoDraft, H= elvetica, Arial, sans-serif; font-size: 14px; font-variant-ligatures: norma= l; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; tex= t-align: start; text-indent: 0px; text-transform: none; word-spacing: 0px; = white-space: normal; background-color: rgb(255, 255, 255); text-decoration-= thickness: initial; text-decoration-style: initial; text-decoration-color: = initial;">>>><span>=C2=A0</span>=C2=A0If XMSS is too scary,</i><br= style=3D"color: rgba(0, 0, 0, 0.87); font-family: Roboto, RobotoDraft, Hel= vetica, Arial, sans-serif; font-size: 14px; font-style: normal; font-varian= t-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-sp= acing: normal; text-align: start; text-indent: 0px; text-transform: none; w= ord-spacing: 0px; white-space: normal; background-color: rgb(255, 255, 255)= ; text-decoration-thickness: initial; text-decoration-style: initial; text-= decoration-color: initial;" /><br style=3D"color: rgba(0, 0, 0, 0.87); font= -family: Roboto, RobotoDraft, Helvetica, Arial, sans-serif; font-size: 14px= ; font-style: normal; font-variant-ligatures: normal; font-variant-caps: no= rmal; font-weight: 400; letter-spacing: normal; text-align: start; text-ind= ent: 0px; text-transform: none; word-spacing: 0px; white-space: normal; bac= kground-color: rgb(255, 255, 255); text-decoration-thickness: initial; text= -decoration-style: initial; text-decoration-color: initial;" /><span style= =3D"color: rgba(0, 0, 0, 0.87); font-family: Roboto, RobotoDraft, Helvetica= , Arial, sans-serif; font-size: 14px; font-style: normal; font-variant-liga= tures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing:= normal; text-align: start; text-indent: 0px; text-transform: none; word-sp= acing: 0px; white-space: normal; background-color: rgb(255, 255, 255); text= -decoration-thickness: initial; text-decoration-style: initial; text-decora= tion-color: initial; display: inline; float: none;">Hi Bas, it is scary lik= e you said; it is too risky to use XMSS in a distributed system like Bitcoi= n, especially when there are a multitude of developers/implementers/users w= orldwide who might not necessarily understand the nuances of a stateful sch= eme.=C2=A0</span><br style=3D"color: rgba(0, 0, 0, 0.87); font-family: Robo= to, RobotoDraft, Helvetica, Arial, sans-serif; font-size: 14px; font-style:= normal; font-variant-ligatures: normal; font-variant-caps: normal; font-we= ight: 400; letter-spacing: normal; text-align: start; text-indent: 0px; tex= t-transform: none; word-spacing: 0px; white-space: normal; background-color= : rgb(255, 255, 255); text-decoration-thickness: initial; text-decoration-s= tyle: initial; text-decoration-color: initial;" /><br style=3D"color: rgba(= 0, 0, 0, 0.87); font-family: Roboto, RobotoDraft, Helvetica, Arial, sans-se= rif; font-size: 14px; font-style: normal; font-variant-ligatures: normal; f= ont-variant-caps: normal; font-weight: 400; letter-spacing: normal; text-al= ign: start; text-indent: 0px; text-transform: none; word-spacing: 0px; whit= e-space: normal; background-color: rgb(255, 255, 255); text-decoration-thic= kness: initial; text-decoration-style: initial; text-decoration-color: init= ial;" /><span style=3D"color: rgba(0, 0, 0, 0.87); font-family: Roboto, Rob= otoDraft, Helvetica, Arial, sans-serif; font-size: 14px; font-style: normal= ; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 4= 00; letter-spacing: normal; text-align: start; text-indent: 0px; text-trans= form: none; word-spacing: 0px; white-space: normal; background-color: rgb(2= 55, 255, 255); text-decoration-thickness: initial; text-decoration-style: i= nitial; text-decoration-color: initial; display: inline; float: none;">At t= he cost of larger block payload sizes due to sig+pub key sizes, storage siz= e, ML-DSA sounds like the a good option.=C2=A0 As a safety hedge till quant= um computers capable of breaking classical cryptography become available, a= hybrid option with ML-DSA+ed25519 or FN-DSA+ed25519 seems a good bet (at r= isk of higher complexity and implementation risk).=C2=A0</span><br style=3D= "color: rgba(0, 0, 0, 0.87); font-family: Roboto, RobotoDraft, Helvetica, A= rial, sans-serif; font-size: 14px; font-style: normal; font-variant-ligatur= es: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: no= rmal; text-align: start; text-indent: 0px; text-transform: none; word-spaci= ng: 0px; white-space: normal; background-color: rgb(255, 255, 255); text-de= coration-thickness: initial; text-decoration-style: initial; text-decoratio= n-color: initial;" /> <br /><br /><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_att= r">On Thursday, May 22, 2025 at 6:01:18=E2=80=AFAM UTC-7 Bas Westerbaan wro= te:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8e= x; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div= dir=3D"auto">On Wednesday, May 21, 2025 at 10:58:00=E2=80=AFPM UTC+2 Hunte= r Beast wrote:<br></div><blockquote style=3D"margin:0px 0px 0px 0.8ex;borde= r-left:1px solid rgb(204,204,204);padding-left:1ex">Thank you for this! It&= #39;s definitely informing how we approach development of BIP-360. SLH-DSA = is concering, in that 7/8 arbitrary data would make it about on par with th= e de facto witness discount. I don'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.</blockquote><div><br></div></div><div><div>At present= , lattices are the only viable approach to post-quantum key agreement in TL= S. If come Q-day they'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.</div></di= v><div><div>=C2=A0</div><blockquote style=3D"margin:0px 0px 0px 0.8ex;borde= r-left:1px solid rgb(204,204,204);padding-left:1ex"><div>Another concern re= garding SLH-DSA might be its performance, it's an order of magnitude mo= re costly to run than FALCON, which itself is an order of magnitude more co= stly to run than secp256k1 Schnorr...</div></blockquote><div><br></div></di= v><div><div>I assume you'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.</div></div><div><div>=C2=A0</div><blockquote style=3D"margin:0px= 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><di= v>We'll also be deprecating ML-DSA because it's too similar to FALC= ON in terms of performance and size.</div></blockquote><div><br></div></div= ><div><div>Falcon has great signature size and verification performance. It= s verification routine is also simple to implement. I do have to warn about= it'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.</div><div><br></div><div>Best,</div><div><br></div><div>=C2=A0Bas</div><= /div><div><div>=C2=A0</div><blockquote style=3D"margin:0px 0px 0px 0.8ex;bo= rder-left:1px solid rgb(204,204,204);padding-left:1ex"><div>JPEG resistance= and scaling will need to be solved through separate means, perhaps with Bi= tZip, which is what I'm calling Ethan's proposal a couple weeks bac= k for block-wide transaction compression scaling PQC signatures through STA= RK proofs.</div><div><br></div><div>Will be making those changes to the BIP= soon. Feedback is always welcome!</div><br><div><div dir=3D"auto">On Wedne= sday, May 21, 2025 at 5:20:02=E2=80=AFAM UTC-6 Bas Westerbaan wrote:<br></d= iv><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(= 204,204,204);padding-left:1ex"><div dir=3D"ltr"><span><p dir=3D"ltr" style= =3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-= size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:tr= ansparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-v= ariant-alternates:normal;vertical-align:baseline">Hi all,</span></p><br><p = dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><sp= an style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);ba= ckground-color:transparent;font-variant-numeric:normal;font-variant-east-as= ian:normal;font-variant-alternates:normal;vertical-align:baseline">My colle= ague Ethan asked me the fun question which post-quantum signature schemes h= ave the following security property, which he called </span><span style=3D"= font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-col= or:transparent;font-style:italic;font-variant-numeric:normal;font-variant-e= ast-asian:normal;font-variant-alternates:normal;vertical-align:baseline">jp= eg resistance</span><span style=3D"font-size:11pt;font-family:Arial,sans-se= rif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:norm= al;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-a= lign:baseline">.</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;mar= gin-left:36pt;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11= pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpare= nt;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-= alternates:normal;vertical-align:baseline">Attacker wins if for a (partiall= y specified) signature and full message, they can find a completed signatur= e and public key, such that the completed signature verifies under the publ= ic key.</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0= pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-family:Arial,sans-= serif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:no= rmal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical= -align:baseline">A naive hash-based signature is not jpeg resistant. School= book Winternitz one-time signatures, forest-of-trees few-time signatures, a= nd Merkle trees all validate signatures (/authentication paths) by recomput= ing the public key (/Merkle tree root) from the signature and the message, = and checking whether the recomputed public key matches the actual public ke= y. That means we can pick anything for the signature, and just set the publ= ic key to the recomputed public key.</span></p><br><p dir=3D"ltr" style=3D"= line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size= :11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transp= arent;font-variant-numeric:normal;font-variant-east-asian:normal;font-varia= nt-alternates:normal;vertical-align:baseline">The situation is more subtle = for actual standardized hash-based signatures. RFC 8391 </span><span style= =3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background= -color:transparent;font-weight:700;font-variant-numeric:normal;font-variant= -east-asian:normal;font-variant-alternates:normal;vertical-align:baseline">= XMSS</span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color= :rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-v= ariant-east-asian:normal;font-variant-alternates:normal;vertical-align:base= line"> doesn=E2=80=99t sign the message itself, but first hashes in (among = others) the public key. Basically the best we can do for XMSS (except for s= etting the signature randomizer) is to guess the public key. Thus it=E2=80= =99s pretty much jpeg resistant.</span></p><br><p dir=3D"ltr" style=3D"line= -height:1.38;margin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11p= t;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparen= t;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-a= lternates:normal;vertical-align:baseline">The situation is different again = for RFC 8391 </span><span style=3D"font-size:11pt;font-family:Arial,sans-se= rif;color:rgb(0,0,0);background-color:transparent;font-weight:700;font-vari= ant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:n= ormal;vertical-align:baseline">XMSS</span><span style=3D"font-size:11pt;fon= t-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;fon= t-weight:700;font-variant-numeric:normal;font-variant-east-asian:normal;fon= t-variant-alternates:normal;vertical-align:baseline"><span style=3D"font-si= ze:0.6em;vertical-align:super">MT</span></span><span style=3D"font-size:11p= t;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparen= t;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-a= lternates:normal;vertical-align:baseline">. XMSS</span><span style=3D"font-= size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:tr= ansparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-v= ariant-alternates:normal;vertical-align:baseline"><span style=3D"font-size:= 0.6em;vertical-align:super">MT</span></span><span style=3D"font-size:11pt;f= ont-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;f= ont-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alte= rnates:normal;vertical-align:baseline"> is basically a certificate chain of= XMSS signatures. An XMSS</span><span style=3D"font-size:11pt;font-family:A= rial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-= numeric:normal;font-variant-east-asian:normal;font-variant-alternates:norma= l;vertical-align:baseline"><span style=3D"font-size:0.6em;vertical-align:su= per">MT</span></span><span style=3D"font-size:11pt;font-family:Arial,sans-s= erif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:nor= mal;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-= align:baseline"> public key is an XMSS public key. An XMSS</span><span styl= e=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);backgroun= d-color:transparent;font-variant-numeric:normal;font-variant-east-asian:nor= mal;font-variant-alternates:normal;vertical-align:baseline"><span style=3D"= font-size:0.6em;vertical-align:super">MT</span></span><span style=3D"font-s= ize:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:tra= nsparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-va= riant-alternates:normal;vertical-align:baseline"> signature is a chain of X= MSS signatures: the XMSS</span><span style=3D"font-size:11pt;font-family:Ar= ial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-n= umeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal= ;vertical-align:baseline"><span style=3D"font-size:0.6em;vertical-align:sup= er">MT</span></span><span style=3D"font-size:11pt;font-family:Arial,sans-se= rif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:norm= al;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-a= lign:baseline"> public key signs another XMSS public key; which signs anoth= er public XMSS public key; =E2=80=A6; which signs the message. Again the to= p XMSS</span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;col= or:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font= -variant-east-asian:normal;font-variant-alternates:normal;vertical-align:ba= seline"><span style=3D"font-size:0.6em;vertical-align:super">MT</span></spa= n><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,= 0);background-color:transparent;font-variant-numeric:normal;font-variant-ea= st-asian:normal;font-variant-alternates:normal;vertical-align:baseline"> pu= blic key is hashed into the message signed, but that only binds the first X= MSS signature. We can=E2=80=99t mess with the first signature, but the othe= r signatures we can choose freely, as those roots are not bound. Thus XMSS<= /span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(= 0,0,0);background-color:transparent;font-variant-numeric:normal;font-varian= t-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"= ><span style=3D"font-size:0.6em;vertical-align:super">MT</span></span><span= style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);back= ground-color:transparent;font-variant-numeric:normal;font-variant-east-asia= n:normal;font-variant-alternates:normal;vertical-align:baseline"> with two = subtrees is only half jpeg resistant and it gets worse with more subtrees.<= /span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margi= n-bottom:0pt"><span style=3D"font-size:11pt;font-family:Arial,sans-serif;co= lor:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;fon= t-variant-east-asian:normal;font-variant-alternates:normal;vertical-align:b= aseline">Similarly </span><span style=3D"font-size:11pt;font-family:Arial,s= ans-serif;color:rgb(0,0,0);background-color:transparent;font-weight:700;fon= t-variant-numeric:normal;font-variant-east-asian:normal;font-variant-altern= ates:normal;vertical-align:baseline">SLH-DSA</span><span style=3D"font-size= :11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transp= arent;font-variant-numeric:normal;font-variant-east-asian:normal;font-varia= nt-alternates:normal;vertical-align:baseline"> (FIPS 205, n=C3=A9e SPHINCS<= /span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(= 0,0,0);background-color:transparent;font-variant-numeric:normal;font-varian= t-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"= ><span style=3D"font-size:0.6em;vertical-align:super">+</span></span><span = style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);backg= round-color:transparent;font-variant-numeric:normal;font-variant-east-asian= :normal;font-variant-alternates:normal;vertical-align:baseline">) is a cert= ificate chain of (a variant of) XMSS signing another XMSS public key, which= signs another XMSS public key, etc, which signs a FORS public key, which s= igns the final message. The SLH-DSA public key is the first XMSS public key= . From the message and the public key it derives the FORS key pair (leaf) i= n the hyper tree to use to sign, and the message to actually sign. This mea= ns we can=E2=80=99t mess with the first XMSS keypair. Thus to attack SLH-DS= A we honestly generate the first XMSS keypair. Then given a message, we jus= t pick the signature arbitrarily for all but the first XMSS signature. We r= un the verification routine to recompute the root to sign by the first XMSS= keypair. Then we sign it honestly. It depends a bit on the parameters, but= basically we get to pick roughly =E2=85=9E of the signature for free.</spa= n></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margin-bo= ttom:0pt"><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:= rgb(0,0,0);background-color:transparent;font-weight:700;font-variant-numeri= c:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vert= ical-align:baseline">ML-DSA</span><span style=3D"font-size:11pt;font-family= :Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-varian= t-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:nor= mal;vertical-align:baseline"> (FIPS 204, n=C3=A9e Dilithium) is a Fiat=E2= =80=93Shamir transform of a (module-)lattice identification scheme. In the = identification scheme the prover picks a nonce y, and sends the commitment = w</span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rg= b(0,0,0);background-color:transparent;font-variant-numeric:normal;font-vari= ant-east-asian:normal;font-variant-alternates:normal;vertical-align:baselin= e"><span style=3D"font-size:0.6em;vertical-align:sub">1</span></span><span = style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);backg= round-color:transparent;font-variant-numeric:normal;font-variant-east-asian= :normal;font-variant-alternates:normal;vertical-align:baseline"> =3D HighBi= ts(A y) to the verifier, where A is a matrix that=E2=80=99s part of the pub= lic key and HighBits drops the lower bits (of the coefficients of the polyn= omials in the vector). The verifier responds with a challenge c, to which t= he prover returns the response z =3D y + c s</span><span style=3D"font-size= :11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transp= arent;font-variant-numeric:normal;font-variant-east-asian:normal;font-varia= nt-alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6e= m;vertical-align:sub">1</span></span><span style=3D"font-size:11pt;font-fam= ily:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-var= iant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:= normal;vertical-align:baseline">, where s</span><span style=3D"font-size:11= pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpare= nt;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-= alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;v= ertical-align:sub">1</span></span><span style=3D"font-size:11pt;font-family= :Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-varian= t-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:nor= mal;vertical-align:baseline"> is part of the private key. The verifier chec= ks, among other things, whether HighBits(Az-ct) =3D w</span><span style=3D"= font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-col= or:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;f= ont-variant-alternates:normal;vertical-align:baseline"><span style=3D"font-= size:0.6em;vertical-align:sub">1</span></span><span style=3D"font-size:11pt= ;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent= ;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-al= ternates:normal;vertical-align:baseline">, where t =3D As</span><span style= =3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background= -color:transparent;font-variant-numeric:normal;font-variant-east-asian:norm= al;font-variant-alternates:normal;vertical-align:baseline"><span style=3D"f= ont-size:0.6em;vertical-align:sub">1</span></span><span style=3D"font-size:= 11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpa= rent;font-variant-numeric:normal;font-variant-east-asian:normal;font-varian= t-alternates:normal;vertical-align:baseline">+s</span><span style=3D"font-s= ize:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:tra= nsparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-va= riant-alternates:normal;vertical-align:baseline"><span style=3D"font-size:0= .6em;vertical-align:sub">2</span></span><span style=3D"font-size:11pt;font-= family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-= variant-numeric:normal;font-variant-east-asian:normal;font-variant-alternat= es:normal;vertical-align:baseline"> is part of the public key. As usual wit= h Fiat=E2=80=93Shamir, in ML-DSA the challenge c is the hash of the commitm= ent, message, and public key. The scheme has commitment recovery, so the si= gnature itself consists of the response z and the challenge c. (There is al= so a hint h, but that=E2=80=99s small and we can ignore it.) If we set s</s= pan><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,= 0,0);background-color:transparent;font-variant-numeric:normal;font-variant-= east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"><= span style=3D"font-size:0.6em;vertical-align:sub">1 </span></span><span sty= le=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);backgrou= nd-color:transparent;font-variant-numeric:normal;font-variant-east-asian:no= rmal;font-variant-alternates:normal;vertical-align:baseline">to zero, then = z=3Dy, which is free to choose. So we can freely choose z, which is by far = the largest part of the signature. Such a public key t is easy to detect, a= s it has small coefficients. Instead we can set s</span><span style=3D"font= -size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:t= ransparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-= variant-alternates:normal;vertical-align:baseline"><span style=3D"font-size= :0.6em;vertical-align:sub">1</span></span><span style=3D"font-size:11pt;fon= t-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;fon= t-variant-numeric:normal;font-variant-east-asian:normal;font-variant-altern= ates:normal;vertical-align:baseline"> to zero on only a few components. Tha= t allows us to choose z arbitrarily for those components, still breaking jp= eg resistance, while being hard to detect. There could well be other approa= ches here.</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-to= p:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-family:Arial,sa= ns-serif;color:rgb(0,0,0);background-color:transparent;font-weight:700;font= -variant-numeric:normal;font-variant-east-asian:normal;font-variant-alterna= tes:normal;vertical-align:baseline">Falcon</span><span style=3D"font-size:1= 1pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpar= ent;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant= -alternates:normal;vertical-align:baseline">. A Falcon private key are smal= l polynomials f,g. Its public key is h =3D g f</span><span style=3D"font-si= ze:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:tran= sparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-var= iant-alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.= 6em;vertical-align:super">-1</span></span><span style=3D"font-size:11pt;fon= t-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;fon= t-variant-numeric:normal;font-variant-east-asian:normal;font-variant-altern= ates:normal;vertical-align:baseline">. With the private key, for any polyno= mial c, we can compute small s</span><span style=3D"font-size:11pt;font-fam= ily:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-var= iant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:= normal;vertical-align:baseline"><span style=3D"font-size:0.6em;vertical-ali= gn:sub">1</span></span><span style=3D"font-size:11pt;font-family:Arial,sans= -serif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:n= ormal;font-variant-east-asian:normal;font-variant-alternates:normal;vertica= l-align:baseline"> and s</span><span style=3D"font-size:11pt;font-family:Ar= ial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-n= umeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal= ;vertical-align:baseline"><span style=3D"font-size:0.6em;vertical-align:sub= ">2</span></span><span style=3D"font-size:11pt;font-family:Arial,sans-serif= ;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;= font-variant-east-asian:normal;font-variant-alternates:normal;vertical-alig= n:baseline"> with s</span><span style=3D"font-size:11pt;font-family:Arial,s= ans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-numeri= c:normal;font-variant-east-asian:normal;font-variant-alternates:normal;vert= ical-align:baseline"><span style=3D"font-size:0.6em;vertical-align:sub">1</= span></span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;colo= r:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-= variant-east-asian:normal;font-variant-alternates:normal;vertical-align:bas= eline"> + s</span><span style=3D"font-size:11pt;font-family:Arial,sans-seri= f;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal= ;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-ali= gn:baseline"><span style=3D"font-size:0.6em;vertical-align:sub">2</span></s= pan><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,= 0,0);background-color:transparent;font-variant-numeric:normal;font-variant-= east-asian:normal;font-variant-alternates:normal;vertical-align:baseline">h= =3D c. A Falcon signature is a pair r, s</span><span style=3D"font-size:11= pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpare= nt;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-= alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;v= ertical-align:sub">2</span></span><span style=3D"font-size:11pt;font-family= :Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-varian= t-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:nor= mal;vertical-align:baseline"> where s</span><span style=3D"font-size:11pt;f= ont-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;f= ont-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alte= rnates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;verti= cal-align:sub">1</span></span><span style=3D"font-size:11pt;font-family:Ari= al,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-nu= meric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;= vertical-align:baseline"> =3D H(r, m) - s</span><span style=3D"font-size:11= pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpare= nt;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-= alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;v= ertical-align:sub">2</span></span><span style=3D"font-size:11pt;font-family= :Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-varian= t-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:nor= mal;vertical-align:baseline"> h is small. s</span><span style=3D"font-size:= 11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpa= rent;font-variant-numeric:normal;font-variant-east-asian:normal;font-varian= t-alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em= ;vertical-align:sub">2</span></span><span style=3D"font-size:11pt;font-fami= ly:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-vari= ant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:n= ormal;vertical-align:baseline"> is Guassian distributed, and is encoded usi= ng an Elias=E2=80=93Fano approach. It=E2=80=99s then padded to make signatu= res fixed-length. Clearly the randomizer r can be set arbitrarily, but it= =E2=80=99s only 40 bytes. Putting arbitrary bytes in most of the encoding o= f s</span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:= rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-va= riant-east-asian:normal;font-variant-alternates:normal;vertical-align:basel= ine"><span style=3D"font-size:0.6em;vertical-align:sub">2</span></span><spa= n style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);bac= kground-color:transparent;font-variant-numeric:normal;font-variant-east-asi= an:normal;font-variant-alternates:normal;vertical-align:baseline"> will lik= ely yield a sufficiently small s</span><span style=3D"font-size:11pt;font-f= amily:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-v= ariant-numeric:normal;font-variant-east-asian:normal;font-variant-alternate= s:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;vertical-a= lign:sub">2</span></span><span style=3D"font-size:11pt;font-family:Arial,sa= ns-serif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric= :normal;font-variant-east-asian:normal;font-variant-alternates:normal;verti= cal-align:baseline">. Now, I thought about using this s</span><span style= =3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background= -color:transparent;font-variant-numeric:normal;font-variant-east-asian:norm= al;font-variant-alternates:normal;vertical-align:baseline"><span style=3D"f= ont-size:0.6em;vertical-align:sub">2</span></span><span style=3D"font-size:= 11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpa= rent;font-variant-numeric:normal;font-variant-east-asian:normal;font-varian= t-alternates:normal;vertical-align:baseline"> as a new g and construct a si= gnature that way by finding s=E2=80=99</span><span style=3D"font-size:11pt;= font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;= font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-alt= ernates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;vert= ical-align:sub">1</span></span><span style=3D"font-size:11pt;font-family:Ar= ial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-n= umeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal= ;vertical-align:baseline"> and s=E2=80=99</span><span style=3D"font-size:11= pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transpare= nt;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-= alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;v= ertical-align:sub">2</span></span><span style=3D"font-size:11pt;font-family= :Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-varian= t-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:nor= mal;vertical-align:baseline"> with s=E2=80=99</span><span style=3D"font-siz= e:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:trans= parent;font-variant-numeric:normal;font-variant-east-asian:normal;font-vari= ant-alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6= em;vertical-align:sub">1</span></span><span style=3D"font-size:11pt;font-fa= mily:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-va= riant-numeric:normal;font-variant-east-asian:normal;font-variant-alternates= :normal;vertical-align:baseline"> + s=E2=80=99</span><span style=3D"font-si= ze:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:tran= sparent;font-variant-numeric:normal;font-variant-east-asian:normal;font-var= iant-alternates:normal;vertical-align:baseline"><span style=3D"font-size:0.= 6em;vertical-align:sub">2</span></span><span style=3D"font-size:11pt;font-f= amily:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-v= ariant-numeric:normal;font-variant-east-asian:normal;font-variant-alternate= s:normal;vertical-align:baseline">s</span><span style=3D"font-size:11pt;fon= t-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;fon= t-variant-numeric:normal;font-variant-east-asian:normal;font-variant-altern= ates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;vertica= l-align:sub">1</span></span><span style=3D"font-size:11pt;font-family:Arial= ,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-nume= ric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;ve= rtical-align:baseline">f</span><span style=3D"font-size:11pt;font-family:Ar= ial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-n= umeric:normal;font-variant-east-asian:normal;font-variant-alternates:normal= ;vertical-align:baseline"><span style=3D"font-size:0.6em;vertical-align:sup= er">-1</span></span><span style=3D"font-size:11pt;font-family:Arial,sans-se= rif;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:norm= al;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-a= lign:baseline"> =3D H(r,m), but my brother suggested a simpler approach. s<= /span><span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(= 0,0,0);background-color:transparent;font-variant-numeric:normal;font-varian= t-east-asian:normal;font-variant-alternates:normal;vertical-align:baseline"= ><span style=3D"font-size:0.6em;vertical-align:sub">2</span></span><span st= yle=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);backgro= und-color:transparent;font-variant-numeric:normal;font-variant-east-asian:n= ormal;font-variant-alternates:normal;vertical-align:baseline"> is likely in= vertible and we can set h =3D H(r, m)/s</span><span style=3D"font-size:11pt= ;font-family:Arial,sans-serif;color:rgb(0,0,0);background-color:transparent= ;font-variant-numeric:normal;font-variant-east-asian:normal;font-variant-al= ternates:normal;vertical-align:baseline"><span style=3D"font-size:0.6em;ver= tical-align:sub">2</span></span><span style=3D"font-size:11pt;font-family:A= rial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant-= numeric:normal;font-variant-east-asian:normal;font-variant-alternates:norma= l;vertical-align:baseline">. Both approaches would be thwarted by using H(H= (h), r, m) instead of H(r, m). I do not know if there is still another atta= ck.</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;m= argin-bottom:0pt"><span style=3D"font-size:11pt;font-family:Arial,sans-seri= f;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal= ;font-variant-east-asian:normal;font-variant-alternates:normal;vertical-ali= gn:baseline">Best,</span></p><br><p dir=3D"ltr" style=3D"line-height:1.38;m= argin-top:0pt;margin-bottom:0pt"><span style=3D"font-size:11pt;font-family:= Arial,sans-serif;color:rgb(0,0,0);background-color:transparent;font-variant= -numeric:normal;font-variant-east-asian:normal;font-variant-alternates:norm= al;vertical-align:baseline">=C2=A0Bas</span></p></span></div></blockquote><= /div></blockquote><div><br></div><div><br></div></div><div><div>[1]=C2=A0<a= href=3D"https://westerbaan.name/~bas/hashcalc/" target=3D"_blank" rel=3D"n= ofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&q= =3Dhttps://westerbaan.name/~bas/hashcalc/&source=3Dgmail&ust=3D1748= 647163266000&usg=3DAOvVaw3D5aR4eXDZy3GxBdLVojJn">https://westerbaan.nam= e/~bas/hashcalc/</a>=C2=A0</div><div>[2]=C2=A0<a href=3D"https://eprint.iac= r.org/2024/018.pdf" target=3D"_blank" rel=3D"nofollow" data-saferedirecturl= =3D"https://www.google.com/url?hl=3Den&q=3Dhttps://eprint.iacr.org/2024= /018.pdf&source=3Dgmail&ust=3D1748647163266000&usg=3DAOvVaw3TzC= VcaWykEcdEJKYDKxqJ">https://eprint.iacr.org/2024/018.pdf</a></div></div></b= lockquote></div> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an e= mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind= ev+unsubscribe@googlegroups.com</a>.<br /> To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/= bitcoindev/14874ca7-853c-4468-a357-a76759e50bben%40googlegroups.com?utm_med= ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind= ev/14874ca7-853c-4468-a357-a76759e50bben%40googlegroups.com</a>.<br /> ------=_Part_31339_1368722702.1748560817651-- ------=_Part_31338_2014820662.1748560817651--