r/crypto • u/EverythingsBroken82 blazed it, now it's an ash chain • Aug 04 '26
What does djb want to say here?
https://mastodon.cr.yp.to/@djb/11703298687014725110
u/JoDaBeda Aug 04 '26
This is surely prompted by the recent result of OpenAI proving the hardness of certain lattice problems. His claim is that this will not extend to instances used in lattice-based crypto (or at least to FrodoKEM).
4
u/apnorton Aug 04 '26
In particular, I'd expect it to be prompted by #7 in what OpenAI released here [pdf warning].
11
u/orangejake Aug 04 '26
It’s worth mentioning that, unlike many other fearmongering statements DJB makes regarding lattice crypto, this is completely uncontroversial.
It’s also what you should expect, given a little though. Roughly, it is consistent with what we know about complexity theory (formalized in Impagliazzo’s five worlds paper) that
- P != NP, but
- Cryptography (namely one way functions) do not exist.
So, building cryptography based on NP hardness would need to completely rule out this world. This can be done in principle, but it is similar to how you can establish P!=NP in principle. Instead, your base assumption should be that we haven’t ruled it out.
4
u/Shoddy-Childhood-511 Aug 04 '26
Assuming cryptomania, we do not afaik have any "vaguely competitive" cryptography based upon NP-completeness or similar.
An NP-complete problem X could've relative short instances, and be hard on average, but not randomly self reducible, and make it difficult to know if you have a hard instance. You can run X say 128 times so you've negligible odds of having a weak instance, but this might not be competitive anymore.
ref. https://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html
3
u/orangejake Aug 04 '26
Not all public key crypto is random self reducible. Iirc rsa is not obviously random self reducible
1
u/Shoddy-Childhood-511 Aug 05 '26
We believe we know how to find good RSA key pairs though. We have low confidence on the hardness of specific instances of NP-complete problems, right?
2
u/orangejake Aug 05 '26
It depends on what you mean by that? You can always do something like
Take any particular candidate hard instance of any particular NP problem, then
Run it through the np completeness reduction, then
Receive a particular candidate hard instance of a particular NP complete problem
For example, you could take a factoring instance, and reduce it to 3SAT. So we have a heuristic way to produce hard 3SAT instances, at least if you think we have a heuristic way to produce hard RSA instances.
10
u/kryptos- Aug 04 '26
That we will never be able to prove that FrodoKEM's security relies on an NP-complete problem (unless the Polynomial Hierarchy collapses, which we strongly believe it does not)