1 Introduction↩︎

Consider \(n\) users indexed by \(i\in\{1,\dots,n\}\), where user \(i\) holds a private datum \(x_i\in\mathbb{R}\).¹ A server aims to compute and release the aggregate sum \(\sum_{i=1}^n x_i\) (or the average \(\frac{1}{n}\sum_{i=1}^n x_i\)) while preserving the privacy of each individual datum. This aggregation task arises in applications such as distributed and federated learning [1], [2], consensus algorithms [3], [4], and sensor network computations [5], [6], where users contribute local updates or statistics that must be combined while preserving individual privacy.

In the central differential privacy (central-DP) model [7], users transmit their raw data to a trusted server, which then adds noise to the aggregate before releasing it. When the server is not trusted (e.g., it may be honest-but-curious), stronger safeguards are required.

As an alternative, local differential privacy (local-DP) was proposed [8], [9]. In this model, privacy is enforced before data leaves the user. We consider an additive local-noise mechanism in which each user transmits \(x_i + Z_i,\) where \(Z_i\) is a random noise variable. The server’s estimate of the sum becomes \[\sum_{i=1}^n x_i + \sum_{i=1}^n Z_i.\] Because noise is added locally, one expects that the server cannot reliably infer any individual \(x_i\).

In this work, we quantify privacy using pure \(\varepsilon\)-differential privacy (\(\varepsilon\)-DP) and focus exclusively on additive noise mechanisms. Let \(x,\widetilde{x}\in\mathbb{R}^n\) be neighboring data vectors, meaning they differ in at most one coordinate and the change is bounded by a sensitivity parameter \(\Delta>0\); i.e., there exists \(i\in\{1,\dots,n\}\) such that \(x_j=\widetilde{x}_j\) for all \(j\neq i\) and \(|x_i-\widetilde{x}_i|\le\Delta\). The \(\varepsilon\)-DP is then defined as follows.

We seek to design the joint noise vector \(Z^n=(Z_1,\dots,Z_n)\) to satisfy 1 while minimizing the aggregate cost, which in our setting depends only on the noise: \[\begin{align} \label{eq:32cost} \mathbb{E}\!\left[\, L\!\left(\sum_{i=1}^n Z_i\right)\right]. \end{align}\tag{2}\] Here \(L(\cdot)\) is even and nondecreasing on \(\mathbb{R}_+\). A common choice is the \(L_p\) loss \(L(x)=|x|^p\) for \(p\ge 1\).

The prevailing approach in the local differential privacy literature is to add independent noise at each user, often i.i.d.from a common distribution [8], [9]. Independence greatly simplifies the privacy constraints: when the \(Z_i\) are independent, satisfying 1 jointly is equivalent to each \(Z_i\) satisfying the corresponding one-dimensional version of 1 .

However, independent local noise typically incurs a strict utility gap relative to the centralized model [9]. In particular, for quadratic loss \(L(x)=x^2\), the optimal independent mechanism is obtained by choosing each \(Z_i\) according to the one-dimensional optimal distribution, and the resulting aggregate cost is \(n\) times the cost of the corresponding centrally added-noise mechanism.

Our goal is to mitigate this utility gap by allowing correlated noise across users. In our setting, such correlations may be established in an offline phase or via secure channels between users before the privatized data are sent to the server. Since the noise is still added on the user side, we refer to this as a local mechanism. Note that Definition 1 does not require independence and continues to guarantee privacy under correlation. In particular, letting \(Z_{\sim i}:=(Z_1,\dots,Z_{i-1},Z_{i+1},\dots,Z_n)\), for any measurable \(A_i\subseteq\mathbb{R}\) and \(B\subseteq\mathbb{R}^{n-1}\), conditioning 1 on the event \(\{Z_{\sim i}\in B\}\) yields \[\begin{align} \label{eq:32condDP} \Pr\big(x_i+&Z_i\in A_i \mid Z_{\sim i}\in B\big)\nonumber\\ &\;\le\; e^\varepsilon \Pr\big(\widetilde{x}_i+Z_i\in A_i \mid Z_{\sim i}\in B\big). \end{align}\tag{3}\] Thus, even if the server knows all other users’ data and noise values, it still cannot reliably distinguish whether user \(i\)’s datum was \(x_i\) or \(\widetilde{x}_i\).

This shows that using correlated noise additions does not compromise the privacy during the computation phase as long as the mechanism satisfies \(\varepsilon\)-DP condition in 1 . Against this backdrop, we ask the following question.

Can we design \(\varepsilon\)-DP additive local mechanisms with correlated noise that significantly outperform the standard independent-noise mechanisms? We show that the answer is affirmative. We prove that appropriately designed correlated local mechanisms can achieve costs arbitrarily close to the optimal cost attainable under centralized \(\varepsilon\)-DP.

