Efficient Privacy-Preserving Jaccard Similarity Evaluation Over Multisets for Secure Collaborative Data Analysis

With the rapidly growing demand for collaborative data analysis, Jaccard Coefficient (JC) computation over multisets has been widely adopted in data deduplication to enhance large-scale data processing efficiency, but meanwhile incurs some security issues such as the leakage of input data sets. Thus, Secure Jaccard Coefficient Computation over Multisets (SCJM) schemes have been proposed. However, existing solutions that indirectly compute JC fail to protect the privacy of intersection and union cardinalities, incur high computational overhead, and rely on approximation techniques that cannot support high-precision analysis or simulation-based security proofs. To address these problems, we propose a secure and efficient protocol to accurately compute JC over multisets. Specifically, the protocol computes JC for small-scale data domains using secure oblivious ratio computation, ensuring that under the semi-honest adversarial model, the intersection and union cardinalities remain concealed from all parties, including the decryption key holder, during and after the computation. And it achieves a linear computational cost ofO(em-1) without accuracy loss, whereem-1denotes the maximum number of repetitions of an element in the multiset. The protocol can also be extended to compute the cardinalities of intersection and union. To further enhance efficiency, we introduce a cloud-assisted encryption scheme, which improves computational efficiency by 25.5% to 30.4% compared with the non-cloud-assisted scheme. Additionally, we provide a secure proof of the proposed protocol in the ideal-real paradigm. Experimental results show efficiency advantages of our protocol over the state-of-the-art solution.