Chapter 3 Pseudorandom Functions Pseudorandom functions PRFs and their cousins pseudorandom permutations PRPs figure as central tools in the design of protocols especially those for shared key cryptography At one level PRFs and PRPs can be used to model blockciphers and they thereby enable the security analysis of protocols based on blockciphers But PRFs and PRPs are also a useful conceptual starting point in contexts where blockciphers don t quite fit the bill because of their fixed block length So in this chapter we will introduce PRFs and PRPs and investigate their basic properties 3 1 Function families A function family is a map F K D R Here K is the set of keys of F and D is the domain of F and R is the range of F The set of keys and the range are finite and all of the sets are nonempty The two input function F takes a key K and an input X to return a point Y we denote by F K X For any key K K we define the map FK D R by FK X F K Y We call the function FK an instance of function family F Thus F specifies a collection of maps one for each key That s why we call F a function family or family of functions Sometimes we write Keys F for K Dom F for D and Range F for R Usually K 0 1 k for some integer k the key length Often D 0 1 for some integer called the input length and R 0 1 L for some integers L called the output length But sometimes the domain or range could be sets containing strings of varying lengths There is some probability distribution on the finite set of keys K Unless otherwise indicated this distribution will be the uniform one We denote by K K the operation of selecting a random string from K and naming it K We denote by f F the operation K K f FK In other words let f be the function FK where K is a randomly chosen key We are interested in the input output behavior of this randomly chosen instance of the family A permutation is a bijection i e a one to one onto map whose domain and range are the same set That is a map D D is a permutation if for every y D there is exactly one x D such that x y We say that F is a family of permutations if Dom F Range F and each FK is a permutation on this common set Example 3 1 1 A blockcipher is a family of permutations In particular DES is a family of permutations DES K D R with K 0 1 56 and D 0 1 64 and R 0 1 64 2 PSEUDORANDOM FUNCTIONS Here the key length is k 56 and the input length and output length are L 64 Similarly AES when AES refers to AES128 is a family of permutations AES K D R with K 0 1 128 and D 0 1 128 and R 0 1 128 Here the key length is k 128 and the input length and output length are L 128 3 2 Games We will use code based games 1 in definitions and some proofs We recall some background here A game see Fig 3 1 for an example has an Initialize procedure procedures to respond to adversary oracle queries and a Finalize procedure A game G is executed with an adversary A as follows First Initialize executes and its outputs are the inputs to A Then A executes its oracle queries being answered by the corresponding procedures of G When A terminates its output becomes the input to the Finalize procedure The output of the latter denoted GA is called the output of the game and we let GA y denote the event that this game output takes value y Variables not explicitly initialized or assigned are assumed to have value except for booleans which are assumed initialized to false Games Gi Gj are identical until bad if their code differs only in statements that follow the setting of the boolean flag bad to true The following is the Fundamental Lemmas of game playing Lemma 3 2 1 1 Let Gi Gj be identical until bad games and A an adversary Let BADi resp BADj denote the event that the execution of Gi resp Gj with A sets bad Then h i h A Pr GA i BADi Pr Gj BADj i h i h i A and Pr GA i Pr Gj Pr BADj When the Finalize is absent it is understood to be the identity function Finalize d Return d In this case the output GA of the game is the same as the output of the adversary 3 3 Random functions and permutations A particular game that we will consider frequently is the game RandR described on the right hand side of Fig 3 1 Here R is a finite set for example 0 1 128 The game provides the adversary access to an oracle Fn that implements a random function This means that on any query the oracle returns a random point from R as response subject to the restriction that if twice queried on the same point the response is the same both time The game maintains the function in the form of a table T where T X holds the value of the function at X Initially the table is everywhere undefined meaning holds in every entry One must remember that the term random function is misleading It might lead one to think that certain functions are random and others are not For example maybe the constant function that always returns 0L on any input is not random but a function with many different range values is random This is not right The randomness of the function refers to the way it was chosen not to an attribute of the selected function itself When you choose a function at random the constant function is just as likely to appear as any other function It makes no sense to talk of the randomness of an individual function the term random function just means a function chosen at random Bellare and Rogaway 3 Example 3 3 1 Let s do some simple probabilistic computations to understand random functions In all of the following we refer to RandR where R 0 1 L 1 Fix X 0 1 and Y 0 1 L Let A be Adversary A Z Fn X Return Y Z Then h i L Pr RandA R true 2 Notice that the probability doesn t depend on Nor does it depend on the values of X Y 2 Fix X1 X2 0 1 and Y 0 1 L Let A be Adversary A Z1 Fn X1 Z2 Fn X2 Return Y Z1 Y Z2 Then h i Pr RandA R true 2 2L if X1 6 X2 L 2 if X1 X2 3 Fix X1 X2 0 1 and Y 0 1 L Let …