# How to intuitively express the hardness of Minicrypt and Cryptomania?

My question is as stated in the title. To give an example of “intuitively express”, it’s like: we often say

• Algorithmica means “NP is easy”,
• Heuristica means “NP is hard on worst-case but easy on average”,
• Pessiland means “NP is hard on average but not hard enough (to have an OWF), i.e. for every efficiently samplable distribution there is a non-negligible fraction of easy instances”.

But for Minicrypt and Cryptomania, the usual statement is “have OWF but no PKE” and “have PKE”, which do not give direct, intuitive expression about “NP is hard in which way”.

After searching for hardness assumptions in the crypto world, I found that PKE is implied by the existence of trapdoor OWF. But what is the difference between trapdoor OWF and OWF? My perspective is:

• trapdoor OWF implies a language where “though (almost) all instances are hard in the same way (reducible to the trapdoor), you are still incapable of solving it”, while
• OWF implies a language where “(almost) all instances are so hard that solving it is out of reach, but it might be an ensemble of several different hard problems”.

(But it seems that trapdoor OWF is only a sufficient condition for PKE, not a necessary one.)

I have long been curious about this. Is my understanding correct, or is there any point I missed?

An intuitive way to think about OWF and trapdoor OWF is that a trapdoor is to a function what a witness is to an NP instance. A function $$f$$ is one-way if given $$y$$ it is hard to find $$x$$ such that $$f(x)=y$$, defining an NP relation $$(x,y)\in R_f \iff f(x)=y$$. A trapdoor makes this problem easy for every $$y$$.
Impagliazzo and Rudich have shown a black-box separation for OWF and PKE. They show that if the OWF is used as a black-box, proving that PKE exists is as hard as proving $$P\neq NP$$. More precisely, relative to a random permutation oracle, PKE does not exist if $$P=NP$$.