  Consider a network of k parties, each holding a long sequence of n entries (a
database), with minimum vertex-cut greater than t. We show that any empirical
statistic across the network of databases can be computed by each party with
perfect privacy, against any set of t < k/2 passively colluding parties, such
that the worst-case distortion and communication cost (in bits per database
entry) both go to zero as n, the number of entries in the databases, goes to
infinity. This is based on combining a striking dimensionality reduction result
for random sampling with unconditionally secure multi-party computation
protocols.
