Distributed Private Data Analysis: On Simultaneously Solving How and What

Details Distributed Private Data Analysis: On Simultaneously Solving How and What Distributed Private Data Analysis: On Simultaneously Solving How and What

2011-03-14

arxiv.org/abs/1103.2626v1

Computer Science

Cryptography and Security

Scientific paper

We examine the combination of two directions in the field of privacy concerning computations over distributed private inputs - secure function evaluation (SFE) and differential privacy. While in both the goal is to privately evaluate some function of the individual inputs, the privacy requirements are significantly different. The general feasibility results for SFE suggest a natural paradigm for implementing differentially private analyses distributively: First choose what to compute, i.e., a differentially private analysis; Then decide how to compute it, i.e., construct an SFE protocol for this analysis. We initiate an examination whether there are advantages to a paradigm where both decisions are made simultaneously. In particular, we investigate under which accuracy requirements it is beneficial to adapt this paradigm for computing a collection of functions including binary sum, gap threshold, and approximate median queries. Our results imply that when computing the binary sum of $n$ distributed inputs then: * When we require that the error is $o(\sqrt{n})$ and the number of rounds is constant, there is no benefit in the new paradigm. * When we allow an error of $O(\sqrt{n})$, the new paradigm yields more efficient protocols when we consider protocols that compute symmetric functions. Our results also yield new separations between the local and global models of computations for private data analysis.

Affiliated with

Also associated with

No associations

Rating

Distributed Private Data Analysis: On Simultaneously Solving How and What does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distributed Private Data Analysis: On Simultaneously Solving How and What, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed Private Data Analysis: On Simultaneously Solving How and What will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-259231