Full Citation
Title: The Opportunity in Difficulty: A Dynamic Privacy Budget Allocation Mechanism for Privacy-Preserving Multi-dimensional Data Collection
Citation Type: Miscellaneous
Publication Year: 2022
ISBN: 10.1145/3569944
ISSN:
DOI: 10.1145/3569944
NSFID:
PMCID:
PMID:
Abstract: Data collection under local diferential privacy (LDP) has been gradually on the stage. Compared with the implementation of LDP on the single attribute data collection, that on multi-dimensional data faces great challenges as follows: (1) Communication cost. Multivariate data collection needs to retain the correlations between attributes, which means that more complex privatization mechanisms will result in more communication costs. (2) Noise scale. More attributes have to share the privacy budget limited by data utility and privacy-preserving level, which means that less privacy budget can be allocated to each of them, resulting in more noise added to the data. In this work, we innovatively reverse the complex multi-dimensional attributes, i.e., the major negative factor that leads to the above diiculties, to act as a beneicial factor to improve the eiciency of privacy budget allocation, so as to realize a multi-dimensional data collection under LDP with high comprehensive performance. Speciically, we irst present a Multivariate k-ary Randomized Response (kRR) mechanism, called Multi-kRR. It applies the RR directly to each attribute to reduce the communication cost. To deal with the impact of a large amount of noise, we propose a Markov-based dynamic privacy budget allocation mechanism Markov-kRR, which determines the present privacy budget (lipping probability) of an attribute related to the state of the previous attributes. Then, we ix the threshold of lipping times in Markov-kRR and propose an improved mechanism called MarkFixed-kRR, which can obtain more optimized utility by choosing the suitable threshold. Finally, extensive experiments demonstrate the eiciency and efectiveness of our proposed methods.
Url: https://doi.org/10.1145/3569944
User Submitted?: No
Authors: Chen, Xue; Wang, Cheng; Yang, Qing; Hu, Teng; Jiang, Changjun
Publisher:
Data Collections: IPUMS USA
Topics: Methodology and Data Collection, Population Data Science
Countries: