Invertible PRF (iPRF)

An Invertible Pseudorandom Function (iPRF) is a strengthening of the traditional Pseudorandom Function (PRF). An iPRF allows a user to succinctly represent and evaluate a function that is indistinguishable from a random function, but also to invert the random function!

Definition

An iPRF is a tuple of efficient functions $(\mathsf{Gen},F,F^{-1})$, 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}$.
• $F_k^{-1}(y)\to X$, is a deterministic algorithm that takes a key $k\in \mathcal{K}$ and input $y\in \mathcal{R}$, and outputs a preimage set of elements $X\subseteq \mathcal{D}$

For iPRF efficiency and security, it is important to consider the sizes of the domain and range (both small and large domains). For domains that are much larger than ranges, the inversion function may not be efficient in its inputs, as the preimage could be very large.

Also, there exists a construction for any domain and range due to HPPY25 which satisfies a strong security notion.

Correctness

An iPRF is correct if for all $k$, $y\in \mathcal{R}$, and $x\in {\mathsf{F}}_k^{-1}(y)$, ${\mathsf{F}}_k(x)=y$. This just implies that the pre-image function works as we would expect it to.

Security

We define the advantage of a distinguisher $D$ as ${\text{Adv}}_D^{\text{iprf}}(\lambda )\le \left|\mathrm{Pr}[D^{F_k,F_k^{-1}}(1^{\lambda })=1]-\mathrm{Pr}[D^{R,R^{-1}}(1^{\lambda })=1]\right|,$where $k\leftarrow \mathsf{Gen}(1^{\lambda })$, $R$ is a random function from $\mathcal{D}$ to $\mathcal{R}$, and $R^{-1}$ denotes the preimage function for $R$.

An iPRF is secure if for all efficient $D$, there exists a negligible function $\nu$, such that: ${\text{Adv}}_D^{\text{iprf}}(\lambda )\le \nu (\lambda )$.

Other results

• OWF implies the existence of iPRFs — HPPY25
• PRPs over large domains are iPRFs — Switching Lemma