A Zero-One Law for Boolean Privacy

A Boolean function f:A₁ × A₂ × ⋯ × Aₙ → \ 0,1 \ is t-private if there exists a protocol for computing f so that no coalition of size t can infer any additional information from the execution, other than the value of the function. It is shown that f is n/2-private if and only if it can be represented as \[ f ( x_1 ,x_2 , ⋯ ,x_n ) = f_1 ( x_1 ) ⊕ f_2 ( x_2 ) ⊕ ⋯ ⊕ f_n ( x_n ), \] where the fᵢ are arbitrary Boolean functions. It follows that if f is n/2-private, then it is also n-private. Combining this with a result of Ben-Or, Goldwasser, and Wigderson, and of Chaum, Crepeau, and Damgard, [Proc. 20th Symposium on Theory of Computing, 1988, pp. 1–10 and pp. 11–19] an interesting “zero-one” law for private distributed computation of Boolean functions is derived: every Boolean function defined over a finite domain is either n-private, or it is ( n - 1 )/2-private but not n/2-private. A weaker notion of privacy is also investigated, where (a) coalitions are allowed to infer a limited amount of additional information, and (b) there is a probability of error in the final output of the protocol. It is shown that the same characterization of n/2-private Boolean functions holds, even under these weaker requirements.In particular, this implies that for Boolean functions, the strong and the weak notions of privacy are equivalent.