Emergency BU Alert Boston University’s Charles River Campus will be closed Wednesday, January 28th for the entire day. All academic and administrative activities (e.g. classes, seminars and meetings) are cancelled, however certain essential student services will be operational. Please go to http://www.bu.edu/today for detailed information. When classes resume on Thursday, they will follow the regular class schedule. Whether or how classes are to be made up is at the discretion of individual faculty members. For detailed information about the Boston University Medical campus, please go to http://www.bu.edu/ehs/comm Please note: Employees in essential services must report as scheduled. Essential services include, but are not limited to, University Police, Facilities Management and Planning, Environmental Health & Safety, University Dining Services, Mail Services, Student Health Services and Network Services. For the very latest information, please go to http://www.bu.edu/today

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.