  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 $\Omega(n)$.
