**
Characterizing Linear Size Circuits in Terms of Privacy.
**

*
Eyal Kushilevitz, Rafail Ostrovsky and
Adi Rosen
*

**
Abstract:
**

In this paper we prove a perhaps unexpected
relationship between the complexity class of
linear size circuits, and $n$-party private protocols.
Specifically, let ƒ:\{0,1\}^{n}→{0,1} be a boolean function.
We show that ƒ has a linear size circuit if and
only if ƒ has a 1-private n-party protocol
in which the total number of random bits used by * all* players is
constant.
From the point of view of complexity theory, our result
gives a characterization of the
class of linear size circuits in terms of another class of a very
different nature.
From the point of view of privacy, this result provides
1-private
protocols that use a constant number of random bits,
for many important functions for which no such protocol was known.
On the other hand, our result suggests that proving, for any NP function,
that it has no 1-private
constant-random protocol, might be
difficult.

**comment:**
Invited paper to the
Journal of Computer and System
Sciences
special issue for STOC 96. Appeared in Vol 58, December 1998.
Preliminary version appeared in the
Proceedings of
The Twenty-Eighth ACM Symposium on Theory of Computing (STOC-96)

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |