1. 6
    1. 5

      Great pragmatic blog post overall. A few comments:

      Kyber decryptions have a failure probability of about 1 in 2^160.

      An algorithm that straight up outputs its own private keys to the adversary with probability 2^-160 could still be proven secure in the computational model. I disagree with this as a criticism, efficient crypto is largely built around these sort of things.

      but I contend that a nonzero risk means they cannot be used in sealing APIs for general purpose cryptography libraries, since the developers of that library cannot be responsible for the decryption failure risk calculus for all of its users.

      With XChaCha, Daniel Bernstein decided for all of us that 2^-192 is large enough never to have to practically worry about IV collisions (birthday bound gives 96 bits of security there). Sometimes cryptography has to make these decisions because the tradeoffs are e.g. those large public keys you mentioned in Classic McEliece. Once we can do better, we will! Promise!

    2. 1

      Kyber decryptions have a failure probability of about 1 in 2^160.

      This is substantially less than the chance that a cosmic ray interferes in the computation of the algorithm, in which case you would get nonsense out with any algorithm.

      In fact without looking into these algorithms further, I’m willing to bet that the 200KB keys have a worse real-world chance of screwing up because there’s more memory in which bits can be swapped.