Re: [bitcoindev] Algorithm Agility for Bitcoin to maintain security in the face of quantum and classic breaks in the signature algorithms

'Mikhail Kudinov' via Bitcoin Development Mailing List
2026-02-27T16:39:45Z

[-- Attachment #1: Type: text/plain, Size: 4876 bytes --]

Speaking of Lattice-Based solutions. There has been significant progress in
adopting PQ solutions in the real world. Signatures are not as widely
deployed, but the work is going on. There is a recent update from Apple:
https://support.apple.com/guide/security/quantum-secure-cryptography-apple-devices-secc7c82e533/web
.

An interesting point is that it does not use level 1 security for lattice
schemes (it offers level 3 or level 5, both for ML-KEM and ML-DSA). A
similar approach was used in Cloudflare:
https://blog.cloudflare.com/pq-2025/. More specifically, see this part:
https://blog.cloudflare.com/pq-2025/#ml-kem-768-and-x25519. Let me cite Bas
here: "There is a lot of trust in the (non post-quantum) security of
X25519: matching AES-128 is more than enough. Although we are comfortable
in the security of ML-KEM-512 today, over the coming decades, cryptanalysis
could improve. Thus, we'd like to keep a margin for now."
Cloudflare settles for a smaller margin for ML-DSA, but the reasoning is
that they can upgrade later if needed:
"ML-DSA-44 as level 2 is comfortably above level 1. It's indeed below
ML-KEM-768. I'd be comfortable with level 2 ML-KEM, but that doesn't exist.
Anyway, ML-DSA requires less margin as it doesn't suffer
store-now/decrypt-later. We can roll ML-DSA certs if attacks improve, but
we can't roll captured data encrypted with ML-KEM."
In our setting, switching to a new set of parameters is more difficult.
So, it seems reasonable that, if we are discussing a lattice-based
construction, we should also include some margin. That said, if we exclude
level 1 security, the smallest size we get is 3073 bytes for Falcon level
5. See https://pqshield.github.io/nist-sigs-zoo/ for a quick comparison.
Level 3 ML-DSA requires 5,261 bytes.

Of course, lattice constructions have more to offer than just smaller
sizes. Different schemes may allow for public key derivation, maybe more
efficient multi/threshold signatures, and so on. We should keep in mind
that, if we want to include a security margin for possible future
improvements, the sizes will be larger.

Best,
Mike

On Thu, Feb 26, 2026 at 4:56 PM Matt Corallo <lf-lists@mattcorallo.com>
wrote:

>
>
> On 2/23/26 4:42 PM, Ethan Heilman wrote:
> > > I thought "tweaking", in general, is lost in SPHINCS, as well as
> multiparty sigs. Be interested
> > to see those solutions. But, regardless, 17kb sigs are... not
> compatible with a decentralized
> > bitcoin, imo. Lattice-sigs are the only reasonable PQ way forward and
> they aren't ready yet.
> >
> > SPHINCS is ~8kb (7,888 bytes) not 17kb.
> >
> > SPHINCS SLH-DSA-128s has 32 byte public keys and 7,856 byte signatures
> > Total size of 7,888 bytes not 17kb.
> >
> > The Lattice sigs aren't that much better than SPHINCS
> >
> > CRYSTALS-Dilithium ML-DSA has 1,312 byte public keys and 2,420 byte
> signatures
> > Total size of 3,732 bytes.
> >
> > Falcon has 897 byte public keys and 666 signatures
> > 1,563 bytes
> >
> > ML-DSA currently has the most support in the Lattice world, but it is
> still too large to be a drop
> > in replacement for ECC without a witness discount. If we had to choose
> tomorrow, I'd advocate for
> > ML-DSA with a massive witness discount, but I'd be very unhappy with the
> witness discount. If the
> > witness discount was out of the question, then I'd advocate for
> something similar to 324-byte
> > stateful hash based SHRINCS signature. Neither is ideal.
> >
> > My current thinking is to use SLH-DSA as a backup. This keeps us safe if
> everything goes wrong and
> > allows us to reach safety early so we can take time to determine the
> right drop-in replacement for
> > ECC. Hopefully in 3 years, SQI-sign is fast enough to be considered.
>
>
> Why not just do SHRINCS today? The cost to use it in "stateless mode" is
> only marginally higher than
> other stateless hash-based signatures, and wallets can elect to use the
> stateful mode at signing
> time if they're set up for it.
>
> Matt
>
> --
> 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/1ee30c09-ca46-404f-a9f4-2ff8ff6a2c0b%40mattcorallo.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/CAPcK4uQvkjUAAvVxS2%2BgX8VBiXp5cnxvCURRtkJSOMU5wfRVHA%40mail.gmail.com.

[-- Attachment #2: Type: text/html, Size: 6213 bytes --]