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 ye t the distribution on t-element subsets of y(1), ..., y(n) depends onl y 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 b its x(1), ..., x(m) satisfy some predicate Q. Unlike previous techniqu es for such perfect zero-knowledge proofs, ours uses an amount of comm unication that is bounded by a fixed polynomial in m, regardless of th e computational complexity of Q.