Stéphane Vento
email: stephane.vento@univ-mlv.fr

Global well-posedness for dissipative Korteweg-de Vries equations

This paper is devoted to the well-posedness for dissipative KdV equations u t +u xxx +|D x | 2α u+uu x = 0, 0 < α ≤ 1. An optimal bilinear estimate is obtained in Bourgain's type spaces, which provides global wellposedness in H s (R), s > -3/4 for α ≤ 1/2 and s > -3/(5-2α) for α > 1/2.

Introduction

We study the initial value problem (IVP) for the dissipative KdV equations

u t + u xxx + |D x | 2α u + uu x = 0, t ∈ R + , x ∈ R, u(0, x) = u 0 (x), x ∈ R, (1.1)
with 0 < α ≤ 1 and where |D x | 2α denotes the Fourier multiplier with symbol |ξ| 2α . These equations can be viewed as a combinaison of the KdV equation

u t + u xxx + uu x = 0 (1.2)
and Burgers equation

u t -u xx + uu x = 0, (1.3)
involving both nonlinear dispersion and dissipation effects.

The Cauchy problem for the KdV equation has been studied by many authors. In [START_REF] Bourgain | Fourier transform restriction phenomena for certain lattice subsets and applications to nonlinear evolution equations. II. The KdVequation[END_REF], Bourgain introduced new functional spaces adapted to the linear symbol τ -ξ 3 and showed that the IVP associated to (1.2) is locally well-posed in L 2 (R). Due to the second conservation law, this result extends globally in time. Then, working in these spaces, Kenig, Ponce and Vega obtained local well-posedness in Sobolev spaces H s (R) for s > -5/8 in [START_REF] Kenig | The Cauchy problem for the Korteweg-de Vries equation in Sobolev spaces of negative indices[END_REF] and for s > -3/4 in [START_REF] Kenig | A bilinear estimate with applications to the KdV equation[END_REF]. More recently, global well-posedness was obtained for s > -3/4 in [START_REF] Colliander | Sharp global well-posedness for KdV and modified KdV on R and T[END_REF]. It is worth noticing that the index -3/4 is far away from the index -3/2 suggested by standard scaling argument. However, -3/4 is indeed the critical index for well-posedness. In fact, the solution map u 0 → u fails to be C 3 in H s (R), s < -3/4 (see [START_REF] Bourgain | Periodic Korteweg de Vries equation with measures as initial data[END_REF]) and C 2 in homogeneous spaces Ḣs (R), s < -3/4 (see [START_REF] Tzvetkov | Remark on the local ill-posedness for KdV equation[END_REF]). Moreover, the bilinear estimate in X b,s spaces used in [START_REF] Kenig | A bilinear estimate with applications to the KdV equation[END_REF] to prove local well-posedness is sharp with respect of s (see also [START_REF] Nakanishi | Counterexamples to bilinear estimates related with the KdV equation and the nonlinear Schrödinger equation[END_REF]).

Concerning the Cauchy problem for the Burgers equation, the situation is quite different. By using the strong smoothing effect of the semigroup related to the heat equation, one can solve (1.3) in the Sobolev space given by an heuristic scaling argument. In [START_REF] Dix | Nonuniqueness and uniqueness in the initial-value problem for Burgers' equation[END_REF], Dix proved local well-posedness of (1.3) in H s (R) for s > -1/2. Then, this result was extended to the case s = -1/2 in [START_REF] Bekiranov | The initial-value problem for the generalized Burgers' equation[END_REF]. Below this critical index, it has been showed in [START_REF] Dix | Nonuniqueness and uniqueness in the initial-value problem for Burgers' equation[END_REF] that uniqueness fails.

When α = 1/4, equation (1.1) models the evolution of the free surface for shallow water waves damped by viscosity, see [START_REF] Ott | Damping of solitary waves[END_REF]. When α = 1, (1.1) is the so-called KdV-Burgers equation which models the propagation of weakly nonlinear dispersive long waves in some contexts when dissipative effects occur (see [START_REF] Ott | Damping of solitary waves[END_REF]). In [START_REF] Molinet | The Cauchy problem for dissipative Korteweg de Vries equations in Sobolev spaces of negative order[END_REF], Molinet and Ribaud treat the KdV-B equation by working in the usual Bourgain space related to the KdV equation, considering only the dispersive part of the equation. They were able to prove global well-posedness for KdV-B in H s (R), s > -3/4 -1/24, getting a lower index than the critical indexes for (1.2) and (1.3). Then, the same authors improved this result in [START_REF] Molinet | On the low regularity of the Korteweg-de Vries-Burgers equation[END_REF] by going down to H s (R), s > -1. The main new ingredient is the introduction of a new Bourgain space containing both dispersive and dissipative parts of the equation. For s < -1, the problem is ill-behaved in the sense that the flow map u 0 → u is not C 2 in H s (R).

Concerning the case 0 < α < 1 in (1.1), Molinet and Ribaud established in [START_REF] Molinet | The Cauchy problem for dissipative Korteweg de Vries equations in Sobolev spaces of negative order[END_REF] the global well-posedness for data in H s (R), s > -3/4, whatever the value of α. On the other hand, ill-posedness is known for (1.1) in Ḣs (R), s < (α -3)/(2(2 -α)), see [START_REF] Molinet | On the low regularity of the Korteweg-de Vries-Burgers equation[END_REF].

In this paper we improve the results obtained in [START_REF] Molinet | The Cauchy problem for dissipative Korteweg de Vries equations in Sobolev spaces of negative order[END_REF]. We show that the Cauchy problem (1.1) is globally well-posed in H s (R), s > s α with

s α = -3/4 if 0 < α ≤ 1/2, -3 5-2α if 1/2 < α ≤ 1 .
Of course the case α ≤ 1/2 is well-known, but our general proofs contain this result. In suitable X b,s spaces, we are going to perform a fixed point argument on the integral formulation of (1.1). This will be achieved by deriving a bilinear estimate in these spaces. By Plancherel's theorem and duality, it reduces to estimating a weighted convolution of L 2 functions. To recover the lost derivative in the nonlinear term ∂ x (u 2 ), we take advantage of the well-known algebraic smoothing relation (2.5) combined with several methods. On one hand, we use Strichartz's type estimates and some techniques introduced in [START_REF] Kenig | A bilinear estimate with applications to the KdV equation[END_REF]. On the other hand, these techniques are not sufficient in certain regions to go down below -3/4 and we are lead tu use dyadic decomposition. In [START_REF] Tao | Multilinear weighted convolution of L 2 -functions, and applications to nonlinear dispersive equations[END_REF], Tao studied some nonlinear dispersive equations like KdV, Schrödinger or wave equation by using such dyadic decomposition and orthogonality. He obtained sharp estimates on dyadic blocs, which leads to multilinear estimates in the X b,s spaces, usable in many contexts. Note that very recently, such a method was exploited in [START_REF] Chen | The well-posedness of Cauchy problem for dissipative modified Korteweg de Vries equations[END_REF] for the dissipative modified-KdV equation

u t + u xxx + |D x | 2α u + u 2 u x = 0.
It is worth pointing out that (1.1) has no scaling invariance, so it is not clear that s α is the critical index for well-posedness. However, the fundamental bilinear estimate used to prove our results is optimal.

Notations

For two positive reals A and B, we write A B if there exists a constant C > 0 such that A ≤ CB. When this constant is supposed to be sufficiently small, we write A ≪ B. Similarly, we use the notations A B, A ∼ B and A ≫ B. When x ∈ R, x + denotes its positive part max(0, x). For f ∈ S ′ (R N ), we define its Fourier transform F(f ) (or f ) by

Ff (ξ) = R N e -i x,ξ f (x)dx.
The Lebesgue spaces are endowed with the norm

f L p (R N ) = R N |f (x)| p dx 1/p , 1 ≤ p < ∞
with the usual modification for p = ∞. We also consider the space-time Lebesgue spaces L p x L q t defined by

f L p x L q t = f L p x (R) L q t (R)
.

For b, s ∈ R, we define the Sobolev spaces H s (R) and their space-time versions H b,s (R 2 ) by the norms

f H s = R ξ 2s | f (ξ)| 2 dξ 1/2 , u H b,s = R 2 τ 2b ξ 2s | u(τ, ξ)| 2 dτ dξ 1/2 , with • = (1 + | • | 2 ) 1/2 .
Let U (t)ϕ denote the solution of the Airy equation

u t + u xxx = 0 u(0) = ϕ , that is, ∀t ∈ R, F x (U (t)ϕ)(ξ) = exp(iξ 3 t) ϕ(ξ), ϕ ∈ S ′ .
In [START_REF] Molinet | On the low regularity of the Korteweg-de Vries-Burgers equation[END_REF], Molinet and Ribaud introduced the function spaces X b,s α related to the linear symbol i(τ -ξ 3 ) + |ξ| 2α and defined by the norm

u X b,s α = i(τ -ξ 3 ) + |ξ| 2α b ξ s u L 2 (R 2 ) .
Note that since F(U (-t)u)(τ, ξ) = u(τ + ξ 3 , ξ), we can re-express the norm of X b,s α as

u X b,s α = iτ + |ξ| 2α b ξ s u(τ + ξ 3 , ξ) L 2 (R 2 ) = iτ + |ξ| 2α b ξ s F(U (-t)u)(τ, ξ) L 2 (R 2 ) ∼ U (-t)u H b,s + u L 2 t H s+2αb x .
We will also work in the restricted spaces X b,s α,T , T ≥ 0, equipped with the norm u X b,s

α,T = inf w∈X b,s α { w X b,s α , w(t) = u(t) on [0, T ]}.
Finally, we denote by W α the semigroup associated with the free evolution of (1.1),

∀t ≥ 0, F x (W α (t)ϕ)(ξ) = exp[-|ξ| 2α t + iξ 3 t] ϕ(ξ), ϕ ∈ S ′ ,
and we extend W α to a linear operator defined on the whole real axis by setting

∀t ∈ R, F x (W α (t)ϕ)(ξ) = exp[-|ξ| 2α |t| + iξ 3 t] ϕ(ξ), ϕ ∈ S ′ .
(1.4)

Main results

Let us first state our crucial bilinear estimate.

Theorem 1.1 Given s > s α , there exist ν, δ > 0 such that for any u, v ∈ X

1/2,s α with compact support in [-T, +T ], ∂ x (uv) X -1/2+δ,s α T ν u X 1/2,s α v X 1/2,s α . (1.5)
This result is optimal in the following sense.

Theorem 1.2 For all s ≤ s α and ν, δ > 0, there exist u, v ∈ X 1/2,s α with compact support in [-T, +T ] such that the estimate (1.5) fails.

Let ψ be a cutoff function such that

ψ ∈ C ∞ 0 (R), supp ψ ⊂ [-2, 2], ψ ≡ 1 on [-1, 1],
and define ψ T (•) = ψ(•/T ) for all T > 0. By Duhamel's principle, the solution to the problem (1.1) can be locally written in the integral form as

u(t) = ψ(t) W α (t)u 0 - χ R + (t) 2 t 0 W α (t -t ′ )∂ x (ψ 2 T (t ′ )u 2 (t ′ ))dt ′ . (1.6)
Clearly, if u is a solution of (1.6) on [-T, +T ], then u solves (1.1) on [0, T /2].

As a consequence of Theorem 1.1 together with linear estimates of Section 2.1, we obtain the following global well-posedness result.

Theorem 1.3 Let α ∈ (0, 1] and u 0 ∈ H s (R) with s > s α . Then for any T > 0, there exists a unique solution u of (1.1) in

Z T = C([0, T ], H s (R)) ∩ X 1/2,s α,T . Moreover, the map u 0 → u is smooth from H s (R) to Z T and u belongs to C((0, T ], H ∞ (R)).
Remark 1.1 Actually, we shall prove Theorems 1.1 and 1.3 in the most difficult case. In the sequel we assume

s α < s < -1/2 if α ≤ 1/2, s α < s < -3/4 if α > 1/2.
(1.7)

Remark 1.2 Theorem 1.3 is known to be sharp in the case α = 0 (KdV equation) and in the case α = 1 (KdV-B equation). On the other hand, as far as we know, most of nonlinear equations for which the multilinear estimate fails in the related X b,s space are ill-posed in H s . Therefore it is reasonable to conjecture that s α is really the critical index for (1.1). The fact that s α = -3/4 for α ≤ 1/2 could mean that the dissipative part in (1.1), when becoming small enough, has no effect on the low regularity of the equation.

Remark 1.3 It is an interesting problem to consider the periodic dissipative

KdV equation

u t + u xxx -|D x | 2α u + uu x = 0, t ∈ R + , x ∈ T, u(0, x) = u 0 (x), x ∈ T, . (1.8)
Concerning the KdV equation on T, global well-posedness is known in H 1/2 (T) (see [START_REF] Colliander | Sharp global well-posedness for KdV and modified KdV on R and T[END_REF]) and the result is optimal (see [START_REF] Bourgain | Periodic Korteweg de Vries equation with measures as initial data[END_REF]). For KdV-B, it is established in [START_REF] Molinet | On the low regularity of the Korteweg-de Vries-Burgers equation[END_REF] that the indexes of the critical spaces are the same on the real line and on the circle. We believe that working in the space X 1/2,s α endowed with the norm

u X 1/2,s α = n∈Z n 2s R i(τ -n 3 ) + |n| 2α | u(τ, n)| 2 dτ 1/2
, and using Tao's [k; Z]-multiplier norm estimates [START_REF] Tao | Multilinear weighted convolution of L 2 -functions, and applications to nonlinear dispersive equations[END_REF], one could get wellposedness results for the IVP (1.8) in H s (T), s > sα with s0 = -1/2 and s1 = -1. We do not pursue this issue here.

The remainder of this paper is organized as follows. In Section 2, we recall some linear estimates on the operators W α and L α , and we introduce Tao's [k; Z]-multiplier norm estimates. Section 3 is devoted to the proof of the bilinear estimate (1.5). Theorem 1.3 is established in Section 4. Finally, we show the optimality of (1.5) in Section 5.

Acknowledgment

The author would like to express his gratitude to Francis Ribaud for his availability and his constant encouragements.

Preliminaries

Linear estimates

In this subsection, we collect together several linear estimates on the operators W α introduced in (1.4) and L α defined by

