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 $f:\{0,1\}^n\to\{0,1\}$ be a boolean function. We show that $f$ has a linear size circuit if and only if $f$ 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 |