Why cryptography is not based on NP-complete problems
26 comments
·February 13, 2025krackers
strulovich
Generally, all problems used for crypto are in NP. Since given the secret, you need to be able to compute it efficiently.
It’s just that being NP hard or complete is not enough.
The theoretical definition of one way functions is used to define cryptography. So reading on that my clarify this some more.
pclmulqdq
There is one cryptosystem that uses an NP-hard problem for its security: the McEliece cryptosystem. The problem used here is decoding a generalized version of an error correcting code, which can be made both NP-hard in theory and in practice if you use the right kind of code. It is reliant on using very specific algorithmic parameters to stay hard, though. However, the versions that are not broken are likely post-quantum ready.
zeroonetwothree
> For example, it could be possible that, if we generated a random map in some way, 99% percent of the time, the three-color map coloring problem would be easy, but 1% of the time, it would be very difficult.
> This would still be NP-complete, but would make for a terrible cryptosystem - a scheme based on this problem would be easily broken 99% of the time!
I don’t think this explanation is great. We could just generate instances until we found the hard one and then use it. So the answer is more complex than just as written.
cobbal
The point is not that all NP hard problems make bad cryptosystems, but rather the NP-hardness guarantee fails to translate into a useful guarantee for a cryptosystem.
It's about the proof, not the computation.
ethanwillis
Can you explain your usage of NP hard in your comment?
saghm
A problem being NP-hard is one of the two requirements of being in NP-complete (the other being that it's NP). If I remember correctly, problems that are NP-hard without being NP are undecidable, so in contexts like "what problems can we base cryptography on?", it's basically the same as saying NP-complete, since we aren't able to base cryptography on undecidable problems.
Vervious
how do you know if an instance you picked is hard?
Another problem with your suggestion: Do we even know that a 1/polynomial sized fraction of 3-coloring instances are hard? (Else you'll never sample one). (NP-Hardness certainly does not give such a guarantee, even though it sounds weak)
goalieca
RSA is kind of shaky like this. You generate key and then run some tests hoping it’s “good”. Most of the time it isn’t so you try again. Many products have failed because they were not.
adgjlsfhk1
this mostly isn't true. for much smaller keys there were risks of "weak primes", but as general purpose factoring algorithms got better and pushed keys bigger a higher and higher percent of primes end up safe. with 2048 bit primes, the odds of your prime being significantly weaker than average drop to something like 1 in 2^1024
alexey-salmin
I'd also note that zero-knowledge proofs (which are considered a branch of cryptography) often do rely on NP-complete problems like the three-color maps.
Vervious
That's completely unrelated, the reliance there is because you want to be able to prove "any statement in NP" in zero knowledge. It then suffices to give a protocol for just 3-colorings, because "any statement in NP" can then be reduced to a 3-coloring.
ars
How do you know which ones are the hard ones? I don't think it's easy to figure that out.
delifue
The RSA problem in article doesn't mention that RSA's difficulty is based on MODULUS prime factorization, not simple prime factorization.
fenomas
There's a footnote along these lines that links to the actual algorithm.
LegionMammal978
Are there any known attack methods that don't involve factoring the public key into two primes?
bmenrigh
Yeah but they usually require RSA to be used in some rather unusual and bad way.
For example, encrypting one message with many different public keys can be broken with chinese remainder theorem and Nth roots. This reveals the message without factoring any key. This is why randomized padding (among other things) is a must with RSA.
userbinator
Aren't hash functions a counterexample? There have been attempts at using SAT solvers to find preimage and collision attacks on them.
elchananHaas
Yes, this article is only talking about asymmetric cryptography. Symmetric cryptography and hashes are based on NP complete problems.This is only when generalized appropriately, most individual hashes/ciphers are fixed so there isn't really a way to talk about their complexity. The broader class of block cipher like problems is NP complete, and very hard.
westurner
SAT Solvers, GA, LLMs, brute force
Birthday paradox probability changes with memoization.
Rainbow tables trade CPU for storage for lookup; but salting, double hashing, and key derivation functions with many rounds like pbkdf and argon2.
tines
Some of the graphics have black text on a transparent background and so are hard to read with a dark theme.
tofof
It's unfortunate that he doesn't understand complexity analysis and has taken it upon himself to write an article that requires it as an underpinning.
In particular, I stopped reading at
> the discrete logarithm for elliptic curves, ... We don’t technically know whether these are NP-complete
This is wildly misleading. We do know with absolute certainty that the decision problem for DLC is NP-Hard, and therefore that EPDLC inherits at least NP-Hardness. While it is true that their presence in NP-Hard does not require their pressence in NP (and thus are not proved NP Complete), it is misleading to characterize as the author has here that they are weaker than NP, instead of the known certainty that NP is the absolute minimum bound for their hardness.
JohnKemeny
DLC is in NP and co-NP. Very unlikely to be NP-hard. It is usually listed as one of the candidates for problems that are NP-intermediate, ie, problems in-between P and NP-hard (should they be different).
See e.g. https://cs.stackexchange.com/a/2765
cevi
If the discrete logarithm problem is NP-hard, then I will eat my hat. The discrete logarithm problem can be solved by Shor's algorithm on a quantum computer, placing it in the complexity class BQP. Anyone who claims that BQP contains an NP-hard problem is selling something - I would bet at a trillion-to-one odds against such a claim (if there were any hope of definitively settling the problem).
Vervious
Not sure it's misleading, he did write the word "technically", and anyone who knows what NP-complete is knows that NP-hard does not necessarily mean NP-complete. I am a cryptographer and the article is fine.
Also, do you have a citation for "We do know with absolute certainty that the decision problem for DLC is NP-Hard"
The article is a bit confusing (to me as a layman), basically as I understand it's saying that the reason we can't form cryptosystems out of arbitrary NP-complete problems is because there exist randomized algorithms that work for 99% of inputs (average vs. worst-case complexity, e.g. why the simplex algorithm works in practice). But there are some things missing:
* We know that randomized algorithms exist for NP-complete problems. But couldn't we have some problem in NP that while reducible to e.g. 3SAT always reduce to "very hard" instances?
* Conversely, there's no guarantee that there doesn't exist a randomized algorithm for something that's NP-hard (and not in NP), right?
The argument along the lines of NP-complete vs NP-hard seems to be a non-sequitur, since the actual distinction is average vs. worst-case hardness right? It may just so happen that all currently known problems in NP are easy "on average", but I don't think that's formally guaranteed.
Edit: https://theory.stanford.edu/~trevisan/average/slides.pdf seems to imply that (1) is an open question.