PRG ⇒ puncturable PRF

Fully-black-box reduction · standard model · BW13, KPTZ13, BGI14 · security loss: a factor 2n for input length n: n PRG hybrids, one per level of the path to , from each of the real and ideal worlds to the world where the sibling seeds and the challenge are independent and uniform; this is for the length-doubling , and stretching a given PRG to adds its own loss

Statement

If a length-doubling PRG exists, the GGM function with , on for , is a puncturable PRF with selective security: the key punctured at is , where and : the point together with the seeds of the siblings of the nodes on the path from the root to , from which every with is computed by descending from the sibling where leaves the path — BW13, KPTZ13, BGI14. Such a exists if any PRG does, since a PRG can be stretched to double its seed length — standard.

Sketch

Replace, level by level along the path to , the pair of children of the current path node by a uniform pair; each step is one PRG hybrid. After steps the sibling seeds and are independent uniform seeds; the same steps, with replaced by an independent uniform value throughout, take the ideal world there too.

Notes

  • The three papers introduced puncturable (more generally constrained) PRFs independently; BW13 also give constrained PRFs for circuit predicates from multilinear maps.
  • The construction is PRG ⇒ PRF (GGM) — GGM86 — with the punctured key added; with OWF ⇒ PRG — HILL99 — puncturable PRFs follow from one-way functions.