Privacy-Optimized Randomized Response for Sharing Multi-Attribute Data

• URL: http://arxiv.org/abs/2402.07584v1
• Date: Mon, 12 Feb 2024 11:34:42 GMT
• Title: Privacy-Optimized Randomized Response for Sharing Multi-Attribute Data
• Authors: Akito Yamamoto, Tetsuo Shibuya,
• Abstract summary: We propose a privacy-optimized randomized response that guarantees the strongest privacy in sharing multi-attribute data. We also present an efficient algorithm for constructing a near-optimal attribute mechanism. Our methods provide significantly stronger privacy guarantees for the entire dataset than the existing method.
• Score: 1.1510009152620668
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: With the increasing amount of data in society, privacy concerns in data sharing have become widely recognized. Particularly, protecting personal attribute information is essential for a wide range of aims from crowdsourcing to realizing personalized medicine. Although various differentially private methods based on randomized response have been proposed for single attribute information or specific analysis purposes such as frequency estimation, there is a lack of studies on the mechanism for sharing individuals' multiple categorical information itself. The existing randomized response for sharing multi-attribute data uses the Kronecker product to perturb each attribute information in turn according to the respective privacy level but achieves only a weak privacy level for the entire dataset. Therefore, in this study, we propose a privacy-optimized randomized response that guarantees the strongest privacy in sharing multi-attribute data. Furthermore, we present an efficient heuristic algorithm for constructing a near-optimal mechanism. The time complexity of our algorithm is O(k^2), where k is the number of attributes, and it can be performed in about 1 second even for large datasets with k = 1,000. The experimental results demonstrate that both of our methods provide significantly stronger privacy guarantees for the entire dataset than the existing method. In addition, we show an analysis example using genome statistics to confirm that our methods can achieve less than half the output error compared with that of the existing method. Overall, this study is an important step toward trustworthy sharing and analysis of multi-attribute data. The Python implementation of our experiments and supplemental results are available at https://github.com/ay0408/Optimized-RR.

Related papers

• Causal Inference with Differentially Private (Clustered) Outcomes [16.166525280886578]
  Estimating causal effects from randomized experiments is only feasible if participants agree to reveal their responses. We suggest a new differential privacy mechanism, Cluster-DP, which leverages any given cluster structure. We show that, depending on an intuitive measure of cluster quality, we can improve the variance loss while maintaining our privacy guarantees.
  arXiv  Detail & Related papers  (2023-08-02T05:51:57Z)
• Mean Estimation with User-level Privacy under Data Heterogeneity [54.07947274508013]
  Different users may possess vastly different numbers of data points. It cannot be assumed that all users sample from the same underlying distribution. We propose a simple model of heterogeneous user data that allows user data to differ in both distribution and quantity of data.
  arXiv  Detail & Related papers  (2023-07-28T23:02:39Z)
• Private Set Generation with Discriminative Information [63.851085173614]
  Differentially private data generation is a promising solution to the data privacy challenge. Existing private generative models are struggling with the utility of synthetic samples. We introduce a simple yet effective method that greatly improves the sample utility of state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-11-07T10:02:55Z)
• Algorithms with More Granular Differential Privacy Guarantees [65.3684804101664]
  We consider partial differential privacy (DP), which allows quantifying the privacy guarantee on a per-attribute basis. In this work, we study several basic data analysis and learning tasks, and design algorithms whose per-attribute privacy parameter is smaller that the best possible privacy parameter for the entire record of a person.
  arXiv  Detail & Related papers  (2022-09-08T22:43:50Z)
• DP2-Pub: Differentially Private High-Dimensional Data Publication with Invariant Post Randomization [58.155151571362914]
  We propose a differentially private high-dimensional data publication mechanism (DP2-Pub) that runs in two phases. splitting attributes into several low-dimensional clusters with high intra-cluster cohesion and low inter-cluster coupling helps obtain a reasonable privacy budget. We also extend our DP2-Pub mechanism to the scenario with a semi-honest server which satisfies local differential privacy.
  arXiv  Detail & Related papers  (2022-08-24T17:52:43Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  differential privacy has emerged as the gold standard of privacy, however, when it comes to sharing sparse datasets. In this work, we consider a variation of $k$-anonymity, which we call smooth-$k$-anonymity, and design simple large-scale algorithms that efficiently provide smooth-$k$-anonymity.
  arXiv  Detail & Related papers  (2022-07-13T17:09:25Z)
• Differentially Private Multi-Party Data Release for Linear Regression [40.66319371232736]
  Differentially Private (DP) data release is a promising technique to disseminate data without compromising the privacy of data subjects. In this paper we focus on the multi-party setting, where different stakeholders own disjoint sets of attributes belonging to the same group of data subjects. We propose our novel method and prove it converges to the optimal (non-private) solutions with increasing dataset size.
  arXiv  Detail & Related papers  (2022-06-16T08:32:17Z)
• Private measures, random walks, and synthetic data [7.5764890276775665]
  Differential privacy is a mathematical concept that provides an information-theoretic security guarantee. We develop a private measure from a data set that allows us to efficiently construct private synthetic data. A key ingredient in our construction is a new superregular random walk, whose joint distribution of steps is as regular as that of independent random variables.
  arXiv  Detail & Related papers  (2022-04-20T00:06:52Z)
• Partial sensitivity analysis in differential privacy [58.730520380312676]
  We investigate the impact of each input feature on the individual's privacy loss. We experimentally evaluate our approach on queries over private databases. We also explore our findings in the context of neural network training on synthetic data.
  arXiv  Detail & Related papers  (2021-09-22T08:29:16Z)
• Attribute Privacy: Framework and Mechanisms [26.233612860653025]
  We study the study of attribute privacy, where a data owner is concerned about revealing sensitive properties of a whole dataset during analysis. We propose definitions to capture emphattribute privacy in two relevant cases where global attributes may need to be protected. We provide two efficient mechanisms and one inefficient mechanism that satisfy attribute privacy for these settings.
  arXiv  Detail & Related papers  (2020-09-08T22:38:57Z)
• Differentially Private Simple Linear Regression [2.614403183902121]
  We study algorithms for simple linear regression that satisfy differential privacy. We consider the design of differentially private algorithms for simple linear regression for small datasets. We study the performance of a spectrum of algorithms we adapt to the setting.
  arXiv  Detail & Related papers  (2020-07-10T04:28:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.