Barak, BoazOng, Shien JinVadhan, Salil2019-10-032007Barak, Boaz, Shien Jin Ong, and Salil Vadhan. 2007. “Derandomization in Cryptography.” SIAM Journal on Computing 37 (2): 380–400. https://doi.org/10.1137/050641958.0097-53971095-7111http://nrs.harvard.edu/urn-3:HUL.InstRepos:41467486We give two applications of Nisan-Wigderson-type (NW-type) ("noncryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct the following two protocols: (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 = DTIME(2(O(n))) has a function of nondeterministic circuit complexity 2(Omega(n)). Our witness-indistinguishable proofs are obtained by using the NW-type generator to derandomize the ZAPs of Dwork and Naor [Proceedings of the 41st Annual ACM Symposium on Foundations of Computer Science, 2000, pp. 283-293]. 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, 4 (1991), pp. 151-158]. Previous constructions of noninteractive commitment schemes were known only under incomparable assumptions.en-USJournal Article2019-10-0310.1137/050641958