- $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?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
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.