Our approach leverages the characterization of the optimal one-dimensional \(\varepsilon\)-DP mechanism in [10]: we reduce the \(n\)-user problem to a one-dimensional optimization along the aggregate noise direction, obtain a one-dimensional lower bound, and show it is essentially tight via a correlated construction.

For basic sum estimation under local differential privacy, prior work [11] shows that protocols with fully interactive communication, where all messages between users and the server are visible to the server, cannot essentially improve the accuracy of standard noninteractive local mechanisms. Our work does not contradict this, as we allow users to establish correlations securely (e.g., offline or over secure channels²) without revealing the underlying randomness to the server, which enables strictly stronger utility guarantees.

Note that our results have direct implications for distributed summation tasks, most notably distributed mean estimation [9], [13], which underlies aggregation in gradient-based optimization and learning [14], [15] as well as consensus algorithms [3]. In particular, under quadratic loss, correlated noise can achieve an \(O(1)\) error for sum estimation, whereas independent local noise leads to an \(O(n)\) scaling of the loss.

1.1 Related work↩︎

It is worth noting that under approximate differential privacy³, gains from correlated noise are known in the Gaussian setting [16]–[20]. In particular, [18] and [20] show that correlated Gaussian noise can match the performance of centrally added Gaussian noise under quadratic loss. However, these results rely on structural properties specific to Gaussian mechanisms and are tailored to quadratic loss. They do not extend to pure \(\varepsilon\)-DP or to general loss functions.

Our focus in this work is to show that carefully constructed correlated local noise can achieve centralized-DP utility. We do not address the efficient or secure generation of such correlations; these may be developed based on secure aggregation techniques [19], [21]–[23].

It is also worth noting that temporal correlations in added noise have been used to improve distributed gradient methods [24], [25], but such correlations are not relevant to our setting.

2 Preliminaries↩︎

2.1 Notation↩︎

We use the following notation throughout: for \(A\subseteq\mathbb{R}^n\) and \(v\in\mathbb{R}^n\), \(A+v:=\{x+v:\,x\in A\}\), and for \(\alpha\in\mathbb{R}\), \(\alpha A:=\{\alpha x:\,x\in A\}\).

For a function \(f:\mathbb{R}^n\to\mathbb{R}\), we write \(f(\alpha(\cdot))\) to denote the function \(x\mapsto f(\alpha x)\). Similarly for a probability measure \(P\) on \(\mathbb{R}^n\), we write \(P(\alpha(\cdot))\) for \(P(\alpha A)\) as a function of \(A\). All probability measures considered in this work are Borel measurable.

2.2 Differential privacy↩︎

In this work, we consider additive mechanisms in which the noise variables \(Z_i\) are chosen independently of the corresponding data \(x_i\). Under this assumption, the privacy requirement 1 depends only on the joint distribution \(P\) of the noise vector \(Z\), and the mechanism is fully specified by \(P\).

To make this observation explicit, define the set of allowable coordinate-wise perturbations \[T_n^\Delta \;:=\; \bigcup_{i=1}^n \{0\}^{i-1}\times[-\Delta,\Delta]\times \{0\}^{n-i},\] i.e., the zero-centered union of length-\(2\Delta\) line segments along each coordinate axis. Then \(x,\widetilde{x}\in\mathbb{R}^n\) are neighboring (for sensitivity \(\Delta\)) if and only if \(\widetilde{x}=x+t\) for a unique \(t\in T_n^\Delta\). Hence 1 is equivalent to requiring that, for all \(x\in\mathbb{R}^n\), all \(t\in T_n^\Delta\), and all measurable \(A\subseteq\mathbb{R}^n\), \[\Pr\!\big(x+Z\in A\big) \;\le\; e^{\varepsilon}\Pr\!\big(x+t+Z\in A\big).\] Equivalently \[\begin{align} \label{eq:32epsDP} P(A)\;\le\; e^{\varepsilon}\,P(A+t). \end{align}\tag{4}\]

Accordingly, when the mechanism \(x\mapsto x+Z\) is \(\varepsilon\)-DP for sensitivity \(\Delta\), we will also say (by abuse of notation) that the noise law \(P\) itself is \(\varepsilon\)-DP for sensitivity \(\Delta\).

2.3 Cost function↩︎

The utility in our setting is quantified by the cost in 2 . If the noise vector \(Z=(Z_1,\dots,Z_n)\) is distributed according to \(P\) then the cost can be written as \[\int_{\mathbb{R}^n} L\!\left(\sum_{i=1}^n z_i\right)\,P(dz_1\cdots dz_n).\]

