3
$\begingroup$

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).

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.