Lowering the cost of anonymization

2.2.9 Summarizing table

In this section we summarize the results from the previous 7 sections into a table where we list the known relations and show the properties with either referring to the original proof or creating a novel one.

In Table 2.20, we list the differential privacy variants and extensions introduced in this work. For each, we specify their name, parameters and where they were introduced (column 1), which dimensions they belong to (column 2), which axioms they satisfy (column 3, post-processing on the left and convexity on the right), whether they are composable (column 4) and how they relate to other differential privacy notions (column 5). We do not list definitions whose only difference is that they apply DP to other types of input, like those from Section 2.2.3, or geolocation-specific definitions.

The references for each claim present in Table 2.20 are listed after the table, while the proofs follow in Section 2.2.9. Like in the rest of this chapter, the following abbreviations are used for dimensions:

Q: Quantification of privacy loss
N: Neighborhood definition
V: Variation of privacy loss
B: Background knowledge
F: Formalism of privacy loss
R: Relativization of knowledge gain
C: Computational power

Name & references	Dimensions	P.P.¹	Cv.²	Cp.³	Relations
$(ε, δ)$ -DP, or $(ε, δ)$ -approximate DP [DKM $+$ 06] also known as max-KL stability [BNS $+$ 16]	Q	$✓$ ⁵	$✓$ ⁵	$✓$ ¹¹	$(ε, δ)$ -DP $\supset^{≺}$ $ε$ -DP
$(ε, δ)$ -probabilistic DP [MKA $+$ 08, Mei18] also known as $(ε, δ)$ -DP in distribution [CO15]	Q	$✗$ ⁴	$✗$ ⁶	$✓$ ¹¹	$(ε, δ)$ -DP $\sim$ $(ε, δ)$ -ProDP $\supset^{≺}$ $ε$ -DP
$(ε, δ_{a}, δ_{p})$ -Relaxed DP [ZQZ $+$ 15]	Q	$✗$ ⁴	$✗$ ⁶	$✓$ ¹¹	$(ε, δ_{p})$ -ProDP $\subset^{≻}$ $(ε, δ_{a}, δ_{p})$ -RelDP $\supset^{≺}$ $(ε, δ_{a})$ -DP
$ε$ -Kullback-Leiber Pr [BD14, CY16]	Q	$✓$ ⁵	$✓$ ⁵	$✓$ ¹¹	$(ε, δ)$ -DP $≺$ $ε$ -KLPr $≺$ $ε$ -DP
$(α, ε)$ -Rényi DP [Mir17]	Q	$✓$ ⁵	$✓$ ⁵	$✓$ ¹¹	$ε$ -KLPr $\subset^{≺}$ $(α, ε)$ -RenyiDP $\supset^{≺}$ $ε$ -DP
binary- $\| χ \|^{α}$ DP [WBK19]	Q	?	?	?	b- $\| χ \|^{α}$ DP $≻$ $(ε, δ)$ -DP
tenary- $\| χ \|^{α}$ DP [WBK19]	Q	?	?	?	t- $\| χ \|^{α}$ DP $≻$ $(ε, δ)$ -DP
$ε$ -total variation Pr [BD14]	Q	?	?	?	$ε$ -TVPr $\subset$ b- $\| χ \|^{α}$ DP
$ε$ -quantum DP [Col16]	Q	?	?	?
$ε$ -mutual-information DP [CY16]	Q	$✓$ ⁵	$✓$ ⁵	$✓$ ¹¹	$(ε, δ)$ -DP $≺$ $ε$ -MIDP $≺$ $ε$ -KLPr
$(μ, τ)$ -mean concentrated DP [DR16]	Q	$✗$ ⁴	?	$✓$ ¹¹	$(ε, δ)$ -DP $≺$ $(μ, τ)$ -mCoDP $≺$ $ε$ -DP
$(ξ, ρ)$ -zero concentrated DP [BS16]	Q	$✓$ ⁵	$✓$ ⁵	$✓$ ¹¹	$(ξ, ρ)$ -zCoDP $\sim$ $(μ, τ)$ -mCoDP
$(ξ, ρ, δ)$ -approximate CoDP [BS16]	Q	$✗$ ⁵	?	$✓$ ¹¹	$(ε, δ)$ -DP $≻$ $(ξ, ρ, δ)$ -ACoDP $\supset^{≺}$ $(ξ, ρ)$ -zCoDP
$(ξ, ρ, ω)$ -bounded CoDP [BS16]	Q	$✓$ ⁵	$✓$ ⁵	$✓$ ¹¹	$(ξ, ρ, ω)$ -bCoDP $\supset^{≺}$ $(ξ, ρ)$ -zCoDP
$(η, τ)$ -truncated CoDP [Col16]	Q	$✓$ ⁵	$✓$ ⁵	$✓$ ¹¹	$(η, τ)$ -tCoDP^[Col16] $\sim$ $ε$ -DP
$(ρ, ω)$ -truncated CoDP [BDRS18]	Q	$✓$ ⁵	$✓$ ⁵	$✓$ ¹¹	$(ρ, ω)$ -tCoDP^[BDRS18] $\subset^{≺}$ $(ξ, ρ, ω)$ -bCoDP
$(f, ε)$ -divergence DP [BD14]	Q	$✓$ ⁵	$✓$ ⁵	?	$(f, ε)$ -DivDP $\supset$ most definitions in Q
$(f_{k}, ε)$ -divergence DP [DR18]	Q	$✓$ ⁵	$✓$ ⁵	?	$(f_{k}, ε)$ -DivDP $\subset$ $(f, ε)$ -DivDP
$(H, f, ε)$ -capacity bounded DP [CIM19]	Q	$✓$ ⁵	$✓$ ⁵	?	$(H, f, ε)$ -CBDP $\subset^{≺}$ $(f, ε)$ -DivDP
$ε$ -unbounded DP [KM11]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$ε$ -DP $\sim$ $ε$ -uBoDP $\subset^{\sim}$ $(c, ε)$ -GrDP
$ε$ -bounded DP [KM11] also known as per-person DP [FMTT18]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$ε$ -BoDP $≺$ $ε$ -DP
$ε$ -attribute/bit DP [KM11]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$ε$ -BitDP $≺$ $ε$ -AttDP $≺$ $ε$ -BoDP
$ε$ -element DP [ADJ19]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$ε$ -ELDP $≺$ $ε$ -DP
$(P, ε)$ -one-sided DP [KDH $+$ 20]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(P, ε)$ -OnSDP $\supset^{≺}$ $ε$ -BoDP
$(N, k, ε)$ -sensitive privacy [APV19]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(N, k, ε)$ -SenPr $\subset$ $ε$ - $(P, ε)$ -OnSDP
$(P, ε)$ -anomaly-restricted DP [BSW18]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(P, ε)$ -ARDP $\supset^{≺}$ $ε$ -DP
$(c, ε)$ -group DP [Dwo08] also known as DP under correlation [CFYD14]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(c, ε)$ -GrDP $\supset^{\sim}$ $ε$ -DP
$(R, c, ε)$ -dependent DP [LCM16]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(R, c, ε)$ -DepDP $\supset$ $(c, ε)$ -GrDP
$(A, ε)$ -bayesian DP [YSN15]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(A, ε)$ -BayDP^[YSN15] $\supset$ $(R, c, ε)$ -DepDP
$(A, ε)$ -correlated DP [WDN17, WWK $+$ 17]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(A, ε)$ -CorDP $\subset$ $(A, ε)$ -BayDP^[YSN15]
$(A, ε)$ -prior DP [LRYY19]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(A, ε)$ -PriDP $\supset$ $(A, ε)$ -BayDP^[YSN15]
$ε$ -free lunch Pr [KM11]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$ε$ -FLPr $≻$ all definitions in N
$(D, ε)$ -individual DP [SCDFSM17] also known as conditioned DP [CH16]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(D, ε)$ -IndDP $≺$ $ε$ -DP
$(D, t, ε)$ -per-instance DP [Wan17]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(D, t, ε)$ -PIDP $≺$ $(D, ε)$ -IndDP
$(R, ε)$ -generic DP [KM11, FC14]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(R, ε)$ -GcDP^[KM11] $\supset$ most definitions in N
$(d, Δ, ε)$ -constrained DP [ZLW09] also known as adjacent DP [KM20] and DP under a neighborhood [FC14]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(d, Δ, ε)$ -ConsDP $\sim$ $(R, ε)$ -GcDP
$(d, Δ, S_{D}, ε)$ -distributional Pr [ZLW09]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(d, Δ, S_{D}, ε)$ -DlPr^[ZLW09] $\subset$ $(R, ε)$ -GcDP
$(f, ε)$ -sensitivity-induced DP [RA17]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$ε$ -SIDP $\subset$ $(R, ε)$ -GcDP
$(Q, ε)$ -induced-neighbors DP [KM11]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(Q, ε)$ -INDP $\subset$ $(R, ε)$ -GcDP
$(G, Q, ε)$ -blowfish Pr [HMD14, HMD15]	N	$✓$ ⁴	$✓$ ⁴	$✓$ ¹²	$(G, Q, ε)$ -BFPr $\subset$ $(R, ε)$ -GcDP $\supset^{≺}$ $(Q, ε)$ -INDP
$ε$ -adjacency-relation div. DP [KM19a]	Q,N	$✓$ ⁵^,⁴	$✓$ ⁵^,⁴	?	$(R, ε)$ -GcDP^[KM11] $\subset$ $(R, f, ε)$ -ARDDP $\supset$ $(f, ε)$ -DivDP
$Ψ$ -personalized DP [NAD14, JYC15, ESS15, GR15, LWS15] also known as heterogeneous DP [AGK17]	V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$Ψ$ -PerDP $\supset$ $ε$ -DP
$Ξ$ -tailored DP [LP15]	V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$Ξ$ -TaiDP $\supset$ $Ψ$ -PerDP
$ε (\cdot)$ -outlier Pr [LP15]	V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$ε (\cdot)$ -OutPr $\subset$ $Ξ$ -TaiDP
$(k, ε)$ -simple-outlier Pr [LP15]	V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$(k, ε)$ -SOPr $\subset$ $ε (\cdot)$ -OutPr
$(k, ε)$ -simple outlier DP [LP15]	V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$ε$ -DP $≻$ $(k, ε)$ -SODP $\subset$ $ε (\cdot)$ -OutPr
$(¯ ¯ ¯ k, ¯ ¯ ¯ ε)$ -staircase outlier DP [LP15]	V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$(¯ ¯ ¯ k, ¯ ¯ ¯ ε)$ -SCODP $\subset$ $ε (\cdot)$ -OutPr
$(ε, p, r)$ -Pareto DP [LP15]	V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$(ε, p, r)$ -ParDP $\subset$ $Ξ$ -TaiDP
$(π, γ, ε)$ -random DP [HWR13]	V	?	$✗$ ⁸	$✓$ ¹¹	$(π, γ, ε)$ -RanDP $\supset^{≺}$ $ε$ -DP
$(π, γ, ε)$ -predictive DP [Hal12] also known as model-specific DP [McC15]	V	?	?	?	$(π, γ, ε)$ -RanDP $≺$ $(π, γ, ε)$ -PredDP $\supset^{≺}$ $ε$ -DP
$(θ, γ, ε)$ -generalized DP [DJRT13]	V	?	?	?	$(θ, γ, ε)$ -GdDP $\supset^{≺}$ $ε$ -DP
$d_{D}$ -Pr [CABP13] also known as extended DP [KM19b]	N,V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$ε$ -DP $\subset$ $d_{D}$ -Pr
$ε$ -weighted DP [PGM14]	N,V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$ε$ -WeiDP $\subset$ $d_{D}$ -Pr
$(d_{D}, ε)$ -smooth DP [BD14]	N,V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$(d_{D}, ε)$ -SmoDP $\sim$ $d_{D}$ -Pr
$(d_{D}, ε)$ -earth mover’s Pr [FDM19]	N,V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$(d_{D}, ε)$ -EMDP $\subset$ $d_{D}$ -Pr
$(π, ε, γ)$ -DP on $δ$ location set [XX15]	N,V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$(π, ε, γ)$ -LocSetDP
$(ε, γ)$ -distributional Pr [ZLW09, Rot10]	N,V	?	?	?	$ε$ -FLPr $\subset$ $(ε, γ)$ -DlPr^{[Rot10, BLR13]}
$(ε (\cdot), δ (\cdot))$ -endogenous DP [Kre19]	Q,V	$✓$ ⁷	$✓$ ⁷	$✓$ ¹²	$(ε, δ)$ -DP $\subset$ $(ε (\cdot), δ (\cdot))$ -EndDP $\supset^{≺}$ $Ψ$ -PerDP
$(π, ε, δ)$ -weak Bayesian DP [TF20]	Q,V	$✓$ ⁴	?	$✓$ ¹²	$(ε, δ)$ -DP $≻$ $(π, ε, δ)$ -WBDP $≺$ $(π, γ, ε)$ -RanDP
$(Θ, ε)$ -on average KL Pr [WLF16, FS18] also known as average leave-one-out KL stability [FS18]	Q,V	$✓$ ⁵^,⁴	?	?¹⁶	$ε$ -KLPr $≻$ $(Θ, ε)$ -avgKLPr $≺$ $(π, γ, ε)$ -RanDP
$(π, ε, δ)$ -Bayesian DP [TF20]	Q,V	$✓$ ⁴	$✗$ ⁸	$✓$ ¹²	$(ε, δ)$ -ProDP $≻$ $(π, ε, δ)$ -BayDP^[TF20] $≺$ $(π, γ, ε)$ -RanDP
$(θ, ε, δ)$ -privacy at risk [DBB20]	Q,V	$✓$ ⁴	$✗$ ⁸	$✓$ ¹²	$(ε, δ)$ -ProDP $≻$ $(θ, ε, δ)$ -PAR $≺$ $(π, γ, ε)$ -RanDP
$(d_{D}, ε, δ)$ -pseudo-metric DP [DNZ $+$ 17]	Q,N,V	?	?	$✓$ ¹¹	$(ε, δ)$ -DP $\subset$ $(d_{D}, ε, δ)$ -PsDP $\supset^{≺}$ $d_{D}$ -Pr
$(f, d, ε)$ -extended divergence DP [KM19a]	Q,N,V	$✓$ ⁷	$✓$ ⁷	?	$d_{D}$ -Pr $\subset$ $(f, d, ε)$ -EDivDP $\supset$ $(f, ε)$ -Div DP
$(R, M)$ -generic DP [KL10]	Q,N,V	$✓$ ⁴	$✓$ ⁴	?	$(R, M)$ -GcDP^[KL10] $\supset$ $(ε, δ)$ -DP
$(R, q)$ -abstract DP [KL10]	Q,N,V	$✗$ ⁴	$✗$ ⁴	?	$(R, q)$ -AbsDP $\supset$ $(R, M)$ -GcDP^[KL10]
$(Θ, ε)$ -noiseless Pr [Dua09, BBG $+$ 11, GK17a, WXH17]	B	$✓$ ⁴	$✓$ ⁴	$✗$ ¹³	$ε$ -DP $\subset$ $(Θ, ε)$ -NPr
$(Θ, ε)$ -causal DP [DMKB19]	B	$✓$ ⁴	$✓$ ⁴	$✗$ ¹³	$(Θ, ε)$ -CausDP $\supset^{≺}$ $ε$ -DP
$(β, ε)$ -DP under sampling [LQS11]	Q,B	$✓$ ⁴	$✓$ ⁴	$✗$ ¹³	$(Θ, ε)$ -NPr $\supset$ $(β, ε)$ -SamDP $\supset^{≺}$ $ε$ -DP
$(Θ, ε, δ)$ -active PK DP [BBG $+$ 11, BGKS13, DMKB19]	Q,B	$✓$ ⁴	$✓$ ⁴	$✗$ ¹³	$(Θ, ε, δ)$ -APKDP $\supset^{≺}$ $(Θ, ε)$ -NPr
$(Θ, ε, δ)$ -passive PK DP [DMKB19]	Q,B	$✓$ ⁴	$✓$ ⁴	$✗$ ¹³	$(Θ, ε, δ)$ -APKDP $≻$ $(Θ, ε, δ)$ -PPKDP $\supset^{≺}$ $(Θ, ε)$ -NPr
$(Θ, Φ, ε)$ -pufferfish Pr [KM12, JB14, KM19b]	N,B	$✓$ ⁴	$✓$ ⁴	$✗$ ¹³	$(Θ, ε)$ -NPr $\subset$ $(Θ, Φ, ε)$ -PFPr $\supset$ $(R, ε)$ -GcDP
$(π, k, ε)$ -Bayesian DP [LL12]	N,B	$✓$ ⁴	$✓$ ⁴	$✗$ ¹³	BayDP^[LL12] $\subset$ $(Θ, Φ, ε)$ -PFPr
$(Θ, ε, δ)$ -distribution Pr [KM19b]	Q,N,B	$✓$ ⁷	$✓$ ⁷	$✗$ ¹³	$(Θ, ε, δ)$ -DnPr $\supset$ $(Θ, ε, δ)$ -APKDP
$(Θ, ε, δ)$ -profile-based DP [GC19]	Q,N,B	$✓$ ⁷	$✓$ ⁷	$✗$ ¹³	$(Θ, ε, δ)$ -PBDP $\subset$ $(Θ, ε, δ)$ -DnPr
$(Θ, ε, δ)$ -probabilistic DnPr [KM19b]	Q,N,B	$✗$ ⁴	$✗$ ⁶	$✗$ ¹³	$ε$ -ProDP $\subset$ $(Θ, ε, δ)$ -PDnPr $\supset$ $(Θ, ε)$ -DnPr
$(f, Θ, ε)$ -divergence DnPr [KM19a]	Q,N,B	$✓$ ⁷	$✓$ ⁷	$✗$ ¹³	$(f, ε)$ -DP $\subset$ $(f, Θ, ε)$ -DDnPr $\supset$ $(Θ, ε)$ -DnPr
$(d, Θ, ε)$ -extended DnPr [KM19b]	N,V,B	$✓$ ⁷	$✓$ ⁷	$✗$ ¹³	$d_{D}$ -Pr $\subset$ $(d, Θ, ε)$ -EDnPr $\supset$ $(Θ, ε)$ -DnPr
$(d, f, Θ, ε)$ -ext. div. DnPr [KM19a]	Q,N,V,B	$✓$ ⁷	$✓$ ⁷	$✗$ ¹³	$(f, Θ, ε)$ -DDPr $\subset$ $(d, f, Θ, ε)$ -EDDnPr $\supset$ $(d, Θ, ε)$ -EDnPr
$ε$ -indistinguishable Pr [LXL13]	F	$✓$ ¹⁴	$✓$ ¹⁴	$✓$ ¹⁴	$ε$ -IndPr $\sim$ $ε$ -DP
$f$ -DP [DRS19]	Q,F	$✓$ ⁴	?	$✓$ ⁴	$f$ -DP $\supset$ $(ε, δ)$ -DP
Gaussian DP [DRS19]	Q,F	$✓$ ⁴	?	$✓$ ⁴	GaussDP $\subset$ $f$ -Pr
$(Θ, ε)$ -positive membership Pr [LQS $+$ 13]	B,F	$✓$ ⁹	$✓$ ⁹	$✗$ ¹³	$(Θ, ε)$ -PMPr $\supset$ $ε$ -BoDP
$(Θ, ε)$ -negative membership Pr [LQS $+$ 13]	B,F	$✓$ ⁹	$✓$ ⁹	$✗$ ¹³	$(Θ, ε)$ -NMPr $\supset$ $ε$ -BoDP
$(Θ, ε)$ -membership Pr [LQS $+$ 13]	B,F	$✓$ ⁹	$✓$ ⁹	$✗$ ¹³	$(Θ, ε)$ -PMPr $≺$ $(Θ, ε)$ -MPr $≻$ $(Θ, ε)$ -NMPr
$(Θ, ε, δ)$ -adversarial Pr [RHMS09, WXH17] also known as information privacy [WXH17]	Q,B,F	$✓$ ⁹	$✓$ ⁹	$✗$ ¹³	$(ε, δ)$ -DP $\subset$ $(Θ, ε, δ)$ -AdvPr $≺$ $(Θ, ε)$ -PMPr
$(Θ, ε)$ -aposteriori noiseless Pr [BBG $+$ 11]	B,F	$✓$ ⁹	$✓$ ⁹	?	$(Θ, ε)$ -ANPr $\sim$ $(Θ, ε)$ -NPr
$ε$ -semantic Pr [GKS08, KS14]	F	?	?	?	$ε$ -SemPr $\sim$ $ε$ -DP
$ε$ -range-bounded Pr [DR19]	F	?	?	?	$ε$ -RBPr $\sim$ $ε$ -DP
$(Θ, ε)$ -inference-based causal DP [DMKB19]	B,F	?	?	?	$(Θ, ε)$ -IBCDP $\sim$ $(Θ, ε)$ -CausDP
$(Θ, ε)$ -information Pr [dPCF12]	N,B,F	?	?	?	$(Θ, ε)$ -InfPr $≻$ $ε$ -DP
$(A g g, ε)$ -zero-knowledge Pr [GLP11]	R	$✓$ ⁴	$✓$ ⁴	?¹⁶	$(A g g, ε)$ -ZKPr $≻$ $ε$ -DP
$(P, ε, δ)$ -bounded leakage DP [LPR20]	Q,R	$✓$ ⁴	$✓$ ⁴	$✓$ ¹¹	$(P, ε, δ)$ -BLDP $\supset$ $(ε, δ)$ -DP
$(Θ, Γ, ε)$ -coupled-worlds Pr [BGKS13]	N,B,R	$✓$ ⁴	$✓$ ⁴	$✗$ ⁷	$(Θ, Γ, ε)$ -CWPr $\supset$ $ε$ -DP
$(Θ, ε)$ -distributional DP [BGKS13]	N,B,R	$✓$ ⁴	$✓$ ⁴	$✗$ ⁷	$(Θ, Γ, ε)$ -CWPr $\supset$ $(Θ, ε)$ -DistDP $\supset^{≺}$ $ε$ -DP
$(Θ, Γ, ε, δ)$ -inference-based CW Pr [BGKS13]	Q,N,B,F,R	?	?	$✗$ ⁷	$(Θ, Γ, ε, δ)$ -IBCWPr $≻$ $(Θ, Γ, ε)$ -CWPr
$(Θ, Γ, ε, δ)$ -inference-based DistDP [BGKS13]	Q,N,B,F,R	?	?	$✗$ ⁷	$(Θ, ε)$ -DDP $≻$ $(Θ, Γ, ε, δ)$ -IBDDP $\subset$ $(Θ, Γ, ε, δ)$ -IBCWPr
$(Θ, ε, γ, δ)$ -typical stability [BF16]	Q,V,R	$✓$ ⁴	?	$✓$ ¹¹
$ε_{κ}$ -SIM-computational DP [MPRV09]	C	$✓$ ¹⁰	$✓$ ¹⁰	$✓$ ¹⁷	$ε_{κ}$ -SimCDP $≺$ $ε$ -DP
$ε_{κ}$ -IND-computational DP [MPRV09]	C	$✓$ ¹⁰	$✓$ ¹⁰	$✓$ ¹⁷	$ε_{κ}$ -IndCDP $≺$ $ε_{κ}$ -SimCDP
$(ε, δ)$ -DP for Record Linkage [HMFS17]	C	$✓$ ¹⁰	$✓$ ¹⁰	$✓$ ¹⁷	$(ε, δ)$ -RLDP $\subset$ $(ε, δ, f)$ -OCDP
$(ε, δ, f)$ -output constrained DP [HMFS17]	N,C	$✓$ ¹⁰	$✓$ ¹⁰	$✓$ ¹⁷	$(ε, δ, f)$ -OCDP $\supset$ $ε_{κ}$ -IndCDP
$(A g g, ε)$ -computational ZK Pr [GLP11]	R,C	$✓$ ¹⁰	$✓$ ¹⁰	?	$(A g g, ε)$ -CZKPr $\supset^{≺}$ $(A g g, ε)$ -ZKPr

