I'm currently working on a proof in the Random Oracle model, and could not find the formal argument on why the random oracle is one-way (i.e. for an Oracle $O$, it is easy to calculate $x=O(n)$, but not efficiently possible to compute $n = O^{-1}(x)$).

Now, I know that the random oracle has that property, and it is intuitively obvious why (as the output is randomly chosen, it is independent from the input and does not contain any information about it). However, as it is not part of the formal specification of a random oracle as per Bellare and Rogaway (as far as I know), I'd like to know how you would formally prove it, based only on the formal specification of a random oracle.


This is very confusing because it seems as it should be something really easy to prove. However, it actually is not, and in fact the proof uses the Borel-Cantelli lemma. Anyway, it was formally proven by Rudich and Impagliazzo in their groundbreaking work on black-box separations. You can find a formal proof in Rudich's thesis, Section 6.2, or in the paper Limits on the provable consequences of one-way permutations by Impagliazzo and Rudich.

  • 1
    $\begingroup$ Thanks! For future reference for others who stumble upon this and need a citable paper as source: as I understand it, the paper Limits on the provable consequences of one-way permutations by Rudich and Impagliazzo also contains the proof (correct me if I'm wrong). $\endgroup$
    – malexmave
    Mar 9 '16 at 12:02
  • 1
    $\begingroup$ Indeed, that also contains the proof. I updated the answer itself to make this easier for others to find; thanks. $\endgroup$ Mar 9 '16 at 20:06
  • $\begingroup$ Is there a concise explanation of why it's difficult to prove? $\endgroup$ Mar 9 '16 at 23:20
  • $\begingroup$ @StephenTouset It's not that it's difficult to prove; it's not straightforward and it's not what you'd expect. Basically, you need to reason about large random objects. Formally, you can't make statements like "what you see is not correlated and so on..."; translating that intuition is just much harder than one would think. The proof is not long (1.5 pages), so it's not hard. But, to come up with it yourself requires a lot of work. $\endgroup$ Mar 10 '16 at 5:15

Your Answer

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

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