Any Non-Private Boolean Function Is Complete For Private Multi-Party Computations

Let g be an n-argument boolean function. Suppose we are given a black-box for g, to which n honest-but-curious players can secretly give inputs and it broadcasts the result of operating g on these inputs to all the players. We say that g is complete (for multi-party private computations) if for every function f, the n players can compute the function f n-privately, given the black-box for g. In this paper, we characterize the boolean functions which are complete: we show that a boolean function g is complete if and only if g itself cannot be computed n-privately (when there is no black-box available). Namely, for boolean functions, the notions of f completeness and f n-privacy are complementary. On the other hand, for non-boolean functions, we show that this two notions are not complementary. Our result can be viewed as a generalization (for multi-party protocols and for (n ? 2)-argument functions) of the two-party case, where it was known that two-argument functions which contain "embedded-OR" are complete.

ICSI Technical Report TR-93-076

Technical Report