Counting distinct elements (cardinality) across multiple data holders (DHs) privately is fundamental with broad applications, ranging from crowd counting to network monitoring. It is referred to as private distributed cardinality estimation (PDCE). Similarly, determining the intersection cardinality between the unions of two DH groups holds practical significance, a problem we call private distributed intersection cardinality estimation (PDICE). While many efficient methods (e.g., FM and LL sketches) exist, their differential privacy relies on secret hash functions. In PDCE, DHs must share the functions to enable sketch merging, which breaks this assumption and invalidates such guarantees. Although a recent protocol implements the FM sketch on a secret-sharing-based multiparty computation (MPC) framework for PDCE, we observe that it lacks differential privacy guarantees and is computationally expensive. To address these limitations, we propose DP-DICE-Bino, a novel protocol that is computationally efficient and differentially private for PDCE. DP-DICE-Bino is flexible in that it can compute the cardinality of any group of DHs without repeatedly interacting with the DHs. Furthermore, DP-DICE-Bino can also handle PDICE. Experiments show that DP-DICE-Bino achieves orders-of-magnitude speedups and reduces the estimation error by several times compared with the state of the art under the same security requirements.

Counting the number of distinct elements distributed over multiple data holders is a fundamental problem with many real-world applications ranging from crowd counting to network monitoring. Although a number of space and computationally efficient sketch methods (e.g., the Flajolet-Martin sketch and the HyperLogLog sketch) for cardinality estimation have been proposed to solve the above problem, these sketch methods are insecure when considering privacy concerns related to the use of each data holder's personal dataset. Despite a recently proposed protocol that successfully implements the well-known Flajolet-Martin (FM) sketch on a secret-sharing based multiparty computation (MPC) framework for solving the problem of private distributed cardinality estimation (PDCE), we observe that this MPC-FM protocol is not differentially private. In addition, the MPC-FM protocol is computationally expensive, which limits its applications to data holders with limited computation resources. To address the above issues, in this paper we propose a novel protocol DP-DICE, which is computationally efficient and differentially private for solving the problem of PDCE. Experimental results show that our DP-DICE achieves orders of magnitude speedup and reduces the estimation error by several times in comparison with state-of-the-arts under the same security requirements.