From the paper 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.

  • $\begingroup$ 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). $\endgroup$ – usul May 25 '15 at 0:41
  • $\begingroup$ I modified the question with a link to the paper. $\endgroup$ – user34219 May 25 '15 at 1:17
  • $\begingroup$ One should interpret that as "A random permutation oracle is provable one-way" relative to itself "in the strongest possible sense". $\:$ I believe your other questions should be on cs.stackexchange rather than here. $\;\;\;\;$ $\endgroup$ – user6973 May 25 '15 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.