Pseudorandom function

A Pseudorandom Function (PRF) allows someone to succinctly represent a function that is indistinguishable from a uniformly random function. A user generates a key and uses it to evaluate a function at many points; any efficient adversary who sees only these input-output pairs cannot distinguish them from a truly random function.

Syntax

A PRF is a pair of efficient algorithms $\mathsf{PRF}=(\mathsf{KeyGen},\mathsf{Eval})$ with respect to keyspace $\mathcal{K}$, domain $\mathcal{D}$, and range $\mathcal{R}$:

• $\mathsf{KeyGen}(1^{\lambda })\to k,$ is a randomized function that samples a key $k\in \mathcal{K},$
• $\mathsf{Eval}(k,x)\to y,$ is a deterministic function that takes a key $k\in \mathcal{K}$ and an input $x\in \mathcal{D}$, outputting $y\in \mathcal{R}.$

Properties

Security

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{prf}}_{\PRF,\calA}(\secpar)$}
\begin{algorithmic}
\State $k \gets \KeyGen(1^\secpar)$; $b \getsr \{0,1\}$
\State $R \getsr \Funcs(\calD,\calR)$
\Comment{Can be sampled lazily for efficiency}
\State $\calO_0(x) := \Eval(k,x)$
\State $\calO_1(x) := R(x)$
\State $b' \gets \calA^{\calO_b}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A PRF $\mathsf{PRF}$ is pseudorandom if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{PRF},\mathcal{A}}^{\mathrm{prf}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{PRF},\mathcal{A}}^{\mathrm{prf}}(\lambda )=1\right]-1\right|$$

is negligible.

Variations

Invertible PRFs

An invertible PRF (iPRF) extends the PRF with an inversion algorithm, allowing recovery of all inputs that map to a given output. An $\mathsf{iPRF}=(\mathsf{KeyGen},\mathsf{Eval},\mathsf{Invert})$ adds:

• $\mathsf{Invert}(k,y)\to X,$ is a deterministic function that returns the preimage set $X=\{x\in \mathcal{D}:\mathsf{Eval}(k,x)=y\}$

Note that for domains much larger than the range, $\mathsf{Invert}$ may return exponentially many preimages, so efficiency is only meaningful when $|\mathcal{D}|$ is reasonable relative to $|\mathcal{R}|$.

Correctness

With an inversion function, it also makes sense to restrict an iPRF to be correct. Meaning if for all for all $x\in \mathcal{D},$ $\mathrm{Pr}[x\in \mathsf{Invert}(k,y):\mathsf{Eval}(k,x)=y]=1,$ where the probability is taken over $k\leftarrow \mathsf{KeyGen}(1^{\lambda }).$

Security

Invertible PRFs can either achieve the traditional security game ${\mathbf{G}}^{\mathrm{prf}}$ or can satisfy the stronger security game ${\mathbf{G}}^{\mathrm{iprf}}$ where $\mathcal{A}$ is additionally given access to an inversion oracle that returns the pre-image of a given output $y\in \mathcal{R}$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{iprf}}_{\mathsf{iPRF},\calA}(\secpar)$}
\begin{algorithmic}
\State $k \gets \KeyGen(1^\secpar)$; $b \getsr \{0,1\}$
\State $R \getsr \Funcs(\calD,\calR)$
\Comment{Can be sampled lazily for efficiency}
\State $\calO_0(x) := \Eval(k,x)$ ; $\calO_0^{-1}(y) := \Invert(k,y)$
\State $\calO_1(x) := R(x)$ ; $ \calO_1^{-1}(y) := R^{-1}(y)$
\State $b' \gets \calA^{\calO_b,\calO_b^{-1}}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

An iPRF $\mathsf{iPRF}$ is strongly pseudorandom if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{iPRF},\mathcal{A}}^{\mathrm{iprf}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{iPRF},\mathcal{A}}^{\mathrm{iprf}}(\lambda )=1\right]-1\right|$$

is negligible.

Related results results

• PRFs imply the existence of iPRFs — HPPY25
• PRPs over large domains are iPRFs — Switching Lemma

Pseudorandom Injective Functions

TODO: define these and say how they relate to PRPs

Puncturable PRFs

Other results

• OWF implies the existence of PRFs - TODO