¹ Post-processing
² Convexity
³ Composition
⁴ See Proposition 11.
⁵ See Proposition 12.
⁶ See Proposition 13.
⁷ See Proposition 14.
⁸ See Proposition 15.
⁹ See Proposition 16.
¹⁰ See Proposition 17.
¹¹ See Proposition 18.
¹² See Proposition 19.
¹³ See Proposition 20.
¹⁴ Follows directly from its equivalence to

ε

-DP.
¹⁵ A modified definition was presented in [KM12], which is an instance of PF Pr.
¹⁶ A proof for a restricted scenario appears in the paper introducing the definition.
¹⁷ This claim appears in [Mir17], its proof is in the unpublished full version.

Table 2.20: Summary of variants/extensions of DP representing the main options in each combination of dimensions.

Proofs of properties

We first list known results for variants and extensions satisfying privacy axioms, prove additional results, then we do the same for composition.

Axioms

Proposition 11.

1.: ProDP, ACoDP, and mCoDP do not satisfy the post-processing axiom [Mei18, BS16].
2.: AbsDP satisfies neither privacy axiom, while GlDP satisfies both [KL10, KM12]²².
3.: WBDP satisfies the post-processing axiom [TF20].
4.: TypSt satisfies the post-processing axiom [BF16].
5.: GaussDP satisfies the post-processing axiom [DRS19].
6.: PFPr satisfies both privacy axioms [KM12].
7.: CWPr satisfies both privacy axioms ²³ [BGKS13].
8.: APKDP and PPKDP satisfy both privacy axioms [DMKB19].
9.: BLDP satisfies both privacy axioms [LPR20].

