Derandomization in Cryptography

Boaz Barak, Shien Jin Ong, and Salil Vadhan


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:

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

2) 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 E = TIME(2^O(n)) has a function of nondeterministic circuit complexity (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.


  • In Advances in Cryptology---CRYPTO `03, volume 2729 of Lecture Notes in Computer Science, pages 299-315, Springer-Verlag, 17--21 August 2003. [Springer page]
  • Cryptology ePrint Archive Report 2005/365, Oct. 2005. [ePrint page]
    Electronic Colloquium on Computational Complexity TR05-114, Oct. 2005. [ECCC page]
  • SIAM Journal on Computing, 37(2):380-400, May 2007. [SIAM page][ps][pdf]

 [ back to Salil Vadhan's research]