Let's say I tell you $G: \mathbb{F} \rightarrow \mathbb{F}$ is a random permutation (some finite field). Does that mean:

  1. $G$ is one-way, so that if I give you $G(x)$, it is infeasible to determine the pre-image $x$?

  2. Is $G$ hiding in the sense that you can't figure out anything about $x$ given $G(x)$? For example, you could determine if $x$ were even/odd?

If the second question is true, how do I capture this in a game?

  • $\begingroup$ Just to clarify: what do you know about $G$? Do you have access to a blackbox implementing $G$? $\endgroup$ Commented Apr 9, 2019 at 12:45
  • $\begingroup$ I can say that we can get $G(x)$ by giving $x$ to a random oracle. $\endgroup$ Commented Apr 9, 2019 at 15:17
  • $\begingroup$ ok, then the answer to 1 is yes and the answer to 2 is no, I'll elaborate on that in an answer later. $\endgroup$ Commented Apr 9, 2019 at 15:55

2 Answers 2


If you have access to $G$ through an oracle, then you have a random permutation oracle, which is the usual way of modeling an idealized one-way permutation. In particular, it is therefore a one-way function.

As pointed out by fgrieu, however, a random one-way permutation is not hiding in general. The natural game to capture the hiding property of some primitive $P$ is as follows: the adversary picks $(x_0,x_1)$ arbitrarily, and sends them to you. Then, you pick a random bit $b$ and return $P(x_b)$; the adversary wins if he finds $b$. A scheme $P$ is hiding if the winning probability of the adversary is negligibly close to $1/2$.

Of course, a random permutation does not satisfy this: as long as the adversary sends different values, he can always compute $G(x_0), G(x_1)$ himself, and check which one is the value he got from you. In general, a deterministic function cannot be hiding.

It is possible, however, to construct a provably secure hiding commitment scheme from a one-way permutation - in your case, it will be perfectly hiding, since you have access to an ideal random permutation. The standard construction goes through the Goldreich-Levin theorem, that shows how to extract a "harcore bit" from the one-way permutation, such that finding this hardcore bit is as hard as inverting the permutation, and uses this hardcore bit to mask the bit you want to commit to (there is a Wikipedia entry about this construction).


If $G$ is only known to be a random permutation, and one $G(x)$ is given, that gives no information whatsoever about $x$ (it can be any element of $\mathbb F$ with equal likelihood if $G$ is uniformly random). So I would say $G$ is one-way and hiding in the sense of the question.

Things change when for the same $G$ it is considered several given $G(x)$ and perhaps $x$. In particular, knowing $G(x)$ and $G(x')$ we can tell if $x=x'$, since that is equivalent to the testable $G(x)=G(x')$.

Capturing the first situation in a game is easy: change the permutation whenever its input or output changes. But that's bound to give dull results: we're not using most of what the permutation is good for.

To capture the second situation, define the permutation early in the game, and make several rounds with $x$ or $G(x)$ varying. It's possible to establish things like: for appropriately large $\mathbb F$, given a $G(x)$ that was not previously disclosed, the computational advantage in predicting $x$ is negligible.

  • $\begingroup$ Please could you refer me to some standard texts on this, especially with respect to your last paragraph? They don’t need to be too advanced, and might be pedagogical. $\endgroup$
    – gen
    Commented Feb 9, 2021 at 2:17

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.