Proposition 12. All instantiations of DivDP satisfy both privacy axioms. In particular, approximate DP, MIDP, KLPr, RenDP, and zCoDP satisfy both axioms.

Proof. The post-processing axiom follows directly from the monotonicity property of the $f$ -divergence. The convexity axiom follows directly from the joint convexity property of the $f$ -divergence. □

Proposition 13. ProDP and ACoDP do not satisfy the convexity axiom.

Proof. Consider the following mechanisms $M_{1}$ and $M_{2}$ , with input and output in ${0, 1}$ .

$M_{1} (0) = 0$ , $M_{1} (1) = 1$ with probability $δ$ , and $M_{1} (1) = 0$ with probability $1 - δ$ .
$M_{2} (0) = M_{2} (1) = 1$ .

Both mechanisms are $(\frac{1}{1 - δ}, δ)$ -ProDP. Now, consider the mechanism $M$ which applies $M_{1}$ with probability $1 - 2 δ$ and $M_{2}$ with probability $2 δ$ . $M$ is a convex combination of $M_{1}$ and $M_{2}$ , but the reader can verify that it is not $(\frac{1}{1 - δ}, δ)$ -ProDP. The result for $(ξ, ρ, δ)$ -ACoDP is a direct corollary, since is is equivalent to $(ξ, δ)$ -ProDP when $ρ = 0$ . □

