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! A user generates a key, which it can use to evaluate a function both forward and backward. This introduces a natural stronger security notion as well; however, the standard security definitions of PRFs can also be applied to an iPRF.

PRFs were originally defined by [HPPY24] and are a building block for the PIR with client pre-processing scheme that they build.

Formal Definition

Syntax

An Invertible Pseudorandom Function (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 element $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 [HPPY24] which satisfies a strong security notion.

Correctness

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

Security

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

${\big |}\Pr[D^{F_{k},F_{k}^{-1}}(1^{\lambda })=1]-\Pr[D^{R,R^{-1}}(1^{\lambda })=1{\big |}\leq \nu (\lambda ),$

where $k\gets {\mathsf {Gen}}(1^{\lambda })$, $R$ is a random function from ${\mathcal {D}}$ to ${\mathcal {R}}$, and $R^{-1}$ denotes the preimage functino for $R$.

Relationship to other primitives

• PRFs and PRPs imply the existence of iPRFs, due to [HPPY24]
• PRPs over large domains are iPRFs, due to the switching lemma (as well as (Truncated PRPs)

Other Notes

The construction in [HPPY24] does not have to enumerate the inverse function. If one instead just wanted to sample from the preimage, this could be done efficiently for any domain and range.