Understanding pseudo-random functions (used in a Oblivious Transfer Protocol)

Question

Given a family of pseudo-random functions

$$\{F_K:\{0,1\}^m\mapsto \{0,1\}^m | K \in \{0,1\}^t \}.$$

I want to understand how the elements behave.

Lets say we take some $F_{K_1}$ and evaluate at $x=(0,\dots,0)\in\{0,1\}^m$, is it true that the evaluation of $F_{K_1}$ at $x$ always yields the same result? Why property does make this set so special? I tried to understand the definition from wikipedia, but failed to do so..

I am asking this questions and trying to understand PRF because I am studying a paper about generalized OT protocols which can be found here ( page 5).

Answer 1

Yes, if you take an instance out of the function family (e.g. $F_{K_1}$), then the evaluation of this function at $x$ always yields the same result. You can think of it like that:

If you fix a key $K$, then your PRF is basically a look-up-table. For every possible input $x \in \{0,1,\cdots,2^m-1\}$ there is an entry in the look-up-table for the output $F_{K_1}(x)$. For each key, there exist a different look-up-table.

So why is called pseudo random? Well imagine some bad guy who sends different $x$ to a black box and gets back some value. Inside the black box, there is either a $F_{K}$ with a key $K$ chosen uniformly at random or a function $f: \{0,1\}^m \rightarrow \{0,1\}^m$ that is chosen uniformly at random from the set of all possible functions from $\{0,1\}^m$ to $\{0,1\}^m$. If the bad guy cannot tell wether he is talking to $F_K$ or $f$, then $F$ a good PRF, because the output looks totally random to him in either cases.

There is a possbile way to distinguish both functions, if the bad guy accidentally finds two distinct values $x_1, x_2$, that yields the same output $f(x_1) = f(x_2)$. Then he knows, that he's talking to $f$. But if $m$ is suffienciently large, the probability of a collision is very low.