• Calendar

February 18, Wednesday
12:00 – 14:00

Verifiable random functions, introduced by Micali, Rabin and Vadhan, are a primitive aimed at coping with the absence of random oracles in the real world. While replacing the random oracle with a pseudorandom function can be a solution in some cases, its drawback is the function's seed owner's ability to adaptively change its answers and thus manipulate the protocol. In a verifiable random function, the seed owner produces a public-key at the beginning of the interaction, which constitutes a commitment to all (pseudorandom) values of the function. It can then produce, for any input, a proof that the output has been computed correctly (with respect to that public-key). Even a maliciously chosen public-key must not enable proving different outputs for the same input.

Verifiable random functions found various implementations and uses. However, no implementation based on a general assumption (such as the existence of one-way functions or even stronger assumptions like trapdoor permutations) is known.

We define a relaxation of verifiable random functions, which we call weak verifiable random functions, in the spirit of Naor and Reingold's weak pseudorandom functions. We show that this relaxed notion can be derived from various assumptions (including general assumptions); that the existence of weak verifiable random functions is essentially equivalent to the existence of non-interactive zero-knowledge proof systems for all of NP (in the common random string model); and prove that weak verifiable random functions (and thus also "standard" verifiable random functions) cannot be constructed from one-way permutations in a black-box manner, providing a first separation result for (standard) verifiable random functions from any cryptographic primitive.

No prior knowledge on black-box separations is assumed.

Joint work with Shafi Goldwasser, Guy Rothblum and Vinod Vaikuntanathan.