# PPDC: A Privacy-Preserving Distinct Counting Scheme for Mobile Sensing
## 1 Introduction  
With the rapid development of information technology and modern manufacturing, mobile devices are almost ubiquitous nowadays and have occupied an indispensable position in daily lives of many. Especially, those devices, like smartphones, which are equipped with ROMs, CPUs, and a variety of sensors such as GPS, camera and so on, are used not only for their traditional functions, but also for sensing, data transmission, and calculation. As a result, these features make these devices ideal mobile carriers favored by researchers as they study many issues. The mobile sensing problem is one of these issues. In recent years, a considerable amount of mobile sensing projects have been developed using different mobile devices, like [1; 2; 3]. The process of mobile sensing can be described in the following steps: the sensing task publisher (or the aggregator) issues tasks to users with mobile devices, then mobile devices of users collect sensing data and send them to the aggregator. After that, the aggregator processes all the data to draw valid conclusions. In general situation, the aggregator needs to collect and monitor users' data continuously, which means that the scale of collected sensing data is considerable. The data can be in various forms, including camera images, location data, etc. There are two essential challenges in actual mobile sensing projects. One is that whether users with mobile devices are willing to give the original sensing data to the aggregator. As the original data may contain users' private information such as physical location, consumption habits, physical health, etc., most users would give a negative reaction to such a mobile sensing application lacking reliable privacy protection. The aggregation result would be incomplete and lack representativeness. The other one is, for the aggregator, how to solve the distinct counting problem [4] when facing the huge sensing dataset with a large amount of duplicate data in various forms. If the aggregator does not have a good understanding of the cardinality of users' data, then a lot of meaningless computing resources will be wasted to handle duplicate data during the whole aggregation. In addition, excessive repetitive elements in an aggregated dataset may result in characteristics of data being inconspicuous. For example, in the vehicular sensing network, users may transmit sensing information about road congestion to aggregators, and information about the same intersection from different users can be highly repetitive. Aggregators should not waste time and resources on duplicate data when they count congestion and expect subsequent analysis, such as optimizing path selection. At this point, the aggregator should first make cardinal statistics of the original data, and then analyse the traffic congestion degree. In other words, a solution which can ensure the safety of users' privacy as well as solve the distinct counting problem is in urgent need. Exiting studies about the distinct counting problem in mobile sensing mainly focus on researching various algorithms (such as the Flajolet-Martin sketch [5] and LogLog [6]); few works have considered the privacy of users during data aggregation. [PERSON] et al. [7] propose a secure data aggregation scheme, while their security goal is to enable the traffic monitoring center to verify whether an aggregate sensing report is correct or not. Their security refers to the aggregator's aggregated security rather than the user's privacy protection. In this paper, we propose a scheme, Privacy-Preserving Distinct Counting scheme (PPDC for short), to solve the distinct counting problem with privacy protection of users. PPDC is based on a semi-honest model and it can complete distinct counting over large datasets with various forms of elements in the mobile sensing scenario.