1 Introduction↩︎

Rooted in a rigorous mathematical framework of statistical indistinguishability, differential privacy provides a robust guarantee that the inclusion or exclusion of a single record remains probabilistically undetectable by bounding output variations within a privacy budget \(\epsilon\) [1]–[3]. By ensuring that an adversary cannot reliably infer an individual’s presence or specific contribution from observable outputs, differential privacy has emerged as the gold standard for privacy-preserving data analysis. Due to its formal security properties, differential privacy is now widely deployed across various domains, including official statistics [4], machine learning [5] and healthcare [6].

The Pufferfish framework extends the principles of differential privacy to scenarios where the original data, such as a query response, exhibits probabilistic dependence on a secret [7], [8]. In this setting, the challenge lies in achieving statistical indistinguishability within the posterior data distribution following sanitization. To address this, the first noise calibration method was introduced by Song et al. (2017), who proposed setting the scale parameter \(b\) of zero-mean Laplace noise according to the \(\infty\)-order Wasserstein metric to satisfy \(\epsilon\)-pufferfish privacy [9]. However, computing the \(\infty\)-Wasserstein metric is complicated by its non-convex nature [10], [11]. To resolve these computational difficulties, Ding (2022) introduced a \(1\)-order Wasserstein (Kantorovich) approach for both Laplace and Gaussian noise mechanisms [12].

While strict privacy constraints often degrade data utility—a primary concern in differential privacy literature [13], [14]—one may resort to relaxations such as Rényi measures. Similar to \((\epsilon, \delta)\)-differential privacy, these relaxations bound the probability of a data breach within specified limits. Building on the principles of Rényi Differential Privacy [15], \(\epsilon\)-pufferfish privacy has been extended to \((\alpha, \epsilon)\)-Rényi Pufferfish Privacy (RPP) [16], which originally utilized a \(W_\infty\) mechanism scaled by the order \(\alpha\) [16]. However, because an order \(\alpha < \infty\) eases the stringent privacy requirements of \(\epsilon\)-pufferfish privacy, and given that \(\alpha\) plays a functionally identical role in the Wasserstein metric, it is logical to expect a Wasserstein mechanism of the same order. This intuition motivated the \(W_\alpha\) mechanism proposed in [16]. Nevertheless, this approach necessitates an additional relaxation via an approximate probability \(\delta\) alongside the Rényi order \(\alpha\) [16].

In this paper, we propose a \(W_\alpha\) mechanism to achieve exact \((\alpha, \epsilon)\)-Rényi Pufferfish Privacy (RPP) without requiring further relaxations. Our main contributions are summarized as follows:

• Calibration of Laplace Mechanisms: By applying Hölder’s inequality, we derive a sufficient condition for calibrating Laplace noise via the \(\alpha\)-Wasserstein metric. Specifically, we show that if the scale parameter \(b\) ensures the \(W_\alpha\) metric is upper bounded by \(\epsilon \frac{\alpha-1}{\alpha}\), \((\alpha,\epsilon)\)-Rényi pufferfish privacy is satisfied. In the limiting case where \(\alpha = \infty\), this recovers the existing \(\infty\)-Wasserstein mechanism for \(\epsilon\)-pufferfish privacy [9]. We further extend this \(W_\alpha\) metric approach to the exponential mechanism.

• Gaussian Noise Refinement: For Gaussian mechanisms, we demonstrate that \((\alpha,\epsilon)\)-Rényi pufferfish privacy is achieved by selecting a variance \(\sigma^2\) such that the \(W_{\alpha(\alpha-1)}\) metric is upper bounded by \(\frac{\epsilon}{\alpha}\). Under deterministic data settings (standard differential privacy), this condition aligns with the results in [15] for \((\alpha, \epsilon)\)-Rényi differential privacy.

• Utility and Performance Analysis: Experimental results indicate that our proposed \(\alpha\)-Wasserstein mechanism requires significantly smaller values for \(b\) and \(\sigma^2\) compared to existing benchmarks in [16], leading to a substantial improvement in data utility. Furthermore, we demonstrate that for a fixed \((\alpha, \epsilon)\)-Rényi pufferfish privacy level, the Gaussian mechanism requires considerably less noise power than the Laplace mechanism when the privacy budget \(\epsilon\) is small.

Finally, we outline several directions for future research, including the derivation of closed-form solutions for noise parameters, the exploration of operational interpretations for the range \(\alpha \in (0,1)\), and the development of \(W_2\) mechanisms utilizing Monge’s formulation for Gaussian priors.

1.0.0.1 Organization

