Boaz Barak, Shien Jin
Ong, and
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.