PRF ⇒ iPRF

Standard model · HPPY25

Statement

Any PRF (indeed any one-way function) yields an invertible PRF $(\mathsf{KeyGen},\mathsf{Eval},\mathsf{Invert})$ for arbitrary domain and range sizes, including small ones, with $\tilde{O}(1)$-time evaluation and inversion time linear in the size of the returned preimage set — HPPY25.

Sketch

The iPRF is $\mathsf{Eval}(k,x)=S(P(x))$, where $P$ is a small-domain PRP on the domain, built from the PRF, and $S$ is a pseudorandom multinomial sampler: a binary tree over the range in which each node splits its contiguous block of inputs between the two halves of its range by a binomial sample, with success probability the left half’s share of the range and PRF-derived coins. With $P$ a uniform permutation and $S$ run on true coins, $\mathsf{Eval}(k,\cdot )$ is a uniform function, since a uniform permutation followed by a map sending contiguous blocks of multinomially distributed sizes to the range points gives each input an independent uniform output; $\mathsf{Invert}(k,y)$ walks the tree to the block $S^{-1}(y)$ and applies $P^{-1}$ to each of its elements — HPPY25.

Notes

• A PRP alone is an iPRF for the forward-oracle game ${\mathbf{G}}^{\mathrm{prf}}$ only over a domain of superpolynomial size, where the Switching Lemma applies (PRP ⇒ iPRF) — folklore.