Pseudorandom functions (PRFs).

A function family $\{f$_k}k∈ (where $$ is the key length, taken to be the security parameter) is a pseudorandom function family if any adversary $A$ (whose resources are bounded by a polynomial in $$) cannot distinguish between a function $f$_k (where $k$ is chosen randomly and kept secret) and a totally random function only with negligible probability. That is, a function $g$ is chosen to be either $f$_k for a random $$-bit key, or a random function with the same range. Next $A$ gets to ask the value of $g$ on as many points as it likes. Nonetheless $A$ should be unable to tell whether $g$ is random or pseudorandom. see [14, 19] for more details.

The schemes below make use of the following property of pseudorandom functions: as long as the key $k$ is random (or pseudorandom) and remains unknown, the value $k$₁=f_k(x) is also pseudorandom for any fixed and known $x$. (In our schemes we use the arbitrary value $x=0$.) This allows us to securely iterate; that is, $k$₂=fk₁(x) is also pseudorandom, and so on. Furthermore, the value $k\text{'}$₁=f_k(x') where $x\ne x\text{'}$ is cryptographically independent from $k$₁ (as long as $k$ remains secret) and can be used as a key for different cryptographic transforms (such as a MAC).