An upper bound for advantage related to differential privacy

Question

My previous question define a security game, advantage $\mathsf{Adv}$ and two probability distributions $P_{m_0}$ and $P_{m_1}$, representing $Enc_k(m_0)$ and $Enc_k(m_1)$ separately.

There, my main task is try to prove formula : $$ \mathsf{Adv}\leq \frac{1}{2} TVD(P_{m_0},P_{m_1}) $$ which has been solved thanks to Mark Schultz-Wu's hint.

Now, I come up with a new question. If we add constraints to $P_{m_0}$ and $P_{m_1}$, i.e., for all events $A\in\mathcal{X}$ : $$ \begin{align} P_{m_0}(A)\leq e^{\varepsilon}\cdot P_{m_1}(A)+\delta\\ P_{m_1}(A)\leq e^{\varepsilon}\cdot P_{m_0}(A)+\delta \end{align} $$ where $\varepsilon$ and $\delta$ are two parameters given, $\mathcal{X}$ is event field (I think these constriants are just like differential privacy) .

What I want is to find a tight upper bound for $\mathsf{Adv}$ using $\varepsilon$ and $\delta$. What I have done is using the definition and equation manipulation, find an upper bound, which is equal to $\frac{1}{2}(|e^{\varepsilon}-1|+|\delta|)$.

But actually, I don't think it is tight. A tight upper bound means that, when given any parameters and distribution, you need to construct a strategy to make sure adversary can achieve this upper bound. However, it seems that I could not find the key point.

Someone told me I need to view it from an innovative angle, like throwing tedious equation manipulation away and just focus on the definition of advantage. I hope someone can give me a hint or innovative angle to solve this.

Answer 1

First, my answer to your prior question is slightly different than you quote. I showed that you can write $\mathsf{Adv} \leq \mathsf{TV}(\mathsf{Bern}(A_0), \mathsf{Bern}(A_1))$, where $A_b$ is the success probability of adversary $A$ in game $b$. If you write that $A$ is a function of the ciphertext they are given, by data-processing inequality you should get the bound you want, but you need this step.

---

There are various kinds of differential privacy. Two of the best-known kinds are

1. Global (the "standard" kind) DP. Here, for any two adjacent inputs $m_0$, $m_1$ (where "adjacent" typically means differing in a single row), one gets inequalities of the type you write down, and

2. Local DP. Here, for any two (possibly non-adjacent) inputs, you get bounds of the type you write down.

Local DP seems more appropriate for your question. It is known that Local DP is equivalent to channel contraction of the $E_\gamma$ divergence. This is to say that there is a generalized distance measure on the space of probability distributions (different from the total variation distance) such that

$$ M\text{ is }(\epsilon,\delta)-LDP\iff \forall P, Q: E_{\exp(\epsilon)}(M(P), M(Q)) \leq \delta E_{\exp(\epsilon)}(P,Q) $$ Here, the $P, Q$ I am quantifying over are all probability distributions on the relevant space. Note that $E_\gamma$ is somewhat related to TV --- namely $E_1 = \mathsf{TV}$. They are more closely related than this though. For example, Proposition 4 part 6 states that

$$ 1 - \gamma(1 - \mathsf{TV}(P, Q))\leq E_\gamma(P,Q) \leq \mathsf{TV}(P,Q). $$

So, we can write

$$ \mathsf{Adv} \leq \mathsf{TV}(P_{m_0}, P_{m_1})\leq \frac{E_\gamma(P_{m_0},P_{m_1})+\gamma-1}{\gamma} \leq \frac{\delta E_\gamma(m_0,m_1)+\gamma-1}{\gamma}. $$

Here, $m_0, m_1$ are the plaintext distributions under consideration, and $\gamma = \exp(\epsilon)$. Given the aformentioned equivalence between local DP and channel contraction, I think this should be tight. If one applies the bound $E_\gamma(m_0,m_1) \leq \mathsf{TV}(m_0,m_1) \leq 1$, then this bound is idential to yours, except for division by the factor $\gamma = \exp(\epsilon)$, which should make the bound meaningfully smaller.

---

This all being said, I'll caution you that the distributions $P_{m_b}$ satisfy a form of differential privacy is highly non-standard. In general there are strong limitations with using "information theoretic" techniques to achieve acceptable levels of cryptographic security, which is the net result of arguments such as the above. In particular, the advantage bound takes the form

$$1 - \frac{1-\delta}{\gamma}$$

This reads as saying the advantage cannot be too close to 1, but it does not say the advantage cannot be that much larger than $2^{-k}$ for large $k$ (typically $k\gg 100$ is the parameter range of interest in cryptography).