Proposition 14. $d_{D}$ -Pr satisfies both privacy axioms. Further, EDivDP also satisfies both privacy axioms.

Proof. The proof of Proposition 11 for PFPr (Appendix B in [KM12]) is a proof by case analysis on every possible protected property. The fact that $ε$ is the same for every protected property has no influence on the proof, so we can directly adapt the proof to $d_{D}$ -Pr, and its combination with PFPr. Similarly, the proof can be extended to arbitrary divergence functions, like in Proposition 12. □

Proposition 15. RanDP does not satisfy the convexity axiom.

Proof. Let $π$ be the uniform distribution on ${0, 1}$ , let $D_{1}$ be generated by picking $10$ records according to $π$ , and $D_{2}$ by flipping one record at random. Let $M_{0}$ return $0$ if all records are $0$ , and $⊥$ otherwise. Let $M_{1}$ return $1$ if all records are $1$ , and $⊥$ otherwise.

Note that both mechanisms are $(π, 2^{- 9}, 0)$ -RanDP. Indeed, $M_{0}$ will only return $0$ for $D_{1}$ with probability $2^{- 10}$ , and for $D_{2}$ with probability $2^{- 10}$ (if $D_{1}$ only has one $1$ , which happens with probability $10 \cdot 2^{- 10}$ , and this record is flipped, which happens with probability $0.1$ ). In both cases, $M_{0}$ will return $⊥$ for the other database; which will be a distinguishing event. Otherwise, $M_{0}$ will return $τ$ for both databases, so $M (D_{1}) \approx_{0} M (D_{2})$ . The reasoning is the same for $M_{1}$ .

