Derandomization in Cryptography

Boaz Barak; Shien Jin Ong; Salil Vadhan

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2005/365

Derandomization in Cryptography

Boaz Barak, Shien Jin Ong, and Salil Vadhan

Abstract

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct: A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any setup assumption, so it is actually an "NP proof system." A noninteractive bit commitment scheme based on any one-way function. The specific NW-type generator we need is a hitting set generator fooling nondeterministic circuits. It is known how to construct such a generator if ETIME = DTIME(2^O(n)) has a function of nondeterministic circuit complexity 2^\Omega(n) (Miltersen and Vinodchandran, FOCS `99). Our witness-indistinguishable proofs are obtained by using the NW-type generator to derandomize the ZAPs of Dwork and Naor (FOCS `00). To our knowledge, this is the first construction of an NP proof system achieving a secrecy property. Our commitment scheme is obtained by derandomizing the interactive commitment scheme of Naor (J. Cryptology, 1991). Previous constructions of noninteractive commitment schemes were only known under incomparable assumptions.

Metadata

Available format(s): PDF PS
Category: Foundations
Publication info: Published elsewhere. An extended abstract of this paper appeared in CRYPTO 2003.
Contact author(s): shienjin @ eecs harvard edu
History: 2005-10-10: received
Short URL: https://ia.cr/2005/365
License: CC BY

BibTeX

@misc{cryptoeprint:2005/365,
      author = {Boaz Barak and Shien Jin Ong and Salil Vadhan},
      title = {Derandomization in Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2005/365},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/365}},
      url = {https://eprint.iacr.org/2005/365}
}