What advantage would knowing the key used for a given pseudorandom function give over having access to an oracle for that function $F_k(\cdot)$ and the actual key $k$ which will be used?

Thanks very much in advance


To elaborate of fkraiem's answer, the security property we want a pseudorandom function family $F$ to possess is (computational) indistinguishability from a random function. That is, an adversary, given oracle access to some function $f: X \to Y$, should not be able to distinguish between the following two possibilities:

  1. $f = F_k$ for some randomly chosen (secret) key $k$, or
  2. $f$ is chosen uniformly at random from the entire set of all functions from $X$ to $Y$.

The key thing to realize is that the adversary is allowed to know how to compute $F_k(x)$ for any given key $k$ and input $x$. Thus, if the adversary knew which key $k$ was supposedly used to be used to instantiate the oracle in case 1, they could simply pick an arbitrary input $x$, query the oracle for $f(x)$, and check if the result matches $F_k(x)$. If $f$ really is $F_k$, the results will obviously always match; if $f$ is a random function, they will only do so with probability $1/|Y|$.

Ps. Since the function family $F$ is efficiently computable, and since we wish to show that no efficient adversary can distinguish a random instance of $F$ from a random function, it really makes no difference whether we explicitly grant the adversary knowledge of how to compute $F$ or not: among all the possible efficient adversaries, there will always be some that just happen to know how to correctly compute $F$. Of course, there are also countless possible adversaries that compute $F$ wrong, and thus fail to distinguish between the two scenarios, but we're only concerned about the few that get it right.

Of course, for any given key $k$, there will also be some adversaries that can simply guess it correctly. The difference is that the definition of $F$ is fixed, whereas in the indistinguishability game, $k$ is chosen at random every time the game is played. So an adversary that correctly guesses the definition of $F$ will evaluate it correctly every time, whereas an adversary that correctly guesses $k$ in one round of the game will almost surely guess wrong on any other round.

Perhaps a clearer way to think about this is that, by allowing the adversary to be any efficient algorithm, and requiring our cryptosystem to be secure against any such adversary, we're basically allowing the adversary to know any information that can be encoded as a polynomial-time algorithm, and that is not explicitly randomized (and kept hidden from the adversary) as part of the game. In particular, this implicitly embodies Kerckhoff's principle: among the set of all possible adversaries, there are always some that know exactly how our cryptosystem works


With $k$ the adversary can compute $F_k(x)$ for some $x$ using the evaluation algorithm, and compare it to the answer of its oracle on $x$.


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.