We utilize a differential privacy mechanism (Laplace noise, with scale $b$) to provide the privacy of records stored within a dataset. Each individual is associated with two, and at most $k$, records. These records are represented as $(\textsf{Username}, O_i)$, where $O_i$ denotes the $i$th noisy value (generated by the mechanism) corresponding to an individual, namely $\textsf{Username}$. How do we calculate the privacy loss for an individual, taking into account that two or at most $k$ records are associated with the individual?

For example, considering user Alice, the following records are assigned to her in the dataset: $(\textsf{Alice}, O_1=1.25), (\textsf{Alice}, O_2=1.89), (\textsf{Alice}, O_3=2.14)$.

I am wondering how much privacy she loses due to these records.


1 Answer 1


The straightforward way to analyze this is via the notion of group privacy. Recall the standard notion of differential privacy.

A mechanism $M$ is said to be $(\epsilon,\delta)$ differentially private if, for all adjacent databases $D\sim D'$, for all sets $S$, one has that $$\Pr[M(D)\in S] \leq \exp(\epsilon) \Pr[M(D')] + \delta$$

Here, the adjacency notion is that $D, D'$ differ in a single record. In other words, when formatted appropriately, one has that $\lVert D-D'\rVert_0 = 1$, where $\lVert x\rVert_0 = |\{i\mid x_i\neq 0\}|$ is the Hamming "metric".

Group privacy deals with the related question for adjacent databases $D\sim_k D'$, where now this means that $\lVert D-D'\rVert_0 \leq k$. The following is well-known (see the footnote of page 20 of the DP book)

If $M$ is $(\epsilon,\delta)$-differentially private for databases $D\sim D'$, then for any $k\in\mathbb{N}$ it is $(k\epsilon, k\exp((k-1)\epsilon)\delta)$-differentially private for databases $D\sim_k D'$.

You're essentially asking about the privacy loss of the "alice group", which may have size at most $k$ members. The easy thing to say is that group privacy implies the resulting scheme is $(k\epsilon, k\exp((k-1)\epsilon)\delta)$-DP.

Note that if you care about approximate-DP schemes, group privacy is somewhat easier to reason about in terms of concentrated DP. Here, a $\rho$-CDP scheme becomes a $k^2\rho$-CDP scheme for groups of size $k$.

One thing I don't know is the following. Let $U$ be your set of users, and for user $u\in U$ let $k_u$ be the number of records your database contains associated with that user. Does the privacy loss of user $u$ scale with $k_u$ or $k:=\max_u k_u$? When reasoning about user $u$, if the quantity $k_u$ is publicly known the privacy loss should scale with $k_u$, but if $k_u$ is a sensitive quantity itself then I am not sure what happens.

  • $\begingroup$ To Mark Schultz-Wu: For example, let's assume there are three users. If they have $k_1$, $k_2$, and $k_3$ records associated with them respectively, then we should consider epsilon as $Max(k_1, k_2, k_3) \times \epsilon$. Am I correct? $\endgroup$ Commented Mar 27 at 9:44
  • 1
    $\begingroup$ @AmirhosseinAdavoudi yes $\endgroup$
    – Mark Schultz-Wu
    Commented Mar 27 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.