×

Reducibility and completeness in private computations. (English) Zbl 0947.68009

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.

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
PDFBibTeX XMLCite
Full Text: DOI