Privacy-loss of an individual due their associated records

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.

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.

• 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? Commented Mar 27 at 9:44
• @AmirhosseinAdavoudi yes Commented Mar 27 at 17:54