However, the mechanism $M_{0.5}$ obtained by applying either $M_{0}$ or $M_{1}$ uniformly randomly does not satisfy $(π, 2^{- 9}, 0)$ -RanDP: the indistinguishability property does not hold if $D_{1}$ or $D_{2}$ have all their records set to either $0$ or $1$ , which happens twice as often as either option alone. □

Proposition 16. All variants of MPr, AdvPr, and ANPr satisfy both axioms. As a direct corollary, InfPr also satisfies both axioms.

Proof. We prove it for AdvPr. A mechanism $M$ satisfies $(Θ, ε, δ)$ -AdvPr if for all $t \in T$ , $θ \in Θ$ , and $S \subseteq O$ , $P_{D \sim θ} [t \in D | M (D) \in S] \leq e^{ε} \cdot P_{D \sim θ} [t \in D] + δ$ . We first prove that it satisfies the convexity axiom. Suppose $M$ is a convex combination of $M_{1}$ and $M_{2}$ . Simplifying $P_{D \sim θ} [\dots]$ into $P [\dots]$ , we have:

P [t \in D | M (D) \in S] = \frac{P [t \in D and M (D) \in S and M = M_{1}]}{P [M (D) \in S]} + \frac{P [t \in D and M (D) \in S and M = M_{2}]}{P [M (D) \in S]}

