Kilian, Joe; Kushilevitz, Eyal; Micali, Silvio; Ostrovsky, Rafail Reducibility and completeness in private computations. (English) Zbl 0947.68009 SIAM J. Comput. 29, No. 4, 1189-1208 (2000). Summary: We define the notions of reducibility and completeness in (two-party and multiparty) 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 blackbox 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\).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 n-argument boolean functions, the notions of completeness and \(n\)-privacy are complementary. This characterization provides a huge collection of complete functions any nonprivate boolean function!) compared to very few examples that were given (implicitly) in previous work. On the other hand, for nonboolean functions, we show that these two notions are not complementary. Cited in 4 Documents MSC: 68M12 Network protocols 68P25 Data encryption (aspects in computer science) 94A60 Cryptography 94A62 Authentication, digital signatures and secret sharing 68Q99 Theory of computing 68R05 Combinatorics in computer science Keywords:private computation; reducibility; completeness; oblivious-transfer PDFBibTeX XMLCite \textit{J. Kilian} et al., SIAM J. Comput. 29, No. 4, 1189--1208 (2000; Zbl 0947.68009) Full Text: DOI