Characterizing linear size circuits in terms of privacy

In this paper we prove a perhaps unexpected relationship between the comple xity class of the boolean functions that have linear size circuits and n-pa rty private protocols. Specifically, let f be a boolean function, We show t hat f has a linear size circuit if and only if f has a 1-private n-party pr otocol in which the total number of random bits used by all players is cons tant. From the point of view of complexity theory, our result gives a chara cterization 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, t hat it has no 1-private constant-random protocol, might be difficult. (C) 1 999 Academic Press.