Biblio

Marginal tables are the workhorse of capturing the correlations among a set of attributes. We consider the problem of constructing marginal tables given a set of user's multi-dimensional data while satisfying Local Differential Privacy (LDP), a privacy notion that protects individual user's privacy without relying on a trusted third party. Existing works on this problem perform poorly in the high-dimensional setting; even worse, some incur very expensive computational overhead. In this paper, we propose CALM, Consistent Adaptive Local Marginal, that takes advantage of the careful challenge analysis and performs consistently better than existing methods. More importantly, CALM can scale well with large data dimensions and marginal sizes. We conduct extensive experiments on several real world datasets. Experimental results demonstrate the effectiveness and efficiency of CALM over existing methods.

We develop an auction framework for privacy-preserving data aggregation in mobile crowdsensing, where the platform plays the role as an auctioneer to recruit workers for a sensing task. In this framework, the workers are allowed to report privacy-preserving versions of their data to protect their data privacy; and the platform selects workers based on their sensing capabilities, which aims to address the drawbacks of game-theoretic models that cannot ensure the accuracy level of the aggregated result, due to the existence of multiple Nash Equilibria. Observe that in this auction based framework, there exists externalities among workers' data privacy, because the data privacy of each worker depends on both her injected noise and the total noise in the aggregated result that is intimately related to which workers are selected to fulfill the task. To achieve a desirable accuracy level of the data aggregation in a cost-effective manner, we explicitly characterize the externalities, i.e., the impact of the noise added by each worker on both the data privacy and the accuracy of the aggregated result. Further, we explore the problem structure, characterize the hidden monotonicity property of the problem, and determine the critical bid of workers, which makes it possible to design a truthful, individually rational and computationally efficient incentive mechanism. The proposed incentive mechanism can recruit a set of workers to approximately minimize the cost of purchasing private sensing data from workers subject to the accuracy requirement of the aggregated result. We validate the proposed scheme through theoretical analysis as well as extensive simulations.