Vervious

not again!

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.

Makes sense!

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…”

why not go public? That would also probably be in the public interest.

I think the controversy was in making the observation

Maybe overall better for society, when a single ivory tower doesn’t have a monopoly on AI!

I think you're being a little selective in trying to show your point. Human-driven climate change is the biggest driver of ecological damage. Even the article you link to is based on a report that climate change is the biggest driver of desertification worldwide.

I agree with you that land management can mitigate desertification, the same way hunting invasive species can help protect native biodiversity.

This doesn't mean it's wrong to focus on climate change, and by extension, carbon emissions. If anything, they demonstrate that we should focus on climate change. It's like scaling an internet technology company: we want to build something small that has a massive impact.

Reducing carbon emissions will by far have a greater impact than trying to eradicate sea urchins from the pacific northwest. It is just as feasible as better land management. And for things like coral reef bleaching, which I'm personally very interested in, it's unclear if there's any other solution.

fyi carbon emissions directly causes global warming and ocean acidification, so yes, mitigating carbon emissions IS very important to help your desertification, rainforests, kelp forests, and coral reefs

proof of stake blockchains certainly have leaders. MEV doesn't exist if there aren't designated block proposers

A blockchain (without all the bells and whistles) is definitionally equivalent to a state-machine or log replication system (but handling byzantine faults). (Each log entry is just a block).

Consensus protocol researcher here. For what it’s worth, I think that the plethora of blockchain research in the last 10 years has made consensus much easier to understand. Raft (in particular, with all of its subtleties) reads (and implements) like Greek in comparison.

For a new beginner to consensus protocols, today, I would start them with Bitcoin, and then move onto Paxos/Tendermint/Simplex, and skip Raft entirely. (Simplex is my paper, a simplified version of PBFT).

Not really; there are algorithms where many nodes propose proposals in parallel, but eventually only one of those proposals gets finalized (or they maintain only a partial ordering, not a full ordering). (See Bullshark and redbelly iirc)

The main issue is that someone has got to pick a final ordering. If there’s a universe of millions of possible orderings it seems that the most efficient way is to have a single node pick a single one.

That said shamir's secret sharing is one of the easiest constructions to reason about so I think the risk is much smaller there

> "It does however have laws around registration of the security"

This sounds a lot like the SEC dictating what can and can't be traded in the modern day. We can't trade something if there isn't an exchange for it.

I mean, everyone hyping up kale as a supergreen on their social media doesn't make Kale --- the vegetable --- a security. Likewise, people shill GOLD on twitter all the time. Is gold a security?

If kale and gold are securities under the current interpretation of the howey test, then the howey test needs to be rewritten.

Well, in a libertarian world, the moral high ground is that we should be able to trade anything -- who is the SEC to tell us what we can't trade? It's almost like freedom of speech.

Plus, I don't think consumers should be protected from dogecoin --- no layman in their right mind invests in doge with the expectation of profit (from common enterprise). Bitcoin is more of a security than doge will ever be.

Sure. But it's an ELI5 "in addition to formalism", not "in lieu of formalism". In theory conferences like STOC or FOCS, the first section of the paper often comprises such an overview.

Certainly some papers are better written than others. But sometimes a blog post cannot replace a paper, unless it also goes into the depth and detail that formalism requires. (Then it becomes a 30 page blog post, where most people don't read past the intro.)

Systems research papers do not represent all research papers out there, not even in computer science.

In cryptography, certainly a paper with formal definitions and proofs can be much more valuable than a corresponding blog post. It's a field where formalism is desired, if not necessary. Otherwise you can't check other people's "proofs", or even know what model you're working in.

I think, since people haven't come up with better formalisms, sometimes it's quite obtuse, which gets mistaken as "academic writing", when really it's a best effort to formalize.

I mostly use twitter on web, for discovery and for work - Meta, please release a web app soon!

They also need to let us change display names; these usernames don't tell us very much. Also, a following-only feed would be great.

I agree that they shouldn't dump it all into chapter 1.

But, when learning any cryptographic scheme, in order to understand what is going on, it is certainly necessary to learn the corresponding mathematical tools. Even to define what it means for a scheme to be secure requires a good grasp of probability (and negligible functions in the asymptotic regime).

Oh never mind, I didn't realize that the mechanism was to go private. I thought that all the subreddits listed were already dark.

I'm clicking on some of them, and can still view the posts?

the op seems very unironic about it though