...researching fundamentals of networking and communications


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

r1 - 2010-10-28 - 19:50:38 - JiaxiJin

Laboratory of Networking and Information Systems
Photonics Building, Room 413
8 St Mary's Street,
Boston MA 02215

Initial web site created by Sachin Agarwal (ska@alum.bu.edu), Modified by Weiyao Xiao (weiyao@alum.bu.edu), Moved to TWiki backend by Ari Trachtenberg (trachten@bu.edu). Managed by Jiaxi Jin (jin@bu.edu).
Syndicate this site RSSATOM