אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

In this work, we analyze privacy in a distributed setting, where privacy is measured in an information theoretic way (i.e. no cryptographic assumptions). The three complexity measures we analyze are (1) internal information, which measures the counter-party privacy-loss inherent in a communication protocol, (2) output information, which measures the reduction in input-privacy that is inherent when the output of the computation is published, and (3) external information, which measures the privacy-loss inherent when the communication between parties is leaked. The main result here is that for public-output protocols, i.e., protocols that require publicly posting the result of the computation, external information can be exponentially larger than the sum of internal and output information. This result can be informally summarized as saying that ``viewing a process from the sidelines (external information) can be vastly more informative than either participating in it (internal information) and/or viewing only its outcome (output information)''. The specific problem for which this exponential separation is shown, and the upper bounds on internal and output information follow closely the recent breakthrough separation of information and communication due to [Ganor, Kol, Raz; FOCS 2014]. The main technical contribution is the lower bound on external information for public-output protocols.