6
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 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
    Commented Mar 9, 2016 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$
    – Yehuda Lindell
    Commented Mar 9, 2016 at 20:06
  • $\begingroup$ Is there a concise explanation of why it's difficult to prove? $\endgroup$
    – Stephen Touset
    Commented Mar 9, 2016 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$
    – Yehuda Lindell
    Commented Mar 10, 2016 at 5:15

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.