Differential Privacy from Axioms

To formalize Theorems 2, 3, and 4 we define a series of axioms that any reasonable and useful privacy measure should satisfy.

We remark upon a few basic properties about Definition 7. First, as is typical of previous definitions of privacy, a single privacy measure $𝒫$ must provide privacy levels for algorithms taking in samples of all sizes $n\in \mathbb{N}$. Later, our scaling axiom (Axiom 4) will enforce some amount of consistency between how $𝒫$ behaves on different sample sizes.

Second, Definition 7 is a single parameter definition of privacy, in contrast to the two-parameters of DP (Definition 1). This single parameter was a deliberate choice. A guiding philosophy in the development of our axioms was to not directly enforce specific meaning to the privacy value $𝒫(ℳ)$, as we did not want our axioms to be biased by the meaning of $\epsilon$ and $\delta$ in DP. If we had a two (or more) parameter definition of privacy, we would need our axioms to somehow encode the distinction between those parameters, contradicting that guiding philosophy.

Furthermore, despite DP having two parameters, they are not of equal importance. Typical applications of DP simply set $\delta$ small enough to ignore and focus on $\epsilon$. Indeed, following the intuition that one only needs $\delta$ “small enough,” we show in Section 3.2 how to collapse Definition 1 into a single parameter in a way that respects all of our axioms.

Given any privacy measure $𝒫$ satisfying our axioms and $𝒫$-private algorithm $ℳ$, we wish to construct an equivalent ${ℳ}^{\prime }$ that is $(\epsilon ,\delta )$-DP. To do so, we use the following intermediate notion of stability.

This definition is useful because (slight modifications) of the results of [7] allow us to convert any TV-stable algorithm into an equivalent DP algorithm (see Lemma 6.1 of the full version [6] for a formal statement of that conversion). Most of our effort goes into converting a $𝒫$-private algorithm into a TV-stable algorithm.

To prove Theorem 10, we show, roughly speaking, that for any non-TV-stable algorithm $ℳ:X^m\to Y$, there exists algorithms ${ℳ}_1,\mathrm{\dots },{ℳ}_{\mathrm{\ell }}$ for $\mathrm{\ell }\approx m$ satisfying,

1. 1.

   Each ${ℳ}_i$ can be formed by preprocessing $ℳ$, and therefore, by the Axiom 1 (preprocessing), should have the same privacy.

2. 2.

   The composed algorithm ${ℳ}_{\mathrm{comp}}$ that takes as input $S$ and outputs the tuple
   $({ℳ}_1(S),\mathrm{\dots },{ℳ}_{\mathrm{\ell }}(S))$ is blatantly non-private.

By Axiom 2 (prohibition of blatant non-privacy), we can conclude that ${ℳ}_{\mathrm{comp}}$ is not $𝒫$-private. Then, Axiom 3 (strong composition) says that at least one ${ℳ}_i$ must satisfy $𝒫({ℳ}_i)\ge \tilde{\mathrm{\Omega }}({\mathrm{\ell }}^{-c})$. By Axiom 1 (preprocessing) this in fact means that $𝒫(ℳ)\ge \tilde{\mathrm{\Omega }}({\mathrm{\ell }}^{-c})=\tilde{\mathrm{\Omega }}(m^{-c})$.

By contrapositive, this allows us to prove something just short of our goal: Any $ℳ$ satisfying sufficiently strong privacy, $𝒫(ℳ)\le \tilde{O}(m^{-c})$, then $ℳ$ itself must be TV-stable.⁵⁵5We note that there are some caveats to this statement: Briefly, it only holds for symmetric algorithms, those whose output does not depend on the order of its input, and assumes the domain is not too small. Both details are handled in the body. In contrast, Theorem 10 only assume that $ℳ$ is $𝒫$-private. Here, we can exploit linear scalability: Using Axiom 4, we can convert any $ℳ:X^n\to Y$ that is $𝒫$-private to an ${ℳ}^{\prime }:X^m\to Y$ satisfying $𝒫({ℳ}^{\prime })\le (1/m^{-c})$ with only a polynomial increase in the sample size. This is the step where we crucially utilize the combined power of linear scalability and strong composition: Ultimately, we want to convert any $𝒫$-stable algorithm using $n$ samples into one using $O(m)$ samples with the additional property that it can be composed $m$ times and still be $𝒫$-stable. Axioms 4 and 3 together allow us to do this.

Since Definition 1 has two parameters, $\epsilon$ and $\delta$, we must collapse them to one parameter for our framework. We do this by defining,

