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