Paper Info
Title
Secure Multiset Intersection Cardinality and its Application to Jaccard Coefficient
Abstract
The Jaccard Coefficient, as an information similarity measure, has wide variety of applications, such as cluster analysis and image segmentation. Due to the concerns of personal privacy, the Jaccard Coefficient cannot be computed directly between two independently owned datasets. The problem, secure computation of the Jaccard Coefficient for multisets (SJCM), considers the situation where two parties want to securely compute the random shares of the Jaccard Coefficient between their multisets. During the process, the content of each party’s multiset is not disclosed to the other party and also the value of Jaccard Coefficient should be hidden from both parties. Secure computation of multiset intersection cardinality is an important sub-problem of SJCM. Existing methods when applied to solve such a problem can lead to either insecure or inefficient solutions. Our work addresses this gap. We first present a basic SJCM protocol constructed using the existing secure dot product method as a sub-routine. Then, as a major contribution, we propose an approximated version of our basic protocol to improve efficiency without compromising accuracy much. We provide various experimental results to show that the proposed protocols are significantly more efficient than the existing techniques when the domain size is small using both simulated and real datasets.
Year
DOI
Venue
2016
10.1109/TDSC.2015.2415482
IEEE Trans. Dependable Sec. Comput.
Keywords
Field
DocType
Garbled Circuits,Homomorphic Encryption,Jaccard Coefficient,Multiset Intersection,Security
Homomorphic encryption,Secure multi-party computation,Similarity measure,Multiset,Computer science,Cardinality,Theoretical computer science,Encryption,Jaccard index,Dot product
Journal
Volume
Issue
ISSN
PP
99
1545-5971
Citations 
PageRank 
References 
3
0.42
27
Authors
2
Name
Order
Citations
PageRank
Samanthula, B.K1873.11
Wei Jiang2953.57