<p>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.</p>
<blockquote>
<p>But what is the difference between trapdoor OWF and OWF?</p>
</blockquote>
<p>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 <span class="math-container">$f$</span> is one-way if given <span class="math-container">$y$</span> it is hard to find <span class="math-container">$x$</span> such that <span class="math-container">$f(x)=y$</span>, defining an NP relation <span class="math-container">$(x,y)\in R_f \iff f(x)=y$</span>. A trapdoor makes this problem easy for every <span class="math-container">$y$</span>.</p>
<blockquote>
<p>But it seems that trapdoor OWF is only a sufficient condition for PKE, not a necessary one</p>
</blockquote>
<p><a href="https://dl.acm.org/doi/abs/10.1145/73007.73012" rel="nofollow noreferrer">Impagliazzo and Rudich</a> 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 <span class="math-container">$P\neq NP$</span>. More precisely, relative to a random permutation oracle, PKE does not exist if <span class="math-container">$P=NP$</span>.</p>

CC BY-SA 4.0
2024-02-02T21:55:49.903Z
2024-02-02T21:55:49.903Z
lamontap
<p>My question is as stated in the title. To give an example of “intuitively express”, it’s like: we often say</p>
<ul>
<li>Algorithmica means “NP is easy”,</li>
<li>Heuristica means “NP is hard on worst-case but easy on average”,</li>
<li>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”.</li>
</ul>
<p>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”.</p>
<p>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:</p>
<ul>
<li>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</li>
<li>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”.</li>
</ul>
<p>(But it seems that trapdoor OWF is only a sufficient condition for PKE, not a necessary one.)</p>
<p>I have long been curious about this. Is my understanding correct, or is there any point I missed?</p>

<cc.complexity-theory><structural-complexity><complexity-assumptions>
How to intuitively express the hardness of Minicrypt and Cryptomania?
Heda Chen
# How to intuitively express the hardness of Minicrypt and Cryptomania?

(Asked by: username_0 on 2024-01-06)

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?

**Tags:** cc.complexity-theory, structural-complexity, complexity-assumptions

---

## 1 answers

### Answer by username_1 on 2024-02-02. Score: 3

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](https://dl.acm.org/doi/abs/10.1145/73007.73012) 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$.


---