The remainder of this paper is organized as follows. Section 2 defines the system model and provides the necessary mathematical foundations and privacy definitions. Section 3 introduces the proposed \(\alpha\)-Wasserstein mechanism for Laplace, Gaussian, and exponential noise, followed by an evaluation of its performance through experimental results. Finally, Section 4 discusses potential directions for future research and concludes the paper.

1.0.0.2 Notation

We use capital letters to denote random variables (r.v.s) and lower case letters to denote the elementary event. Calligraphic letters refer to the alphabet of r.v.s. For example, \(x\) is an instance of r.v. \(X\), that takes value in alphabet \(\mathcal{X}\). Denote \(P_{X}(x) = \Pr(X = x)\) the probability of outcome \(X=x\) when r.v. \(X\) takes the value \(x\). We use \(P_X = (P_{X}(x) \colon x \in \mathcal{X})\) to denote a probability distribution and \(X \sim P_{X}\) means that r.v. \(X\) follows distribution \(P_{X}\). The support of \(P_{X}(\cdot)\) is denoted by \(\text{supp}(P_{X}) = \{x \in \mathcal{X}\colon P_X(x) > 0\}\). The expected value of \(f(X)\) for some deterministic function \(f\) w.r.t. probability \(P_{X}\) is denoted by \(\mathbb{E}_{X \sim P_{X}}[f(X)] = \int P_{X}(x) f(x) \mathop{}\!\mathrm{d}x\). The conditional probability \(P_{Y|X}(y|x) = \Pr(Y=y|X=x)\) denotes the chances of having \(Y=y\) given the outcome \(X=x\). \(P_{Y|x} = (P_{Y|X}(y|x) \colon y \in \mathcal{Y})\) refers to the probability distribution of \(Y\) conditioned on \(X = x\). For two probability distributions \(P_X\) and \(Q_X\), the Rényi divergence [17] is \[\label{eq:RD} D_{\alpha}(P_X \| Q_X) = \frac{1}{\alpha-1} \log \int \frac{P_X^{\alpha}(x)}{Q_X^{\alpha-1}(x)} \mathop{}\!\mathrm{d}x\tag{1}\] where \(\alpha \in [0,\infty]\) is referred to as Rényi order. In this paper, we assume \(P_X \ll Q_X\) so that the Radon–Nikodym derivative is always well defined. For extended orders \(\alpha= 1\) and \(\infty\), we should apply the L’Hôpital’s rule to get \(D_{1}(P_X \| Q_X) = \mathbb{E}_{X \sim P_X} \big[ \log \frac{P_X(x)}{Q_{X}(x)} \big]\) and \(D_{\infty}(P_X \| Q_X) = \log \max\limits_{x\in\mathcal{X}} \frac{P_{X}(x)}{Q_{X}(x)}\), respectively. Here, \(D_{1}\) refers to the Kullback-Leibler divergence.

2 Preliminary↩︎

We review the Pufferfish privacy framework as originally proposed by Kifer and Machanavajjhala (2012, 2014) [7], [8], alongside its extension to the Rényi-divergence-based variant, Rényi Pufferfish Privacy (Pierquin et al., 2024 [16]). Furthermore, we examine established noise calibration methods based on the recent \(W_1\) and \(W_\infty\) Wasserstein metric calibration techniques.

2.1 System Setting and Rényi Pufferfish privacy↩︎

Assume that the data to be published, \(X\) (e.g., a query response or a column in a table), is statistically correlated with a sensitive secret \(S\). Let \(P_{X|s, \rho}\) denote the conditional probability distribution of the data \(X\) given a secret instance \(S = s\), where \(\rho\) represents the adversary’s prior knowledge—such as the mean and covariance in the case of Gaussian-distributed data. In a multi-adversary environment, different agents may possess distinct prior beliefs \(\rho\). To preserve privacy, we transform \(X\) into a randomized output \(Y\) before publication. The adversary is assumed to have access only to this sanitized data \(Y\), though they may attempt to infer individual secrets by analyzing aggregated statistics from repeated queries. Let \(\mathbb{S}\) define a set of secret pairs \((s_i, s_j)\) specified by the data curator. This set identifies the instances where statistical indistinguishability must be enforced to ensure robust data protection. Any significant discrepancy between the distributions of \(Y\) conditioned on \(S = s_i\) versus \(S = s_j\) could be exploited by an adversary to distinguish between secret states, leading to a privacy breach. This risk motivates a formal privacy definition that imposes an upper bound on the statistical distinguishability between such posterior distributions.

2.1.0.1 Pufferfish Privacy

