# 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:

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.

### Versions

- 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]