Pseudorandom Function A pseudorandom function (PRF) is a seeded function, when the seed is uniformly chosen and kept secret, evaluating such a function on any point yields a random-looking output. This means the adversary can not distinguish whether she is interacting with a random function chosen from the whole function space, or she is interacting with a function chosen according to a key (this is from a space with size equal to the key space which could be exponentially smaller). We will see in the homework that PRF can be seen as the central hub in the symmetric key cryptography, it can be used to construct all other symmetric key primitives.

Formally, consider the following experiments described in Fig. 1. Suppose Exp^b_A is the random variable denoting the output of A in experiment b,

Definition 1 (PRF) A function F : K {0, 1}¹⁰³ {0, 1}²⁰⁶ is a pseudorandom function, if for any P.P.T adversary A,

| Pr[Exp⁰_A = 1] Pr[Exp¹_A = 1]| negl(), where is the security parameter, K is the key space with |K| = 2⁸⁰, F is the set of all functions mapping

from {0, 1}¹⁰³ to {0, 1}²⁰⁶.

Experiment 0: K $ K RF O0 :=F(K,) O1 := R() b AO0() Return b

Experiment 1: K $ K RF O0 :=F(K,) O1 := R() b AO1() Return b

Figure 1: The PRF experiments

The oracle notation means the adversary can freely ask queries to it and obtains the correct answer, alternatively, we can see the experiment defined using a game described in Fig.??.

Q4: Get a feeling that such a small subspace can be used to trick the adversary to think that she is interacting with function chosen from the whole function space.

Count how many functions are there in a PRF family, and how many functions are there in F, assuming K = {0, 1}⁸⁰.