From: "'conduition' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
To: Nagaev Boris <bnagaev@gmail.com>
Cc: Jesse Posner <jesse.posner@gmail.com>,
Isabel Foxen Duke <isabel.duke@gmail.com>,
Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] PQC: Lattice-based signatures
Date: Wed, 27 May 2026 18:55:54 +0000 [thread overview]
Message-ID: <i6AhbPWFLhGBLEbaWlHepHwVSRg0Goa0ZOvHRs4RjZQGhMTwpXfWbyo23xVEkC8TMGsrU7P7hmz9hXYx5nKLj_NhPXfib_-hLE1jnDYTm9w=@proton.me> (raw)
In-Reply-To: <CAFC_Vt6wrrz+pVmOazHoJitTDQCbEswWDALKxiBLhFayYntVcg@mail.gmail.com>
[-- Attachment #1.1: Type: text/plain, Size: 19550 bytes --]
That's a very neat idea Boris!
However I'm pretty sure using a recoverable pubkey scheme will lead to loss of some security for the EC scheme. For instance, Schnorr with pubkey recovery precludes key-prefixing, which is necessary to avoid related-key attacks on BIP32. From BIP340:
> Key prefixing Using the verification rule above directly makes Schnorr signatures vulnerable to "related-key attacks" in which a third party can convert a signature (R, s) for public key P into a signature (R, s + a⋅hash(R || m)) for public key P + a⋅G and the same message m, for any given additive tweak a to the signing key. This would render signatures insecure when keys are generated using BIP32's unhardened derivation and other methods that rely on additive tweaks to existing keys such as Taproot.
Maybe ECDSA would be a viable option though, due to its non-linearity? But then we give up the nice linear properties of Schnorr of course.
Clever idea to reuse the EC nonce as the SHRINCS randomizer. For security, the SHRINCS randomizer needs to be sampled from a PRF that ingests `SK.prf` and the message to sign. A straightforward approach would be to simply reuse the same PRF to generate a scalar nonce `r`, then use `xonly(r*G)` as the randomizer. Even if a CRQC can factor and find `r`, the randomizer `r*G` is still randomly distributed among the secp256k1 curve, so no security is lost there on the SHRINCS side I think.
I will note the SHRINCS randomizer is actually being shrunk from 32 bytes to 16 bytes, to better align with SLH-DSA and XMSS standards, so reusing the EC nonce only saves 16 bytes, not 32 bytes, but still pretty cool.
regards,
conduition
On Wednesday, May 27th, 2026 at 2:17 AM, Nagaev Boris <bnagaev@gmail.com> wrote:
> Note that if the hybrid scheme is implemented as a single
> construction, we can optimize its total footprint. Let's assume we do
> the SHRINCS + EC hybrid scheme. We can apply the following
> optimizations to get the same footprint as SHRINCS itself, plus 32
> bytes.
>
> 1. Use an EC signature with a recoverable public key. It could be
> ECDSA or a Schnorr with a public key recovery option (not exactly
> BIP-340).
>
> Then we can put the EC pubkey into the hybrid key commitment - no
> additional space! The verifier recovers the EC public key from the
> signature and message, then checks that it matches the hybrid key
> commitment. Then they just use the recovered EC pubkey as well as PQ
> pubkey to recompute the hybrid public-key commitment. No need to store
> EC pubkey separately.
>
> 2. We can also save 32 bytes of the total 64 bytes in the signature if
> we reuse the encoding of the EC signature's public nonce R to serve as
> the randomization field R of SHRINCS.
>
> So the total signature is just 32 bytes larger than a SHRINCS
> signature and the pubkey is of the same size - EC pubkey does not add
> to total pubkey size.
>
> However if the same policy is expressed as two consecutive Bitcoin
> Script opcodes, for example:
>
> <bip340_pubkey> OP_CHECKSIGVERIFY <shrincs_pubkey> OP_CHECKSHRINCSSIG
>
> then the EC public key must appear in the revealed script/witness for
> a Taproot script-path spend, and the two independent signatures cannot
> share the public nonce/randomization field. That loses both
> optimizations.
>
> On Tue, May 26, 2026 at 4:41 PM 'conduition' via Bitcoin Development
> Mailing List <bitcoindev@googlegroups.com> wrote:
> >
> > We can also do that with script.
> >
> > <bip340_pubkey> OP_CHECKSIGVERIFY <dilithium_pubkey> OP_CHECKDILITHIUMSIG
> >
> > Note this is an opt-in construction. The main argument in favor of a unified hybrid scheme is it prevents people from using a PQC CHECKSIG operation independently - which is presumed risky because the new scheme or implementation could have bugs.
> >
> > However that same restriction used for safety will eventually become dead weight after enough time has passed, so we need a way to relax it later.
> >
> > regards,
> > conduition
> >
> > On Tuesday, May 26th, 2026 at 3:29 PM, Jesse Posner <jesse.posner@gmail.com> wrote:
> >
> > I'm not suggesting this is the right approach, but I believe the rationale for a hybrid scheme would be to enable lattice signatures with their superior functionality over hash-based schemes, while hedging against a break in lattice security using BIP340.
> >
> > On Sat, May 23, 2026 at 8:44 AM 'conduition' via Bitcoin Development Mailing List <bitcoindev@googlegroups.com> wrote:
> >>
> >> Hi Isabel,
> >>
> >> I'm curious to get your thoughts on the following: it sounds like Dan is advocating for a hybrid scheme and I'm wondering if this would render the strategy of implementing different signatures at different times less practical? In other words, does it still make sense to implement something like SHRINCS before a lattice-based signature — if we're ultimately hoping to implement a single hybrid scheme as Dan proposes here?
> >>
> >>
> >> Argh, I'm a bit torn about the idea of a unified hybrid scheme. Like on one-hand, yes, technically if we wanted to maximize security and reduce misuse, we could do it. For example, SHRINCS+BIP340 in a single unified scheme. Or HAWK+BIP340. This would be strictly more secure than any of these individual schemes in isolation.
> >>
> >> But also, a unified hybrid scheme would immediately be handicapped and uncompetitive after Q-day. It would inflate witness sizes by around 100 bytes per input, and complicate signer code for no good reason (except arguably to mitigate statefulness risks). A hybrid scheme would create a technical debt we'd have to pay off later by migrating everyone to a pure PQC scheme, maybe even requiring another soft-fork. That kind of tech-debt is easier to pay off in a web2 world, but not so easy on a blockchain.
> >>
> >> Perhaps there is a way to engineer it such that we can soft-fork the ECC component of a hybrid-scheme out later without the need to migrate everyone. Or we can bind individual schemes together into a hybrid scheme using feature flags (e.g. each pubkey starts with a flag byte, where bit 0 turns on BIP340, and bit 1 turns on SHRINCS, etc), and let users migrate on their own without a follow-up soft-fork.
> >>
> >> However, I'm not convinced that any of this engineering complexity is necessary when you can achieve comparable security by hiding keys for classical and PQ schemes in two different P2MR script leaves, which was an OG defining use-case of P2MR.
> >>
> >> Or you can get almost exactly the same security, if you use both schemes in the same script leaf: Anyone who wants the security of a hybrid BIP340+SHRINCS scheme is free to implement it, and we could even write wallet standards for it. But to require everyone to use a hybrid scheme seems overkill to me, especially if we're talking about hash-based sigs which are arguably more classically secure than ECC (modulo the risks of stateful schemes).
> >>
> >> regards,
> >> conduition
> >> On Saturday, May 23rd, 2026 at 6:49 AM, Isabel Foxen Duke <isabel.duke@gmail.com> wrote:
> >>
> >> Hi Conduition,
> >>
> >> Nevermind on the hybrid scheme question -- Jonas explained in this thread that hybrid scheme is likely something that would happen on the wallet level (not consensus/opcode level), so this is now clarified on my end - thanks again for all your help!
> >>
> >> x Isabel
> >>
> >>
> >>
> >> On Friday, May 22, 2026 at 8:25:41 AM UTC-7 Isabel Foxen Duke wrote:
> >>>
> >>> Hi Conduition,
> >>>
> >>> So glad you enjoyed the interview! I'm thrilled Dan is speaking on quantum-issues more publicly these days :)
> >>>
> >>> Noted about threshold signatures and other features potentially being only theoretical and not truly practical with Lattice based signatures. I will bring this up with Dan and see if he has any comment here - or if he has updates that may affect thinking on this.
> >>>
> >>> I'm curious to get your thoughts on the following: it sounds like Dan is advocating for a hybrid scheme and I'm wondering if this would render the strategy of implementing different signatures at different times less practical? In other words, does it still make sense to implement something like SHRINCS before a lattice-based signature — if we're ultimately hoping to implement a single hybrid scheme as Dan proposes here?
> >>>
> >>> thanks for all your hard work on this
> >>>
> >>> Warmly,
> >>> Isabel Foxen Duke
> >>>
> >>> On Thursday, May 21, 2026 at 12:29:21 PM UTC-7 conduition wrote:
> >>>>
> >>>> Hey Isabel, I watched the interview, very cool stuff. I loved seeing Dan dodge your question about the mysterious "restrictions" google was under (hello NSA).
> >>>>
> >>>> Dan is right that lattice-based crypto offers the promise of algebraic structure, whereas hash-based crypto offers none. Having open research avenues towards goals like threshold signatures is a great thing. Yet the promise of the algebraic structure in lattices hasn't materialized into anything usable. At least, there are no schemes - yet - which tick the boxes we need. At best we have hope for future developments. Lattice threshold and key-rerandomization schemes will likely improve from where they are now, but until proven otherwise we should make choices about consensus based on what we have, not what we hope we will have someday.
> >>>>
> >>>> Also, in the interview Dan acted as though deploying hash-based signatures would preclude the deployment of lattice crypto later. It doesn't. If we deploy a more cutting-edge cryptosystem like HAWK or SQIsign, it will be once we have a suitably flexible and compact schemes ready to build atop it, and when that happens we will still be glad to have hash-based crypto as a backstop in case the cutting-edge assumptions (or implementations) are busted.
> >>>>
> >>>> regards,
> >>>> conduition
> >>>> On Wednesday, May 20th, 2026 at 3:47 PM, Isabel Foxen Duke <isabe...@gmail.com> wrote:
> >>>>
> >>>> FWIW —
> >>>>
> >>>> "I would actually like to push for lattice-based signatures..." says Dan Boneh in new interview out this morning (1:11:00)
> >>>>
> >>>> He primarily cites algebraic structure as allowing greater functionality - and is concerned that features like threshold signature schemes will be much harder to implement with hash-based signatures.
> >>>>
> >>>> -Isabel Foxen Duke
> >>>>
> >>>> On Tuesday, May 19, 2026 at 8:27:40 PM UTC-7 conduition wrote:
> >>>>>
> >>>>> Hey Nikita, thanks for broaching the idea.
> >>>>>
> >>>>> I can't speak for Blockstream, but as to the spirit of your question - Why people are looking at hash-based sigs more than lattices - I can think of four major reasons:
> >>>>>
> >>>>> 1. Conservatism. Hash based signatures are incredibly conservative. They rely on strictly weaker assumptions than what we already depend on for other things. No other family of signatures can claim this property, and for something as inflexible-yet-sensitive as Bitcoin, conservativism is appealing.
> >>>>>
> >>>>> 2. Simplicity. Hash-based signatures are easier to grasp, simpler to prove secure, and easier to implement compared to almost anything else (even simpler than ECC). We Bitcoiners tend to clutch our pearls in fear of trusting flawed assumptions... but in reality most vulnerabilities are not cryptographic in nature: Most are implementation failures. Hash-based sigs are harder (but not impossible) to screw up. An experienced engineer can implement FIPS-205 (SPHINCS) in a weekend, or less with AI tools. This simplicity also makes hash-based sigs easier to pitch during consensus debates: It's harder to fear something once you understand it.
> >>>>>
> >>>>> 3. Efficiency. Hash-based sigs are surprisingly fast to verify [0]. Their cost-per-byte is way lower than Schnorr. If you can bite the statefulness bullet, hash-based sigs can even be compact (and still fast). There remains some hope we might be able to use them as a daily driver if CRQCs appear faster than anticipated. This efficiency comes at a price of course, but that price is paid by the signer implementation while verifiers remain slim, quick, and secure.
> >>>>>
> >>>>> 4. Future-proofing. Because of their conservatism, hash-based sigs stand a better chance of remaining secure over a long time-frame, so it seems more likely we could rely on them to fulfill a long-term fallback role. We will likely someday need to deploy a new cryptosystem to replace ECC as a daily driver if ECDLP is broken, whether classically or by a CRQC. When/if this happens, we'll be REALLY glad we added hash-based sigs first, because then we'll have something to use if the novel scheme's assumptions (or more likely, implementation) are broken.
> >>>>>
> >>>>> This is not to say we shouldn't be researching lattices. Or isogenies, or anything else for that matter. We need to know what's possible, and to educate the community about the options we have. I'm glad to see Blockstream funding this important work. I view hash-based sigs as the first episode of a decades-long saga, but unfortunately we lack enough knowledge to know what should come next. Maybe that is lattices? maybe something else. With time, effort, and (hopefully) funding, we shall find out.
> >>>>>
> >>>>> If I had to pen a wishlist of stuff I'd like to see from lattice crypto research, this would be it:
> >>>>>
> >>>>> - [ ] compact keys and sigs. Ideally, less than a kilobyte witness size total, but I'd be happy with at least a twofold improvement over what stateless hash-based sigs can offer.
> >>>>> - [ ] rerandomization e.g. BIP32 unhardened derivation. This has been done [1], but AFAIK it is impossible without massively expanding the sizes of keys and/or signatures.
> >>>>> - [ ] a multisignature scheme, or a threshold protocol with a DKG. Again, never seen this without massive keys and sigs, but I see no reason why it should be impossible.
> >>>>> - [ ] integer-only arithmetic. Falcon keys and sigs are smaller than ML-DSA, but it comes at the expense of complex floating point arithmetic headaches. It'd be nice if we could do away with that.
> >>>>> - [ ] signature aggregation. This is a more general wish of any PQ scheme, and if someone can do it, even with somewhat large sigs or poor performance, it might make the whole scheme way more palatable, in tandem with a CISA proposal.
> >>>>>
> >>>>> Also see this relevant delvingbitcoin thread [1] for more sources.
> >>>>>
> >>>>> regards,
> >>>>> conduition
> >>>>>
> >>>>> [0]: https://conduition.io/code/fast-slh-dsa-verification/
> >>>>> [1]: https://delvingbitcoin.org/t/post-quantum-hd-wallets-silent-payments-key-aggregation-and-threshold-signatures/1854/
> >>>>>
> >>>>> On Tuesday, May 19th, 2026 at 9:06 PM, Nikita Karetnikov <nik...@karetnikov.org> wrote:
> >>>>>
> >>>>> > Dear list,
> >>>>> >
> >>>>>
> >>>>> > I hate to contribute to the recent flood of PQC posts, but I think it’s an important issue that’s worth discussing.
> >>>>> >
> >>>>>
> >>>>> > In particular, what I usually see is various competing proposals without a clear winner.
> >>>>> >
> >>>>>
> >>>>> > So I’d like to bring everyone’s attention to this new post from Blockstream:
> >>>>> > https://blog.blockstream.com/schnorr-but-with-vectors-lattice-based-signatures-explained/
> >>>>> >
> >>>>>
> >>>>> > This post is interesting because unlike a lot of PQC discussions, it actually includes a comparison table of various approaches, where lattices seem to come out ahead.
> >>>>> >
> >>>>>
> >>>>> > This raises a few questions.
> >>>>> >
> >>>>>
> >>>>> > Since lattices are not a new topic in cryptography, why has Blockstream focused their efforts on hash-based approaches so far?
> >>>>> > Are hashes seen as a more conservative choice?
> >>>>> >
> >>>>>
> >>>>> > Given the problems with hashes outlined in the post, are lattices actually the current most likely candidate for a PQC implementation?
> >>>>> > If so, should the community effort be focused on lattices instead of other proposals?
> >>>>> > Or is the comparison table not telling the whole story?
> >>>>> >
> >>>>>
> >>>>> > I’d like to hear your thoughts on the topic.
> >>>>> >
> >>>>>
> >>>>> > Thanks,
> >>>>> > Nikita
> >>>>> >
> >>>>>
> >>>>> > --
> >>>>> > 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 email to bitcoindev+...@googlegroups.com.
> >>>>> > To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/ffa56d63-32c6-4fc3-a150-4fe62ac2e00b%40app.fastmail.com.
> >>>>> >
> >>>>
> >>>> --
> >>>> 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 email to bitcoindev+...@googlegroups.com.
> >>>>
> >>>> To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/42faeb16-5d01-41ba-a192-e05936b84248n%40googlegroups.com.
> >>>>
> >>>>
> >> --
> >> 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 email to bitcoindev+unsubscribe@googlegroups.com.
> >> To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/ce98d232-4f6b-456b-ac3e-a1df12fa91ecn%40googlegroups.com.
> >>
> >>
> >> --
> >> 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 email to bitcoindev+unsubscribe@googlegroups.com.
> >> To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/01s-bZes3N5535LMO_sAysU1tdXtsRsaFt130av-xvYrDmZiopXZ7Y0mRkwQzKV0PJJCZZBIx6IXOsdqhszyDcz_F6AU0nzsYHh7_N70jkA%3D%40proton.me.
> >
> > --
> > 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 email to bitcoindev+unsubscribe@googlegroups.com.
> > To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAL3ujSqcOhwga_edaYs3WfEFOLYS%2BBfMj1rG2%3D%3D%2BfydxPczd-g%40mail.gmail.com.
> >
> >
> > --
> > 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 email to bitcoindev+unsubscribe@googlegroups.com.
> > To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/BEYEntuP_982nSOJVg_e4oIDBg0XQWyhLtMSSdB31ue1iAvMLtksMiuJS0wF-QJGKIKGuWeSWCtOZnDxz__yQgTagnUSDfcwicYQ-QHjvko%3D%40proton.me.
>
>
>
> --
> Best regards,
> Boris Nagaev
>
--
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 email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/i6AhbPWFLhGBLEbaWlHepHwVSRg0Goa0ZOvHRs4RjZQGhMTwpXfWbyo23xVEkC8TMGsrU7P7hmz9hXYx5nKLj_NhPXfib_-hLE1jnDYTm9w%3D%40proton.me.
[-- Attachment #1.2: publickey - conduition@proton.me - 0x474891AD.asc --]
[-- Type: application/pgp-keys, Size: 649 bytes --]
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 343 bytes --]
next prev parent reply other threads:[~2026-05-27 20:29 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-05-19 19:33 [bitcoindev] PQC: Lattice-based signatures Nikita Karetnikov
2026-05-20 3:18 ` 'conduition' via Bitcoin Development Mailing List
2026-05-20 9:56 ` 'Mikhail Kudinov' via Bitcoin Development Mailing List
2026-05-20 10:35 ` Alex
2026-05-20 17:58 ` Isabel Foxen Duke
2026-05-21 19:16 ` 'conduition' via Bitcoin Development Mailing List
2026-05-22 15:22 ` Isabel Foxen Duke
2026-05-23 13:48 ` Isabel Foxen Duke
2026-05-23 15:38 ` 'conduition' via Bitcoin Development Mailing List
2026-05-26 21:28 ` Jesse Posner
2026-05-26 21:38 ` 'conduition' via Bitcoin Development Mailing List
2026-05-27 6:16 ` Nagaev Boris
2026-05-27 18:55 ` 'conduition' via Bitcoin Development Mailing List [this message]
2026-05-28 5:48 ` Nagaev Boris
2026-05-28 18:37 ` 'conduition' via Bitcoin Development Mailing List
2026-05-21 20:15 ` Voltairine
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='i6AhbPWFLhGBLEbaWlHepHwVSRg0Goa0ZOvHRs4RjZQGhMTwpXfWbyo23xVEkC8TMGsrU7P7hmz9hXYx5nKLj_NhPXfib_-hLE1jnDYTm9w=@proton.me' \
--to=bitcoindev@googlegroups.com \
--cc=bnagaev@gmail.com \
--cc=conduition@proton.me \
--cc=isabel.duke@gmail.com \
--cc=jesse.posner@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox