Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

The Opportunity in Difficulty: A Dynamic Privacy Budget Allocation Mechanism for Privacy-Preserving Multi-dimensional Data Collection

The Opportunity in Difficulty: A Dynamic Privacy Budget Allocation Mechanism for... Data collection under local differential 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 difficulties, to act as a beneficial factor to improve the efficiency of privacy budget allocation, so as to realize a multi-dimensional data collection under LDP with high comprehensive performance. Specifically, we first 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 (flipping probability) of an attribute related to the state of the previous attributes. Then, we fix the threshold of flipping 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 efficiency and effectiveness of our proposed methods. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Management Information Systems (TMIS) Association for Computing Machinery

The Opportunity in Difficulty: A Dynamic Privacy Budget Allocation Mechanism for Privacy-Preserving Multi-dimensional Data Collection

Download PDF
24 pages

Loading next page...
 
/lp/association-for-computing-machinery/the-opportunity-in-difficulty-a-dynamic-privacy-budget-allocation-ELslrojEqD
Publisher
Association for Computing Machinery
Copyright
Copyright © 2023 Association for Computing Machinery.
ISSN
2158-656X
eISSN
2158-6578
DOI
10.1145/3569944
Publisher site
See Article on Publisher Site

Abstract

Data collection under local differential 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 difficulties, to act as a beneficial factor to improve the efficiency of privacy budget allocation, so as to realize a multi-dimensional data collection under LDP with high comprehensive performance. Specifically, we first 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 (flipping probability) of an attribute related to the state of the previous attributes. Then, we fix the threshold of flipping 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 efficiency and effectiveness of our proposed methods.

Journal

ACM Transactions on Management Information Systems (TMIS) – Association for Computing Machinery

Published: Jan 16, 2023

Keywords: Multi-dimensional data collection

References

  • Comparing security and privacy attitudes among US users of different smartphone and smart-speaker platforms
    [,
  • Learning with privacy at scale
    [,
  • Practical locally private heavy hitters
    [,
  • Local, private, efficient protocols for succinct histograms
    [,
  • Machine learning for identifying group trajectory outliers
    [,
  • Data poisoning attacks to local differential privacy protocols
    [,
  • PowerCut and obfuscator: An exploration of the design space for privacy-preserving interventions for smart speakers
    [,
  • Introduction to the Special Issue on Pattern-Driven Mining, Analytics, and Prediction for Decision Making, Part 1
    [,
  • Collecting telemetry data privately
    [,
  • Local privacy and statistical minimax rates
    [,
  • RAPPOR: Randomized aggregatable privacy-preserving ordinal response
    [,
  • Building a RAPPOR with the unknown: Privacy-preserving learning of associations and data dictionaries
    [,
  • Bayesian Data Analysis
    [,
  • Machine learning basics
    [,
  • How to make private distributed cardinality estimation practical, and get differential privacy for free
    [,
  • Locally differentially private analysis of graph statistics
    [,
  • Discrete distribution estimation under local privacy
    [,
  • Extremal mechanisms for local differential privacy
    [,
  • Understanding Users’ knowledge about the privacy and security of browser extensions
    [,
  • What can we learn privately? SIAM J
    [,
  • The use of differential privacy for census data and its impact on redistricting: The case of the 2020 US Census
    [,
  • Leveraging individual and collective regularity to profile and segment user locations from mobile phone data
    [,
  • From the information bottleneck to the privacy funnel
    [,
  • Foundations of Statistical Natural Language Processing
    [,
  • Distributed privacy-preserving decision support system for highly imbalanced clinical data
    [,
  • Automated feature selection for anomaly detection in network traffic data
    [,
  • Privacy engineering for the smart micro-grid
    [,
  • Anonymization of daily activity data by using-diversity privacy model
    [,
  • Heavy hitter estimation over set-valued data with local differential privacy
    [,
  • From t-closeness-like privacy to postrandomization via information theory
    [,
  • Information theory and privacy in data banks
    [,
  • LoPub: High-dimensional crowdsourced data publication with local differential privacy
    [,
  • Utility-privacy tradeoffs in databases: An information-theoretic approach
    [,
  • Deciding on personalized ads: Nudging developers about user privacy
    [,
  • Estimating travel speed of a road section through sparse crowdsensing data
    [,
  • Mutual information optimally local private discrete distribution estimation
    [,
  • Locally differentially private protocols for frequency estimation
    [,
  • Locally differentially private heavy hitter identification
    [,
  • Randomized response: A survey technique for eliminating evasive answer bias
    [,
  • CALM: Consistent adaptive local marginal for marginal release under local differential privacy
    [,
  • PrivSyn: Differentially private data synthesis
    [,
  • “Whether it’s moral is a whole other story”: Consumer perspectives on privacy regulations and corporate data practices
    [,