Denoting $X_{i} = P [M (D) \in S and M = M_{i}]$ for $i \in {1, 2}$ , this gives:

\begin{matrix} P [t \in D | M (D) \in S] & = \frac{X_{1} \cdot P [t \in D | M_{1} (D) \in S]}{X_{1} + X_{2}} + \frac{X_{2} \cdot P [t \in D | M_{2} (D) \in S]}{X_{1} + X_{2}} \leq \frac{X_{1} (e^{ε} \cdot P [t \in D]) + δ}{X_{1} + X_{2}} + \frac{X_{2} (e^{ε} \cdot P [t \in D]) + δ}{X_{1} + X_{2}} \leq e^{ε} \cdot P [t \in D] + δ . \end{matrix}

The proof for the post-processing axiom is similar, summing over all possible outputs $M (D)$ . It is straightforward to adapt the proof to all other definitions which change the shape of the prior-posterior bounds. □

Proposition 17. Both versions of CDP satisfy both privacy axioms; where the post-processing axiom is modified to only allow post-processing with functions computable on a probabilistic polynomial time Turing machine. As a direct corollary of Proposition 11 for CWPr, CZKPr also satisfies both privacy axioms.

Proof. For Ind-CDP and the post-processing axiom, the proof is straightforward: if post-processing the output could break the $ε$ -indistinguishability property, the attacker could do this on the original output and break the $ε$ -indistinguishability property of the original definition.

