# 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

Abstract:

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