We impose the following mild and natural assumptions on the loss function \(L:\mathbb{R}\to\mathbb{R}\): (A1) \(L\) is even; (A2) \(L\) is nondecreasing on \(\mathbb{R}_+\); and (A3) \(L\) has at most subexponential growth, i.e., \[L(x)=\exp(o(|x|))\qquad \text{as } |x|\to\infty.\]

Since both privacy and utility are determined by the noise law \(P\) of \(Z=(Z_1,\dots,Z_n)\), our focus is to solve the following optimization problem. \[\begin{align} \label{eq:32opt95problem} \inf_{P} \int_{\mathbb{R}^n} L\!\left(\sum_{i=1}^n z_i\right)\,P(dz), \end{align}\tag{5}\] where optimization is over all \(P\) satisfying \(\varepsilon\)-DP for sensitivity \(\Delta\). Our main result (Theorem 1) resolves 5 by matching its optimum to the centralized benchmark and showing it is approachable under local DP using correlated noise.

Although the cost in 5 is defined in terms of an \(n\)-dimensional noise measure \(P\), it is useful to also consider costs associated with one-dimensional probability measures, as much of the analysis reduces to a scalar problem. Accordingly, for a cost function \(L:\mathbb{R}\to\mathbb{R}\) and a probability measure \(Q\) on \(\mathbb{R}\), we define the associated cost \[C(L,Q):= \int_{\mathbb{R}} L(x)\,Q(dx).\]

Let \(\mathcal{P}_n(\varepsilon,\Delta)\) denote the class of Borel probability measures on \(\mathbb{R}^n\) that satisfy \(\varepsilon\)-differential privacy for sensitivity \(\Delta\). We define the optimal cost (over one-dimensional noise measures) as \[\begin{align} \label{eq:32minimize} C^*_{\varepsilon,\Delta}(L) \;\triangleq\; \inf_{Q \in \mathcal{P}_1(\varepsilon,\Delta)} C(L,Q). \end{align}\tag{6}\]

It was shown in [10] that for any cost function \(L\) satisfying Assumptions (A1)–(A3), an optimal noise distribution exists and admits a density, which we denote by \(f^*_{L,\varepsilon,\Delta}\). The optimal value of the objective can therefore be written as \[\begin{align} C^*_{\varepsilon,\Delta}(L) \;=\; \int_{\mathbb{R}} L(x)\, f^*_{L,\varepsilon,\Delta}(x)\, dx . \end{align}\]

More specifically, [10] shows that the optimal density \(f^*_{L,\varepsilon,\Delta}\) belongs to the parametric family of staircase mechanisms \(\{f_\gamma^{(\varepsilon,\Delta)}:\gamma\in[0,1]\}\). We use these functions to prove the achievability part of our main theorem; see Appendix 6 for details.

We state a simple scaling property of the optimal cost under dilation of the loss function, which will be used in the proof of the main theorem. The proof is deferred to Appendix 5.

3 The main result↩︎

Our main result characterizes the optimal cost achievable under \(\varepsilon\)-DP for sensitivity \(\Delta\). The theorem is stated in two parts: a universal lower bound and an achievability statement.

This result shows that by using a correlated local differential privacy mechanism, we can arbitrarily approximate the optimal cost of the central DP setting, while still preventing the server from learning individual data.

Before proceeding with the proof, we introduce some notation. Let \(S\) be an orthogonal matrix whose first row is \(\frac{1}{\sqrt{n}}(1,\ldots,1)\), and define \(U = SZ\). Under this transformation, \[U_1 = \frac{1}{\sqrt{n}}(Z_1 + \cdots + Z_n),\] while the remaining coordinates span the subspace orthogonal to the all-ones vector.

The distribution of \(U\) is denoted by \(P^{S}\) and is obtained from \(P\) via the change of coordinates induced by \(S\): \[P^{S}(A) := P(S^{-1}A), \qquad A \subseteq \mathbb{R}^n \text{ measurable},\] where \(S^{-1}A=\{S^{-1}u:\,u\in A\}\). With this notation in place, we prove the lower bound in 8 .

We numerically evaluate the two-user case (\(n=2\)) with sensitivity \(\Delta=2\). Figure 1 compares the aggregate squared loss under several mechanisms; the dashed black curve shows the lower bound \(C^*_{\varepsilon,\Delta}\). All other curves are estimated from \(5\times 10^5\) samples of \((Z_1,Z_2)\).

The orange curve corresponds to independent \(\mathrm{Laplace}(\Delta/\varepsilon)\) noise⁴, the green curve to the product of one-dimensional optimal densities \(f^*_{L,\varepsilon,\Delta}\), and the blue curve to our correlated construction \(\widetilde{P}\) with \(\varepsilon_0=\varepsilon-0.1\) (specified in Appendix 6). These results empirically validate the optimality of the correlated construction relative to standard local DP schemes.

