Reducibility and completeness in private computations

We define the notions of reducibility and completeness in (two-party and mu ltiparty) private computations. Let g be an n-argument function. We say tha t a function f is reducible to a function g if n honest-but-curious players can compute the function f n-privately, given a black box for g (for which they secretly give inputs and get the result of operating g on these input s). We say that g is complete (for private computations) if every function f is reducible to g. In this paper, we characterize the complete boolean functions: we show that a boolean function g is complete if and only if g itself cannot be compute d n-privately (when there is no black box available). Namely, for n-argumen t boolean functions, the notions of completeness and n-privacy are compleme ntary. This characterization provides a huge collection of complete functio ns (any non-private boolean function!) compared to very few examples that w ere given (implicitly) in previous work. On the other hand, for nonboolean functions, we show that these two notions are not complementary.