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.

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.

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.

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.

> 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.

Right, but Paxos is double hard in comparison. I’ve read both papers multiple times, tried to implement and failed, and I still don’t think I understand Paxos.

It was not one sitting... That's a textbook, it took a while. Probably over a year. I was also doing it along learning some of the math involved in another course. Also my SO is a physicist so I had some help.

The theory is great. The problem is that it all hinges on a scientific breakthrough that has not happened yet. I don't see it happening soon. Just my not totally uneducated opinion. I have no horse in the race I think the people claiming it will work "soon" are being a bit dishonest with themselves as well as everyone else. For all we know it will end up taking several other scientific breakthroughs to get all the parts needed. I personally think that is the case and why I say it will not be in our lifetime.