Computer Science – Cryptography and Security
Scientific paper
2010-01-19
Computer Science
Cryptography and Security
34 pages, nine figures, one table. Version 2 adds acknowledgements and Appendix B
Scientific paper
In previous work (arXiv:0910.5714), we introduced the Privacy Approximation Ratio (PAR) and used it to study the privacy of protocols for second-price Vickrey auctions and Yao's millionaires problem. Here, we study the PARs of multiple protocols for both the disjointness problem (in which two participants, each with a private subset of {1,...,k}, determine whether their sets are disjoint) and the intersection problem (in which the two participants, each with a private subset of {1,...,k}, determine the intersection of their private sets). We show that the privacy, as measured by the PAR, provided by any protocol for each of these problems is necessarily exponential (in k). We also consider the ratio between the subjective PARs with respect to each player in order to show that one protocol for each of these problems is significantly fairer than the others (in the sense that it has a similarly bad effect on the privacy of both players).
Feigenbaum Joan
Jaggard Aaron D.
Schapira Michael
No associations
LandOfFree
Approximate Privacy: PARs for Set Problems 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 Approximate Privacy: PARs for Set Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Privacy: PARs for Set Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-637007