2026-07-23T08:16:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6469 2024-03-06T10:38:21Z ddc:004 open_access

Multi-Party Protocols, Information Complexity and Privacy Kerenidis, Iordanis Rosén, Adi Urrutia, Florent multi-party protocols information theory communication complexity multi-party private computation (MPC) randomness We introduce the new measure of Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing peer-to-peer model and show a number of interesting properties and applications of our new notion: the Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; an explicit calculation of the zero-error Public Information Complexity of the k-party, n-bit Parity function, where a player outputs the bit-wise parity of the inputs. The latter result establishes that the amount of randomness needed for a private protocol that computes this function is Omega(n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Iordanis Kerenidis and Adi Rosén and Florent Urrutia 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.57 urn:nbn:de:0030-drops-64696 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.57 eng https://creativecommons.org/licenses/by/3.0/legalcode