Privacy-Preserving Sketches for Securely Estimating Intersection Cardinality Over Distributed Data Sets

Computing the number of distinct elements (i.e., cardinality) in the intersection of two sets is a fundamental task in various distributed systems, including measuring origin-destination flows in wide-area networks and data synchronization in distributed databases. Due to the enormous data scale, lightweight probabilistic methods, such as FM sketch and HyperLogLog sketch, are extensively used in these systems to estimate the set intersection cardinality, with memory efficiency, high accuracy, and low communication costs. However, if a set's sketch and the hash functions used to construct the sketch are disclosed to an untrusted third party, the privacy of the set's sensitive elements may be compromised. Applying the differential privacy mechanism directly to safeguard the sketch's privacy may incur significant estimation errors. To address this challenge, we propose a novel private sketch, SetXor, for securely estimating intersection cardinality for static sets. Specifically, we incorporate the randomized response noise into the constructed sketch to achieve local differential privacy while ensuring our SetXor sketch is mergeable. We establish a concrete probabilistic model to mitigate the estimation error caused by the noise and theoretically analyze the variance. We further propose a novel sketch SetXorDyn enabling intersection cardinality estimation for streaming sets where elements appear sequentially and contain duplicates. We employ a sampling-like method to eliminate the impact of different parities of element occurrences, allowing us to handle all elements without bias. We conduct extensive experiments on synthetic and four real-world datasets. The results demonstrate that our methods reduce the Average Absolute Relative Error (AARE) of state-of-the-art baselines by up to 110× on synthetic datasets and 80× on real-world datasets, while achieving up to 18.7× speedup under the same settings.