# Technical Report CS0869

 TR#: CS0869 Class: CS Title: CHARACTERIZING LINEAR SIZE CIRCUITS IN TERMS OF PRIVACY. Authors: E. Kushilevitz, R. Ostrovsky and A. Rosen PDF Not Available Abstract: In this paper we prove an unexpected relationship between the complexity class of linear size circuits, and $n$-party private protocols. Specifically, let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a boolean function. We show that $f$ has a linear size circuit if and only if $f$ has 1-private, $n$-party protocol in which the total number of random bits used by {\em 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 $O(1)$-random protocols for many important functions for which no such protocol was known. On the other hand, it suggests that proving, for any NP function, that it has no 1-private $O(1)$-random protocol might be quite difficult. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1995/CS/CS0869), rather than to the URL of the PDF files directly. The latter URLs may change without notice.