On Unconditionally Secure Computation with Vanishing Communication Cost - 10/29/2010

Ye Wang

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 is available here [http://arxiv.org/abs/1010.0670v2]

-- JiaxiJin - 28 Oct 2010