Locally Random Reductions: Improvements and Applications

Authors: n Beaver, Joan Feigenbaum, Joe Kilian and Phillip Rogaway

Reference: Advances in Cryptology - CRYPTO '95, Lecture Notes in Computer Science, Vol. 963, D. Coppersmith, ed., Springer-Verlag, 1995.

Abstract: The notions of reducibility and self-reducibility have yielded valuable insights into many branches of complexity theory. In this paper, we formally define and develop the theory of locally random reductions, which are special cases of multi-oracle instance hiding schemes. Informally, a (t,n)-locally random reduction maps a problem instance X to a set of random problem instances Y1,...,Yn, in such a way that the answers to Y_1, ..., Y_n allow one to reconstruct the answer to X, but for any I1,..., It, the induced distribution on Y_{I1},..., Y_{It} depends only on the size of X.

We express theorems of Beaver-Feigenbaum and Lipton in terms of locally random reductions and improve on their results. Let P be a multivariate polynomial P of degree at most d over a sufficiently large finite field. For any t>0, we exhibit a simple (t,dt+1)-locally random self-reduction for P. Given a function f on n bits, we exhibit simple (t,tn / c lg n)-locally random reductions from f to a related polynomial g.

We then use locally random reductions in a novel protocol for zero-knowledge proofs on committed bits. A computationally unbounded prover commits a sequence of bits X1, ..., Xn to a computationally unbounded verifier using an ideal commitment scheme. At some later time, the prover convinces the verifier of some arbitrary predicate Q(X_1,...,X_n), without revealing any additional information about X_1,...,Xn. We present the first protocol for this problem in which the total amount of communication (including bit commitments) is polynomial in n and independent of the computational complexity of the predicate Q.

Available as PDF or PostScript

Rogaway's home page.