Paper 2006/078

Verifiable Random Permutations

Yevgeniy Dodis and Prashant Puniya

Abstract

Pseudorandom Functions (PRFs), introduced by Goldreich, Goldwasser and Micali, allow one to efficiently simulate the computation of a function which is indistinguishable from a truly random function. A seemingly stronger primitive is that of a (strong) pseudorandom permutation (PRP), which allows one to efficiently simulate a truly random permutation (and its inverse). The celebrated result of Luby and Rackoff shows that these primitives are, in fact, equivalent: four rounds of the Feistel transform are necessary and sufficient to turn a PRF into a (strong) PRP. In this paper we study a similar conversion for the verifiable analogs of PRFs and PRPs, called Verifiable Random Functions (VRFs) and Verifiable Random Permutations (VRPs). VRFs, introduced by Micali, Rabin and Vadhan, extend the notion of a PRF to allow the owner of the secret key for the VRF to prove to the outside parties that a given VRF value was correctly (and uniquely!) computed. Yet, such proofs do not violate the pseudorandomness of the remaining, yet ``unopened'' values. VRPs, introduced in this paper, similarly extend the notion of PRPs. We notice that the result of Luby and Rackoff no longer applies to converting VRFs into VRPs, since the VRP proofs must reveal the VRF outputs (and proofs) of the intermediate rounds. Indeed, we show that even logarithmic (in the security parameter) number of rounds is not enough for this conversion. Our main result, however, shows that super-logarithmic number of rounds of the Feistel transform suffice to build a VRP out of an arbitrary VRF. As an application, we give a construction of non-interactive zero-knowledge (NIZK) proofs with efficient provers for any NP language from any VRF. The result is obtained from our VRF--->VRP conversion, by noticing that VRPs easily yield ``invariant signatures'' of Goldwasser and Ostrovsky , which are known to imply NIZK. (We also notice that the detour through VRPs seems necessary for this implication, since using VRFs in place of invariant signatures is provably insufficient for the NIZK construction of Goldwasser et al. to go through.)