L α : f → χ R + (t)ψ(t) t 0 W α (t -t ′ )f (t ′ )dt ′ .
All the results stated here were proved in [START_REF] Molinet | On the low regularity of the Korteweg-de Vries-Burgers equation[END_REF] for α = 1 and in [START_REF] Chen | The well-posedness of Cauchy problem for dissipative modified Korteweg de Vries equations[END_REF] for the general case.

Lemma 2.1 For all s ∈ R and all ϕ ∈ H s (R),

ψ(t)W α (t)ϕ X 1/2,s α ϕ H s .
(2.1)

Lemma 2.2 Let s ∈ R. (a) For all v ∈ S(R 2 ), χ R + (t)ψ(t) t 0 W α (t -t ′ )v(t ′ )dt ′ X 1/2,s α v X -1/2,s α + R ξ 2s R | v(τ +ξ 3 ,ξ)| iτ +|ξ| 2α dτ dξ 1/2 . (b) For all 0 < δ < 1/2 and all v ∈ X -1/2+δ,s α , χ R + (t)ψ(t) t 0 W α (t -t ′ )v(t ′ )dt ′ X 1/2,s α v X -1/2+δ,s α . (2.2)
To globalize our solution, we will need the next lemma.

Lemma 2.3 Let s ∈ R and δ > 0. Then for any f ∈ X -1/2+δ,s α , t -→ t 0 W α (t -t ′ )f (t ′ )dt ′ ∈ C(R + , H s+2αδ ). Moreover, if (f n ) is a sequence satisfying f n → 0 in X -1/2+δ,s α , then t 0 W α (t -t ′ )f n (t ′ )dt ′ L ∞ (R + ,H s+2αδ ) -→ 0.
Finally, we recall the following L 4 Strichartz's type estimate showed in [START_REF] Kenig | The Cauchy problem for the Korteweg-de Vries equation in Sobolev spaces of negative indices[END_REF][START_REF] Molinet | The Cauchy problem for dissipative Korteweg de Vries equations in Sobolev spaces of negative order[END_REF].

Lemma 2.4 Let f ∈ L 2 (R 2 ) with compact support (in time) in [-T, +T ].
For 0 ≤ θ ≤ 1/8 and ρ > 3/8, there exists ν > 0 such that

F -1 ξ θ f (τ, ξ) τ -ξ 3 ρ L 4 xt T ν f L 2 xt .

Tao's [k; Z]-multipliers

Now we turn to Tao's [k; Z]-multiplier norm estimates. For more details, please refer to [START_REF] Tao | Multilinear weighted convolution of L 2 -functions, and applications to nonlinear dispersive equations[END_REF].

Let Z be any abelian additive group with an invariant measure dξ. For any integer k ≥ 2 we define the hyperplane

Γ k (Z) = {(ξ 1 , ..., ξ k ) ∈ Z k : ξ 1 + ... + ξ k = 0}
which is endowed with the measure

Γ k (Z) f = Z k-1 f (ξ 1 , ..., ξ k-1 , -(ξ 1 + ... + ξ k-1 ))dξ 1 ...dξ k-1 . A [k; Z]-multiplier is defined to be any function m : Γ k (Z) → C. The multiplier norm m [k;Z]
is defined to be the best constant such that the inequality

Γ k (Z) m(ξ) k j=1 f j (ξ j ) ≤ m [k;Z] k j=1 f j L 2 (Z) (2.3)
holds for all test functions f 1 , ..., f k on Z. In other words,

m [k;Z] = sup f j ∈S(Z) f j L 2 (Z) ≤1 Γ k (Z) m(ξ) k j=1 f j (ξ j ) .
In his paper [START_REF] Tao | Multilinear weighted convolution of L 2 -functions, and applications to nonlinear dispersive equations[END_REF], Tao used the following notations. Capitalized variables N j , L j (j = 1, ..., k) are presumed to be dyadic, i.e. range over numbers of the form 2 ℓ , ℓ ∈ Z. In this paper, we only consider the case k = 3, which corresponds to the quadratic nonlinearity in the equation. It will be convenient to define the quantities N max ≥ N med ≥ N min to be the maximum, median and minimum of N 1 , N 2 , N 3 respectively. Similarly, define

L max ≥ L med ≥ L min whenever L 1 , L 2 , L 3 > 0.
The quantities N j will measure the magnitude of frequencies of our waves, while L j measures how closely our waves approximate a free solution.

Here we consider [3, R × R]-multipliers and we parameterize R × R by (τ, ξ) endowed with the Lebesgue measure dτ dξ. If τ, τ 1 , ξ, ξ 1 are given, we set

σ = σ(τ, ξ) = τ -ξ 3 , σ 1 = σ(τ 1 , ξ 1 ), σ 2 = σ(τ -τ 1 , ξ -ξ 1 ).
(2.4)

From the identity σ 1 + σ 2 -σ = 3ξξ 1 (ξ -ξ 1 ) one can deduce the well-known smoothing relation

max(|σ|, |σ 1 |, |σ 2 |) ≥ |ξξ 1 (ξ -ξ 1 )| (2.5)
which will be extensively used in Section 3. By a dyadic decomposition of the variables ξ 1 , ξ 2 = -ξ, ξ 3 = ξ -ξ 1 , and σ 1 , σ 2 , σ 3 = -σ, we are lead to consider

3 j=1 χ |ξ j |∼N j χ |σ j |∼L j [3;R×R] . (2.6)
We can now state the fundamental dyadic estimates for the KdV equation on the real line ([14], Proposition 6.1).

Lemma 2.5 Let N 1 , N 2 , N 3 , L 1 , L 2 , L 3 satisfying N max ∼ N med , L max ∼ max(N 1 N 2 N 3 , L med ). 1. ((++) Coherence) If N max ∼ N min and L max ∼ N 1 N 2 N 3 then we have (2.6) L 1/2 min N -1/4 max L 1/4
med .

(2.7)

2. ((+-) Coherence) If N 2 ∼ N 3 ≫ N 1 and N 1 N 2 N 3 ∼ L 1 L 2 , L 3 then (2.6) L 1/2 min N -1 max min N 1 N 2 N 3 , N max N min L med 1/2 . (2.8)
Similarly for permutations.

3. In all other cases, we have

(2.6) L 1/2 min N -1 max min(N 1 N 2 N 3 , L med ) 1/2 .
(2.9)

Because only one region needs to be controlled by using a dyadic approach, we just require the (+-) coherence case. On the other hand, these estimates are sharp. In particular, testing (2.3) with

f 1 (τ, ξ) = χ |ξ|∼N 1 ;|τ -3N 2 2 ξ| N 2 1 N 2 , f 2 (τ, ξ) = χ |ξ-N 2 | N 1 ;|σ| L 2 , f 3 (τ, ξ) = χ |ξ+N 2 | N 1 ;|σ| L 3 ,
one obtain the optimality of bound (2.8) in the case

N 2 ∼ N 3 N 1 and N 1 N 2 N 3 ∼ L 1 L 2 L 3 .
This will be crucial in the proof of Theorem 1.2.

Bilinear estimate

In this section, we derive the bilinear estimate (1.5). To get the required contraction factor T ν in our estimates, the next lemma is very useful (see [START_REF] Ginibre | On the Cauchy problem for the Zakharov system[END_REF]).

Lemma 3.1 Let f ∈ L 2 (R 2 ) with compact support (in time) in [-T, +T ].
For any θ > 0, there exists ν = ν(θ) > 0 such that

F -1 f (τ, ξ) τ -ξ 3 θ L 2 xt T ν f L 2 xt .
We will also need the following elementary calculus inequalities.

Lemma 3.2 (a) For b, b ′ ∈] 1 4 , 1 2 [ and α, β ∈ R, R dx x -α 2b x -β 2b ′ 1 α -β 2b+2b ′ -1 . (3.1) (b) For b, b ′ ∈] 1 4 , 1 2 [ and α, β ∈ R, |x|≤|β| dx x 2b+2b ′ -1 |α -x| β 2(1-b-b ′ ) α 1/2 . (3.2)
Proof of Theorem 1.1 : By duality, (1.5) is equivalent to

R 2 ∂ x (uv)w T ν w X 1/2-δ,-s α u X 1/2,s α v X 1/2,s α for all w ∈ X 1/2,s α
, and setting

f (τ, ξ) = i(τ -ξ 3 ) + |ξ| 2α 1/2 ξ s u(τ, ξ), g(τ, ξ) = i(τ -ξ 3 ) + |ξ| 2α 1/2 ξ s v(τ, ξ), h(τ, ξ) = i(τ -ξ 3 ) + |ξ| 2α 1/2-δ ξ -s w(τ, ξ),
it is equivalent to show that

I = R 4 K(τ, τ 1 , ξ, ξ 1 ) h(τ, ξ) f (τ 1 , ξ 1 ) g(τ -τ 1 , ξ-ξ 1 )dτ dτ 1 dξdξ 1 T ν f L 2 xt g L 2 xt h L 2 xt with K = |ξ| ξ s iσ + |ξ| 2α 1/2-δ ξ 1 -s iσ 1 + |ξ 1 | 2α 1/2 ξ -ξ 1 -s iσ 2 + |ξ -ξ 1 | 2α 1/2 .
By Fubini's theorem, we can always assume f , g, h ≥ 0. By symmetry, one can reduce the integration domain of

I to Ω = {(τ, τ 1 , ξ, ξ 1 ) ∈ R 4 , |σ 1 | ≥ |σ 2 |}. Split Ω into four regions, Ω 1 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω : |ξ 1 | ≤ 1, |ξ -ξ 1 | ≤ 1}, Ω 2 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω : |ξ 1 | ≤ 1, |ξ -ξ 1 | ≥ 1}, Ω 3 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω : |ξ 1 | ≥ 1, |ξ -ξ 1 | ≤ 1}, Ω 4 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω : |ξ 1 | ≥ 1, |ξ -ξ 1 | ≥ 1}.

Estimate in Ω 1

Using Cauchy-Schwarz inequality and Lemma 3.1, we easily obtain

I 1 sup τ,ξ |ξ| ξ s iσ + |ξ| 2α 1/2-δ/2 Ω 1 ξ 1 -2s ξ -ξ 1 -2s iσ 1 + |ξ 1 | 2α iσ 2 + |ξ -ξ 1 | 2α dτ 1 dξ 1 1/2 × T ν f L 2 xt g L 2 xt h L 2 xt (3.3) with Ω 1 = {(τ 1 , ξ 1 ) : ∃τ, ξ ∈ R, (τ, τ 1 , ξ, ξ 1 ) ∈ Ω 1 }.
In Ω 1 , one has |ξ| ≤ 2 ans thus if K 1 denotes the term between brackets in (3.3),

K 1 Ω 1 dτ 1 dξ 1 σ 1 σ 2 1/2 |ξ 1 |≤1 R dτ 1 σ 2 2 dξ 1 1/2 1. Estimate in Ω 2 We split Ω 2 into Ω 21 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω 2 : |σ| ≥ |σ 1 |}, Ω 22 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω 2 : |σ 1 | ≥ |σ|}.
Estimate in Ω 21 : Note that in this region, |ξ -ξ 1 | ∼ ξ -ξ 1 and ξ ξ -ξ 1 . Thus using (3.3) as well as (2.5), it follows that

K 21 ξ 1/2+s+δ/2 Ω 21 ξ -ξ 1 -2s-1+δ |ξ 1 | 1-δ σ 1 σ 2 ε ξ -ξ 1 2α(1-ε) dτ 1 dξ 1 1/2 |ξ 1 |≤1 ξ -ξ 1 -2α(1-ε)+2δ |ξ 1 | 1-δ R dτ 1 σ 1 σ 2 ε dξ 1 1/2 |ξ 1 |≤1 dξ 1 |ξ 1 | 1-δ 1/2 1.
Estimate in Ω 22 : By similar arguments, we estimate

K 22 |ξ| ξ s ξ α(1-δ) Ω 22 ξ -ξ 1 -2s |ξξ 1 (ξ -ξ 1 )| 1-ε σ 1 ε σ 2 dτ 1 dξ 1 1/2 ξ 1/2+s-α(1-δ)+ε/2 |ξ 1 |≤1 ξ -ξ 1 -2s-1+ε |ξ 1 | 1-ε dξ 1 1/2 ξ -α(1-δ)+ε 1.
Estimate in Ω 3 By symmetry, the desired bound in this region can be obtained in the same way.

Estimate in Ω 4 Divide Ω 4 into

Ω 41 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω 4 : |σ 1 | ≥ |σ|}, Ω 42 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω 4 : |σ| ≥ |σ 1 |}. Estimate in Ω 41 We write Ω 41 = Ω 411 ∪ Ω 412 ∪ Ω 413 with Ω 411 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω 41 : |ξ 1 | ≤ 100|ξ|}, Ω 412 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω 41 : |ξ 1 | ≥ 100|ξ|, 3|ξξ 1 (ξ -ξ 1 )| ≤ 1 2 |σ 1 |}, Ω 413 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω 41 : |ξ 1 | ≥ 100|ξ|, 3|ξξ 1 (ξ -ξ 1 )| ≥ 1 2 |σ 1 |}.
Estimate in Ω 411 : We have ξ 1 ξ and ξ -ξ 1 ξ thus with (2.5), we deduce for 0 < λ < 1,

K 411 ξ 1/2+s σ λ/2 ξ α(1-λ-2δ) ξ 1 -s-1/2 ξ -ξ 1 -s-1/2 σ 2 λ/2 ξ -ξ 1 α(1-λ) ξ [-s/2-1/4-α(1-λ-δ)] + σ λ/2 ξ -ξ 1 [-s/2-1/4-α(1-λ-δ)] + σ 2 λ/2 .
Consequently, using Plancherel's theorem and Hölder inequality,

I 411 R 2 F -1 ξ [-s/2-1/4-α(1-λ-δ)] + h σ λ/2 F -1 ( f )F -1 ξ [-s/2-1/4-α(1-λ-δ)] + g σ λ/2 dtdx F -1 ξ [-s/2-1/4-α(1-λ-δ)] + h σ λ/2 L 4 xt f L 2 xt F -1 ξ [-s/2-1/4-α(1-λ-δ)] + g σ λ/2 L 4 xt .
Now we choose λ = 3/4 + δ so that λ/2 > 3/8 and for s > -3/4 -α/2 and δ > 0 small enough,

