On Unconditionally Secure Computation with Vanishing Communication Cost

Tuesday November 23, 2010, 10:00 am in MCS 137

Speaker: Ye Wang, Boston University Electric and Computer Engineering

We propose a novel distortion-theoretic approach to a secure
three-party computation problem. Alice and Bob have deterministic
sequences, and Charlie wishes to compute a normalized sum-type
function of those sequences. We construct three-party protocols that
allow Charlie to compute the function with arbitrarily high accuracy,
while maintaining unconditional privacy for Alice and Bob and
achieving vanishing communication cost. This work leverages a striking
dimensionality reduction that allows a high accuracy estimate to be
produced from only a random subsampling of the sequences. The
worst-case distortion of the estimate, across all arbitrary
deterministic sequences of any length, is independent of the
dimensionality (length) of the sequences and proportional to inverse
square root of the number of samples that the estimate is based upon.

The paper can be found on Arxiv here http://arxiv.org/abs/1010.0670