Any Non-Private Boolean Function Is Complete For Private Multi-Party Computations
Title | Any Non-Private Boolean Function Is Complete For Private Multi-Party Computations |
Publication Type | Technical Report |
Year of Publication | 1993 |
Authors | Kushilevitz, E., Micali S., & Ostrovsky R. |
Other Numbers | 864 |
Abstract | Let g be an n-argument boolean function. Suppose we are given a black-box for g, to which n honest-but-curious players can secretly give inputs and it broadcasts the result of operating g on these inputs to all the players. We say that g is complete (for multi-party private computations) if for every function f, the n players can compute the function f n-privately, given the black-box for g. In this paper, we characterize the boolean functions which are complete: 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 f n-privacy are complementary. On the other hand, for non-boolean functions, we show that this two notions are not complementary. Our result can be viewed as a generalization (for multi-party protocols and for (n ? 2)-argument functions) of the two-party case, where it was known that two-argument functions which contain "embedded-OR" are complete. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-076.pdf |
Bibliographic Notes | ICSI Technical Report TR-93-076 |
Abbreviated Authors | E. Kushilevitz, S. Micali, and R. Ostrovsky |
ICSI Publication Type | Technical Report |