VRF ⇒ weak VRF

Fully-black-box reduction · standard model · folklore · security loss: additive at most 2q/|X| for q oracle queries

Statement

Every VRF with input space is a weak VRF, with the same provability and unique provability: for every efficient against weak pseudorandomness making oracle queries there is an efficient admissible whose advantage in is within an additive of that of , which is negligible since is superpolynomial — standard.

Sketch

forwards to , answers each oracle call of by sampling and querying , and draws a uniform as its own challenge input, forwarding . The simulation is exact unless equals an earlier sample, which may not submit, or a later sample hits , which may not query; each event has probability at most .