Private and threshold set-intersection

Abstract: "In this paper we consider the problem of privately computing the intersection of sets (set-intersection), as well as several variations on this problem: cardinality set-intersection, threshold set-intersection, and over-threshold set-intersection. Cardinality set-intersection is the problem of determining the size of the intersection set, without revealing the actual threshold set. In threshold set-intersection, only the elements which appear at least a threshold number t times in the players' private inputs are revealed. Over-threshold set-intersection is a variation on threshold set-intersection in which not only the threshold set is revealed, but also the number of times each element in the threshold set appeared in the private inputs. We propose protocols that are more efficient than those previously known for set-intersection in the malicious case, as well as new protocols for problems which had no previous solution that did not utilize general secure circuit computation: Set-intersection protocols for the case of: n = 2 malicious parties that do not utilize the cut-and-choose technique; n [> or =] 3 malicious parties, for which there was no previous efficient solution; and multisets, in which elements may appear more than once. Cardinality set-intersection protocols secure against n [> or =] 2 malicious parties and n [> or =] 3 honest-but-curious parties, for which there were no previous efficient solutions. Threshold set-intersection protocols for n [> or =] 2 honest-but-curious parties, for which there was no previous efficient solution. Over-threshold set-intersection protocols for the case of n [> or =] 2 honest-but-curious parties and the case of n [> or =] 2 malicious parties, for which there was no previous efficient solution. Fair protocols for all problems (when fairness in decryption is enforced). Protocols which are secure against even n-1 dishonest colluding parties.