Publication Details
Title: Any Non-Private Boolean Function Is Complete For Private Multi-Party Computations
Author: E. Kushilevitz, S. Micali, and R. Ostrovsky
Group: ICSI Technical Reports
Date: November 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-076.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-93-076
Bibliographic Reference:
E. Kushilevitz, S. Micali, and R. Ostrovsky. Any Non-Private Boolean Function Is Complete For Private Multi-Party Computations. ICSI Technical Report TR-93-076, November 1993
Author: E. Kushilevitz, S. Micali, and R. Ostrovsky
Group: ICSI Technical Reports
Date: November 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-076.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-93-076
Bibliographic Reference:
E. Kushilevitz, S. Micali, and R. Ostrovsky. Any Non-Private Boolean Function Is Complete For Private Multi-Party Computations. ICSI Technical Report TR-93-076, November 1993