Abstract  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.