Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-209 | 29th December 2015 10:16

On the information leakage of public-output protocols


Authors: Eli Ben-Sasson, Gal Maor
Publication: 29th December 2015 10:16
Downloads: 1579


In this paper three complexity measures are studied: (i) internal information, (ii) external information, and (iii) a measure called here "output information". Internal information (i) measures the counter-party privacy-loss inherent in a communication protocol. Similarly, the output information (iii) measures the reduction in input-privacy that is inherent when the output of the computation is published. External information (ii) 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.

ISSN 1433-8092 | Imprint