F-PRF, F-PRP — Pseudorandom function, permutation

F-PRF, F-PRP (Pseudorandom function, permutation) is part of Cryptographic Library and Symmetric Primitives in the UC functionality encyclopedia. Status: an emerging formulation, still an active area of research — corrected by this entry to open; see below.

Treated as a single entry: pseudorandom functions and permutations are folded together here, the same way F-COT and F-ROT are.

The page’s one citation does print an idealization of a keyed function — and this site already carries it, on another page. Küsters and Tuengerthal’s \(\mathcal{F}_{\mathsf{crypto}}\) has a Derive command: give it a pointer to a pre-key and a salt, and it returns a pointer to a fresh key that is uniform and unrelated to everything else. That is the ideal behaviour of a pseudorandom function, and it is written up as F-KDF. Transcribing it here would put the same box on two pages under two names, which the encyclopedia has rejected once already — the duplicate flagged between F-ledger and G-ledger was resolved by establishing that they are different objects, and here they would not be.

So the finding is narrower and more useful than “nothing exists”: the ideal PRF exists, it is called key derivation, and its home on this site is F-KDF. What has no separate box is a PRF used as anything other than a key-derivation step.

Why there is no separate box

A PRF’s guarantee only becomes a functionality when the key stays inside. \(\mathcal{F}_{\mathsf{crypto}}\)’s design principle, in its own words, is that users “do not get their hands on the actual symmetric keys, but only on pointers to these keys, since otherwise no security guarantees could be provided”. Once you accept that, an ideal PRF is an ideal key-derivation step — the output is a handle to a fresh uniform key, and there is nothing left to add. A PRF whose key the caller holds is a function the caller can compute, and a box around it guarantees nothing.

The permutation half has a printed idealization too, and it is also elsewhere. A keyed permutation idealized is an ideal cipher, and the UC literature’s answer to that is on F-RP: the full ideal cipher is used as a hybrid everywhere and printed as a functionality essentially nowhere, and what is printed is a deliberate relaxation, the randomized half-ideal cipher. That page records the negative result at length. Between it and F-KDF, both halves of this slot’s title are accounted for on other pages.

The status line said “emerging”, and that was wrong. “Emerging” claims an active formulation in progress. What the literature actually shows is a settled arrangement in which the ideal versions of these primitives live under other names, and the primitives themselves appear in UC statements as hypotheses on realizations. Corrected to open, which is what the three sibling pages carry — F-OWF, F-CRHF, F-PRG.

What would resolve this

  1. A box for a PRF that is not a key-derivation step — one whose outputs are values a protocol uses directly rather than handles to further keys — printed and hybridized against. It would have to say what it gives that F-KDF does not.
  2. Retire the slot and let the cross-references stand. Given that both halves are covered elsewhere, this is the more likely right answer. An editorial decision, not a transcription’s to make.

Formal artifacts

No machine-checked formalization yet, and none is possible before there is a definition to formalize.

References:

  • Küsters and Tuengerthal. Ideal key derivation and encryption in simulation-based security. In Topics in Cryptology – CT-RSA 2011, volume 6558 of LNCS, pages 161–179, 2011. This page’s original and only citation. It prints \(\mathcal{F}_{\mathsf{crypto}}\) (Figures 4–6, pp. 30–32 of revision 20101011:201701), whose item 12, Derive, is the ideal keyed function this slot would otherwise carry — and which is transcribed on F-KDF. Items 13–14 are on F-MAC and the whole is on F-crypto. The design principle quoted above is §3.1, p. 4.
  • Dos Santos, Gu, and Jarecki. Randomized half-ideal cipher on groups with applications to UC (a)PAKE. In Advances in Cryptology – EUROCRYPT 2023. Cited for the permutation half: the printed object nearest an ideal keyed permutation, and the page recording why the full ideal cipher has no box. It is on F-RP. Added to this page’s references by this entry.