And many problems, namely, enormous keys and signatures that make PKI nigh impossible for the embedded/IoT space.
> This variety of different trade-offs gives developers a lot of flexibility. For an embedded device where speed and bandwidth are important but ROM space is cheap, McEliece might be a great option for key establishment. For server farms where processor time is cheap but saving a few bytes of network activity on each connection can add up to real savings, NTRUSign might be a good option for signatures. Some algorithms even provide multiple parameter sets to address different needs: SPHINCS+ includes parameter sets for “fast” signatures and “small” signatures at the same security level.
I also think the article is overly optimistic claiming that ECC is “hard” because of the need for careful curve selection (even though we have very good established curves), but I find it hard to believe that PQ algorithms are immune to parameter selection problems and implementation challenges.
[0] https://web.archive.org/web/20110401080052/https://www.cdc.i...
[1] https://news.ycombinator.com/item?id=33925383 I wrote about this "Dahmen-Krauß Hash-Chain Signature Scheme" (DKSS) algorithm previously in a comment a couple of years ago
To be clear my comment is specifically only relating to signature schemes, not encryption.
> The state is enormous
The scheme I linked to points towards efficient "pebbling" and "hash chain traversal" algorithms which minimize the local state required in quite a fascinating way (e.g. see https://www.win.tue.nl/~berry/pebbling/).
> tracking state across components and through distribution channels
Assuming you have reliable ordering in those channels I don't see how the stateful nature of such schemes makes it hugely more complex than the essential hard problem of key distribution.
Lattice-based algorithms are around 1kb.