A ZERO-ONE LAW FOR BOOLEAN PRIVACY

A Boolean function f: A1 x A2 x ... x A(n)--> {0, 1} is t-private if there exists a protocol for computing f so that no coalition of size less-than-or-equal-to t can infer any additional information from the execution, other than the value of the function. It is shown that f is inverted-right-perpendicular n/2 inverted-left-perpendicular if and only if it can be represented as f(x1, x2,..., x(n)) = f1(x1) + f2(x2) +... + f(n)(x(n)), where the f(i) are arbitrary Boolean functions. It follows that if f is inverted-right-perpendicular n/2 inverted-left-perpendicular-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 right-perpendicular (n - 1)/2 left-perpendicular-private but not inverted-right-perpendicular n/2 left-inverted-perpendicular-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 inverted-right-perpendicular n/2 inverted-left-perpendicular-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.