Pseudorandom Functions - Contemporary Cryptography - page 322

./

Figure 13.1 A random function f .

only requirement is that if a specific input value x is fed multiple times into the box,
then the output value f ( x ) must always be the same.
Another way to think about a random function f is as a large random table T
with entries of the form T [ x ]=( x, f ( x )) for all x

∈ X . The table can either be

statically determined or dynamically generated:

• If T is statically determined, then somebody must have flipped coins (or used

another source of random bits) to determine f ( x ) for all x

∈ X and put these

values into the table.

• If T is dynamically generated, then there must be a program that initializes

the table with empty entries and that proceeds as follows for every input value
x : it checks whether T [ x ] is empty. If it is empty, then it randomly chooses
f ( x ) from Y , writes this value into T [ x ], and returns it as a result. If T [ x ] is
not empty, then it returns the corresponding value as a result.

Note that a random function is neither something useful in practice nor
something that is intended to be implemented in the first place. It is only a conceptual
and theoretical construct. Also note that the term random function is somehow
misleading. In fact, it may lead one to believe that some functions are more random
than others or—more generally—that randomness is a property that can be attributed
to a function or the output it eventually provides. This is not the case. The attribute
random in the term random function refers only to the way it was chosen. In fact, a
random function f : X Y is a function that is randomly chosen from Rand X→Y

(i.e., the set of all functions of X to Y ). Consequently, even a constant function can
occur as a random function (even though one would intuitively think that a constant
function is not random at all).
Similarly, we use the term random permutation to refer to a function f : X

→

→
X that is randomly chosen from Perm X→X , and hence the identity function can
also occur as random permutation. Most of the things we say in this chapter about
PRFs also apply to pseudorandom permutations (PRPs) in an analog way.
The fact that a PRF is computationally indistinguishable from a random
function means that somebody who has only black box access to a function (in
the sense that he or she can only observe the input-output behavior of a box that