1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Just to clarify: what do you know about $G$? Do you have access to a blackbox implementing $G$? $\endgroup$ – Geoffroy Couteau Apr 9 at 12:45
  • $\begingroup$ I can say that we can get $G(x)$ by giving $x$ to a random oracle. $\endgroup$ – eternalmothra Apr 9 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$ – Geoffroy Couteau Apr 9 at 15:55
1
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.