5
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

The existence of (trapdoor) OWF implies that there are NP relations that are hard on average. But the difference of both worlds is no longer about the hardness of NP. It is much more about the relationship between cryptographic tasks rather than about complexity theory.

But what is the difference between trapdoor OWF and OWF?

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.