PRP ⇒ iPRF (large domains)

A PRP over a large domain is an invertible PRF.

Statement

Migrated verbatim from PRF § Related results:

PRPs over large domains are iPRFs — Switching Lemma

The same claim is stated from the other end at PRP § Other results:

PRPs imply the existence of large-domain PRFs (and in fact these are invertible PRFs) — Switching Lemma

Notes

source: folklore with via: switching-lemma. Before this pass the switching lemma sat in the citation slot, which made an unattributed claim read as an attributed one: Switching Lemma is a wiki page with no author, year, or venue, not a bibliographic record. It is the technique, so it belongs in via; the statement itself has no citation and says so.

status: stub, for two reasons recorded and not fixed:

• over large domains is a hypothesis qualifier carried in prose. The switching lemma is only meaningful for superpolynomial $|\mathcal{D}|$; compare small-domain PRPs.
• The iPRF security game gives $\mathcal{A}$ an inversion oracle, so the forward- only switching lemma does not by itself justify the claim — a strong PRP and a two-sided bound appear to be needed. This is already flagged against both pages in the fact-check queue.