- s 2 - 1 4 -α(1 -λ -δ) = 1 8 - 1 2 s + 3 4 + α 2 + 2αδ ≤ 1 8 .
Hence with help of Lemma 2.4,

I 411 T ν f L 2 xt g L 2 xt h L 2 xt .
Estimate in Ω 412 : Using the same arguments that for (3.3), we show that

I 412 sup τ 1 ,ξ 1 ξ 1 -s iσ 1 + |ξ 1 | 2α 1/2 Ω 412 |ξ| 2 ξ 2s ξ -ξ 1 -2s iσ + |ξ| 2α 1-δ iσ 2 + |ξ -ξ 1 | 2α dτ dξ 1/2 × T ν f L 2 xt g L 2 xt h L 2 xt (3.4)
with Ω 412 = {(τ, ξ) : ∃τ 1 , ξ 1 ∈ R, (τ, τ 1 , ξ, ξ 1 ) ∈ Ω 422 }. Moreover, we easily check that in Ω 412 ,

|σ 1 + 3ξξ 1 (ξ -ξ 1 )| ≥ 1 2 |σ 1 | and |ξ| ≤ |σ 1 |,
which combined with (3.1) and smoothing relation (2.5) yield

K 422 1 σ 1 1/2 Ω 412 ξξ 1 (ξ -ξ 1 ) -2s ξ 2+4s σ 1-δ σ 2 1-δ dτ dξ 1/2 σ 1 -s-1/2 Ω ′ 412 ξ 2+4s σ 1 + 3ξξ 1 (ξ -ξ 1 ) 1-2δ dξ 1/2 σ 1 -s-1+δ |ξ|≤|σ 1 | dξ ξ -4s-2 1/2 , (we have set Ω ′ 412 = {ξ : ∃τ, τ 1 , ξ 1 ∈ R, (τ, τ 1 , ξ, ξ 1 )
∈ Ω 412 }). Now from the assumptions (1.7) on s we see that

K 422 σ 1 -s-1+δ σ 1 2s+3/2 1 if α ≤ 1/2 and K 422 σ 1 -s-1+δ 1 otherwise.
Estimate in Ω 413 : In this domain,

|ξ 1 | ∼ |ξ -ξ 1 | thus using (3.4) it follows that K 413 ξ 1 -s-1/2+δ σ 1 δ Ω 413 ξ 2s+1+2δ ξ -ξ 1 -2s-1+2δ σ 1-δ σ 2 1-δ dτ dξ 1/2 ξ 1 -2s-1+2δ σ 1 δ Ω ′ 413 dξ σ 1 + 3ξξ 1 (ξ -ξ 1 ) 1-2δ 1/2 .
Following the works of Kenig, Ponce and Vega [START_REF] Kenig | A bilinear estimate with applications to the KdV equation[END_REF], we perform the change of

variables µ 1 = σ 1 + 3ξξ 1 (ξ -ξ 1 ). Thus, since dξ ∼ dµ 1 |ξ 1 | 1/2 |4τ 1 -ξ 3 1 -4µ 1 | and in view of (3.2), we bound K 413 by K 413 ξ 1 -2s-5/4+2δ σ 1 δ |µ 1 |≤2|σ 1 | dµ 1 µ 1 1-2δ |4τ 1 -ξ 3 1 -4µ 1 | 1/2 ξ 1 -2s-5/4+2δ σ 1 δ σ 1 δ 4τ 1 -ξ 3 1 1/4 ξ 1 -2s-5/4+2δ 4τ 1 -ξ 3 1 -1/4 .
Note that in Ω 413 , we have

|σ 1 | ≤ 12 100 |ξ 1 | 3 , which leads to 3|ξ 1 | 3 ≤ |4σ 1 + 3ξ 3 1 | + 4|σ 1 | ≤ |4τ 1 -ξ 3 1 | + 48 100 |ξ 1 | 3 and thus |ξ 1 | 3 |4τ 1 -ξ 3 1 |.
One deduce that for -2s -5/4 + 2δ > 0,

K 413 4τ 1 -ξ 3 1 1 3 (-2s-5/4+2δ)-1/4 4τ 1 -ξ 3 1 -2 3 (s+1)+2δ/3
1.

Estimate in Ω 42

We split this region in two components :

Ω 421 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω 42 : |ξ 1 | ≤ 100|ξ|}, Ω 422 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω 42 : |ξ 1 | ≥ 100|ξ|}.
Estimate in Ω 421 : In Ω 421 , ξ 1 ξ and ξ -ξ 1 ξ . Then, we bound I 421 exactly in the same way that for I 411 . After Plancherel and Hölder, we are lead to the estimate

I 421 h L 2 xt F -1 ξ [-s/2-1/4-α(1-λ)+3δ/2] + f σ λ/2 L 4 xt × F -1 ξ [-s/2-1/4-α(1-λ)+3δ/2] + g σ λ/2 L 4 xt .
It suffices to choose λ = 3/4 + ε to apply Lemma 2.4 with s > -3/4 -α/2.

Estimate in Ω 422 : We split Ω 422 into three sub-domains

Ω 4221 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω 422 : 3|ξξ 1 (ξ -ξ 1 )| ≤ 1 2 |σ|}, Ω 4222 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω 422 : 3|ξξ 1 (ξ -ξ 1 )| ≥ 1 2 |σ|, |σ 2 | ≤ 1}, Ω 4223 = {(τ, τ 1 , ξ, ξ 1 ) ∈ Ω 422 : 3|ξξ 1 (ξ -ξ 1 )| ≥ 1 2 |σ|, |σ 2 | ≥ 1}.
Estimate in Ω 4221 : In this region one has that

