Technical Report CS0869

TR#:CS0869
Class:CS
Title: CHARACTERIZING LINEAR SIZE CIRCUITS IN TERMS OF PRIVACY.
Authors: E. Kushilevitz, R. Ostrovsky and A. Rosen
PDFNot 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.
CopyrightThe 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.

To the list of the CS technical reports of 1995
To the main CS technical reports page

Computer science department, Technion
admin