A Brief Opinionated Overview of NIST’s Post-Quantum Cryptography Round 3 Candidates
16 comments · 71% upvoted · source · other discussions
comments
Thue
dcarroll9999
I would 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.
I don't feel like this is really concerning. Say a crypto library provided a signature scheme that used private keys with 128 bits of entropy (I think ed25519 is something like this?). If an application that used this library for identities, and there was a key collision (birthday problem so probability higher than 1/(2128)) would the crypto library be held responsible for the results? I'd say no.
bitwiseshiftleft
From a purist point of view I don't like decryption failures, but I've also made my peace with them. From sources I've read online, the number of meteors that hit Earth per day, and reach the ground, is in the single digits to low double digits. So a single square meter gets hit by around 2^-64 meteors per second. Computers are smaller than a square meter, and not all meteors are big enough to cause failure (if the deployment is inside), and maybe we care about time scales shorter than a second. So call the probability of failure due to meteor strike 2^-80 .
If Kyber has a decryption failure probability 2^-160 , then this is only a problem for deployments which are engineered to survive at least two simultaneous meteor strikes. Or, like, one really big meteor strike, or many simultaneous cosmic ray strikes. Or a nuclear war, or a supervolcano eruption, or ... basically nobody engineers to that failure rate, except for purism reasons.
Of course, it also has cryptographic implications, because decryption failures can be an attack avenue. But there have been several papers analyzing this kind of attack, and if the appropriate CCA transform is used, such an attack is extremely unlikely to work on something with so low a failure probability.
dcarroll9999
Yeah, I guess this just goes to show the elegance of the Diffie-Hellman exchange: it's so simple and it has zero decryption failure probability, something that's proven difficult to replicate in the post-quantum case.
bitwiseshiftleft
Yeah. It’s also not hard to make a lattice scheme with zero failure probability. NTRU-HRSS and NTRU prime/LPRime don’t fail. You just get a worse bandwidth vs security tradeoff, and you have to use a more complicated sampling algorithm.
But the only DH-like scheme in the competition is SIKE, which is quite slow and complicated.
GibbsSamplePlatter
We can also think of it as whatever secrets we are storing what mean time to failure do we allow. Still rubs me the wrong way a bit but maybe it's fine.
bitwiseshiftleft
Yeah, MTTF is the way to think about while actually engineering, and meteor strikes is how you defend it to a nontechnical customer :-)
The MTTF from a 2-160 failure probability is going to be like 1020something years of course.
espadrine
I don’t think it is a serious argument.
After all, the whole industry cranks out random <128-bit UUIDs that are not checked for collision all the time, and if a collision did happen, that user would have a very bad day.
Soatok
They happen, but only when using an insecure RNG like OpenSSL's.
Semaphor
TBH I'm surprised by seeing SIKE as an alternate.
Matic-Arabic1
Nice
Cryptography is full of schemes that fail with probabilities higher than 2-160. E.g. AES-128, the attacker has a probability of 2-128 of just guessing the key outright in one try. Add in birthday paradoxes etc.. Any computer you have, even with ECC, also have error rates bigger than 2-160. Network traffic error codes also have error rates bigger than 2-160. I assume that hard disk and RAID error codes also have error probabilities larger than that.
My understanding is that by best practice, a failure probability of 1 in 2160 is entirely reasonable, usable, and secure. Rejecting a scheme on the basis of this is unreasonable. Many other parts of any practical system will statistically fail long before you encounter this problem.
peterrindal 3 points · Aug 2020
2-160 is extremely small for a statistical error parameter. A cpu has a much higher fault rate. Bit flips happen...