Pseudorandom Function (PRF)

A Pseudorandom Function (PRF) is a primitive that allows someone to succinctly represent a function that is indistinguishable from a random function. A user of a PRF generates a key, which it can use to evaluate a function at many points. Any efficient adversary, who only sees these inputs and outputs of the keyed function, cannot distinguish them from a random function.

PRFs were originally defined by [GGM84] and are a basic building block for many more complex primitives such as Symmetric Encryption (SE).

Formal Definition

Syntax

A Pseudorandom Function (PRF) is a tuple of efficient functions $({\mathsf {Gen}},F)$, with respect to a keyspace ${\mathcal {K}}$, domain ${\mathcal {D}}$, and range ${\mathcal {R}}$, such that:

• ${\mathsf {Gen}}(1^{\lambda })\to k$, is a randomized algorithm that takes a security parameter, and outputs a key $k\in {\mathcal {K}}$,
• $F_{k}(x)\to y$, is a deterministic algorithm that takes a key $k\in {\mathcal {K}}$ and input $x\in {\mathcal {D}}$, and outputs an element $y\in {\mathcal {R}}$.

Generally, we assume that $|{\mathcal {D}}|$ is "large," in the sense that it grows exponentially with the security parameter. If instead $|{\mathcal {D}}|$ bounded by some polynomial in the security parameter, then the primitive is a "small-domain" PRF.

Security

A PRF is secure if for all efficient $D$, there exists a negligible function $\nu$, such that

${\big |}\Pr[D^{F_{k}}(1^{\lambda })=1:k\gets {\mathsf {Gen}}(1^{\lambda })]-\Pr[D^{R}(1^{\lambda })=1:R\gets {\mathcal {F}}[{\mathcal {D}},{\mathcal {R}}]]{\big |}\leq \nu (\lambda ).$

Weak Security

A PRF is weakly secure if for all efficient $D$, and all polynomials $s$, there exists a negligible function $\nu$, such that

${\big |}\Pr _{x_{i}\gets {\mathcal {D}}}[D((x_{i},F_{k}(x_{i}))_{i\in [s(\lambda )]})=1]-\Pr _{x_{i}\gets {\mathcal {D}}}[D((x_{i},R(x_{i}))_{i\in [s(\lambda )]})=1]{\big |}\leq \nu (\lambda ).$

The difference in this definition is that we sample $s(\lambda )$ inputs at random instead of allowing a distinguisher to choose them. This is strictly weaker, as a distinguisher could always query their oracle at random locations in the stronger definition.

Relationship to other primitives

• PRGs imply the existence of PRFs, due to [GGM84] (this means that OWFs imply the existence of PRFs, in combination with [HILL99])
• PRFs imply the existence of PRPs, due to [LR88]

There are also many folklore results surrounding pseudorandom functions:

• PRPs over are PRFs, due to the switching lemma [[[folklore]]]

Sufficient assumptions

• DDH implies PRFs
• LWE implies PRFs

Variations

• Puncturable PRF
• Invertible PRF
• Pseudorandom Permutation (PRP)
• Oblivious PRF (OPRF)