Uniqueness is a different story: Impossibility of verifiable random functions from trapdoor permutations

Fiore D, Schröder D (2012)


Publication Language: English

Publication Status: Published

Publication Type: Authored book, Volume of book series

Publication year: 2012

Series: Theory of Cryptography - TCC 2012

Pages Range: 636-653

Event location: Taormina, Sicily

ISBN: 9783642289132

DOI: 10.1007/978-3-642-28914-9_36

Abstract

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. © 2012 Springer-Verlag.

Authors with CRIS profile

How to cite

APA:

Fiore, D., & Schröder, D. (2012). Uniqueness is a different story: Impossibility of verifiable random functions from trapdoor permutations.

MLA:

Fiore, Dario, and Dominique Schröder. Uniqueness is a different story: Impossibility of verifiable random functions from trapdoor permutations. 2012.

BibTeX: Download