Full text  Click to download. 
Citation  DIMACS Technical Report

Authors  Joan Feigenbaum
Aaron D. Jaggard Michael Schapira 
In previous work (DIMACS TR 200914), we introduced the Privacy Approximation Ratio (PAR) and used it to study the privacy of protocols for secondprice 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).