Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 9 down vote accepted

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.

share|improve this answer
1  
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). – malexmave Mar 9 at 12:02
1  
Indeed, that also contains the proof. I updated the answer itself to make this easier for others to find; thanks. – Yehuda Lindell Mar 9 at 20:06
    
Is there a concise explanation of why it's difficult to prove? – Stephen Touset Mar 9 at 23:20
    
@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. – Yehuda Lindell Mar 10 at 5:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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