Characterizing Linear Size Circuits in Terms of Privacy

✍ Scribed by Eyal Kushilevitz; Rafail Ostrovsky; Adi Rosén

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 145 KB
• Volume: 58
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1997.1544

✦ Synopsis

In this paper we prove a perhaps unexpected relationship between the complexity class of the boolean functions that have linear size circuits and n-party private protocols. Specifically, let f 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 previously 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.