Question

Describe what is a function family and what is a keyed function. Explain what is a Pseudo Random Function.

Answer 1

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.

KEYED FUNCTIONS:
A keyed function F:{0,1}*x{0,1}*{0,1}*
The first input is called the key. The key is chosen randomly and then fixed, resulting in a single argument function, Fk: {0,1}*{0,1}*
Assume that the functions are length preserving, meaning that the inputs, output and key are all of the same size.

PSEUDORANDOM FUNCTIONS:
Pseudorandom functions are used to model blockciphers, and they thereby enable the security analysis of protocols based on blockciphers.
A pseudorandom function is a family of functions with the property that the input-output behavior of a random instance of the family is “computationally indistinguishable” from that of a random function. Someone who has only black-box access to a function, meaning can only feed it inputs and get outputs, has a hard time telling whether the function in question is a random instance of the family in question or a random function.
We fix a family of functions F: K × D → R. (You may want to think K = {0, 1}^k
, D = {0, 1}^ℓ and R = {0, 1} L for some integers k, ℓ, L ≥ 1.) Imagine that you are in a room which contains a terminal connected to a computer outside your room. You can type something into your terminal and send it out, and an answer will come back. The allowed questions you can type must be elements of the domain D, and the answers you get back will be elements of the range R. The computer outside your room implements a function Fn: D → R, so that whenever you type a value X you get back Fn(X). However, your only access to Fn is via this interface, so the only thing you can see is the input-output behavior of Fn.