For a privacy budget \(\epsilon>0\), the privatized data \(Y\) is said to be \(\epsilon\)-pufferfish privacy if [7], [8] \[\begin{align} \label{eq:PP} P_{Y|S}(y|s_i,\rho) \leq e^{\epsilon} P_{Y|S}(y|s_j,\rho), \quad \forall y, \rho, (s_i,s_j) \in \mathbb{S}. \end{align}\tag{2}\] Equation 2 guarantees an \(\epsilon\)-level of indistinguishability across all adversarial prior beliefs \(\rho\). The formalization of Rényi Pufferfish Privacy mirrors the extension of differential privacy to its Rényi counterpart, as established in [15].

2.1.0.2 Rényi Pufferfish Privacy

For a privacy budget \(\epsilon>0\) and Rényi order \(\alpha \in [1,\infty]\), the privatized data \(Y\) is said to be \((\alpha,\epsilon)\)-Rényi pufferfish privacy in \(\mathbb{S}\) if [16] \[\begin{align} \label{eq:RPP} D_{\alpha} (P_{Y|s_i,\rho} \| P_{Y|s_j, \rho}) \leq \epsilon, \quad \forall \rho, (s_i,s_j) \in \mathbb{S}. \end{align}\tag{3}\]

For given input distributions, \(D_\alpha\) is (strictly) increasing in \(\alpha\) [18]. It reaches maximum at \(\alpha = \infty\), where \((\infty,\epsilon)\)-Rényi pufferfish privacy refers to \(D_{\infty} (P_{Y|s_i,\rho} \| P_{Y|s_j, \rho}) =\log \max\limits_{y} \frac{P_{Y|S}(y|s_i,\rho) }{P_{Y|S}(y|s_j,\rho)} \leq \epsilon, \forall \rho, (s_i,s_j) \in \mathbb{S}\), equivalent to \(\epsilon\)-pufferfish privacy. This is clear if we rewrite the definition as \[\label{eq:RDP95GenMean} D_{\alpha} (P_{Y|s_i, \rho} \| P_{Y|s_j, \rho} ) = \log \Big( \mathbb{E}_{Y \sim P_{Y|s_i,\rho}} \Big[ \big( \frac{P_{Y|S}(\cdot|s_i,\rho)}{P_{Y|S}(\cdot|s_j, \rho)} \big)^{\alpha-1} \Big] \Big)^{\frac{1}{\alpha-1}}\tag{4}\] \(e^{D_{\alpha} (P_{Y|s_i, \rho} \| P_{Y|s_j, \rho} )}\) is an \((\alpha-1)\)-exponent generalized (Hölder) mean that is monotonically nondecreasing in \(\alpha\).

The expression in 4 elucidates how Rényi Pufferfish Privacy provides a relaxation of the standard Pufferfish framework. At \(\alpha = \infty\), the generalized mean locates at the maximum statistical distinguishability, \(\frac{P_{Y|S}(y|s_i,\rho)}{P_{Y|S}(y|s_j,\rho)}\), aligning with the core objective of data privacy: protecting against the worst-case, or catastrophic, data breach, irrespective of its frequency. However, when preventing this worst-case scenario becomes practically infeasible—for instance, when the required noise power severely degrades the utility of the published data—one may trade a degree of privacy for enhanced data utility. By selecting a finite order \(\alpha < \infty\), the generalized mean incorporates the statistical distinguishability across the entire support, where the influence of the maximum distinguishability is effectively discounted by its associated probability mass. Consequently, an upper bound \(\epsilon\) on the Rényi divergence \(D_\alpha\) no longer constrains the instantaneous worst-case ratio, but rather bounds the overall statistical distinguishability in an average sense. Thus, we can satisfy \(D_{\alpha} (P_{Y|s_i, \rho} \| P_{Y|s_j, \rho} ) \leq \epsilon\) even if specific events \(X = x\) violate the stringent \(\epsilon\)-Pufferfish constraint, \(\frac{P_{Y|S}(y|s_i,\rho)}{P_{Y|S}(y|s_j,\rho)} \leq e^\epsilon\).

