no, the article is talking about symmetric key crypto also. (i.e. one way functions). You're talking about cryptosystems that don't have proofs of security, or reductions to heuristical assumptions
1) It'd be really really awesome to show average-case hardness version of a natural problem (i.e. 3SAT on a natural distribution) from the worst-case hardness of that problem (i.e. 3SAT). I believe it's wide open in the context of building one-way functions.
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.
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.
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"
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)
tit for tat makes the U.S. more like the CCP, and less like the version of the U.S. that stands for freedom and democracy (that I presume you want to live in).
if you want to live in an American version of china where instead of bytedance we have zuckagram, go for it. Chinese social media has vastly out-innovated American platforms and the Zuck/Musk response is to ban the competition rather than write a proper law regulating social media platforms
Raft has a problem where, in the protocol description, sometimes I have no idea why some line is there, but if you take it out the protocol comes to a grinding halt... it's really a mumble jumble. It has good intuition, but the details are really messy, it's edge cases all the way down.
Whereas I think each line of pseudocode in Paxos is much more motivated.
In other words, if a philosopher had to design a crash-fault protocol from scratch, without having seen any before, I think 80% of the time it would look exactly like Paxos.
I don’t see how you can read and understood Nielsen and Chuang in one sitting, unless you are already a quantum computation theorist. I also don’t see how reading what is essentially an algorithms textbook can lead you to develop an informed opinion about the state of quantum computer engineering…
it’s like reading saying “I was curious about how computer software works so I ordered and read CLRS and I don’t think faster computers are anywhere on the horizon in 100 years…”
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.
