Private Approximate Heavy Hitters

Details Private Approximate Heavy Hitters Private Approximate Heavy Hitters

2006-09-29

arxiv.org/abs/cs/0609166v1

Computer Science

Cryptography and Security

17 pages, submitted

Scientific paper

We consider the problem of private computation of approximate Heavy Hitters. Alice and Bob each hold a vector and, in the vector sum, they want to find the B largest values along with their indices. While the exact problem requires linear communication, protocols in the literature solve this problem approximately using polynomial computation time, polylogarithmic communication, and constantly many rounds. We show how to solve the problem privately with comparable cost, in the sense that nothing is learned by Alice and Bob beyond what is implied by their input, the ideal top-B output, and goodness of approximation (equivalently, the Euclidean norm of the vector sum). We give lower bounds showing that the Euclidean norm must leak by any efficient algorithm.

Affiliated with

Also associated with

No associations

Rating

Private Approximate Heavy Hitters 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 Private Approximate Heavy Hitters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Private Approximate Heavy Hitters will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-184282