For Ind-CDP and the convexity axiom, without loss of generality, we can assume that the sets of possible outputs of both mechanisms are disjoint (otherwise, this give strictly less information to the attacker). The proof is then the same as for the post-processing axiom.

For SimCDP, applying the same post-processing function to the “true” differentially private mechanism immediately leads to the result, since DP satisfies post-processing. The same reasoning holds for convexity. □

Composition

In this section, if $M_{1}$ and $M_{2}$ are two mechanisms, we denote $M_{1 + 2}$ the mechanism defined by $M_{1 + 2} (D) = (M_{1} (D), M_{2} (D))$ .

Proposition 18 (Existing results). If $M_{1}$ and $M_{2}$ are respectively…

1.: $(ε_{1}, δ_{1})$ -DP and $(ε_{2}, δ_{2})$ -DP, then $M_{1 + 2}$ is $(ε_{1} + ε_{2}, δ_{1} + δ_{2})$ -DP [DKM $+$ 06].
2.: $(ε_{1}, δ_{1})$ -ProDP and $(ε_{2}, δ_{2})$ -ProDP, then $M_{1 + 2}$ is $(ε_{1} + ε_{2}, δ_{1} + δ_{2})$ -ProDP [MKA $+$ 08, CO15, Mei18].
3.: $(ε_{1}, δ_{a, 1}, δ_{p, 1})$ -RelDP and $(ε_{2}, δ_{a, 2}, δ_{p, 2})$ -RelDP, then $M_{1 + 2}$ is $(ε_{1} + ε_{2}, δ_{a, 1} + δ_{a, 2}, δ_{p, 1} + δ_{p, 2})$ -RelDP [ZQZ $+$ 15].
4.: $ε_{1}$ -MIDP and $ε_{2}$ -MIDP, then $M_{1 + 2}$ is $(ε_{1} + ε_{2})$ -MIDP [CY16].
5.: $ε_{1}$ -KLDP and $ε_{2}$ -KLDP, then $M_{1 + 2}$ is $(ε_{1} + ε_{2})$ -KLDP [BD14, CY16].
6.: $(α_{1}, ε_{1})$ -RenDP and $(α_{2}, ε_{2})$ -RenDP, then $M_{1 + 2}$ is $(max (α_{1}, α_{2}), ε_{1} + ε_{2})$ -RenyiDP [Mir17].
7.: $(μ_{1}, τ_{1})$ -mCoDP and $(μ_{2}, τ_{2})$ -mCoDP, then $M_{1 + 2}$ is $(μ_{1} + μ_{2}, \sqrt{{μ_{1}}_{1}^{2} + {μ_{2}}_{2}^{2}})$ -mCoDP [DR16, BS16].
8.: $(ξ_{1}, ρ_{1})$ -zCoDP and $(ξ_{2}, ρ_{2})$ -zCoDP, then $M_{1 + 2}$ is $(ξ_{1} + ξ_{2}, ξ_{1} + ξ_{2})$ -zCoDP [BS16].
9.: $(ξ_{1}, ρ_{1}, δ_{1})$ -ACoDP and $(ξ_{2}, ρ_{2}, δ_{2})$ -ACoDP, then $M_{1 + 2}$ is $(ξ_{1} + ξ_{2}, ξ_{1} + ξ_{2}, δ_{1} + δ_{2} - δ_{1} δ_{2})$ -ACoDP [BS16].
10.: $(ξ_{1}, ρ_{1}, ω_{1})$ -bCoDP and $(ξ_{2}, ρ_{2}, ω_{2})$ -bCoDP, then $M_{1 + 2}$ is $(ξ_{1} + ξ_{2}, ξ_{1} + ξ_{2}, min (ω_{1}, ω_{2}))$ -bCoDP [BS16].
11.: $(η_{1}, τ_{1})$ -CCoDP and $(η_{2}, τ_{2})$ -CCoDP, then $M_{1 + 2}$ is $(η_{1} + η_{2}, \frac{{η_{1} + η_{2}}_{1}^{2}}{2})$ -CCoDP [Col16].
12.: $f_{1}$ -DP and $f_{2}$ -DP, than then $M_{1 + 2}$ is $f_{1} \otimes f_{2}$ -DP [DRS19].
13.: $(π, γ_{1}, ε_{1})$ -RanDP and $(π, γ_{2}, ε_{2})$ -RanDP, then $M_{1 + 2}$ is $(π, γ_{1} + γ_{2}, ε_{1} + ε_{2})$ -RanDP [Hal12].
14.: $(π, ε_{1}, δ_{1})$ -BayDP^[TF20] and $(π, ε_{1}, δ_{1})$ -BayDP^[TF20], then $M_{1 + 2}$ is $(π, ε_{1} + ε_{2}, δ_{1} + δ_{2})$ -BayDP^[TF20]. The same result holds for WBDP as an immediate consequence of Theorem 1 in [TF20].
15.: $(Θ, ε_{1}, γ_{1}, δ_{1})$ -TypSt and $(Θ, ε_{2}, γ_{2}, δ_{2})$ -TypSt, then $M_{1 + 2}$ is $(Θ, ε_{1} + ε_{2}, γ_{1} + γ_{2}, δ_{1} + δ_{2})$ -TypSt [BF16].
16.: $(d_{D}, ε_{1}, δ_{1})$ -PsDP and $(d_{D}, ε_{2}, δ_{2})$ -PsDP then $M_{1 + 2}$ is $(d_{D}, ε_{1} + ε_{2}, δ_{1} + δ_{2})$ -PsM DP [DNZ $+$ 17].
17.: $(P_{1}, ε_{1}, δ_{1})$ -BLDP and $(P_{2}, ε_{2}, δ_{2})$ -BLDP, then $M 1 + 2$ is $(P_{1 + 2}, ε_{1} + ε_{2}, δ_{1} + δ_{2})$ -BLDP, where $P_{1 + 2}$ is the concatenation of $P_{1}$ and $P_{2}$ (where the randomness is not shared between $P_{1}$ and $P_{2}$ , nor between $M_{1}$ and $M_{2}$ ) [LPR20].

