Reducibility and completeness in multi-party private computations
Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky · 2002
We define the notions of reducibility and completeness in multi-party private computations. Let g be an n-argument function. We say that a function f is reducible to 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 inputs). We say that g is complete (for multi-party 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 computed n-privately (when there is no black-box available). Namely, for Boolean functions, the notions of completeness and n-privacy are complementary. This characterization gives a huge collection of complete functions (any non-private Boolean function!) compared to very few examples given (implicitly) in previous work. On the other hand, for non-Boolean functions, we show that these two notions are not complementary. Our results can be viewed as a generalization (for multi-party protocols and for (n/spl ges/2)-argument functions) of the two-party case, where it was known that Oblivious Transfer protocol (and its variants) are complete.>