There is just one of many ways to collapse $\epsilon$ and $\delta$ into a single parameter in a way that respects our axioms. The exponents $4/5$ and $8/5$ could be replaced with $\alpha$ and $2\alpha$ for any $\alpha \in (0.5,1)$. Furthermore, the $n^3$ factor could be replaced with any $n^{\beta }$ for $\beta >3$. With this privacy measure, we can state the formal version of Theorem 3. We first state the formal version of Theorem 3.

The reason we want $\delta$ to be much smaller than $\epsilon$ is because that’s the regime in which differential privacy satisfies strong composition. The following well-known theorem shows that DP has strong composition.

Given that we have forced $\delta$ to be small, we cannot simply use subsampling [4] to ensure that ${𝒫}_{\mathrm{DP}}$ satisfies linear scalability, as subsampling’s effect on $\delta$ is too mild. Instead, we use (a small modification of) a recent result of [7] to prove ${𝒫}_{\mathrm{DP}}$ satisfies linear scalability. See Lemma 7.1 of the full version [6] for this amplification procedure and the surrounding discussion for comparison to [7]’s result. Given the well-known strong-composition theorem for DP and this amplification procedure, showing that ${𝒫}_{\mathrm{DP}}$ satisfies all our axioms is straightforward.

Here, we explain why all four of our axioms are necessary. For each axiom, we exhibit ill-behaved notions of privacy that would be allowed if we removed the axiom. In the case of Axiom 1, we even show this is true if only one of the two parts of it are removed, and in the case of Axiom 3, we will show it is true even if we replace strong composition with linear composition (i.e. setting $c=1$). The proof of Theorem 4, given in the full version, will build on these ill-behaved privacy measures by showing that they allow algorithms solving statistical tasks that no differentially private algorithm can solve..

If we remove just the first part of Axiom 1, that reordering the input maintains privacy, then there is a privacy measure satisfying the remaining axioms, that we call ${𝒫}_{\mathrm{half}}$, which deems the algorithm $ℳ:X^n\to X^{\lfloor n/2\rfloor }$ that outputs the first half of its dataset perfectly private, satisfying ${𝒫}_{\mathrm{half}}(ℳ)=0$.

If we remove the second half of Axiom 1, that remapping the domain maintains privacy, then there is a privacy measure satisfying the remaining axioms, that we call ${𝒫}_{\text{heavy}}$, that deems the following algorithm perfectly private: Let $ℳ:X^n\to X^n\cup \{\mathrm{\varnothing }\}$ be the algorithm with the following behavior:

Essentially, $ℳ$ is allowed to leak the entire dataset if there is any element appearing frequently enough. Despite this leakage, ${𝒫}_{\text{heavy}}(ℳ)=0$, indicating that $ℳ$ should have “perfect” privacy. We further observe that ${𝒫}_{\text{heavy}}$ still satisfies that permuting the domain maintains privacy. This shows that we could not have replaced the arbitrary mappings $\sigma :X\to X$ in Axiom 1 with arbitrary permutations without allowing this ill-behaved notion of privacy.

If we remove Axiom 2 (prohibition of blatant non-privacy), then a privacy measure ${𝒫}_{\mathrm{all}}$ that deems all algorithms perfectly private, i.e. ${𝒫}_{\mathrm{all}}(ℳ)=0$ for all $ℳ$, satisfies the remaining axioms.

If we relax strong composition to linear composition, i.e. allow $c=1$ in Axiom 3, then there is a privacy measure, that we call ${𝒫}_{\mathrm{junta}}$ with the following behavior: The algorithm $ℳ:X^n\to X^k$ which outputs the first $k$ points in its dataset satisfies ${𝒫}_{\mathrm{junta}}(ℳ)=\frac{k}{2n}$. For example, an algorithm which outputs the first half of its dataset is still ${𝒫}_{\mathrm{junta}}$-private.

If we remove Axiom 4 (linear scaling), then there is a rescaling, ${𝒫}_{\sqrt{\mathrm{junta}}}$, of the above privacy measure that satisfies the remaining axioms. The algorithm $ℳ:X^n\to X^k$ which outputs the first $k$ points in its dataset is satisfies ${𝒫}_{\sqrt{\mathrm{junta}}}(ℳ)=\sqrt{\frac{k}{2n}}$. This still has essentially the same consequences as if we weakened Axiom 3. For example, we still have that the algorithm which outputs the first half of its dataset is ${𝒫}_{\sqrt{\mathrm{junta}}}$-private.