Remix.run Logo
moi2388 7 hours ago

Fair, but recently several PQ algorithms have been shown to in fact not be secure, with known attacks, so I wouldn’t equate them

tptacek 7 hours ago | parent | next [-]

Which PQ algorithms would you be referring to here?

nick238 4 hours ago | parent [-]

https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography... and search for "published attacks".

tptacek 4 hours ago | parent [-]

Why don't you go ahead and pick out the attacks in here that you think are relevant to this conversation? It can't be on me to do that, because obviously my subtext is that none of them are.

sophacles 7 hours ago | parent | prev [-]

Interesting. I'd like to learn more about this - where can I find info about it?

mswphd 3 hours ago | parent [-]

they're almost assuredly talking about two things (maybe 3 if they really know what they're talking about, but the third is something that people making this argument like to pretend doesn't exist).

1. the main "eye catching" attack was the [attack on SIDH](https://eprint.iacr.org/2022/975.pdf). it was very much a "thought to be entirely secure" to "broken in 5 minutes with a Sage (python variant) implementation" within ~1 week. Degradation from "thought to be (sub-)exp time" to "poly time". very bad.

2. the other main other "big break" was the [RAINBOW attack](https://eprint.iacr.org/2022/214.pdf). this was a big attack, but it did not break all parameter sets, e.g. it didn't suddenly reduce a problem from exp-time to poly-time. instead, it was a (large) speedup for existing attacks.

anyway, someone popular among some people in tech (the cryptographer Dan Bernstein) has been trying (successfully) to slow the PQC transition for ~10 years. His strategy throughout has been complaining that a very particular class of scheme ("structured LWE-based schemes") are suspect. He has had several complaints that have shifted throughout the years (galois automorphism structure for a while, then whatever his "spherical models" stuff was lmao). There have been no appreciable better attacks (nothing like the above) on them since then. But he still complains, saying that instead people should use

1. NTRU, a separate structured lattice scheme (that he coincidentally submitted a scheme for standardization with). Incidentally, it had [a very bad attack](https://eprint.iacr.org/2016/127) ~ 2016. Didn't kill PQC, but killed a broad class of other schemes (NTRU-based fully homomorphic encryption, at least using tensor-based multiplication)

2. McCliece, a scheme from the late 70s (that has horrendously large public keys --- people avoid it for a reason). He also submitted a version of this for standardization. It also had a [greatly improved attack recently](https://eprint.iacr.org/2024/1193).

Of course, none of those are relevant to improved attacks on the math behind ML-KEM (algebraically structured variants on ring LWE). there have been some progress on these, but not really. It's really just "shaving bits", e.g. going from 2^140 to 2^135 type things. The rainbow attack (of the first two, the "mild" one) reduced things by a factor ~2^50, which is clearly unacceptable.

Unfortunately, because adherents of Dan Bernstein will pop up, and start saying a bunch of stuff confidently that is much too annoying to refute, as they have no clue what the actual conversation is. So the conversation becomes

1. people who know things, who tend to not bother saying anything (with rare exceptions), and 2. people who parrot Dan's (very wrong at this point honestly, but they've shifted over time, so it's more of 'wrong' and 'unwilling to admit it was wrong') opinions.

the dynamic is similar to how when discussions of vaccines on the internet occur, many medical professionals may not bother engaging, so you'll get a bunch of insane anti-vax conspiracies spread.

tptacek an hour ago | parent [-]

For whatever it's worth I think I cosign all of this.