4 Conclusion↩︎

We showed that the utility gap between local and centralized differential privacy is not inherent to locality, but to the restriction to independent noise. By introducing carefully designed correlations among locally added noise variables, we constructed \(\varepsilon\)-DP mechanisms whose aggregate cost can approach the optimal centralized cost arbitrarily closely.

Our approach extends beyond pure \(\varepsilon\)-DP: the lower-bound and scaling arguments carry over to approximate DP and Rényi DP [26], and achievability should persist when the relevant one-dimensional optimizers are stable under small parameter changes.

Our analysis also extends to vector-valued data. Under \(\ell_\infty\) sensitivity, the problem decouples coordinatewise and reduces to the scalar setting studied here. When sensitivity is measured using other norms, similar lower-bound continue to apply. Moreover, recent results on optimal mechanisms for vector-valued sensitivities [27] suggest that our construction can be extended as well.

An important direction for future work is the efficient and secure generation of the required correlations. In the approximate DP setting, correlated Gaussian schemes use independent noise combined with pairwise anticorrelated components that cancel upon aggregation [19], [21], [22]. While similar ideas may be relevant here, our construction is not directly reducible to such a decomposition, as the resulting aggregate noise cannot generally be expressed as a sum of independent random variables.

5 Proof of Lemma 1↩︎

For convenience, we restate Lemma 1.

6 Proof of achievability of Theorem 1↩︎

For the reader’s convenience, we restate the achievability claim in Theorem 1:

For every \(\eta>0\), there exists a probability measure \(\widetilde{P}\) on \(\mathbb{R}^n\) such that the additive-noise mechanism with \(Z\sim \widetilde{P}\) satisfies \(\varepsilon\)-DP for sensitivity \(\Delta\) and \[\begin{align} \label{eq:32achieve2} \int_{\mathbb{R}^n} L\!\left(\sum_{i=1}^n z_i\right)\,\widetilde{P}(dz_1\cdots dz_n) - C^*_{\varepsilon,\Delta}(L) \;\le\; \eta. \end{align}\tag{13}\]

To prove achievability, we construct a probability measure \(\widetilde{P}\) on \(\mathbb{R}^n\) that satisfies \(\varepsilon\)-DP for sensitivity \(\Delta\) and whose cost approaches the lower bound in 8 .

Our construction relies on the staircase densities of [10], named for their piecewise-constant form. They are parametrized by \((\varepsilon,\Delta)\) and a shape parameter \(\gamma\in[0,1]\). For notational simplicity, we suppress \((\varepsilon,\Delta)\) and write \(f_\gamma\) for \(f_\gamma^{(\varepsilon,\Delta)}\): \[\begin{align} \label{eq:32stair} f_\gamma(x)\! =\! \begin{cases} a_\gamma, & \!\!\!\! 0 \le x < \gamma\Delta,\\ e^{-\varepsilon} a_\gamma, &\!\!\!\! \gamma\Delta \le x < \Delta,\\ e^{-k\varepsilon} f_\gamma(x-k\Delta), &\!\!\!\! k\Delta \le x \!< (k+1)\Delta, k\in\mathbb{N},\\ f_\gamma(-x), &\!\!\!\! x<0, \end{cases} \end{align}\tag{14}\] where \(a_\gamma:=a(\gamma,\varepsilon,\Delta)\) is the normalizing constant. Under Assumptions (A1)–(A3), [10] shows that the optimizer \(f^*_{L,\varepsilon,\Delta}\) belongs to this family.

Armed with this characterization, we now prove achievability.

We visualize the asymptotic convergence of \(\widetilde{P}\) by numerically simulating two users (\(n = 2\)) with \(\Delta = 2\). The samples of \(Z\) are generated where the choice for \(g\) is a \(\mathrm{Laplace}(\frac{\Delta}{\varepsilon-\varepsilon_0})\). We plot the quadratic loss versus \(\varepsilon\) for various choices of \(\varepsilon_0\) and observe that as \(\varepsilon_0\) approaches \(\varepsilon\), the quadratic loss decreases and is closer to the theoretical lower bound \(C^*_{\varepsilon,\Delta}(L)\).

Figure 3 illustrates the density of \(\widetilde{P}\) for \(n=2\).

The plot corresponds to the two-user case with \(\varepsilon=0.5\), \(\Delta=1\), and \(\varepsilon_0=0.4\), where \(g\) is chosen as \(\mathrm{Laplace}\!\big(\Delta/(\varepsilon-\varepsilon_0)\big)\). As expected, the mass concentrates near the line \(z_1+z_2=0\) (i.e., \(u_1=0\)) and exhibits staircase decay along \(z_1=z_2\), equivalently along the \(u_1\) direction.

References↩︎