  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
computational 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.
