About the definition of "differential privacy" in communication complexity
Your definition is wrong. The correct definition is as follows. A protocol $P$ is $\epsilon$-differentially private (for $\epsilon &gt; 0$) if for any two inputs $Z_1,Z_2$ differing in a single coordinates and any $p$,
$$
e^{-\epsilon} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^\epsilon.
$$
For small $\epsilon&gt;0$, $e^\epsilon \approx 1 + \epsilon$, and $e^{-\epsilon} \approx 1 - \epsilon$; the quantity $e^\epsilon$ is easier to work with compared to $1+\epsilon$, since $e^{\epsilon_1} e^{\epsilon_2} = e^{\epsilon_1+\epsilon_2}$, whereas $(1+\epsilon_1)(1+\epsilon_2) \approx 1 + \epsilon_1 + \epsilon_2$ holds only approximately.

Another small note: the upper bound implies the lower bound and vice versa.

The definition implies that for any two inputs $Z_1,Z_2$ that differ in at most $d$ places,
$$
e^{-\epsilon d} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^{\epsilon d}.
$$
In particular, if the inputs have length $m$, then for any $Z_1,Z_2$ we have
$$
e^{-\epsilon m} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^{\epsilon m}.
$$
In your case $m = 2n$.