What you got now as new standards is already the result of multiple iterations of improvements in key size reductions and performance improvements. But you'll likely not get drop-in replacements for existing public key crypto in post-quantum variations. It appears signatures are even more challenging regarding size than encryption in the post-quantum world.

It may be worth noting that choosing the algorithms that are now chosen, which are primarily lattice-based, is already kinda a compromise. They're not the ones with the highest trust in security, which would've been McEliece and SPHINCS (though the latter has been standardized as a fallback). But those come with key and signature sizes that are entirely impractical for the most common use cases.

It appears most of the crypto community came around thinking that the somewhat-smaller lattice algos are now "almost certainly secure". But surely there's at least one famous cryptographer raising his voice that he still has concerns.

Yes, Kyber (ML-KEM) ciphertexts can be compressed somewhat when you are sending the same message to multiple recipients. See https://csrc.nist.gov/csrc/media/Events/2024/fifth-pqc-stand... for details:

> "Asymptotically, the size of an mKyber multi-recipient ciphertext is 16 times smaller than the sum of the sizes of N Kyber ciphertexts.”

There’s a whole zoo of useful variants on the “KEM” idea, but sadly NIST decided to standardise the least flexible variant. See my blog from a few years ago for some background on the literature: https://neilmadden.blog/2021/02/16/when-a-kem-is-not-enough/

AIUI part of the problem with size is due to hybrid setups. Size could probably be reduced if you only used a PQC algorithm instead of combining it with existing crypto.