PRG ⇒ puncturable PRF
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.