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

• OWFs imply PRFs via a two-step construction: OWF → PRG (HILL99) → PRF via the GGM binary-tree construction (GGM86)
  • The GGM tree construction: given a length-doubling PRG $G:\{0,1{\}}^n\to \{0,1{\}}^{2n}$, define $\mathsf{Eval}(k,x_1\cdots x_{\ell })$ by starting from $k$ and at each bit $x_i$ applying either the left or right half of $G$
• PRF from DDH: the Naor-Reingold construction maps $(x_1,\dots ,x_n)\in \{0,1{\}}^n$ to $g^{a_0\cdot a_1^{x_1}\cdots a_n^{x_n}}$ and is secure under DDH — NR97
• PRF implies CPA-secure SKE: CTR-mode encryption $\mathsf{Enc}(k,m_1\cdots m_{\ell })=\mathsf{PRF}(k,1)\Vert \cdots \Vert \mathsf{PRF}(k,\ell )\oplus m_1\Vert \cdots \Vert m_{\ell }$
• PRF implies MAC: $\mathsf{Tag}(k,m)=\mathsf{PRF}(k,m)$ is a secure one-time MAC; extending to many messages uses standard domain-extension techniques