The conceptual motivation for relaxing \(\alpha\) from \(\infty\) parallels the \(\delta\)-approximation used in \((\epsilon, \delta)\)-differential and pufferfish privacy. While \((\epsilon, \delta)\)-privacy guarantees that the probability of violating the requirement \(\frac{P_{Y|S}(y|s_i,\rho)}{P_{Y|S}(y|s_j,\rho)} \leq e^\epsilon\) is bounded by \(\delta\), Rényi privacy offers a different, though related, form of relaxation. Because of this shared goal, \((\alpha, \epsilon)\)-pufferfish privacy can always be translated into the \((\epsilon, \delta)\) framework. For instance, according to [15], a finite order \(\alpha\) can be viewed as an increase in the effective privacy budget from \(\epsilon\) to \(\epsilon + \frac{-\log\delta}{\alpha-1}\) within a \(\delta\)-approximate setting. Alternatively, an \(\alpha < \infty\) can be expressed in terms of the approximation probability itself. By applying the Chernoff bound, for any \(\alpha \in (1, \infty)\), \[\label{eq:Chernoff} \Pr \Big( \frac{P_{Y|S}(Y|s_i,\rho)}{P_{Y|S}(Y|s_j,\rho)} > e^{\epsilon} \Big) \leq e^{(\alpha-1) ( D_{\alpha}(P_{Y|s_i,\rho}, P_{Y|s_j,\rho}) - \epsilon) }.\tag{5}\]

Here, \(\Pr(\cdot)\) denotes the probability with respect to the distribution \(P_{Y|s_i, \rho}\). Recall that \((\epsilon, \delta)\)-pufferfish privacy is satisfied if \(P_{Y|s_i, \rho}(\mathcal{A}) \leq e^{\epsilon} P_{Y|s_j, \rho}(\mathcal{A}) + \delta\) for all measurable sets \(\mathcal{A}\), all priors \(\rho\), and all secret pairs \((s_i, s_j) \in \mathbb{S}\) [12]. Therefore, any \((\alpha,\epsilon)\)-Rényi pufferfish privacy guarantee such that \(D_{\alpha}(P_{Y|s_i,\rho}, P_{Y|s_j,\rho}) \leq \epsilon\) inherently provides the approximation \((\epsilon, e^{(\alpha-1) (D_{\alpha}(P_{Y|s_i,\rho}, P_{Y|s_j,\rho}) - \epsilon)})\)-pufferfish privacy. It is important to note that these two relaxation methods—selecting a finite \(\alpha\) in the Rényi framework or allowing a \(\delta\)-approximation with \(\alpha = \infty\)—serve similar purposes. In this paper, we focus on the former, attaining exact \((\alpha, \epsilon)\)-Rényi pufferfish privacy without introducing an additional \(\delta\) parameter.

2.2 Additive Noise Mechanism↩︎

A straightforward approach to data sanitization is adding noise to the original data. Let \(N\) denote a zero-mean noise variable that is statistically independent of \(X\). The randomized output is then generated as \(Y = X + N\). When \(X\) is an r.v., the resulting probability distribution of \(Y\) is determined by the convolution \[\label{eq:conv} P_{Y|S}(y|s,\rho) = \int P_{N} (y-x) P_{X|S}(x|s,\rho) \mathop{}\!\mathrm{d}x.\tag{6}\] Laplace noise \(N \sim \text{Lap}(b)\) follows the probability distribution \(P_{N}(z) = \frac{1}{2b}e^{-\frac{|z|}{b}}, \forall z \in \mathbb{R}\). The scale parameter \(b\) indicates the flatness of Laplace distribution and determines noise variance \(2b^2\). For exponential mechanisim \(N \sim \text{Exp}(\theta)\) [1], \(c\) is a metric that is nonnegative, symmetric \(c(z) = c(-z), \forall z\), and satisfies the triangular inequality \(c(z) \leq c(a) + c(z-a), \forall z,a\). The noise ditribution is \(P_{N} (z) \propto e^{ -\eta(\theta) c(z)}\), where \(\eta \propto \frac{1}{\theta}\). By the triangular inequality, \(P_{N}(y-x) \leq e^{\eta(\theta) c(x-x')} P_{N}(y-x') , \forall x,x',y\), where \(e^{\eta(\theta) c(x-x')}\) refers to an upper bound on the probability mass transport cost from \(x\) to \(x'\). It is clear that Laplace noise is an example of the exponential mechanism when \(\eta(\theta) = 1/\theta\) and \(c(z) = |z|\). For Gaussian noise \(N \sim \text{Gauss}(\sigma^2)\), the probability distribution is \(P_{N}(z) = \frac{1}{\sqrt{2\pi} \sigma}e^{-\frac{z^2}{2\sigma^2}}, \forall z \in \mathbb{R}\), with the noise variance being \(\sigma^2\).

Noise calibration involves determining the optimal values for the parameters \(b\), \(\theta\), and \(\sigma\) for the Laplace, exponential, and Gaussian mechanisms, respectively. To preserve the utility of the randomized data \(Y\), it is essential to minimize the noise power (variance), thereby navigating the privacy-utility tradeoff. Specifically, the noise parameters must be tuned to the minimum threshold necessary to satisfy the privacy constraint. Excessively large parameters should be avoided, as they unnecessarily deteriorate data utility without providing additional requisite protection.

2.2.0.1 Wasserstein Metric

For each pair of prior distributions \(P_{X|s_i,\rho}\) and \(P_{X|s_j,\rho}\), denote \(\pi\) a coupling joint distribution such that \(P_{X|S}(x|s_i,\rho) = \int \pi(x,x') \mathop{}\!\mathrm{d}x'\) for all \(x\) and \(P_{X|S}(x'|s_j,\rho) = \int \pi(x,x') \mathop{}\!\mathrm{d}x\) for all \(x'\). Note that \(\pi\) is not unique. For \(\alpha \in [1,\infty]\) and a nonnegative cost (or distance) function \(d(\cdot)\), the \(\alpha\)-Wasserstein distance is \[W_\alpha (P_{X|s_i,\rho},P_{X|s_j,\rho}) := \Big( \inf_{\pi}\int d(x-x')^\alpha \mathop{}\!\mathrm{d}\pi(x,x^{\prime}) \Big)^{\frac{1}{\alpha}}\] measuring the minimum cost for transforming the probability mass from \(P_{Y|s_i,\rho}\) to \(P_{Y|s_j,\rho}\). Wasserstein distance \(W_\alpha\) is monotonically increasing in \(\alpha\). For \(\alpha = 1\), \(W_1 (P_{X|s_i,\rho}, P_{X|s_j,\rho}) = \inf_{\pi}\int |x-x'| \mathop{}\!\mathrm{d}\pi(x,x^{\prime})\) is called the earth mover distance, and the minimization is a linear programming. The minimizer \(\pi^*\) is called Kantorovich optimal transport plan [19], [20]. Assuming convex \(d\), the optimal joint probability \(\pi^*\) can be computed directly using the existing knowledge of \(P_{X|s_i,\rho}\) and \(P_{X|s_j,\rho}\): let \(F_{X|S}(\cdot|s_i,\rho)\) and \(F_{X|S}(\cdot|s_j,\rho)\) be the corresponding cumulative density functions, \(\pi^*(x,x') = \frac{\mathop{}\!\mathrm{d}^2}{\mathop{}\!\mathrm{d}x \mathop{}\!\mathrm{d}x'} \min \big\{ F_{X|S}(x|s_i,\rho), F_{X|S}(x'|s_j,\rho) \big\}.\) For \(\alpha = \infty\), \(W_\infty (P_{X|s_i,\rho},P_{X|s_j,\rho}) = \inf_{\pi} \sup_{(x,x') \in \text{supp}(\pi)} d(x-x')\).

3 \(\alpha\)-Wasserstein Mechanism↩︎

We maintain consistent notation by using \(\alpha\) to denote the order for both the Rényi divergence (\(D_\alpha\)) and the Wasserstein metric (\(W_\alpha\)), as the parameter serves a functionally analogous role in both frameworks. This notation establishes a direct correspondence between the two measures for any given value of \(\alpha\). Given that the \(W_\infty\) metric is utilized to calibrate noise for \(\epsilon\)-pufferfish privacy [9], it is natural to anticipate a corresponding \(W_\alpha\) mechanism for \((\alpha, \epsilon)\)-Rényi pufferfish privacy. In this section, we formally validate this intuition by proposing \(\alpha\)-Wasserstein mechanisms for Laplace and Gaussian noise, as well as an exponential mechanism, for the range \(\alpha \in (1, \infty)\).

3.1 Laplace Noise↩︎

The Laplace mechanism was the inaugural method proposed for achieving differential privacy, introduced concurrently with the framework’s formal definition in [1]. Its prominence stems from the fact that the privacy requirement can be satisfied through straightforward arithmetic properties of the Laplace distribution. Consequently, it remains the most widely adopted additive noise mechanism across various extensions and variations of the differential privacy framework. In the context of pufferfish privacy, Song et al. [9] first demonstrated that calibrating the Laplace scale parameter to the \(\infty\)-Wasserstein distance between discriminative secrets ensures \(\epsilon\)-pufferfish privacy—a result later extended to a Kantorovich (\(W_1\)) mechanism in [12]. Intuitively, this suggests that an \(\alpha\)-Wasserstein mechanism should exist for the Rényi Pufferfish Privacy framework. In this section, we derive a method for calibrating the scale parameter using the \(W_\alpha\) metric to satisfy \((\alpha, \epsilon)\)-Rényi pufferfish privacy, and we demonstrate that our approach generalizes the existing \(W_\infty\) mechanism.

To determine the parameter \(b\) in Theorem 1, we can utilize the modified Brent’s method proposed in [21], [22].The approach involves employing the standard Brent’s method [23], [24] to iteratively refine the lower and upper bounds of the root in ?? . Upon convergence, the algorithm outputs the lower bound to satisfy the inequality constraint in 11 . For a detailed implementation of this searching algorithm, we refer the reader to [21]. It should be noted that other numerical root-finding techniques are equality applicable for determining \(b\) in Theorem 1.

Although the optimal transport plan \(\pi^*\) in ?? is formulated similarly to the Kantorovich \(W_1\) metric, Theorem 1 actually establishes a sufficient condition based on the \(W_\alpha\) metric. This relationship becomes evident by rewriting 11 as: \[\label{eq:AlphaW95Lap95Min95Alt} W_{\alpha}(P_{X|s_i,\rho}, P_{X|s_j,\rho}) = \Big( \inf_{\pi} \int e^{\alpha \frac{|x-x'|}{b}} \mathop{}\!\mathrm{d}\pi(x,x') \Big)^{\frac{1}{\alpha}} \leq e^{ \frac{\alpha-1}{\alpha} \epsilon }\tag{12}\] where the distance function is defined as \(d(z) = e^{\frac{|z|}{b}}\) for all \(z \in \mathbb{R}\). Under this formulation, the scale parameter \(b\) in Theorem 1 is effectively calibrated by the \(W_\alpha\) distance; hence, we refer to this as the \(\alpha\)-Wasserstein mechanism. This approach integrates seamlessly with the established \(W_\infty\) mechanism for \(\epsilon\)-pufferfish privacy, providing a unified framework for varying privacy requirements.

It was previously established in [16] that a scale parameter satisfying \(\epsilon = \frac{\alpha}{2\alpha-1} e^{\frac{\alpha-1}{b} W_{\infty}(P_{Y|s_i,\rho},P_{Y|s_j,\rho}) } + \frac{\alpha-1}{2\alpha-1} e^{\frac{\alpha}{b} W_{\infty}(P_{Y|s_i,\rho},P_{Y|s_j,\rho}) }\) ensures \((\alpha, \epsilon)\)-Rényi Pufferfish Privacy. This result was derived by applying the shift reduction lemma [25] to obtain the shifted Rényi divergence [25]. Essentially, this constitutes an \(\infty\)-Wasserstein mechanism analogous to the Rényi differential privacy framework in [15], with the \(\ell_1\)-sensitivity replaced by the \(W_{\infty}\) distance. This alignment is expected, as the maximum \(\ell_1\)-norm in the pufferfish setting corresponds exactly to the \(\infty\)-Wasserstein distance. However, because the \(W_{\alpha}\) metric is monotonically non-decreasing with respect to \(\alpha\), relying on the \(W_{\infty}\) distance inevitably necessitates a larger noise scale to satisfy the privacy constraint. Experimental results in Figure 1 demonstrate that our proposed \(\alpha\)-Wasserstein mechanism, as defined in Theorem 1, requires a significantly smaller scale parameter \(b\) compared to [16].

One approach to improving data utility is to relax the Wasserstein mechanism from \(\alpha = \infty\) to a finite \(\alpha < \infty\). To this end, [16] introduced a \(\delta\)-approximation for Rényi Pufferfish Privacy, formally defined by the triplet \((\alpha, \epsilon, \delta)\)-Rényi Pufferfish Privacy [16]. Subsequently, a sufficient condition based on the \(\alpha\)-Wasserstein metric was proposed in [16] for general cases. This was achieved by approximating the shift reduction in the post-processing of Rényi divergence [16]. However, as discussed in Section 2.1, the Rényi measure is itself a relaxation of the stringent \(\epsilon\)-pufferfish privacy constraint. Specifically, it allows for a breach probability bounded by \(e^{(\alpha-1) ( D_{\alpha}(P_{Y|s_i,\rho}, P_{Y|s_j,\rho}) - \epsilon)}\), as shown in 5 . Consequently, there is no inherent need to further approximate Rényi pufferfish Privacy, as the framework is already an approximation by design. Introducing an additional parameter \(\delta\) further eases the privacy constraint, which may lead to unintended consequences. For instance, an \((\alpha, \epsilon, \delta)\)-Rényi Pufferfish Privacy guarantee may be equivalent to an \((\epsilon, \delta')\)-pufferfish privacy bound where \(\delta' = e^{(\alpha-1) ( D_{\alpha}(P_{Y|s_i,\rho}, P_{Y|s_j,\rho}) - \epsilon)} + \delta\).¹ In such cases, \(\delta\) must be selected with extreme care; if the combined \(\delta'\) approaches or exceeds 1, the privacy guarantee becomes vacuous. It is evident that applying relaxations via both \(\alpha\) and \(\delta\) complicates the calculation of the cumulative privacy loss. Therefore, Theorem 1 and the subsequent results in this work focus exclusively on relaxation through the Rényi order \(\alpha\).

3.1.0.1 Exponential Mechanism

The \(\alpha\)-Wasserstein mechanism for Laplace noise can be easily extended to the exponential mechanism as follows. The proof is in Appendix 5.

This can be reformulated as an \(\alpha\)-Wasserstein mechanism: \[\label{eq:AlphaW95Exp95Min95Alt} W_{\alpha}(P_{X|s_i,\rho}, P_{X|s_j,\rho}) = \Big( \inf_{\pi} \int e^{\alpha \eta(\theta) c(x-x')} \mathop{}\!\mathrm{d}\pi(x,x') \Big)^{\frac{1}{\alpha}} \leq e^{ \frac{\alpha-1}{\alpha} \epsilon }\tag{13}\] where the distance function is defined as \(d(z) = e^{\alpha \eta(\theta) c(z)}, \forall z \in \mathbb{R}\). In the limiting case where \(\alpha = \infty\), we obtain the closed-form expression \(\theta = \eta^{-1} \big( \epsilon / \sup_{(x,x')\in \text{supp}(\pi^*)} c(x-x') \big)\). This result recovers the Kantorovich-exponential mechanism originally proposed in [12].

3.2 Gaussian Noise↩︎

Another widely adopted approach is the Gaussian mechanism. Owing to its sub-Gaussian concentration properties and rapidly decaying tail probabilities, it is often preferred over the Laplace mechanism in applications requiring high data utility and accuracy [26], [27]. In the context of Rényi differential Privacy, the Gaussian mechanism yields a closed-form expression for privacy loss [15], making noise calibration significantly more straightforward than for the Laplace mechanism [15], [28]. Below, we propose an \(\alpha\)-Wasserstein mechanism for calibrating Gaussian noise to satisfy Rényi pufferfish Privacy. We further demonstrate that this formulation generalizes the established Rényi differential Privacy results found in [15] to correlated data settings.

The proof is in Appendix 6. Theorem [theorem:AlphaW95Gauss] is in fact a \(W_{\alpha(\alpha-1)}\) mechanism. This is clear if we rewrite ?? to \[\label{eq:AlphaW95Gaussian95Min95Alt} W_{\alpha(\alpha-1)}(P_{X|s_i}, P_{X|s_j}) = \Big( \inf_{\pi} \int e^{\alpha (\alpha-1) \frac{(x-x')^2}{2 \sigma^2}} \mathop{}\!\mathrm{d}\pi(x,x') \Big)^{\frac{1}{\alpha(\alpha-1)}} \leq e^{ \frac{ \epsilon }{\alpha} }\tag{14}\] where the distance function is \(d(z) = e^{\frac{z^2}{2\sigma^2}}, \forall z \in \mathbb{R}\).

Consistent with the framework in [15], our approach does not require additional relaxations—such as the \(\delta\)-approximation introduced in [16]—to calibrate Gaussian noise for Rényi pufferfish privacy. Experimental results presented in Figure 1 demonstrate that our proposed \(\alpha\)-Wasserstein mechanism, as defined in Theorem 2, requires a significantly smaller variance \(\sigma^2\) compared to the bounds established in [16].

3.3 Experiment↩︎

The experimental results in Figure 1 are obtained in three real-world datasets in the UCI machine learning repository [29]: adult, heart disease and student performance. For adult, \(X\) refers to attribute education, \(s_i=\)’relationship=Husband’, and \(s_j=\)’relationship=Not-in-family’; for heart disease, \(X\) refers to oldpeak, \(s_i=\)’fbs=0’ and \(s_j=\)’fbs=1’; for student performance, \(X\) refers to G3 (the final grade), \(s_i=\)’guardian=mother’ and \(s_j=\)’guardian=father’. Figure 1 further evaluates the noise power requirements by comparing the variance of the Laplace mechanism in Theorem 1 with that of the Gaussian mechanism in Theorem 2 for \(\epsilon = 0.1\) (row 4) and \(\alpha = 1.5\) (row 5). The results indicate that the Gaussian mechanism requires considerably less noise power than the Laplace mechanism; this advantage is particularly pronounced in the high-privacy regime where the budget \(\epsilon\) is small.

The minor irregularities observed in Figure 1 for the Laplace mechanism (Theorem 1) near \(\alpha = 1\) arise because the Rényi divergence in 1 is undefined at this limit. Consequently, our \(\alpha\)-Wasserstein mechanisms in Theorems 1 and 2 do not apply when \(\alpha = 1\). Furthermore, the case of \(\alpha = 1\) represents an excessive relaxation where \(D_1\) (Kullback–Leibler divergence) measures only the average statistical distinguishability. This should generally be avoided in privacy contexts, which focus on preventing worst-case or catastrophic data breaches. Figure 2 also shows for smaller value of \(\alpha\), a larger scale parameter \(b\) for Laplace noise should be chosen to satisfy the sufficient condition in Theorem 1.

4 Conclusion↩︎

We investigated the calibration of Wasserstein mechanisms to achieve \((\alpha, \epsilon)\)-Rényi pufferfish privacy. We proposed an \(\alpha\)-Wasserstein mechanism where the parameters for Laplace and Gaussian noise are calibrated using an upper-bounded \(W_\alpha\) metric of the same order \(\alpha\). Experimental results demonstrate that our \(\alpha\)-Wasserstein mechanism significantly reduces noise compared to existing \(W_\infty\)-based approaches. The results further verify that the Gaussian mechanism offers superior data utility over the Laplace mechanism when utilizing the Rényi divergence as a privacy relaxation.

4.0.0.1 Discussion

The primary results of this paper leverage Hölder’s inequality for the conjugate exponents \(\alpha\) and \(\frac{\alpha}{\alpha-1}\). This established technique is a staple of information theory, used in generalized error bounds [30], [31] , entropy power inequalities [32], [33], and foundational bounds on guessing entropy [34], [35].. Furthermore, Rényi measures of order \(\frac{\alpha}{\alpha-1}\) have recently gained prominence in information-theoretic privacy [36], [37]. Beyond its core application to differential and pufferfish privacy, we highlight several promising extensions for future work.

Closed-form Solution: For ?? , find an invertible function \(f\) such that \(\int e^{\alpha\frac{|x-x'|}{b}} \mathop{}\!\mathrm{d}\pi^*(x,x') \leq f_\alpha(b)\), and compute scale parameter \(b = f_{\alpha}^{-1}(e^{(\alpha-1) \epsilon})\), we obtain a closed-form sufficient condition.

Range \(\alpha \in (0,1)\): It is not difficult to derive the sufficient condition \(\int e^{-\alpha\frac{|x-x'|}{b}} \mathop{}\!\mathrm{d}\pi(x,x') \geq e^{(\alpha-1) \epsilon}, \forall \rho, (s_i,s_j) \in \mathbb{S}\) for attaining \((\alpha,\epsilon)\)-Rényi pufferfish privacy for \(\alpha \in (0,1)\) by Laplace mechanism. See Proposition 1 in Appendix 7. However, the operational interpretation for Rényi pufferfish (and differential) privacy in range \(\alpha \in (0,1)\) should be studied first.

\(W_2\) Mechanism for Gaussian Noise and Gaussian Priors: For 17 , we have the sufficient condition \(D_{\alpha} (P_{Y|s_i,\rho} \| P_{Y|s_j,\rho}) \leq \frac{1}{\alpha-1} \log \inf_{\pi} \int e^{ \big( \frac{ \alpha (x-x')}{\sqrt{2}\sigma} \big)^2} \mathop{}\!\mathrm{d}\pi(x,x') \leq \epsilon,\) equivalent to \(W_2(P_{Y|s_i,\rho}, P_{Y|s_j,\rho}) \leq e^{\frac{\alpha-1}{2}\epsilon}\) for \(d(z) = e^{ \big( \frac{ \alpha z }{\sqrt{2}\sigma} \big)^2}, \forall z \in \mathbb{R}\). For \(P_{X|s_i}\) and \(P_{X|s_j}\) being Gaussian distributions, the value of \(W_2\) is determined by Monge’s formulation [38]–[40]. It is worth discussing if meaningful results can be derived.

5 Proof of Corollary 1↩︎

6 Proof of Theorem 2↩︎

7 A Sufficient Condition for \(\alpha \in (0,1)\)↩︎

8 More Experimental Results↩︎

Figure 2 shows how the LHS \(W_{\alpha}(P_{X|s_i,\rho}, P_{X|s_j,\rho})\)and RHS \(e^{ \frac{\alpha-1}{\alpha} \epsilon }\) of the inequality 12 varies with \(\alpha\), for different values of scale parameter \(b\) of Laplace noise. Figure 3 is an example of Remark 1. It shows the scale parameter \(b\) determined by Theorem 1 and [16] both converges to \(W_\infty/\epsilon\), the \(\infty\)-Wasserstein mechanism in [9], when \(\alpha\) grows large.

References↩︎