correct me if I am wrong as I havent spent much time looking into it, but the security analysis essentially says "we assume the Goppa code is indistinguishable from a random code so the best attack is to do generic decoding for a random code (NP-hard problem)". but there is no reduction to some NP-hard problem that Goppa code (the specific code used in Classical McEliece) is indistinguishable.
the assumption is reasonable as nobody has been able to find a distinguisher for decades. also, if a distinguisher exists, it also doesn't translate into a direct attack against the system, it just means you cannot rule out "structural attacks" and jump to NP-hard problem.
(And this is even with the simplification that polytime = practical and not-polytime = infeasible.)
* 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.
What it comes down to is that there are phase transitions in computational systems that depend on how constrained the problem is.
Consider a sudoku puzzle. If the board is almost empty of numbers then it's easy to solve. If the board is almost full of numbers it's easy to solve. But there's some critical amount of numbers filled in (say half of them) that makes the sudoko most difficult to solve. That's where the phase transition is.
The notion of a phase transition comes from thermodynamics where ice becomes water becomes gas.
Here's an early paper on phase transition is AI.
https://www.sciencedirect.com/science/article/pii/0004370287...
Here's a later one on phase transitions for the satisfiability problem (SAT).
2) Randomized polynomial-time algorithms don't exist for NP-hard problems unless P = NP (iirc).
I think you have the right intuition. The issue is that right now cryptography is built on top of relatively "fragile" "average-case hard" problems -- discrete log, lattice stuff, etc. They are hard by assumption and we really don't know how to study them. (I would bet on some of this stuff being broken in our lifetimes).
It'd be really nice to instead base cryptography on an assumption that we are much more confident in being true, i.e. worst-case hardness of 3SAT. (I mean, who is going to prove P=NP). There are two steps:
1) First, show cryptography from average-case hardness of a "more believable" problem.
2) Second, to show average-case hardness of that problem is implied by the worst-case hardness of an NP-complete problem.
(1) is sort of better studied now, with a line of work on meta-complexity. (2) I believe is wide open, as previously mentioned.
Anyways I'm not really an expert in this area, but it's really quite fascinating.
For example, it's really nice to have a problem generator which make a series of hard problems, for things like benchmarking. It's very common that someone comes up with such a system, then someone ends up finding a way of solving "almost everything" that the random generator makes, by finding a good way of finding solutions to the solvable problems, and/or finding a way to easily prove unsolvable problems have no solutions.
The second category tends to be more interesting, it ends up being really hard to make large random unsolvable problems which don't end up including some kind of "flaw" with high probability, where the flaw ends up being easy to find, and easily proves the problem is unsolvable.
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.
> 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.
It's about the proof, not the computation.
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)
Amateur observation, take with a grain of salt: On the other hand, I guess we are doing something similar when generating a new public/private key pair on an elliptic curve. It just turns out that finite fields have very little (known) structure to exploit compared to e.g. colored graphs, so we have more confidence in the assumption that the generated discrete logarithm problem is indeed hard.
Similarly, who is to say that there isn't some way to define what the hard instances of NP-complete problems are, and we just should be sampling from that difficult region of the problem space instead of all possible problems, the same way we sample only from the difficult-to-factor coprimes instead of from all possible numbers? There is definitely something interesting going on with the harder instances of these problems, and researchers have managed to discover a kind of "phase transition" among instances of some of the problems between ones with so many solutions they are easy and ones with so few solutions they are also once again easy (and my knowledge on this is about 20 years rusty and outdated... maybe this is better understood and characterized now).
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.
But we do know that the shortest vector problem is NP-hard (in Linf norm), and so is its decision version [1]. We don't have a reduction in the other direction, but we know that SVP is as-hard-as-NP-complete-or-harder.
This goes against the general argument of the article, but only weakly so, because I think lattice-based systems are less broadly deployed than elliptic curves or factoring (not a crypto person, though).
[1] H. Bennett, "The Complexity of the Shortest Vector Problem.", 2022 https://simons.berkeley.edu/sites/default/files/docs/21271/s...
Lattice crypto is going to be broadly deployed because it hopefully can resist quantum attack, unlike ECDLP and factoring.
Even if most instances of a problem are deterministically hard, they might still have a randomized algorithm which solves them feasibly.
You can do the reverse (encode the hash into a SAT problem), but that's possible for any NP problem, because SAT is NP-complete.
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.
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.
Also, do you have a citation for "We do know with absolute certainty that the decision problem for DLC is NP-Hard"
See e.g. https://cs.stackexchange.com/a/2765
You're confused here. The two conditions for a problem being NP-complete are (1) it being NP-hard and (2) it being in NP.
You suggest (2) is the issue, but usually it's harder to prove (1) rather than (2). In the context of factorization problems, the factors are simply the certificate that satisfy condition (2).
