Reducibility and Completeness In Multi-Party Private Computations.
Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky
Abstract:
We define the notions of reducibility and completeness in (two party and multi-party) private computations. Let g be an n-argument function. We say that a function f is reducible to a function gif 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 private computations) if every function fis 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 f 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.
comment: Accepted to SICOMP. Preliminary version appeared in Proceedings of Thirty-fifth Annual IEEE Symposium on the Foundations of Computer Science (FOCS-94)
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |