On Unconditionally Secure Computation With Vanishing Communication Cost

Date Added: Oct 2010
Format: PDF

The authors 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. They 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 sub sampling of the sequences.