Proposition 19. If $M_{1}$ is $d_{D}^{1}$ -private and $M_{2}$ is $d_{D}^{2}$ -private, then $M_{1 + 2}$ is $d_{D}^{1 + 2}$ -private, where $d_{D}^{1 + 2} (D_{1}, D_{2}) = d_{D}^{1} (D_{1}, D_{2}) + d_{D}^{2} (D_{1}, D_{2})$ .

Proof. The proof is essentially the same as for $ε$ -DP. $M_{1}$ ’s randomness is independent from $M_{2}$ ’s, so:

\begin{matrix} P [M_{1} (D_{1}) = O_{1} and M_{2} (D_{1}) = O_{2}] & = P [M_{1} (D_{1}) = O_{1}] \cdot P [M_{2} (D_{1}) = O_{2}] \leq e^{d_{D}^{1} (D_{1}, D_{2})} \cdot P [M_{2} (D_{2}) = O_{1}] \cdot e^{d_{D}^{2} (D_{1}, D_{2})} \cdot P [M_{2} (D_{2}) = O_{2}] \leq e^{d_{D}^{1 + 2} (D_{1}, D_{2})} \cdot P [M_{1} (D_{2}) = O_{1} and M_{2} (D_{2}) = O_{2}] . \end{matrix}

Each definition listed in Proposition 18 can also be combined with $d_{D}$ -privacy, and the composition proofs can be similarly adapted. □

Proposition 20. In general, definitions which assume limited background knowledge from the adversary do not compose.

Proof. The proof of Proposition 19 cannot be adapted to a context in which the attacker has limited background knowledge: as the randomness partially comes from the data-generating distribution, the two probabilities are no longer independent. A typical example considers two mechanisms which answer e.g., queries “how many records satisfy property $P$ ” and “how many records satisfy property $P$ and have an ID different from 4217”: the randomness in the data might make each query private, but the combination of two queries trivially reveals something about a particular user. Variants of this proof can easily be obtained for all definitions with limited background knowledge. □

²²As an immediate corollary, all definitions which combine notions in N and NPr also satisfy both axioms.

²³As an immediate corollary, DistDP and ZKPr also satisfy both axioms.

LINKPREV LINKUP LINKNEXT