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