diana@csri.toronto.edu (Diana Li) (07/21/89)
Department of Computer Science, University of Toronto
(GB = Gailbraith Building, 35 St. George Street)
-------------------------------------------------------------
THEORY SEMINAR
GB 244, at 11:00 a.m., Friday 28 July 1989
Benny Chor
Computer Science Dept., Technion, Israel
"A Zero - One Law for Boolean Privacy"
A Boolean function $f:A_1 X A_2 X ... X A_n --> {0,1}$ is $t$--private if
there exists a protocol for computing $f$ so that no coalition of size $<=
t$ can infer any additional information from the execution, other than the
value of the function. We show that $f$ is $ceil{n/2}$--private if and only
if it can be represented as $$f(x_1,x_2,... ,x_n) = f_1(x_1) xor f_2(x_2)
xor ... xor f_n(x_n),$$ where the $f_i$ are arbitrary Boolean functions.
It follows that if $f$ is $ceil{n/2}$--private, then it is also $n$--
private. Combining this with a result of Ben-Or, Goldwasser, and
Wigderson, we derive an interesting ``zero--one'' law for private
distributed computation of Boolean functions: Every Boolean function
defined over a finite domain is either $n$--private, or it is $floor{(n-
1)/2}$--private but not $ceil{n/2}$--private.
We also investigate a weaker notion of privacy, where (a) coalitions are
allowed to infer a limited amount of additional information, and (b) there
is a probability of error in the final output of the protocol. We show that
the same characterization of $ceil{n/2}$--private Boolean functions holds,
even under these weaker requirements. In particular, this implies that for
Boolean functions, the strong and the weak notions of privacy are
equivalent.
This is joint work with Eyal Kushilevitz.
Sponsored by I.T.R.C.