Locally random reductions: Improvements and applications

A (t, n)-locally random reduction maps a problem instance x into a set of problem instances y(1), ..., y(n) in such a way that it is easy to construct the answer to x from the answers to y(1), ..., y(n), and yet the distribution on t-element subsets of y(1), ..., 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 bits x(1), ..., x(m) satisfy some predicate Q. Unlike previous techniques for such perfect zero-knowledge proofs, ours uses an amount of communication that is bounded by a fixed polynomial in m, regardless of the computational complexity of Q.