2016/06/22 by Kerenidis, Iordanis, Rosén, Adi, Urrutia, Florent
#94A05 #94A17 #Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #E.4 #F.0 #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1606.06872
We introduce a new information theoretic measure that we call 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 also establishes that the amount of randomness needed by a private protocol that computes this function is Ω(n).