3
$\begingroup$

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?

| improve this question | |
$\endgroup$
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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.) $\;\;\;$ $\endgroup$ – user991 Nov 24 '13 at 7:55
  • $\begingroup$ The "availability to everyone" is critical in the writing of security proofs. The Random Oracle has programmability, which a random permutation that can somehow be computed internally (and undetectably) by an adversary does not have programmability. $\endgroup$ – dionyziz Sep 19 '19 at 14:38

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.