= Pseudorandom function family
{wiki}
A <pseudorandom function family> is a collection $\{F_k:D\to R\}$ indexed by a key $k$, with an efficient evaluation <algorithm>. For a random key, an adversary receiving answers to chosen queries should be unable to distinguish $F_k$ from a uniformly random <function> on the same finite domain and range, within a declared resource bound.
Both experiments answer repeated queries consistently. Fresh queries to the random <function> receive independent uniform values; queries to $F_k$ use one fixed key throughout. The adversary may choose its next query using previous answers.
For a one-bit output, an all-zero family is easily distinguished: two different queries return $00$ with <probability> one there and <probability> $1/4$ for a random <function>. State key length, query bound, running time and distinguishing advantage when using the definition quantitatively.<How to Construct Random Functions by Oded Goldreich, Shafi Goldwasser and Silvio Micali>[function ensembles and oracle indistinguishability definition]{ref}
Back to article page
