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 $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 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 {\bf completeness\/} and {\bf $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.
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 |