Single-Server Private Linear Transformation: The Individual Privacy Case
- URL: http://arxiv.org/abs/2106.05222v2
- Date: Thu, 10 Jun 2021 01:06:50 GMT
- Title: Single-Server Private Linear Transformation: The Individual Privacy Case
- Authors: Anoosheh Heidarzadeh, Nahid Esmati, and Alex Sprintson
- Abstract summary: This paper considers the single-server Private Linear Transformation (PLT) problem with individual privacy guarantees.
The goal is to minimize the download cost while keeping the identity of each message required for the computation individually private.
- Score: 10.072633952908456
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers the single-server Private Linear Transformation (PLT)
problem with individual privacy guarantees. In this problem, there is a user
that wishes to obtain $L$ independent linear combinations of a $D$-subset of
messages belonging to a dataset of $K$ messages stored on a single server. The
goal is to minimize the download cost while keeping the identity of each
message required for the computation individually private. The individual
privacy requirement ensures that the identity of each individual message
required for the computation is kept private. This is in contrast to the
stricter notion of joint privacy that protects the entire set of identities of
all messages used for the computation, including the correlations between these
identities. The notion of individual privacy captures a broad set of practical
applications. For example, such notion is relevant when the dataset contains
information about individuals, each of them requires privacy guarantees for
their data access patterns. We focus on the setting in which the required
linear transformation is associated with a maximum distance separable (MDS)
matrix. In particular, we require that the matrix of coefficients pertaining to
the required linear combinations is the generator matrix of an MDS code. We
establish lower and upper bounds on the capacity of PLT with individual
privacy, where the capacity is defined as the supremum of all achievable
download rates. We show that our bounds are tight under certain conditions.
Related papers
- Confounding Privacy and Inverse Composition [32.85314813605347]
In differential privacy, sensitive information is contained in the dataset while in Pufferfish privacy, sensitive information determines data distribution.
We introduce a novel privacy notion of ($epsilon, delta$)-confounding privacy that generalizes both differential privacy and Pufferfish privacy.
arXiv Detail & Related papers (2024-08-21T21:45:13Z) - Mean Estimation Under Heterogeneous Privacy Demands [5.755004576310333]
This work considers the problem of mean estimation, where each user can impose their own privacy level.
The algorithm we propose is shown to be minimax optimal and has a near-linear run-time.
Users with less but differing privacy requirements are all given more privacy than they require, in equal amounts.
arXiv Detail & Related papers (2023-10-19T20:29:19Z) - Optimal Private Discrete Distribution Estimation with One-bit Communication [63.413106413939836]
We consider a private discrete distribution estimation problem with one-bit communication constraint.
We characterize the first-orders of the worst-case trade-off under the one-bit communication constraint.
These results demonstrate the optimal dependence of the privacy-utility trade-off under the one-bit communication constraint.
arXiv Detail & Related papers (2023-10-17T05:21:19Z) - Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free [13.198689566654103]
This work considers the problem of mean estimation under heterogeneous Differential Privacy constraints.
The algorithm we propose is shown to be minimax optimal when there are two groups of users with distinct privacy levels.
arXiv Detail & Related papers (2023-04-27T05:23:06Z) - How Do Input Attributes Impact the Privacy Loss in Differential Privacy? [55.492422758737575]
We study the connection between the per-subject norm in DP neural networks and individual privacy loss.
We introduce a novel metric termed the Privacy Loss-Input Susceptibility (PLIS) which allows one to apportion the subject's privacy loss to their input attributes.
arXiv Detail & Related papers (2022-11-18T11:39:03Z) - 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) - 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) - Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD.
We find that most examples enjoy stronger privacy guarantees than the worst-case bound.
This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
arXiv Detail & Related papers (2022-06-06T13:49:37Z) - Single-Server Private Linear Transformation: The Joint Privacy Case [10.072633952908456]
This paper introduces the problem of Private Linear Transformation (PLT) which generalizes the problems of private information retrieval and private linear computation.
The problem includes one or more remote server(s) storing (identical copies of) $K$ messages and a user who wants to compute $L$ independent linear combinations of a $D$-subset of messages.
arXiv Detail & Related papers (2021-06-09T17:09:22Z) - Private Reinforcement Learning with PAC and Regret Guarantees [69.4202374491817]
We design privacy preserving exploration policies for episodic reinforcement learning (RL)
We first provide a meaningful privacy formulation using the notion of joint differential privacy (JDP)
We then develop a private optimism-based learning algorithm that simultaneously achieves strong PAC and regret bounds, and enjoys a JDP guarantee.
arXiv Detail & Related papers (2020-09-18T20:18:35Z) - Bounding, Concentrating, and Truncating: Unifying Privacy Loss
Composition for Data Analytics [2.614355818010333]
We provide strong privacy loss bounds when an analyst may select pure DP, bounded range (e.g. exponential mechanisms) or concentrated DP mechanisms in any order.
We also provide optimal privacy loss bounds that apply when an analyst can select pure DP and bounded range mechanisms in a batch.
arXiv Detail & Related papers (2020-04-15T17:33:10Z)
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.