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