Take the 2-minute tour ×
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.

Assume

  • $S$ be a finite set
  • $O$ be a random oracle from $S$ to $S$, such that $O$ is bijective
  • $f$ be a random permutation of $S$

Is there any difference between $O$ and $f$?

Does it makes any difference if $S$ is not finite?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

At some level, there is no essential difference. Certainly, there is no difference in the distribution on the random variable $O$ vs $f$.

However, there is a potential difference in how the terms are typically used.

  • If we say that $O$ is a random (bijective) oracle, then we are usually implicitly hinting that it is available to everyone: the legitimate parties, the attacker, everyone -- anyone can supply an $x$ and get back $O(x)$.

  • In contrast, if we say that $f$ is a random permutation, we have not yet made any commitment about whether it is made available as an oracle to everyone, or whether it is closely held.

Hopefully the set of parties who have access to $O$/$f$ should be made clear elsewhere (e.g., in the formalization of security), so there is no real danger of serious confusion, but this might serve as a hint to let readers know what to expect.

share|improve this answer
1  
Note that even if they are both available to everyone, "random permutation" would suggest a stricter limit on the number of queries than "random bijective oracle" would. $\:$ (See FPE.) $\;\;\;$ –  Ricky Demer Nov 24 '13 at 7:55

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.