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.)

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
pseudo-randomnessverifiable random functionsFeistel TransformZero knowledge
Contact author(s)
puniya @ cs nyu edu
History
2006-02-28: received
Short URL
https://ia.cr/2006/078
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/078,
      author = {Yevgeniy Dodis and Prashant Puniya},
      title = {Verifiable Random Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2006/078},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/078}},
      url = {https://eprint.iacr.org/2006/078}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.