PQC: Lattice-based signatures

[Nikita Karetnikov]

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

[conduition]

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/

> --
> 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.
>

[Mikhail Kudinov]

The floating-point arithmetic of Falcon can be solved with integer simulation. This makes the algorithms less efficient, but still more efficient than SLH-DSA.

Best,
Mike

[Alex]

>  Hash based signatures are incredibly conservative.

Yes exactly. Hash based signatures like SHRINCS (324 byte signatures) are basically abstractions above the hash function (SHA256) which is already a security assumption (it already must protect block integrity and Merkle trees). This means, if SHA256 is weakened and needs replacing, technically you could introduce SHA3 without needing to change anything above it (like SHRINCS). So hash based signatures are incredibly "forwards compatible" abstractions.

This is not the case for new signature algorithms which otherwise would be ideal (like SQIsign). And since Bitcoin is mainly battling conservative forces, pushing for a conservative fix (hash based signatures) is far more likely to reach consensus (in my estimation).

[Isabel Foxen Duke]

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

[conduition]

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

To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/42faeb16-5d01-41ba-a192-e05936b84248n%40googlegroups.com.

[Voltairine]

Hi Emily,

Many would agree that lattice-based schemes are preferable in nearly every way to the rather impractical hash-based schemes. Still, the algebraic structure of modules over polynomial rings falls well short of offering the functionalities bitcoin users would most wish to see retained. Perhaps you could say more about the particular advantages you perceive these structures bringing to bitcoin? 

cordially,

V

[Isabel Foxen Duke]

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

[Isabel Foxen Duke]

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

[conduition]

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

To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/ce98d232-4f6b-456b-ac3e-a1df12fa91ecn%40googlegroups.com.

[Jesse Posner]

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.

To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/01s-bZes3N5535LMO_sAysU1tdXtsRsaFt130av-xvYrDmZiopXZ7Y0mRkwQzKV0PJJCZZBIx6IXOsdqhszyDcz_F6AU0nzsYHh7_N70jkA%3D%40proton.me.

[conduition]

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

To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAL3ujSqcOhwga_edaYs3WfEFOLYS%2BBfMj1rG2%3D%3D%2BfydxPczd-g%40mail.gmail.com.

[Nagaev Boris]

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

> 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

[conduition]

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

[Nagaev Boris]

On Wed, May 27, 2026 at 1:55 PM conduition <condu...@proton.me> wrote:
>
> 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.

There is an approach that seems to preserve public-key recovery and
Schnorr linearity while avoiding the related-key issue.

Start from BIP340-style Schnorr, but prefix the challenge with the
final hybrid public key rather than with the raw EC public key P:

s*G = R + H(R || P || m)*P

becomes:

s*G = R + H(R || hybrid_pk || m)*P

Here hybrid_pk commits to both the PQ root and P. The verifier already
knows hybrid_pk from the pkscript (which is the source of truth), so
there is no circular dependency: compute the challenge, recover P from
the Schnorr equation, reconstruct the PQ root from the PQ signature,
and check that both recompute hybrid_pk.

The related-key attack no longer works because tweaking P changes
hybrid_pk, which changes the challenge. In particular, a signature for
one BIP32-derived key cannot be converted into a valid signature for a
neighboring key in the same derivation family.

For the PQ side, the message hash should also be bound to the final
hybrid key rather than only to the standalone PQ key. This prevents
extraction of a PQ signature from a hybrid signature and reusing it
independently, so EC and PQ signatures are strongly glued together.

This is a deviation from what is currently deployed, and it would need
a formal security argument. But the Schnorr signing equation remains
linear, so the EC side should remain compatible with
MuSig2/FROST-style aggregation.

[conduition]

So you'd essentially be computing:

e = H(R || hybrid_pk || m)
P = e^{-1} * (s*G - R)

i.e. the same as BIP340 Schnorr, but hashing a commitment to the pubkey instead of the actual pubkey.

By binding the signature to a specific `hybrid_pk` you prevent any related-key attacks, including the fact that a valid signature from `P` cannot be applied to other hybrid keys - even if they commit to the same `P`.

Also note that this structure prevents a CRQC from factoring P until they see the first signature.

Seems reasonable. This would definitely break batch verification but we're going to have to give that up anyway in a PQ-world.

Does this break xonly arithmetic? Well if P is never put on-chain explicitly, we don't really need to care about shaving a byte off the public key, so the question is really whether the nonce R will let us recompute the correct public key if we elide its parity byte. And this is easy to engineer: Just negate R (and its discrete log) before signing if R has odd parity. Then you can encode x(R) in the signature and challenge hash, and the recovered pubkey is always correct.

This is a very clever idea. Seems like we'd shave about 48 bytes off the witness compared to a naive two-opcode script.

-16 bytes by removing the SHRINCS randomizer
-32 bytes by removing the Schnorr pubkey

Or about 48 bytes larger than bare SHRINCS:

+32 bytes for the Schnorr `s` component
+32 bytes for the Schnorr `R` component
-16 bytes by removing the SHRINCS randomizer

I'm still not fully convinced a hybrid scheme is ideal, since I expect the majority of users will not use hybrid scripts anyway - they'll use hybrid P2MR trees with one leaf per sig algo - but this is at least worthy of consideration when weighing options.

regards,
conduition