# 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 , with respect to a keyspace , domain , and range , such that:

- , is a randomized algorithm that takes a security parameter, and outputs a key ,
- , is a deterministic algorithm that takes a key and input , and outputs an element .

Generally, we assume that is "large," in the sense that it grows exponentially with the security parameter. If instead is 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 , there exists a negligible function , such that

### Weak Security

A PRF is *weakly secure* if for all efficient , and all polynomials , there exists a negligible function , such that

The difference in this definition is that we sample 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: