No fully-black-box reduction from TDP to VRF

Unconditional · against fully-black-box reductions · FS12

Statement

There is no fully-black-box construction of a verifiable random function from trapdoor permutations. FS12 separate VRFs from adaptive trapdoor permutations in a black-box manner, and an adaptive trapdoor permutation is a trapdoor permutation that stays one-way even given an inversion oracle on other points, so the separation from trapdoor permutations follows — FS12. This extends the black-box impossibility of VRFs from one-way permutations — BGRV09.

Notes

• CCA-secure public-key encryption, oblivious transfer and key agreement follow from adaptive trapdoor permutations, so none of them gives VRFs by a fully-black-box construction — FS12.
• VRFs follow non-uniformly from subexponentially hard trapdoor permutations, and uniformly under a standard derandomization assumption — Bit17.