|σ + 3ξξ 1 (ξ -ξ 1 )| ≥ 1 2 |σ| and since σ 1 + σ 2 -σ = 3ξξ 1 (ξ -ξ 1 ) it follows that |σ 1 | ≤ |σ| ≤ 2|σ 1 + σ 2 | ≤ 4|σ 1 |
and |σ 1 | ∼ |σ| ≥ |ξξ 1 (ξ -ξ 1 |. Therefore using (3.4), one obtain

K 4221 ξ 1 -s σ 1 1/2 Ω 4221 |ξ| 2 ξ 2s ξ -ξ 1 -2s σ 1-δ σ 2 dτ dξ 1/2 1 σ 1 1-δ Ω 4221 ξξ 1 (ξ -ξ 1 ) -2s ξ 2+4s σ 2 1+δ dτ dξ 1/2 σ 1 -s-1+δ |ξ| |σ 1 | dξ ξ -4s-2 1/2 1 as for K 422 .
Estimate in Ω 4222 : First consider the case α ≤ 1/2. Then,

K 4222 |ξ| ξ s σ 1/2-δ/2 Ω 4222 ξ 1 -2s ξ -ξ 1 -2s σ 1 σ 2 dτ 1 dξ 1 1/2 |ξ| 1+s ξ s σ 1/2-δ/2 Ω 4222 ξξ 1 (ξ -ξ 1 ) -2s σ 1 1-δ σ 2 1-δ dτ 1 dξ 1 1/2 |ξ| 1+s ξ s σ -s-1/2+δ/2 Ω ′ 4222 dξ 1 σ + 3ξξ 1 (ξ -ξ 1 ) 1-2δ 1/2 .
The change of variables µ = σ + 3ξξ 1 (ξ -ξ 1 ) gives the inequalities

K 4222 |ξ| 3/4+s ξ s σ -s-1/2+δ/2 |µ|≤2|σ| dµ µ 1-2δ |4τ -ξ 3 -4µ| 1/2
|ξ| 3/4+s ξ s σ -s-1/2+3δ/2 4τ -ξ 3 -1/4 , which is bounded on R 2 . If α > 1/2, we have directly

K 4222 |ξ| ξ s σ 1/2-δ/2 Ω 4222 ξ 1 -4s ξ 1 2α ξ -ξ 1 2α σ 2 1+ε dτ 1 dξ 1 1/2 ξ 1/2+s+δ/2 R dξ 1 ξ 1 4s+2+4α+2δ 1/2 1 for s > -1/4 -α.
Estimate in Ω 4223 : As we will see below, that is in this sub-domain that the condition s > s α appears. Also, to obtain our estimates, we will need tu use a dyadic decomposition of the variables ξ 1 , ξ -ξ 1 , ξ and σ 1 , σ 2 , σ. Hence, following the notations introduced in Subsection 2.2, we have to bound

I 4223 = N 3 ≪N 1 ∼N 2 N 1 1 L 3 L 1 L 2 L 3 ∼N 3 N 2 1 N 3 N 3 s N -s 1 N -s 2 max(L 3 , N 2α 3 ) 1/2-2δ max(L 1 , N 2α 1 ) 1/2 max(L 2 , N 2α 2 ) 1/2 × R 4 h(τ, ξ) σ δ f (τ 1 , ξ 1 ) g(τ -τ 1 , ξ -ξ 1 )χ |ξ|∼N 3 ,|ξ 1 |∼N 1 ,|ξ-ξ 1 |∼N 2 χ |σ|∼L 3 ,|σ 1 |∼L 1 ,|σ 2 |∼L 2 dτ dτ 1 dξdξ 1 .
Using the (+-) coherence case of Lemma 2.5 as well as Lemma 3.1, we get

R 4 h(τ, ξ) σ δ f (τ 1 , ξ 1 ) g(τ -τ 1 , ξ -ξ 1 )χ |ξ|∼N 3 ,|ξ 1 |∼N 1 ,|ξ-ξ 1 |∼N 2 χ |σ|∼L 3 ,|σ 1 |∼L 1 ,|σ 2 |∼L 2 dτ dτ 1 dξdξ 1 L 1/2 2 N -1 1 min N 3 N 2 1 , N 1 N 3 L 1 1/2 F -1 h(τ, ξ) σ δ L 2 xt f L 2 xt g L 2 xt T ν L 1/2 2 N -1 1 min N 3 N 2 1 , N 1 N 3 L 1 1/2 h L 2 xt f L 2 xt g L 2 xt .
Thus we reduce to show

N 3 ≪N 1 ∼N 2 N 1 1 L 3 L 1 L 2 L 3 ∼N 3 N 2 1 N 3 N 3 s N -s 1 N -s 2 max(L 3 , N 2α 3 ) 1/2-2δ max(L 1 , N 2α 1 ) 1/2 max(L 2 , N 2α 2 ) 1/2 ×L 1/2 2 N -1 1 min N 3 N 2 1 , N 1 N 3 L 1 1/2
1.

(3.5)

Recalling that N j = 2 n j and L j = 2 ℓ j , j = 1, 2, 3, for all λ ∈ [0, 1], the right hand side of (3.5) is bounded by

N 3 ≪N 1 ∼N 2 N 1 1 L 3 L 1 L 2 L 3 ∼N 3 N 2 1 N 3 N 3 s N -2s-1 1 (N 3 N 2 1 ) λ/2 N 1 N 3 L 1 (1-λ)/2 L δ 3 (N 3 N 2 1 ) 1/2-3δ L (1-λ)/2 1 N αλ 1 N 3 ≪N 1 ∼N 2 N 1 1 L 1 ,L 2 ,L 3 1 1 (L 1 L 2 L 3 ) δ/3 N λ+3δ 3 N 3 s N -2s-3/2+λ(1/2-α)+6δ 1
N 1 1 N 3 ≪N 1 N λ+3δ 3 N 3 s N -2s-3/2+λ(1/2-α)+6δ 1
.

This last expression is finite if λ+3δ < -s and -2s-3/2+λ(1/2-α)+6δ < 0. When α ≤ 1/2, it suffices to choose λ = 0 and λ = -s -4δ otherwise.

Proof of the main result

In this section, we briefly indicate how the results stated in Section 2.1 and the bilinear estimate (1.5) yield Theorem 1.3 (see for instance [START_REF] Molinet | On the low regularity of the Korteweg-de Vries-Burgers equation[END_REF] for the details). Actually, local existence of a solution is a consequence of the following modified version of Theorem 1.1. Proposition 4.1 Given s + c > s α , there exist ν, δ > 0 such that for any s ≥ s + c and any u, v ∈ X

1/2,s α with compact support in [-T, +T ], ∂ x (uv) X -1/2+δ,s α T ν ( u X 1/2,s + c α v X 1/2,s α + u X 1/2,s α v X 1/2,s + c α
). (4.1) Estimate (4.1) is obtained thanks to (1.5) and the triangle inequality

∀s ≥ s + c , ξ s ≤ ξ s + c ξ 1 s-s + c + ξ s + c ξ -ξ 1 s-s + c .
Let u 0 ∈ H s (R) with s obeying (1.7). Define F (u) as

F (u) = F u 0 (u) = ψ(t) W α (t)u 0 - χ R + (t) 2 t 0 W α (t -t ′ )∂ x (ψ 2 T (t ′ )u 2 (t ′ ))dt ′ .
We shall prove that for T ≪ 1, F is contraction in a ball of the Banach space

Z = {u ∈ X 1/2,s α , u Z = u X 1/2,s + c α + γ u X 1/2,s α < +∞},
where γ is defined for all nontrivial ϕ by

γ = ϕ H s + c ϕ H s .
Combining (2.1), (2.2) as well as (4.1), it is easy to derive that

F (u) Z ≤ C( u 0 H s + c + γ u 0 H s ) + CT ν u 2 Z and F (u) -F (v) Z ≤ CT ν u -v Z u + v Z
for some C, ν > 0. Thus, taking T = T ( u 0 H s + c ) small enough, we deduce that F is contractive on the ball of radius 4C u 0 H s + c in Z. This proves the existence of a solution u to u = F (u) in X 1/2,s α,T . Following similar arguments of [START_REF] Molinet | On the low regularity of the Korteweg-de Vries-Burgers equation[END_REF], it is not too difficult to see that if u 1 , u 2 ∈ X 1/2,s α,T are solutions of (1.6) and 0 < δ < T /2, then there exists ν > 0 such that

u 1 -u 2 X 1/2,s α,δ T ν u 1 X 1/2,s α,T + u 2 X 1/2,s α,T u 1 -u 2 X 1/2,s α,δ
, which leads to u 1 ≡ u 2 on [0, δ], and then on [0, T ] by iteration. This proves the uniqueness of the solution.

It is straightforward to check that

W α (•)u 0 ∈ C(R + , H s (R))∩C(R * + , H ∞ (R)
). Then it follows from Theorem 1.1, Lemma 2.3 and the local existence of the solution that

u ∈ C([0, T ], H s (R)) ∩ C((0, T ], H ∞ (R))
for some T = T ( u 0 H s + c ). By induction, we have u ∈ C((0, T ], H ∞ (R)). Taking the L 2 -scalar product of (1.1) with u, we obtain that t → u(t) H s + c is nonincreasing on (0, T ]. Since the existence time of the solution depends only on the norm u 0 H s + c , this implies that the solution can be extended globally in time. K(τ, τ 1 , ξ, ξ 1 ) h(τ, ξ) f (τ 1 , ξ 1 ) g(τ -τ 1 , ξ-ξ 1 )dτ dτ 1 dξdξ 1 is infinite. Setting

A = {f ∈ S(R 2 ) : f ≥ 0, f L 2 xt 1},
and performing as previously a dyadic decomposition of the variables ξ 1 , ξ -ξ 1 , ξ and σ 1 , σ 2 , σ, it follows that M sup f,g,h∈A N 1 ,N 2 ,N 3 L 1 ,L 2 ,L 3

N 3 N 3 s N 1 -s N 2 -s max(L 3 , N 2α
3 ) 1/2-δ max(L 1 , N Now we localize the previous supremum to the critical region

N 3 ≪ N 1 ∼ N 2 N 3 N 2 1 ∼ L 3 L 1 L 2 1
which corresponds to a sub-domain of Ω 4223 . In this case, the optimality of (2.8) gives sup

f,g,h∈A R 4 h(τ, ξ) f (τ 1 , ξ 1 ) g(τ -τ 1 , ξ -ξ 1 )χ |ξ|∼N 3 ,|ξ 1 |∼N 1 ,|ξ-ξ 1 |∼N 2 χ |σ|∼L 3 ,|σ 1 |∼L 1 ,|σ 2 |∼L 2 L 1/2 2 N -1 1 min N 3 N 2 1 , N 1 N 3 L 1 1/2 .
Therefore we have the bound

M sup 1 N 3 ≪N 1 ∼N 2 sup 1 L 2 L 1 L 3 L 3 ∼N 3 N 2 1 N 1+s 3 N -2s 1 L 1/2 2 N -1 1 min N 3 N 2 1 , N 1 N 3 L 1 1/2 max(N 3 N 2 1 , N 2α
3 ) 1/2-δ max(L 1 , N 2α 1 ) 1/2 max(L 2 , N 2α 2 ) 1/2 .

First consider the case 0 ≤ α ≤ 1/2. Then,

M sup N 1 ≫1 N 3 ∼1 sup L 1 ∼L 2 ∼N 2 3 N 1 N -2s-1 1 L 1/2 2 N 1 N 3 L 1 1/2 N 1-2δ 1 L 1/2 1 L 1/2 2

5 2 xt

 2 Proof of Theorem 1.2 Let s ≥ s α . To prove Theorem 1.2, it suffices to show that the multiplierM = sup f,g,h∈S(R 2 ) f L

4 .

 4 Now if 1/2 < α ≤ 1, we estimate -5/4 -α/2 + (α -1/2)(s + 1/2) ≥ 0, i.e. s ≤ -3 5 -2α.

  (τ 1 , ξ 1 ) g(τ -τ 1 , ξ -ξ 1 )χ |ξ|∼N 3 ,|ξ 1 |∼N 1 ,|ξ-ξ 1 |∼N 2 χ |σ|∼L 3 ,|σ 1 |∼L 1 ,|σ 2 |∼L 2 sup N 1 ,N 2 ,N 3 sup L 1 ,L 2 ,L 3 (τ, ξ) f (τ 1 , ξ 1 ) g(τ -τ 1 , ξ -ξ 1 )χ |ξ|∼N 3 ,|ξ 1 |∼N 1 ,|ξ-ξ 1 |∼N 2 χ |σ|∼L 3 ,|σ 1 |∼L 1 ,|σ 2 |∼L 2 .

						2α 1 ) 1/2 max(L 2 , N 2α 2 ) 1/2
	×	R 4	h(τ, ξ) f N 3 N 3	s N 1	-s N 2	-s
			max(L 3 , N 2α 3 ) 1/2-δ max(L 1 , N 2α 1 ) 1/2 max(L 2 , N 2α 2 ) 1/2
	× sup
		f,g,h∈A R 4

h


Gilles Barthe
email: gjbarthe@gmail.com

Thomas Espitau
email: t.espitau@gmail.com

Justin Hsu

Tetsuya Sato
email: satoutet@kurims.kyoto-u.ac.jp

Pierre-Yves Strub
email: pierre-yves@strub.nu

-Liftings for Differential Privacy

Keywords: 1998 ACM Subject Classification D.2.4 Software/Program Verification Keywords and phrases Differential Privacy, Probabilistic Couplings, Formal Verification Digital Object Identifier 10.4230/LIPIcs.ICALP.2017

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Differential privacy [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF] is a rigorous notion of statistical privacy that delivers strong individual guarantees for privacy-preserving computations. Informally, differential privacy guarantees to every individual that their (non)-participation in a database will have a small (in a rigorous, quantitative sense) effect on the results obtained by third parties when querying the database. The formal definition of differential privacy is parametrized by two non-negative real numbers, ( , δ). These parameters quantify the effect of individuals on the output of the private query; smaller values give stronger privacy guarantees. The main strengths of differential privacy lie in its theoretical elegance, minimal assumptions, and flexibility for many applications.

Motivated by the importance of differential privacy, programming language researchers have developed approaches based on dynamic analysis, type systems, and program logics for formally proving differential privacy for programs. (We refer the interested reader to a recent

Outline of the paper

After reviewing the necessary mathematical preliminaries in Section 2, we introduce our main technical contribution: a new, existential definition of approximate lifting. This construction, which we call -lifting, is a generalization of an existing definition by Barthe and Olmedo [START_REF] Barthe | Beyond differential privacy: Composition theorems and relational logic for f -divergences between probabilistic programs[END_REF], Olmedo [START_REF] Olmedo | Approximate Relational Reasoning for Probabilistic Programs[END_REF]. The key idea is to allow the witness distributions to have a larger domain, broadening the class of approximate liftings. By a maximum flow/minimum cut argument, we show that -liftings are equivalent to Sato's lifting over discrete distributions. This equivalence can be viewed as an approximate version of Strassen's theorem [START_REF] Strassen | The existence of probability measures with given marginals[END_REF], a classical result in probability theory describing the existence of probabilistic couplings. We present the definition of -lifting and the proof of equivalence in Section 3.

Then, we show that -liftings satisfy desirable theoretical properties. We are able to leverage the equivalence of liftings in two ways. In one direction, Sato's definition gives simpler proofs of more general properties of -liftings. In the other direction, -liftings-like other existential definitions-can smoothly incorporate composition principles from the theory of differential privacy. Our connection shows that Sato's definition can use these principles in the discrete case. We describe the key theoretical properties of -liftings in Section 4.

Finally, we provide a thorough comparison of -lifting with existing definitions of approximate lifting in Section 5, and describe how to construct -liftings for more general version of approximate liftings based on f -divergences in Section 6.

Overall, the equivalence of -liftings and Sato's lifting, along with the natural theoretical properties satisfied by the common notion, suggest that these definitions are two views on the same concept: an approximate version of probabilistic coupling.

Background

To model probabilistic behavior, we work with discrete sub-distributions.

Definition 1. A sub-distribution over a set A is defined by its mass function µ : A → R + , which gives the probability of the singleton events a ∈ A. This mass function must be s.t. |µ| = a∈A µ(a) is well-defined and at most 1. In particular, the support supp(µ) = {a ∈ A | µ(a) = 0} must be discrete (i.e. finite or countably infinite). When the weight |µ| is equal to 1, we call µ a (proper) distribution. We let D(A) denote the set of sub-distributions over A. The probability of an event E(x) w.r.t. µ, written P x∼µ [E(x)] or P µ [E], is defined as x∈A|E(x) µ(x).

Simple examples of sub-distributions include the null sub-distribution 0 A ∈ D(A), which maps each element of A to 0, and the Dirac distribution centered on x, written 1 x , which maps x to 1 and all other elements to 0. One can equip distributions with a monadic structure using the Dirac distributions 1 x for the unit and distribution expectation E x∼µ [f (x)] for the bind; if µ is a distribution over A and f has type A → D(B), then the bind defines a sub-distribution over B:

E a∼µ [f (a)] : b → a µ(a) • f (a)(b). If f : A → B, we can lift f to a function f : D(A) → D(B) as follows: f (µ) = E a∼µ [1 f (a) ] -or, equivalently, f (µ) : b → P a∼µ [a ∈ f -1 (b)].
For instance, when working with subdistributions over pairs, this allows to obtain the probabilistic versions π 1 and π 2 (called marginals) of the usual projections π 1 and π 2 . One can check that the first and second marginals π 1 (µ) and π 2 (µ) of a distribution µ over A × B are also given by the following equations:

π 1 (µ)(a) = b∈B µ(a, b) and π 2 (µ)(b) = a∈A µ(a, b). When f : A → D(B)
, we will abuse notation and write the lifting f :

D(A) → D(B) to mean f (µ) = E x∼µ [f (x)]. Finally, if α : A → R + , we write α[X] ∈ R + ∪ {∞} for x∈X α(x). Moreover, if α : A × B → R + , we write α[X, Y ] (resp. α[x, Y ], α[X, y]) for α[X × Y ] (resp. α[{x} × Y , α[X × {y}]). Note that for a sub-distribution µ ∈ D(A) and an event E ⊆ A, P µ [E] = µ[E].
We now review the definition of differential privacy.

Definition 2 (Dwork et al. [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF]). A probabilistic computation M : A → D(B) satisfies ( , δ)-differential privacy w.r.t. an adjacency relation φ ⊆ A × A iff for every pair of inputs a, a ∈ A such that a φ a and every subset of outputs E ⊆ B,

P M (a) [E] ≤ e • P M (a ) [E] + δ.
It is useful to define a notion of distance on distributions, reflecting differential privacy. [START_REF] Barthe | Beyond differential privacy: Composition theorems and relational logic for f -divergences between probabilistic programs[END_REF], Barthe et al. [START_REF] Barthe | Probabilistic relational reasoning for differential privacy[END_REF], Olmedo [START_REF] Olmedo | Approximate Relational Reasoning for Probabilistic Programs[END_REF]).

Definition 3 (Barthe and Olmedo

Let ≥ 0. The -DP divergence ∆ (µ 1 , µ 2 ) between two sub-distributions µ 1 , µ 2 ∈ D(B) is defined as sup E⊆B (P µ1 [E] -e • P µ2 [E]) .
Then, differential privacy admits an alternative characterization based on DP divergence.

Lemma 4. A probabilistic computation

M : A → D(B) satisfies ( , δ)-differential privacy w.r.t. an adjacency relation φ ⊆ A × A iff ∆ (M (a), M (a )) ≤ δ for every pair of inputs a, a ∈ A such that a φ a .
Our new definition of approximate lifting is inspired by a version of approximate liftings involving two witness distributions, proposed by Barthe and Olmedo [START_REF] Barthe | Beyond differential privacy: Composition theorems and relational logic for f -divergences between probabilistic programs[END_REF], Olmedo [START_REF] Olmedo | Approximate Relational Reasoning for Probabilistic Programs[END_REF].

I C A L P 2 0 1 7

XX:4 -Liftings for Differential Privacy Definition 5 (Barthe and Olmedo [START_REF] Barthe | Beyond differential privacy: Composition theorems and relational logic for f -divergences between probabilistic programs[END_REF], Olmedo [START_REF] Olmedo | Approximate Relational Reasoning for Probabilistic Programs[END_REF]). Let µ 1 ∈ D(A) and µ 2 ∈ D(B) be sub-distributions, , δ ∈ R + and R be a binary relation over

A & B. An ( , δ)-approximate 2-lifting of µ 1 & µ 2 for R is a pair (µ , µ ) of sub-distributions over A × B s.t. 1. π 1 (µ ) = µ 1 and π 2 (µ ) = µ 2 ; 2. ∆ (µ , µ ) ≤ δ; and 3. supp(µ) ⊆R. We write µ 1 R (2)
,δ µ 2 if there exists an ( , δ)-approximate (2-)lifting of µ 1 & µ 2 for R; the [START_REF] Barthe | Beyond differential privacy: Composition theorems and relational logic for f -divergences between probabilistic programs[END_REF] indicates that there are two witnesses in this definition of lifting.

Combined with Lemma 4, a probabilistic computation M : A → D(B) is ( , δ)-differentially private if and only if for every two adjacent inputs a φ a , there is an approximate lifting of the equality relation:

M (a) = (2)
,δ M (a ). 2-liftings can be generalized by varying the notion of distance given by ∆ ; we will return to this point in Section 6. These liftings also satisfy useful theoretical properties, but some of the properties are not as general as we would like. For example, it is known that 2-liftings satisfy the following mapping property.

Theorem 6 (Barthe et al. [4]). Let µ 1 ∈ D(A 1 ), µ 2 ∈ D(A 2 ), f 1 : A 1 → B 1 , f 2 : A 2 → B 2 surjective maps and R a binary relation on B 1 & B 2 . Then f 1 (µ 1 ) R (2) ,δ f 2 (µ 2 ) ⇐⇒ µ 1 S (2) ,δ µ 2 where a 1 S a 2 ⇐⇒ f 1 (a 1 ) R f 2 (a 2 ).
This property can be used to pull back an approximate lifting on two distributions over B 1 , B 2 to an approximate lifting on two distributions over A 1 , A 2 . For applications in program logics, B 1 , B 2 could be the domain of a program variable, A 1 , A 2 could be the set of memories, and f 1 , f 2 could project a memory to a program variable. While the mapping theorem is quite useful, it is puzzling why it only applies to surjective maps. For instance, this theorem cannot be used when the maps f 1 , f 2 embed a smaller space into a larger space.

For another example, there exist 2-liftings of the following form, sometimes called the optimal subset coupling.

Theorem 7 (Barthe et al. [START_REF] Barthe | Advanced probabilistic couplings for differential privacy[END_REF]). Let µ ∈ D(A) and consider two subsets P 1 ⊆ P 2 ⊆ A. Suppose that P 2 is a strict subset of A. Then, we have the following equivalence:

P µ [P 2 ] ≤ e • P µ [P 1 ] ⇐⇒ µ R (2) ,0 µ, where a 1 R a 2 ⇐⇒ a 1 ∈ P 1 ⇐⇒ a 2 ∈ P 2 .
In this construction, it is puzzling why the larger subset P 2 must be a strict subset of the domain A. For example, this theorem does not apply for P 2 = A, but we may be able to construct the approximate lifting if we simply embed A into a larger space B-even though µ has support over A! Furthermore, it is not clear why the subsets must be nested, nor is it clear why we can only relate µ to itself.

These shortcomings suggest that the definition of 2-liftings may be problematic. While the distance condition appears to be the most constraining requirement, the marginal and support conditions are responsible for the main issues.

XX:5

Witnesses can only use pairs in the relation.

For some relations R, there may be elements a such that a R b does not hold for any b, or vice versa. It can be impossible find witnesses with the correct marginals on these elements, even if the distance condition can be easily satisfied. For instance, we can sometimes construct a pair µ and µ satisfying the distance requirement, but where µ needs additional mass to achieve the marginal requirement for an element b. Adding this mass anywhere preserves the distance bound, but there may not be an element a such that a R b.

No canonical choice of witnesses.

A related problem is that the marginal requirement only constrains one marginal of each witness distribution. Along the other component, the witnesses may place the mass anywhere on any pair in the relation. As a result, witnesses to an approximate lifting

µ 1 R (2)
,δ µ 2 may have mass outside of supp(µ 1 ) × supp(µ 2 ), even though it seems that only elements in the support should be relevant to the lifting.

-Liftings and Strassen's Theorem

To improve the theoretical properties of 2-liftings, we propose a simple extension: allow witnesses to be distributions over a larger set.

Notation 8. Let A be a set. We write A for A { }.

Definition 9 ( -lifting). Let µ 1 ∈ D(A) and µ 2 ∈ D(B) be sub-distributions, , δ ∈ R + and R be a binary relation over

A & B. An ( , δ)-approximate -lifting of µ 1 & µ 2 for R is a pair of sub-distributions η ∈ D(A × B ) and η ∈ D(A × B) s.t.
1. π 1 (η ) = µ 1 and π 2 (η ) = µ 2 ; 2. supp(η |A×B ), supp(η |A×B ) ⊆ R; and 3. ∆ (η , η ) ≤ δ, where η • is the canonical lifting of η • to A × B .

We write µ 1 R ( ) ,δ µ 2 if there exists an ( , δ)-approximate lifting of µ 1 & µ 2 for R.

By adding an element , we address both problems discussed at the end of the previous section. First, for every a ∈ A, witnesses may place mass at (a, ); for every b ∈ B, witnesses may place mass at ( , b). Second, can serve as a generic element where all mass that lies outside the supports supp(µ 1 ) × supp(µ 2 ) may be placed, while preserving the marginal and distance requirements, giving more control over the form of the witnesses.

Lemma 10. Let µ 1 ∈ D(A) and µ 2 ∈ D(B) be distributions such that µ 1 R ( )
,δ µ 2 . Then, there are witnesses with support contained in supp(µ 1 ) × supp(µ 2 ) .

Proof. See Appendix, p. 14

Basic Properties

-liftings satisfy all basic properties satisfied by other notions of lifting. We start by proving that this new definition of lifting still characterizes differential privacy.

Lemma 11. A randomized algorithm

P : A → D(B) is ( , δ)-differentially private for φ iff for all a 1 , a 2 ∈ A, a 1 φ a 2 implies P (a 1 ) = ( ) ,δ P (a 2 ).
Proof. See Appendix, p. 14

I C A L P 2 0 1 7

XX:6 -Liftings for Differential Privacy

The next lemma establishes several other basic properties of -liftings: monotonicity, and closure under relational and sequential composition.

Lemma 12.

Let µ 1 ∈ D(A), µ 2 ∈ D(B), and R be a binary relation over

A & B. If µ 1 R ( ) ,δ µ 2 , then for any ≥ , δ ≥ δ and S ⊇ R, we have µ 1 S ( ) ,δ µ 2 . Let µ 1 ∈ D(A), µ 2 ∈ D(B), µ 2 ∈ D(C) and R (resp. S) be a binary relation over A & B (resp. over B & C). If µ 1 R ( ) ,δ µ 2 and µ 2 S ( ) ,δ µ 3 , then µ 1 (S • R) ( ) + ,δ+e •δ µ 3 . For i ∈ {1, 2}, let µ i ∈ D(A i ) and η i : A i → D(B i ). Let R (resp. S) be a binary relation over A 1 & A 2 (resp. over B 1 & B 2 ). If µ 1 R ( )
,δ µ 2 for some , δ ≥ 0 and for any

(a 1 , a 2 ) ∈R, η 1 (a 1 ) S ( ) ,δ η 2 (a 2 ) for some , δ ≥ 0, then E µ1 [η 1 ] S ( ) + ,δ+δ E µ2 [η 2 ].
Proof. See Appendix, p. 14

Equivalence with Sato's Definition

In recent work on verifying differential privacy over general, continuous distributions, Sato [START_REF] Sato | Approximate relational Hoare logic for continuous random samplings[END_REF] proposes an alternative definition of approximate lifting. In the special case of discrete distributions, where measurability of events can be forgotten, his definition can be stated as follows.

Definition 13 (Sato [11]). Let µ 1 ∈ D(A) and µ 2 ∈ D(B), R be a binary relation over

A & B and , δ ≥ 0. Then, there is an ( , δ)-approximate lifting of µ 1 & µ 2 for R if ∀X ⊆ A. µ 1 [X] ≤ e • µ 2 [R(X)] + δ.
Notice that this definition has no witness distributions at all; instead, it uses a universal quantifier over all subsets. We can show that -liftings are equivalent to Sato's definition in the case of discrete distributions. This equivalence is reminiscent of Strassen's theorem from probability theory, which characterizes the existence of probabilistic couplings.

Theorem 14 (Strassen [12]). Let µ 1 ∈ D(A), µ 2 ∈ D(B) be two proper distributions, and R let be a binary relation over

A & B. Then there exists a joint distribution µ ∈ D(A × B) with support in R such that π 1 (µ) = µ 1 and π 2 (µ) = µ 2 if and only if ∀X ⊆ A. µ 1 [X] ≤ µ 2 [R(X)].
Our result (Theorem 19) can be viewed as a generalization of Strassen's theorem to approximate couplings. The key ingredient in our proof is the max-flow min-cut theorem for countable networks; we begin by reviewing the basic setting.

Definition 15 (Flow network). A flow network is a structure ((V, E), , ⊥, c) s.t. N = (V, E)
is a loop-free directed graph without infinite simple path (or rays), and ⊥ are two distinct distinguished vertices of N s.t. no edge starts from ⊥ and ends at , and c : E → R + ∪{+∞} is a function assigning to each edge of N a capacity. The capacity c is extended to V 2 by assigning capacity 0 to any pair (u, v)

s.t. (u, v) / ∈ E. Definition 16 (Flow). Given a flow network N = ((V, E), , ⊥, c), a function f : V 2 → R is a flow for N iff 1. ∀u, v ∈ V. f (u, v) ≤ c(u, v), 2. ∀u, v ∈ V. f (u, v) = -f (v, u), and a 1 a 2 a n ⊥ b ⊥ 1 b ⊥ 2 b ⊥ n ⊥ ai R bj ⇓ ∞ ∞ e -• µ1(ai) ω -e -|µ1| µ2(bj) e -δ Figure 1 Flow Network in Theorem 19 3. ∀u ∈ V. u / ∈ { , ⊥} =⇒ v∈V f (u, v) = 0 (Kirchhoff's Law).
The

mass |f | of a flow f is defined as |f | = v∈V f ( , v) ∈ R{∪ + ∞}. Definition 17 (Cut). Given a flow network N = ((V, E), , ⊥, c), a cut for N is any set C ⊆ V that partition V s.t. ∈ V but ⊥ / ∈ V . The cut-set E(C) of a cut C is defined as: {(u, v) ∈ E | u ∈ S, v / ∈ S}. The capacity |C| ∈ R + ∪ {∞} of a cut is defined as |C| = (u,v)∈E(C) c(u, v).
For flow networks with finitely many vertices an edges, the maximum flow is equal to the minimum cut. Aharoni et al. [START_REF] Aharoni | The max-flow min-cut theorem for countable networks[END_REF] consider when this is the case for a countable network. For the flow networks that we consider in this paper-where there are no infinite directed paths-equality holds.

Theorem 18 (Weak Countable Max-Flow Min-Cut). Let N be a network flow. Then,

sup{|f | | f is a flow for N } = inf{|C| | C is a cut for N }
and both the supremum and infimum are reached.

We are now ready to prove an approximate version of Strassen's theorem, thereby showing equivalence between -liftings and Sato's liftings.

Theorem 19. Let µ 1 ∈ D(A) and µ 2 ∈ D(B), R be a binary relation over A & B and , δ ∈ R + . Then, µ 1 R ( ) ,δ µ 2 iff ∀X ⊆ A. µ 1 (X) ≤ e • µ 2 (R(X)) + δ.
Proof. We only detail the reverse direction. We can assume that A and B are countable; in the case where A and B are not both countable, we first consider the restriction of µ 1 and µ 2 to their respective supports-which are countable sets-and construct witnesses to the -lifting. The witnesses can then be extended to a coupling of µ 1 and µ 2 by adding a null mass to the extra points.

Let ω = |µ 2 | + e -• δ and let and ⊥ be fresh symbols. For any set X, define X and X ⊥ resp. as {x | x ∈ X} and {x ⊥ | x ∈ X}. Let N be the flow network of Figure 1 whose resp. source and sink are and ⊥, whose set of vertices V is { , ⊥} (A ) (B ) ⊥ , and whose set of edges

E is E E ⊥ E R E with E = { → µ1(a) a | a ∈ A} E ⊥ = {b ⊥ → e -µ2(b) ⊥ | b ∈ B} E R = {a → ∞ b ⊥ | a R b ∨ a = ∨ b = } E = { → (ω-e -|µ1|) , ⊥ → e -δ ⊥}.
Let C be a cut of N -in the following, we use C independently for the cut C and its cut-set

E(C). We check |C| ≥ ω. If C ∩ E R = ∅ then |C| = ∞. Note that C ∩ E = ∅ implies I C A L P
= ∅ and E ⊆ C), for C to be a cut, we must have R(A -A † ) ⊆ B † where A † = {x ∈ A | ( , x ) ∈ C} and B † = {y ∈ B | (y ⊥ , ⊥) ∈ C}. Thus, |C| = e -• µ 1 [A † ] + µ 2 [B † ] + |E | ≥ e -• µ 1 [A † ] + µ 2 [R(A -A † )] + e -• δ + (ω -e -• |µ 1 |) ≥ e -• (µ 1 [A † ] + µ 1 [A -A † ]) + ω -e -• |µ 1 | = ω.
Hence, E {( ⊥ , ⊥)} is a minimum cut with capacity ω. By Theorem 18, we obtain a maximum flow f with mass ω. Note that the flow f saturates the capacity of all edges in E , E ⊥ , and

E . Let f : (a, b) ∈ A × B → f (a , b ⊥
). We now define the following distributions:

η : A × B → R + (a, b) → e • f (a, b) η : A × B → R + (a, b) → f (a, b). We clearly have π 1 (η ) = µ 1 and π 2 (η ) = µ 2 . Moreover, by construction of the flow network N , supp( f|A×B ) ⊆ R. Hence, supp(η |A×B ), supp(η |A×B ) ⊆ R. It remains to show that ∆ (η , η ) ≤ δ. Let X be a subset of A × B . Let X a = {a ∈ A | (a, ) ∈ X}, X b = {b ∈ B | ( , b) ∈ X} and X = X ∩ (A × B). Then, η [X] -e • η [X] = e f [X] + f [X a × { }] -e f [X] + f [{ } × X b ] ≤ e • f [X a × { }] ≤ e • f [A × { }] = δ.
The last equality holds by Kirchhoff's law:

f [A × { }] = a∈A f (a , ⊥ ) = f ( ⊥ , ⊥) = e -• δ.

Properties of -Liftings

Our main theorem can be used to show a variety of natural properties of -liftings. To begin, we can generalize the mapping property from Theorem 6, lifting the requirement that the maps must be surjective.

Lemma 20. Let µ 1 ∈ D(A 1 ), µ 2 ∈ D(A 2 ), f 1 : A 1 → B 1 , f 2 : A 2 → B 2 and R a binary relation on B 1 & B 2 . Let S such that a 1 S a 2 ⇐⇒ f 1 (a 1 ) R f 2 (a 2 ). Then f 1 (µ 1 ) R ( ) ,δ f 2 (µ 2 ) ⇐⇒ µ 1 S ( ) ,δ µ 2 .
Proof. See Appendix, p. 15 Similarly, we can generalize the existing rules for up-to-bad reasoning (cf. Barthe et al. [START_REF] Barthe | Advanced probabilistic couplings for differential privacy[END_REF]Theorem 13]), which restrict the post-condition to be equality. There are two versions: the conditional event is either on the left side, or the right side. Note that the resulting index δ are different in the two cases.

Lemma 21. Let µ 1 ∈ D(A), µ 2 ∈ D(B), θ ⊆ A and R ⊆ A × B. Assume that µ 1 (θ =⇒ R) ( ) ,δ µ 2 for some parameters , δ ≥ 0. Then, µ 1 R ( ) ,δ µ 2 , where δ = δ + µ 1 [θ].
Proof. See Appendix, p. 15

Lemma 22. Let µ 1 ∈ D(A), µ 2 ∈ D(B), θ ⊆ B and R ⊆ A × B. Assume that µ 1 (θ =⇒ R) ( ) ,δ µ 2 for some parameters , δ ≥ 0. Then, µ 1 R ( ) ,δ µ 2 , where δ = δ + e • µ 2 [θ].
Proof. See Appendix, p. 16

As a consequence, an approximately lifted relation can be conjuncted with a one-sided predicate if the δ parameter is increased. This principle is useful for constructing approximate liftings that express accuracy bounds: when θ a, is an event that happens with high probability, we can assume that θ a, holds if we increase the δ parameter of the approximate lifting.

Lemma 23. Let µ 1 ∈ D(A), µ 2 ∈ D(B), θ a ⊆ A, θ b ⊆ B and R ⊆ A × B. Assume that µ 1 R ( ) ,δ µ 2 . Then, µ 1 (θ a, ∧ R) ( ) ,δa µ 2 and µ 1 (θ b, ∧ R) ( ) ,δ b µ 2 where δ a = δ + µ 1 [θ a ] and δ b = δ + e • µ 2 [θ b ].
Proof. See Appendix, p. 16 -liftings also support a significant generalization of optimal subset coupling. Unlike the known construction for 2-liftings (Theorem 7), the two subsets need not be nested, and either subset may be the entire domain. Furthermore, the distributions µ 1 , µ 2 need not be the same, or even have the same domain. Finally, the equivalence is valid for any parameters ( , δ), not just δ = 0.

Theorem 24. Let µ 1 ∈ D(A 1 ), µ 2 ∈ D(A 2 ) and consider two subsets P 1 ⊆ A 1 , P 2 ⊆ A 2 .
Then, we have the following equivalence:

P µ1 [P 1 ] ≤ e • P µ2 [P 2 ] + δ ∧ P µ1 [A 1 -P 1 ] ≤ e • P µ2 [A 2 -P 2 ] + δ ⇐⇒ µ 1 R ( ) ,δ µ 2 ,
where a 1 R a 2 ⇐⇒ a 1 ∈ P 1 ⇐⇒ a 2 ∈ P 2 .

Proof. Immediate by Theorem 19.

We can then recover the existing notion of optimal subset coupling [START_REF] Barthe | Advanced probabilistic couplings for differential privacy[END_REF] for -liftings, as a special case of the previous theorem.

Corollary 25 (Barthe et al. [START_REF] Barthe | Advanced probabilistic couplings for differential privacy[END_REF]). Let µ ∈ D(A) and consider two nested subsets P 2 ⊆ P 1 A. Then, we have the following equivalence:

P µ [P 1 ] ≤ e • P µ [P 2 ] ⇐⇒ µ 1 R ( ) ,0 µ 2 , where a 1 R a 2 ⇐⇒ a 1 ∈ P 1 ⇐⇒ a 2 ∈ P 2 .
Proof. Immediate by Theorem 24, noting that

P µ [A -P 1 ] ≤ e • P µ [A -P 2 ] is automatic since P 2 ⊆ P 1 implies P µ [A -P 1 ] ≤ P µ [A -P 2 ].
Finally, we can directly extend known composition theorems from differential privacy to -liftings. This connection is quite useful for lifting existing results from the privacy literature-which can be quite sophisticated-to approximate liftings.

f i (-, a) : D → D(A) is ( i , δ i )-differentially
private for some parameters i , δ i ≥ 0 and fixed adjacency relation φ, then, for any a ∈ A, F (-, a) is ( * , δ * )-differentially private for φ, where

F : (d, a) → ( i<n (f i (d, -)) )(1 a ) is the the n-fold composition of the [f i ] i<n and ( * , δ * ) = r([( i , δ i )] i<n ).
Let n ∈ N and assume given two families of sets {A i } i≤n and {B i } i≤n , together with a family of binary relations {R(i) ⊆ A i × B i } i≤n . Fix two families of functions {g i : A i → D(A i+1 )} i<n and {h i : B i → D(B i+1 )} i<n s.t. for any i < n and (a, b) ∈ R(i) we have:

1. g i (a) R(i + 1) ( ) i,δi h i (b)
for some parameters i , δ i ≥ 0, and 2. g i (a) and h i (b) are proper distributions.

Then, for (a 0 , b 0 ) ∈ R 0 , there exists a -lifting

G(a 0 ) R(n) ( ) * ,δ * H(b 0 ) where ( * , δ * ) = r([( i , δ i )] i<n ), and G : A 0 → D(A n ) and H : B 0 → D(B n ) are the n- fold compositions of [g i ] i≤n and [h i ] i≤n respectively -i.e. G(a) = ( i<n g i )(1 a ) and H(b) = ( i<n h i )(1 b ).
For some of the more sophisticated composition results (notably, the advanced composition theorem by Dwork et al. [START_REF] Dwork | Boosting and differential privacy[END_REF]), Lemma 26 is not quite strong enough and requires a slight adaptation of the notion of -lifting. We refer to the full version of the paper for more details.

Comparison with Existing Approximate Liftings

Now that we have seen -liftings, we briefly consider other definitions of approximate liftings.

We have already seen 2-liftings, which involve two witnesses (Definition 5). Evidently, -liftings strictly generalize 2-liftings.

Theorem 27. For all binary relations R over A & B and parameters , δ ≥ 0, we have R [START_REF] Barthe | Beyond differential privacy: Composition theorems and relational logic for f -divergences between probabilistic programs[END_REF] ,δ ⊆R ( ) ,δ . There exist relations and parameters where the inclusion is strict.

Proof. The inclusion R (2) ,δ ⊆R ( ) ,δ is immediate. We have a strict inclusion R (2) ,δ R ( )
,δ even for δ = 0 by considering the optimal subset coupling from Theorem 7. Consider a distribution µ over set A, and let P 1 ⊆ P 2 = A. There is an ( , 0)-approximate -lifting (by Theorem 24), but a ( , 0)-approximate 2-lifting does not exist if µ has non-zero mass outside of P 1 : the first witness µ must place non-zero mass at (a 1 , a 2 ) with a 1 / ∈ P 1 in order to have π 1 (µ ) = µ, but we must have a 2 / ∈ P 2 for the support requirement, and there is no such a 2 .

It is more interesting to compare -liftings with the original definitions of ( , δ)-approximate lifting, by Barthe et al. [START_REF] Barthe | Probabilistic relational reasoning for differential privacy[END_REF]. They introduce two notions, a symmetric lifting and an asymmetric lifting, each using a single witness distribution. We will focus on the asymmetric version.

Definition 28 (Barthe et al. [START_REF] Barthe | Probabilistic relational reasoning for differential privacy[END_REF]). Let µ 1 ∈ D(A) and µ 2 ∈ D(B) be sub-distributions, , δ ∈ R + and R be a binary relation over

A & B. An ( , δ)-approximate 1-lifting of µ 1 & µ 2 for R is a sub-distribution µ ∈ D(A × B) s.t.
In the first point we take the point-wise order on sub-distributions: if µ and µ are subdistributions over X, then µ ≤ µ when µ(x) ≤ µ (x) for all x ∈ X. We will write µ 1 R

(1) ,δ µ 2 if there exists an ( , δ)-approximate 1-lifting of µ 1 & µ 2 for R; the [START_REF] Aharoni | The max-flow min-cut theorem for countable networks[END_REF] indicates that there is one witness for this lifting.

1-liftings bear a close resemblance to probabilistic couplings from probability theory, which also have a single witness. However, 1-liftings are less well-understood theoretically than 2-liftings-basic properties such as mapping (Theorem 20) are not known to hold; the subset coupling (Theorem 7) is not known to exist. Somewhat surprisingly, 1-liftings are equivalent to -liftings (and hence by Theorem 19, also to Sato's approximate lifting).

Theorem 29. For all binary relations R over A & B and parameters , δ ≥ 0, we have R

-Lifting for f -Divergences

The definition of -lifting can be extended to lifting constructions based on general fdivergences, as previously proposed by Barthe and Olmedo [START_REF] Barthe | Beyond differential privacy: Composition theorems and relational logic for f -divergences between probabilistic programs[END_REF], Olmedo [START_REF] Olmedo | Approximate Relational Reasoning for Probabilistic Programs[END_REF]. Roughly, a f -divergence a function ∆ f (µ 1 , µ 2 ) that measures the difference between two probability distributions µ 1 and µ 2 . Much like we generalized their definition for ( , δ)-liftings, we can define -lifting with f -divergences. Before going any further, let us first define formally f -divergences. We denote by F the set of non-negative convex functions vanishing at 1:

F = {f : R + → R + | f (1) = 0}.
We also adopt the following notational conventions: 0 • f (0/0) = 0, and 0 • f (x/0) = x • lim t→0 + t • f (1/t); we write L f for the limit.

Definition 30. Given f ∈ F , the f -divergence ∆ f (µ 1 , µ 2 ) between two distributions µ 1 and µ 2 in D(A) is defined as:

∆ f (µ 1 , µ 1 ) = a∈A ν(a)f µ 1 (a) µ 2 (a) .
Examples of f -divergences include statistical distance (f (t) = 1 2 |t -1|), Kullback-Leibler divergence (f (t) = ln(t) -t + 1), and Hellinger distance (

f (t) = 1 2 ( √ t -1) 2 ).
Definition 31 ( -lifting for f -divergences). Let µ 1 ∈ D(A) and µ 2 ∈ D(B) be distributions, R be a binary relation over A & B, and

f ∈ F. An (f ; δ)-approximate lifting of µ 1 & µ 2 for R is a pair of distributions η ∈ D(A × B ) and η ∈ D(A × B) s.t. π 1 (η ) = µ 1 and π 2 (η ) = µ 2 ; supp(η |A×B ), supp(η |A×B ) ⊆R; and ∆ f (η , η ) ≤ δ,
where η • is the canonical lifting of η • to A × B . We will write:

µ 1 R ( ) f ;δ µ 2 if there exists an (f ; δ)-approximate lifting of µ 1 & µ 2 for R.
-liftings for f -divergences compose sequentially.

Lemma 32. Suppose f has divergence statistical distance, Kullback-Leibler, or Hellinger distance. For i ∈ {1, 2}, let µ i ∈ D(A i ) and η i :

A i → D(B i ). Let R (resp. S) be a binary relation over A 1 & A 2 (resp. over B 1 & B 2 ). If µ 1 R ( )
f ;δ µ 2 for some δ ≥ 0 and for any (a 1 , a 2 ) ∈R we have η 1 (a 1 ) S ( )

f ;δ η 2 (a 2 ) for some δ ≥ 0, then E µ1 [η 1 ] S ( ) f ;δ+δ E µ2 [η 2 ].

I C A L P 2 0 1 7 XX:12 REFERENCES

Much like the -liftings we saw before, -liftings for f -divergences have witness distributions with support determined by the support of µ 1 and µ 2 (cf. Lemma 10).

Lemma 33. Let µ 1 ∈ D(A) and µ 2 ∈ D(B) be distributions such that µ 1 R ( ) f ;δ µ 2 .
Then, there are witnesses with support contained in supp(µ 1 ) × supp(µ 2 ) .

Proof. See Appendix, p. 17 Finally, the mapping property from Lemma 20 holds also for these -liftings. While the proof of Lemma 20 relies on the equivalence for Sato's definition, there is no such equivalence (or definition) for general f -divergences. Therefore, we must work directly with the witnesses of the approximate lifting.

Lemma 34. Let µ 1 ∈ D(A 1 ), µ 2 ∈ D(A 2 ), g 1 : A 1 → B 1 , g 2 : A 2 → B 2 and R a binary relation on B 1 & B 2 . Let S such that a 1 S a 2 ⇐⇒ g 1 (a 1 ) R g 2 (a 2 ). Then g 1 (µ 1 ) R ( ) f ;δ g 2 (µ 2 ) ⇐⇒ µ 1 S ( ) f ;δ µ 2 .
Proof. See Appendix, p. 18

Conclusion

We have proposed a new definition of approximate lifting that unifies existing constructions and satisfies an approximate variant of Strassen's theorem. Our notion is useful both to simplify the soundness proof of existing program logics and to strengthen some of their proof rules. We see at least two important directions for future work. First, adapting existing program logics (for instance, apRHL [START_REF] Barthe | Probabilistic relational reasoning for differential privacy[END_REF]) to use -liftings, and formalizing examples that were out of reach of previous systems. Second, our notion of -liftings only applies when distributions have discrete support. It would be interesting to see if -liftings-and the approximate Strassen's theorem-can be generalized to the continuous setting.

A Detailed Proofs

In the proofs, we will sometimes refer to the witnesses of a -lifting. ,δ µ 2 , then we write:

η , η R ,δ µ 1 & µ 2 .
Proof of Lemma 10. Let µ and µ be any pair of witnesses to the approximate lifting. We will construct witnesses η , η with the desired support. For ease of notation, let

S i = supp(µ i ) for i ∈ {1, 2}. Define: η (a, b) = µ (a, b) : (a, b) ∈ S 1 × S 2 µ [a, B -S 2 ] : η (a, b) = µ (a, b) : (a, b) ∈ S 1 × S 2 µ [A -S 1 , b] : a = Evidently, η and η have support in S 1 × S 2 . Additionally, it is straightforward to check that π 1 (η ) = π 1 (µ ) = µ 1 and π 2 (η ) = π 2 (µ ) = µ 2
∀a 1 , a 2 ∈ A, ∀X ⊆ B. (a 1 , a 2 ) ∈ φ =⇒ P (a)[X] ≤ e • P (a)[X] + δ.
This is the definition of P being ( , δ)-differentially private for φ.

Proof of Lemma 12.

Immediate. Let = + and δ = δ + e • δ . By Theorem 19, it is sufficient to show that µ 1 (X) ≤ e • µ 1 (S(R(X))) + δ for any set X. We have:

µ 1 [X] ≤ e • µ 2 [R(X)] + δ (Theorem 19) ≤ e • (e • µ 3 [S(R(X))] + δ ) + δ (Theorem 19) = e + • µ 3 [S(R(X))] + e • δ + δ.

XX:15

We know that ∃ µ , µ

R ,δ µ 1 & µ 2 . Likewise, for a = (a 1 , a 2 ) ∈ R, ∃ η ,a , η ,a S ,δ η 1 (a 1 ) & η 2 (a 2 )
. Let η and η be the following distribution constructors:

η : a → η ,a if a ∈R 0 otherwise η : a → η ,a if a ∈R 0 otherwise and let ξ = E µ [η ] (resp. ξ = E µ [η ]
). We now prove that:

ξ , ξ S + ,δ+δ E µ1 [η 1 ] & E µ2 [η 2 ] .
The marginal and support conditions are immediate. The distance condition is obtained by an immediate application of the previous point.

Proof of Theorem 19. To show the forward direction of Theorem 19, let X ⊆ A and R(X) = B -R(X). Then, we have

µ 1 [X] = π 1 (η )[X] = η [X, B ] = η [X, B ] = η [X, R(X) R(X) { }] = η [X, R(X) { }] + η [X, R(X) ] = 0 ≤ e • η [X, R(X) { }] + δ ≤ e • η [A , R(X)] = η [A ,R(X)] +e • η [A , { }] = 0 +δ = e • π 2 (η )[R(X)] + δ = e • µ 2 [R(X)] + δ, as desired. Proof of Lemma 20. (=⇒) Assume that f 1 (µ 1 ) R ( ) ,δ f 2 (µ 2 ) and let X ⊆ A 1 . Then, µ 1 [X] ≤ µ 1 [f -1 1 (f 1 (X))] = f 1 (µ 1 )[f 1 (X)] ≤ e • f 2 (µ 2 )[R(f 1 (X))] + δ (Theorem 19) = e • µ 2 [f -1 2 (R(f 1 (X))) ⊆S(X) ] + δ ≤ e • µ 2 [S (X)] + δ.
Hence, by Theorem 19, µ 1 S ( )

,δ µ 2 . (⇐=) Assume that µ 1 S ( ) ,δ µ 2 and let X ⊆ A 2 . Then, f 1 (µ 1 )[X] = µ 1 [f -1 1 (X)] ≤ e • µ 2 [S (f -1 1 (X)) ⊆f -1 2 (R(X)) ] + δ ≤ e • f 2 (µ 2 )[R(X)] + δ. ( Theorem 19)
Hence, by Theorem 19,

f 1 (µ 1 ) R ( ) ,δ f 2 (µ 2 ).
Proof of Lemma 21. By Theorem 19, it is sufficient to prove that

µ 1 [X] ≤ e • µ 2 [R(X)] + µ 1 [θ ] + δ
for any X ⊆ A. By direct computation:

µ 1 [X] = µ 1 [X ∩ θ] + µ 1 [X ∩ θ ] ≤ µ 1 [X ∩ θ] + µ 1 [θ ] ≤ e • µ 2 [(θ =⇒ R)(X ∩ θ) = R(X∩θ) ⊆ R(X) ] + δ + µ 1 [θ ] ≤ e • µ 2 [R(X)] + µ 1 [θ ] + δ. I C A L P 2 0 1 7
Proof of Lemma 22. By Theorem 19, it is sufficient to prove that

µ 1 [X] ≤ e • µ 2 [R(X)] + e • µ 2 [θ ] + δ for any X ⊆ A.
Let X be such a set, then:

µ 1 [X] ≤ e • µ 2 [(θ =⇒ R)(X)] + δ ≤ e • (µ 2 [(θ =⇒ R)(X) ∩ θ] + µ 2 [θ ]) + δ ≤ µ 2 [(θ =⇒ R)(X) ∩ θ ⊆R(X)∩θ ] + e • µ 2 [θ ] + δ ≤ µ 2 [R(X)] + e • µ 2 [θ ] + δ. Proof of Lemma 23. From µ 1 R ( )
,δ µ 2 and Lemma 12, we have µ 1 S ( )

,δ µ 2 where S = θ a, =⇒ θ a, ∧ R. Hence, by Lemma 21, we obtain µ 1 (θ a, ∧ R)

( )
,δa µ 2 . Using similar reasoning with θ b, =⇒ θ b, ∧ R and Lemma 22, we have

µ 1 (θ b, ∧ R) ( ) ,δ b µ 2 .
Proof of Theorem 29. Suppose that (µ L , µ R ) are witnesses to µ 1 R

µ L (a, b)    η(a, b) • µ1(a)-δ(a) π 1 η(a) : b = µ 1 (a) -b∈B µ L (a, b) : b = µ R (a, b) η(a, b) : a = µ 2 (b) -a∈A µ R (a, b) : a = .
We can also bound the mass on points (a, ). Let S ⊆ A be any subset. µ R (S × { }) ≤ exp( )µ L (S × { }) + δ is clear. For the other direction:

µ L (S × { }) = a∈S µ 1 (a) -µ 1 (a) b∈B η(a, b) π 1 η(a) + δ(a) b∈B η(a, b) π 1 η(a) = µ 1 (S) -µ 1 (S) + δ(S) ≤ exp( )µ R (S × { }) + δ.
The mass at points ( , b) can be bounded in a similar way. Let T ⊆ B be any subset. Then, µ L ({ } × T ) ≤ exp( )µ R ({ } × T ) + δ is clear. For the other direction:

µ R ({ } × T ) = b∈T µ 2 (b) -µ 2 (b) a∈A η(a, b) π 2 η(b) + δ (b) a∈A η(a, b) π 2 η(b) = µ 2 (T ) -µ 2 (T ) + δ (T ) ≤ exp( )µ L ({ } × T ) + δ. So ∆ (µ L , µ R ) ≤ δ and ∆ (µ R , µ L ) ≤ δ so we have witnesses to µ 1 R ( ) ,δ µ 2 . Hence, R (1) ,δ =R ( ) ,δ .
The main use of symmetric approximate liftings is to support richer composition results that only apply to symmetric adjacency relations. We have the following reduction, a symmetric version of Lemma 26.

Lemma 39. Let n be a natural number. Suppose that there exists a function r : (R + × R + ) n → (R + × R + ) such that for any sets D, A, symmetric adjacency relation φ ⊆ D × D, n pairs i , δ i ≥ 0, and n functions f i : D×A → D(A) such that for every a, f i (-, a) : D → D(A) is ( i , δ i )-differentially private with respect to φ, the n-fold composition F : D → D(A) is r({( i , δ i )})-differentially private with respect to φ. Then for:

1. any relations {R(i)} i on A i & B i with i ranging from 0, . . . , n; and 2. any functions {g i : A i → D(A i+1 )} i , {h i : B i → D(B i+1 )} i with i ranging from 0, . . . , n-1 and for all (a, b) ∈ R(i), we have

g i (a) R(i + 1) ( ) i+1,δi+1 h i (b)
and g i (a), h i (b) proper distributions, there is a symmetric -lifting

G(a 0 ) R(n) ( ) r({( i,δi)}) H(b 0 )
for every (a 0 , b 0 ) ∈ R 0 , where G :

A 0 → D(A n ) and H : B 0 → D(B n ) are the n-fold (Kleisli) compositions of {g i } and {h i } respectively.
With this reduction we hand, we can generalize the advanced composition theorem from differential privacy to -liftings.

Theorem 40 (Advanced composition, [START_REF] Dwork | Boosting and differential privacy[END_REF]). Consider a symmetric adjacency relation φ on databases D. Let f i : D × A → D(A) be a sequence of n functions, such that for every a ∈ A the functions f i (-, a) : D → D(A) are ( , δ)-differentially private with respect φ. Then, for every a ∈ A and ω ∈ (0, 1), running f 1 , . . . , f n in sequence is ( * , δ * )-differentially private for * = 2n ln(1/ω) + n (e -1) and δ * = nδ + ω.

I C A L P 2 0 1 7 XX:24 REFERENCES Theorem 41. Let n be a natural number, , δ ≥ 0, and ω ∈ (0, 1) be real parameters. Suppose we have:

1. sets {A i } i , {B i } i with i ranging from 0, . . . , n; 2. relations {R(i)} i on A i & B i with i ranging from 0, . . . , n; and

functions {f

i : A i → D(A i+1 )} i , {g i : B i → D(B i+1 )} i with i ranging from 0, . . . , n -1 such that for all (a, b) ∈ R(i), we have f i (a) R(i + 1) ( ) ,δ g i (b)
and f i (a), g i (b) proper distributions. Then, there is an approximate lifting of the compositions:

F (a 0 ) R(n) ( ) ,δ G(b 0 ) for every (a 0 , b 0 ) ∈ R 0 , where F : A 0 → D(A n ) and G : B 0 → D(B n ) are the n-fold (Kleisli)
compositions of {f i } and {g i } respectively, and the lifting parameters are:

= 2n ln(1/ω) + n (e -1) δ = nδ + ω.
Proof. By Lemma 39 and the advanced composition for differential privacy (Theorem 40).

C An Elementary Proof of Weak Max-Flow Min-Cut Theorem

We give here an elementary proof of Max-Flow Min-Cut theorem for countable networks. We call it weak because it only covers graphs without rays and with a capacity function that is summable at each node. Our proof of approximate Strassen's theorem lies in this setting. Indeed, using the notations of Theorem 19, although an infinite capacity can occur on an edge of the form a → b ⊥ , we know that the flow between these two nodes cannot be above min{α a , β b } where α a and β b are the respective capacities of the edges → a and b ⊥ → ⊥. Hence, we can built a network flow whose set of flows is identical to the former one and with only finite capacities. It is immediate to check that the capacity of the network flow is summable at each node, the families {α a } a∈(A ) and {β b } b∈(B ) ⊥ being summable.

From now on, let N = ((V, E), , ⊥, c) be a flow network that contains only finite capacities. Moreover, assume that for any u ∈ V , the families {c(u, v)} v∈V and {c(v, u)} v∈V are summable. In the proof, we will use the edge definition of cuts (as defined in the paper above) or the equivalent following one:

Definition 42. Given a flow network N = ((V, E), , ⊥, c), a cut for N is any subset C of V s.t. ∈ C but ⊥ / ∈ C. The capacity |C| of a cut C is defined as |C| = {c(u, v) | u ∈ C, v / ∈ C} ∈ R + ∪ {+∞}.
We can now start our proof of Weak Max-Flow Min-Cut Theorem.

Lemma 43. There exists a flow for N with maximal mass.

Proof. We assume that V , the set of vertices, is countably infinite -the finite case is already covered by the usual max-flow min-cut theorem. Let { n } n∈N be an enumeration of V 2 .

Let F = {f | f is a flow for N }. We order F by f g iff |f | ≤ |g|. We first show that F is an inductive set. Let X = {f i } i∈I be a -chain for F for some countable set I. We prove that X admits an upper bound in F. If I = ∅, we take the null flow as the upper bound of X. If I is finite but non empty, we take any f of X, that maximizes |f |, as the upper bound of X. Otherwise, wlog, we can assume that X = {f i } i∈N with ∀i. f i f i+1 . We inductively construct a sequence {t n } n∈N of strictly increasing functions from N to itself. Let n ∈ N and assume that t k is constructed for any k < n. Let tn = t 0 • • • • • t n-1 . The sequence t n is chosen among all the strictly monotone sequences {i n } n 's s.t. {f tn(ik) ( n )} k converges. Such a sequence exists by the Bolzano-Weierstrass theorem, {f tn(k) ( n )} k being absolutely bounded by c( n ). Let {ω n } n be defined as ω n = tn (n). By construction, it is immediate that for any k ∈ N, {f ωn } n is a sub-sequence, at infinity, of {f tk (n) } n . As such, for any e ( = k ) ∈ V 2 , {f ωn (e)} n admits a limit which is equal to lim

n→∞ [f tk+1 (n) (e)].
We denote by f the point-wise limit of {f ωn } n and prove that f is an upper bound of E. Let u, v ∈ V . Then,

           f (u, v) = lim n→∞ [f ωn (u, v)] ≤c(u,v) ≤ c(u, v) f (u, v) = lim n→∞ [f ωn (u, v)] -fω n (v,u) = -lim n→∞ [f ωn (v, u)] = -f (v, u).
Last, let u ∈ V s.t. u / ∈ { , ⊥}. First, note that for any v ∈ V and k ∈ N, f + ω k (u, v) ≤ c(u, v) and f - ω k (u, v) ≤ c(v, u), where f + ω k and f - ω k are the respective positive and negative parts of f ω k . Hence, by taking k → ∞, we obtain f + (u, v) ≤ c(u, v) and f -(u, v) ≤ c(v, u). By summability of the in-and out-going capacities of u, we obtain that {f (u, v)} v∈V is summable. We now prove that v∈V f (u, v) = 0: where swapping lim and is by the dominated convergence theorem. Hence, F is an inductive set, and by Zorn's lemma, it admits a maximal element.

Lemma 44. For any cut X of F, the mass of any flow f for F is equal to the flow of f going through C, i.e. to {f (u, v) | (u, v) ∈ X † } where X † = X × X .

Proof. The proof identical to the finite case. XX:26 REFERENCES Proof. By Lemma 43, there exists a maximal flow for N that we denote by f. Let R be s.t. u R v ⇐⇒ f(u, v) < c(u, v) and consider the set C = R * ({ }), where R * is the reflexivetransitive closure of R. Assume that ⊥ ∈ C. Then, there exists a path from to ⊥ following R that we can assume, wlog, simple. Let u 0 R u 1 R • • • R u n+1 be such a path -i.e. u 0 = , u n+1 = ⊥ and the u i 's are pairwise disjoint. Let δ = min i≤n [c(u i , u i+1 ) -f(u i , u i+1 )] (that is strictly positive by assumption of R), and let Ω : V 2 → R be defined as Ω(u, v) = σ u,v • δ, where ∀i. σ ui,ui±1 = ±1 and is equal to 0 otherwise -all these cases being mutual exclusive by simplicity of the path. We consider g = f + Ω and prove that g is a flow for N s.t. |g| > |f|. The two first properties of a flow are immediate. For the first one, consider u, v ∈ V s.t. g(u, v) > f(u, v). This can only happen if σ u,v > 0. In that case, u = u k and v = u k+1 for some k, and we have

g(u, v) = g(u k , u k+1 ) = f(u k , u k+1 ) + δ ≤ f(u k , u k+1 ) + c(u k , u k+1 ) -f(u k , u k+1 ) = c(u k , u k+1 ) = c(u, v).
For the second flow property, consider any pair (u, v) of vertices. Then,

g(u, v) = f(u, v) + σ u,v • δ = -f(v, u) -σ v,u • δ = -f(v, u).
For the Kirchhoff law, let u ∈ V s.t. u / ∈ { , ⊥}. If u is not part of the considered path, then ∀v ∈ V , g(u, v) = f(u, v) and the flow at node u is identical for f and g. Otherwise, there exists an index k ∈ [1, n] s.t. u = u k and f(u, v) and g(u, v) only differ for v = u k-1 and v = u k+1 . Hence, v∈V g(u, v) converges and:

Lemma 26 . 7 XX: 10 -

 26710 Pose R + 2 = R + × R + and let (R + 2 ) * be the set of finite sequences over R + 2 . Let r : (R + 2 ) * → R + 2 be a DP-composition operator, i.e. r is an operator such that for any sets A, D and family {f i : D × A → D(A)} i<n of functions, if for every a ∈ A and i < n, I C A L P 2 0 1 Liftings for Differential Privacy

Notation 35 .

 35 Let µ 1 ∈ D(A) and µ 2 ∈ D(B) be sub-distributions, , δ ∈ R + and R be a binary relation over A & B. If two distributions η ∈ D(A × B ) and η ∈ D(A × B) are witnesses to the -lifting µ 1 R ( )

  so η and η have the desired marginals. It only remains to check the distance condition. By the definition of the distance ∆ , we know that there are non-negative values δ(a, b) such that (i) µ (a, b) ≤ e µ (a, b) + δ(a, b) and (ii) a,b δ(a, b) ≤ δ. We can define new constants: ζ(a, b) = δ(a, b) : (a, b) ∈ S 1 × S 2 ∪ { } × B δ[a, B -S 2 ] : b = . Since µ ( , b) = η ( , b) = 0 for all b ∈ B , and µ (a, b) = η (a, b) = 0 for all b / ∈ S 2 , point (i) holds for the witnesses η , η and constants ζ(a, b). Since a,b ζ(a, b) = a,b δ(a, b) ≤ δ, point (ii) holds as well. Hence, ∆ (η , η ) ≤ δ and we have witnesses for the desired approximate lifting. Proof of Lemma 11. (=⇒) Let P be ( , δ)-differentially private for φ and a 1 , a 2 ∈ A s.t. a 1 φ a 2 . Let X be a subset of B. Then, by definition of differential privacy, we have P (x)[X] ≤ e • P (a)[X] + δ = e • P (a)[(=)(X)] + δ. Hence, by application of Theorem 19, we have P (a 1 ) = ( ) ,δ P (a 2 ). (⇐=) By application of Theorem 19, we have that

  µ 2 . Define the witness η ∈ D(A × B) as the point-wise minimum: η(a, b) min(µ L (a, b), µ R (a, b)). We will show that η is a witness toµ 1 R (1),δ µ 2 . The support condition follows from the support condition for (µ L , µ R ). The marginal conditions π 1 (η) ≤ µ 1 and π 2 (η) ≤ µ 2 also follow by the marginal conditions for (µ L , µ R ). The only thing to check is the distance condition. By the distance condition on (µ L , µ R ), there exist non-negative values δ(a, b) such thatµ L (a, b) ≤ exp( )µ R (a, b) + δ(a, b)and a,b δ(a, b) ≤ δ. So, µ R (a, b) ≥ exp(-)(µ L (a, b) -δ(a, b)). Now let S ⊆ A be any subset. Then: µ 1 (S) -exp( )π 1 (η)(S) = a∈S µ 1 (a) -exp( ) b∈B min(µ L (a, b), µ R (a, b)) ≤ a∈S µ 1 (a) -exp( ) b∈B exp(-)(µ L (a, b) -δ(a, b)) = a∈S,b∈B δ(a, b) ≤ δ. Thus, η witnesses µ 1 R The other direction is more interesting. Let η ∈ D(A × B) be the witness for R (1) ,δ . By the distance condition ∆ (µ 1 , π 1 η) ≤ δ, there exist non-negative values δ(a) such that µ 1 (a) ≤ exp( )π 1 η(a) + δ(a) with equality when δ(a) is strictly positive, and a∈A δ(a) ≤ δ. Define two witnesses µ L ∈ D(A × B ), µ R ∈ D(A × B) as follows:

  v∈V f (u, v) = v∈V lim n→∞ [f ωn (u, v)] = lim n→∞ v∈V f ωn (u, v) 0 = 0,where the swapping lim and is obtained by the dominated convergence theorem. (As noted above, for any v ∈ V and k∈ N, f + ω k (u, v) ≤ c(u, v) and f - ω k (u, v) ≤ c(v, u) with {c(u, v)} v∈V and {c(v, u)} v∈V summable families.) So, f is a flow for N .Finally, we show that the flow is maximal: f g for any g ∈ X. Calculating,|f | = v∈V f ( , v) = v∈V lim n→∞ f ωn ( , v) = lim n→∞ f ωn ( , v) = lim n→∞ |f ωn | = sup g∈X |g|,

Theorem 45 (

 45 Weak Countable Max-Flow Min-Cut). We have sup{|f | | f is a flow for N } = inf{|C| | C is a cut for N } and both the supremum and infimum are reached. I C A L P 2 0 1 7

  v∈V g(u, v) = v∈V f(u, v) + σ ui,ui+1 +1 •δ + σ ui,ui-1 -1 •δ = v∈V f(u, v) = 0.We now prove that the flow g has a mass strictly greater than the one of f:|g| = v∈V g( , v) = v∈V f( , v) + Ω( , u 1 ) = |f| + δ > |f|.By maximality of f, such a flow g cannot exist. Hence, ⊥ / ∈ C and C is a cut.We can now conclude the proof. By Lemma 44, for any cut X, |f| = e∈X † f(e) ≤ e∈X † c(e) = |C|. Hence, f inf{|C| | C is a cut for N }. Now, by definition of C, any edge in X † is saturated by f. Hence, for e ∈ C † , f(e) = c(e) and |f| = |C|. This proves that C is a minimal cut and that the infimum is a minimum.

2 0 1 7 XX:8 -Liftings for Differential Privacy

  This implies that |C| ≥ ω since E {( , )} is a cut with capacity ω. If ( , ) / ∈ C and (⊥, ⊥ ) ∈ C then we have |C| ≥ ω in the similar way as above. Otherwise (i.e. C ∩ E R

C ∩ E R = ∅. If ( , ) ∈ C and (⊥, ⊥ ) / ∈ C then we must have E ⊆ C.

π 1 (µ) ≤ µ 1 and π 2 (µ) ≤ µ 2 ;

∆ (µ 1 , π 1 (µ)) ≤ δ; and

supp(µ) ⊆R.

Acknowledgments.

We thank the anonymous reviewers for their helpful suggestions. This work is partially supported by a grant from the NSF (TWC-1513694) and a grant from the Simons Foundation (#360368 to Justin Hsu).

(As usual, if any denominator is zero, we take the probability to be zero as well.)

The support condition follows from the support condition of η. The marginal conditions hold by definition. Note that all probabilities are non-negative. For µ L , note that if δ(a) > 0 then µ 1 (a) -δ(a) = exp( )π 1 η(a) ≥ 0 and hence µ L (a, ) = µ 1 (a) -δ(a) ≥ 0. assuming π 1 η(a) > 0; if π 1 η(a) = 0 then µ L (a, ) = 0. For µ R , non-negativity holds because π 2 η ≤ µ 2 .

We show the distance bound. We can also bound the mass on points (a, ). Let S ⊆ A be any subset. Then:

So ∆ (µ L , µ R ) ≤ δ as desired, and we have witnesses to

,δ ⊆R ( ) ,δ .

Proof of Lemma 33. Let µ and µ be any pair of witnesses to the approximate lifting. We will construct witnesses η , η with the desired support. For ease of notation, let S i = supp(µ i ) for i ∈ {1, 2}. Define:

Evidently, η and η have support in S 1 × S 2 . Additionally, it is straightforward to check that π 1 (η ) = π 1 (µ ) = µ 1 and π 2 (η ) = π 2 (µ ) = µ 2 so η and η have the desired marginals. It only remains to check the distance condition. We can compute:

XX:18 REFERENCES

Now, note that for all b ∈ B -S 2 , we know µ (a, b ) = 0. Similarly, for all a ∈ A -S 1 , we know µ (a , b) = 0. Hence, the last line is equal to

Thus, η and η witness the desired -lifting.

Proof of Lemma 34. For the reverse direction, take the witnesses µ , µ ∈ D(A × A ) and define witnesses ν =(g 1 × g 2 ) (µ ) and ν =(g 1 × g 2 ) (µ ), where g 1 × g 2 takes a pair (a 1 , a 2 ) to the pair (g 1 (a 1 ), g 2 (a 2 )) and maps to . The support and marginal requirements are clear. The only thing to check is the distance condition, but this follows from monotonicity of f -divergences-under the mapping g 1 × g 2 : A × A → B × B , the f -divergence can only decrease (see, e.g., ? ]).

For the forward direction, let ν , ν ∈ D(B × B ) be the witnesses to the second lifting. By Lemma 33, we may assume without loss of generality that supp(ν ) and supp(ν ) are contained in

We aim to construct a pair of witnesses µ , µ ∈ D(A × A ) to the first lifting. The basic idea is to define µ and µ based on equivalence classes of elements in A mapping to a particular b ∈ B, and then smooth out the probabilities within each equivalence class. To begin, for a ∈ A, define [a] g = g -1 (g(a)) and α i (a) = Pr µi [{a} | [a] gi ]. We take α i (a) = 0 when µ i ([a] fi ) = 0, and we let α i ( ) = 0. We define µ and µ as

where

The support and marginal conditions follow from the support and marginal conditions of ν , ν . For instance:

.

XX:19

In the last line, we replace the sum over b 2 ∈ g 2 (A ) with a sum over b 2 ∈ B ; this holds since the support of g 2 (µ 2 ) is contained in g 2 (A), so we can assume that ν (a, b 2 ) = 0 for all b 2 outside of g 2 (A ). Then, we can conclude by the marginal condition π 1 (ν ) =g 1 (µ 1 ). The second marginal is similar. We now check the distance condition ∆ f (µ , µ ) ≤ δ. We can split the f -divergence into ∆ f (µ , µ ) = P 0 + P 1 + P 2 + P 3 , where

We will handle each term separately. Evidently P 0 = 0. For P 1 , we have:

where the sets S =0 and S =0 are defined as:

By further rearranging:

The final equality is because without loss of generality, we can assume (by Lemma 33) that ν , ν are zero outside of the support of g 1 (µ 1 ) and g 2 (µ 2 ), which have support contained in (g 1 × g 2 )(A × A).

The remaining two terms P 2 and P 3 are simpler to bound. For P 2 , note that µ (a, ) = 0 for all a ∈ A. Thus:

where the last equality is because ν (b, ) = 0 for all b ∈ B.

Similarly for P 3 , using µ ( , a) = ν ( , b) = 0 for all a ∈ A and b ∈ B, we have:

Putting everything together, we conclude

by assumption, so µ , µ witness the desired approximate lifting.

B Symmetric -lifting

The approximate liftings we have considered so far are all asymmetric. For instance, the approximate lifting

,δ µ 2 may not imply the lifting µ 2 (R -1 ) ( )

,δ µ 1 . Given witnesses (µ L , µ R ) to the first lifting, we may consider the witnesses (ν L , ν R ) (µ R , µ L ) where the transpose map (-) : D(A × B) → D(B × A) is defined in the obvious way. Then (ν L , ν R ) almost witness the second lifting, except that the distance bound is in the opposite direction:

In general, we cannot bound ∆ (ν L , ν R ) and the symmetric lifting µ 2 (R -1 ) ( ) ,δ µ 1 may not hold. To recover symmetry, we can define a symmetric version of -lifting.

Definition 36 (Symmetric -lifting). Let µ 1 ∈ D(A) and µ 2 ∈ D(B) be sub-distributions, , δ ∈ R + and R be a binary relation over

Symmetric -lifting is a special case of -lifting that can capture differential privacy under when the adjacency relation φ is symmetric: a probabilistic computation M : A → D(B) is ( , δ)-differentially private if and only if for every two adjacent inputs a φ a , there is an approximate lifting of the equality relation:

,δ M (a ). Unfortunately, the more advanced properties in Section 4 do not all hold when moving to symmetric liftings. However, we can show that symmetric -liftings are equivalent to the symmetric version of 1-witness lifting proposed by Barthe et al. [START_REF] Barthe | Probabilistic relational reasoning for differential privacy[END_REF].

Definition 37 (Barthe et al. [START_REF] Barthe | Probabilistic relational reasoning for differential privacy[END_REF]). Let µ 1 ∈ D(A) and µ 2 ∈ D(B) be sub-distributions, , δ ∈ R + and R be a binary relation over

1. π 1 (µ) ≤ µ 1 and π 2 (µ) ≤ µ 2 ; 2. ∆ (µ 1 , π 1 (µ)) ≤ δ and ∆ (µ 2 , π 2 (µ)) ≤ δ; and 3. supp(µ) ⊆R.

We will write µ 1 R

,δ µ 2 if there exists an ( , δ)-approximate symmetric 1-lifting of µ 1 & µ 2 for R; the [START_REF] Aharoni | The max-flow min-cut theorem for countable networks[END_REF] indicates that there is one witness for this lifting.

Theorem 38 (cf. the asymmetric result Theorem 29). For all binary relations R over A & B and parameters , δ ≥ 0, we have R ). We will show that η is a

,δ µ 2 . The support condition follows from the support condition for (µ L , µ R ). The marginal conditions π 1 (η) ≤ µ 1 and π 2 (η) ≤ µ 2 also follow by the marginal conditions for (µ L , µ R ). The only thing to check is the distance condition. By the distance condition on (µ L , µ R ), there exist non-negative values δ(a, b) such that Now let S ⊆ A be any subset. Then:

The other marginal is similar. For any subset T ⊆ B we have

Thus, η witnesses µ 1 R

,δ µ 2 .

I C A L P 2 0 1 7

XX:22 REFERENCES

The other direction is more interesting. Let η ∈ D(A × B) be the single witness to R

,δ . By the distance conditions ∆ (µ 1 , π 1 η) ≤ δ and ∆ (µ 2 , π 2 η) ≤ δ, there exist non-negative values δ(a) and δ (b) such that

(As usual, if any denominator is zero, we take the probability to be zero as well.)

The support condition follows from the support condition of η. The marginal conditions hold by definition. Note that all probabilities are non-negative. For instance in µ L , note that if δ(a) > 0 then µ 1 (a) -δ(a) = exp( )π 1 η(a) ≥ 0 and hence µ L (a, ) = µ 1 (a) -δ(a) ≥ 0. We can also lower bound the ratios: