In privacy-related computer science literature, we say that a randomized algorithm $\mathcal{K}$ that produces a model $\theta$ from a sample $X=(x_1,...,x_n)$ is $\epsilon$-differentially private iff

$$ \forall \theta, \quad \mathbb{P}[\mathcal{K}(X)=\theta | X=X_0] \leq e^\epsilon \mathbb{P}[\mathcal{K} (X)=\theta|X=X_1] \tag{1} $$

where $X_0$ and $X_1$ are any Hamming-1 neighbors (differ by a single entry)

Using Bayes rule, we can rewrite (1) as a bounded Bayes ratio

$$ \frac{\mathbb{P}[X=X_0|\theta]}{\mathbb{P}[X=X_1|\theta]} \leq e^\epsilon \frac{\mathbb{P}[X=X_0]}{\mathbb{P}[X=X_1]} \tag{2} $$

In order to relate this to the Bayes (irreducible) error of an adversary trying to estimate $X$ from $\theta$, one can leverage the min-entropy

$$ H_\infty(X) = -\log \max_x \mathbb{P}[X=x] \\ \text{and} \\ H_\infty(X|\theta) = -\log \mathbb{E}_\theta \max_x \mathbb{P}[X=x|\theta] $$

First part of the question : Can we translate (2) into a bound involving $H_\infty(X|\theta)$ and $H_\infty(X)$ ?

Second part of the question : Since $H_\infty(X|\theta)$ takes the expectation over $\theta$, it looks like a weaker guarantee than (1), (bounded leakage only holding in expectation, with some $\theta$ leaking more than the bound). Is there a well-accepted entropy definition that keeps the same expressivity as (1), e.g.,

$$ H_\text{bla}(X|\theta) = -\log \max_{\theta,x} \mathbb{P}[X=x|\theta] $$

or something like that ?

thanks !


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.