Locally random reductions: Improvements and applications

A (t, n)-locally random reduction maps a problem instancex into a set of problem instancesy ₁,...,y _n in such a way that it is easy to construct the answer tox from the answers toy ₁,...,y _n, and yet the distribution ont-element subsets ofy ₁,...,y _n depends only on |x|. In this paper we formalize such reductions and give improved methods for achieving them. Then we give a cryptographic application, showing a new way to prove in perfect zero knowledge that committed bitsx ₁,...,x _m satisfy some predicateQ. Unlike previous techniques for such perfect zero-knowledge proofs, ours uses an amount of communication that is bounded by a fixed polynomial inm, regardless of the computational complexity ofQ. These results were presented in preliminary form at the 10th Annual Crypto Conference, Santa Barbara, CA, August 1990. The work of D. Beaver was done at Harvard University, supported in part by NSF Grant CCR-870-4513. The work of J. Kilian was done at MIT and Harvard University, supported by an NSF postdoctoral fellowship.