<p>From the <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.46.6873&amp;rep=rep1&amp;type=pdf" rel="nofollow">paper</a> of Impagliazzo and Rudich "Limits on the Provable Consequences of One-Way Permutations":</p>

<blockquote>
  <p>We provide strong evidence that it will be difficult to prove that secure secret agreement is possible assuming only that a one-way permutation exists. We model the existence of a one-way permutation by allowing all parties access to a randomly chosen permutation oracle. A random permutation oracle is provable one-way in the strongest possible sense.</p>
</blockquote>

<p>Given that we don't know if one-way function exists, how should one interpret this? Doesn't the above say one-way fucntion <em>does</em> exist?</p>

<p>Also, they exhibit an oracle relative to which one-way permutation exists, but not key agreement. Again, how is that possible? What does that mean? A <em>black-box</em> key agreement can be constructed independently ignoring <em>both</em> the oracle and the one-way permutation. </p>

CC BY-SA 3.0
2015-05-25T00:41:08.043Z
Please link to the paper or state the title! ... Regarding your first question, it sounds like what's going on is that the "random permutation oracle" is an oracle that produces truly random permutations. The fact that it's an oracle means it's not necessarily *computable* in polynomial time, hence it's not a one-way function in the usual sense. (Though it is one-way in being hard to invert).
usul
CC BY-SA 3.0
2015-05-25T01:17:27.290Z
I modified the question with a link to the paper.
user34219
<random-oracles>
The meaning of separations in cryptography
user34219
# The meaning of separations in cryptography

(Asked by: username_0 on 2015-05-24)

From the [paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.46.6873&rep=rep1&type=pdf) of Impagliazzo and Rudich "Limits on the Provable Consequences of One-Way Permutations":

> We provide strong evidence that it will be difficult to prove that secure secret agreement is possible assuming only that a one-way permutation exists. We model the existence of a one-way permutation by allowing all parties access to a randomly chosen permutation oracle. A random permutation oracle is provable one-way in the strongest possible sense.

Given that we don't know if one-way function exists, how should one interpret this? Doesn't the above say one-way fucntion *does* exist?

Also, they exhibit an oracle relative to which one-way permutation exists, but not key agreement. Again, how is that possible? What does that mean? A *black-box* key agreement can be constructed independently ignoring *both* the oracle and the one-way permutation.

**Tags:** random-oracles

> **Comments:**
> **username_1**: Please link to the paper or state the title! ... Regarding your first question, it sounds like what's going on is that the "random permutation oracle" is an oracle that produces truly random permutations. The fact that it's an oracle means it's not necessarily *computable* in polynomial time, hence it's not a one-way function in the usual sense. (Though it is one-way in being hard to invert).  
> **username_0**: I modified the question with a link to the paper.  

---

## 0 answers

