Uniqueness Is a Different Story: Impossibility of Verifiable Random Functions from Trapdoor Permutations

Verifiable random functions (VRFs) are pseudorandom functions with the additional property that the owner of the seed

SK

can issue publicly-verifiable proofs for the statements “

f

(

SK

,

x

) = 

y

”, for any input

x

. Moreover, the output of VRFs is guaranteed to be unique, which means that

y

 = 

f

(

SK

,

x

) is the only image that can be proven to map to

x

. Despite their popularity, constructing VRFs seems to be a challenging task and only a few constructions based on specific number-theoretic problems are known. Basing a scheme on general assumptions is still an open problem. Towards this direction, Brakerski

et al.

showed that verifiable random functions cannot be constructed from one-way permutations in a black-box way.

In this paper we continue the study of the relationship between VRFs and well-established cryptographic primitives. Our main result is a separation of VRFs and adaptive trapdoor permutations (ATDPs) in a black-box manner. This result sheds light on the nature of VRFs and is interesting for at least three reasons:

First, the separation result of Brakerski

et al.

gives the impression that VRFs belong to the “public-key world”, and thus their relationship with other public-key primitives is interesting. Our result, however, shows that VRFs are strictly stronger and cannot be constructed (in a black-box way) form primitives like e.g., public-key encryption (even CCA-secure), oblivious transfer, and key-agreement.

Second, the notion of VRFs is closely related to weak verifiable random functions and verifiable pseudorandom generators which are both implied by TDPs. Dwork and Naor (FOCS 2000) asked whether there are transformation between the verifiable primitives similar to the case of “regular” PRFs and PRGs. Here, we give a negative answer to this problem showing that the case of verifiable random functions is essentially different.

Finally, our result also shows that

unique

signatures cannot be instantiated from ATDPs. While it is well known that standard signature schemes are equivalent to OWFs, we essentially show that the uniqueness property is crucial to change the relations between primitives.