Pseudorandom function

From CRYPTUTOR

A pseudorandom function (PRF) is a function whose input-output functionality, when accessed as an oracle, appears like that of a random function, to any polynomial-time computations.

1 Definition
2 Relationship to pseudorandom generators
3 Existence
4 See also

[edit]

Definition

Let $m$ and $\ell$ be polynomials, let $k$ be a security parameter, and let $\mathcal{R}_k$ be the set of all functions from $\{0,1\}^{m(k)} \to \{0,1\}^{\ell(k)}$ .

Let $\mathcal{F}_k = \{ F_s \}_{s \in \{0,1\}^k}$ be a set of functions indexed by seeds $s$ ( $\mathcal{F}_k \subseteq \mathcal{R}_k$ ). Then $\mathcal{F}_k$ is a pseudorandom function family if it has the following properties:

Efficiency: $F_s(x)\,$ is computable in deterministic polynomial time, given the seed $s$ and $x$ .
Pseudorandomness: For all non-uniform oracle PPT adversaries $A$ , the following difference is negligible in $k$ :

$\Pr_{s\leftarrow\{0,1\}^k}[A^{F_s}=1] - \Pr_{R\leftarrow\mathcal{R}_k}[A^{R}=1]$

Note that the adversary $A$ gets access only $F_s\,$ as an oracle, and that the seed $s$ is not given to the adversary.

We often abuse notation and simply call the function $F$ (or $F_s\,$ for a randomly chosen $s$ ) a PRF.

[edit]

Relationship to pseudorandom generators

The definition of pseudorandomness does not apply to exponentially long input strings, but the PRF definition can be viewed as an extention of pseudorandomness for exponentially long strings. Since we cannot give an exponentially long string as input to a polynomial-time adversary, we instead provide a mechanism for random access into the string. Under this interpretation, a PRF $F_s\,$ implicitly represents the exponentially long pseudorandom string:

$F_s(0\cdots 0) F_s(0 \cdots 01) \cdots F_s(1 \cdots 1)$ .