Nathael Gozlan

POINCAR É INEQUALITIES FOR NON EUCLIDEAN METRICS AND TRANSPORTATION COST INEQUALITIES ON R d

Keywords: . 1991 Mathematics Subject Classification. 60E15 and 26D10 Poincaré inequality, Transportation cost inequalities, Concentration of measure, Logarithmic-Sobolev inequalities

In this paper, we consider Poincaré inequalities for non euclidean metrics on R d . These inequalities enable us to derive precise dimension free concentration inequalities for product measures. This technique is appropriate for a large scope of concentration rate: between exponential and gaussian and beyond. We give different equivalent functional forms of these Poincaré type inequalities in terms of transportation-cost inequalities and infimum convolution inequalities. Workable sufficient conditions are given and a comparison is made with generalized Beckner-Latala-Oleszkiewicz inequalities.

1. Introduction 1.1. Poincaré inequality and concentration of measure. One says that a probability measure on a metric space (X , d) satisfies a Poincaré inequality also called spectral gap inequality with the constant C, if for all locally Lipschitz function f , one has [START_REF] Aida | Logarithmic sobolev inequalities and exponential integrability[END_REF] Var

µ (f ) ≤ C |∇f | 2 dµ,
where the length of the gradient is defined by (when x is not an accumulation point of X , one defines |∇f |(x) = 0).

It is well known since the works [START_REF] Gromov | A topological application of the isoperimetric inequality[END_REF], [START_REF] Aida | Logarithmic sobolev inequalities and exponential integrability[END_REF], [START_REF] Aida | Moment estimates derived from poincaré and logarithmic sobolev inequalities[END_REF] and [START_REF] Bobkov | Poincaré's inequalities and Talagrand's concentration phenomenon for the exponential distribution[END_REF] that the inequality (1) implies dimension free concentration inequalities for the product measures µ n , n ≥ 1. For example, in [START_REF] Bobkov | Poincaré's inequalities and Talagrand's concentration phenomenon for the exponential distribution[END_REF], M. Ledoux Another way to express the concentration of the product measure µ n is the following:

Corollary 2 (Bobkov-Ledoux). Let µ be a probability measure on X satisfying the Poincaré inequality (1) on (X , d) with the constant C > 0. Define K(C) = α( 1 √ Cκ )/16, where as before κ = 18e √ 5 , then for all subset A of X n with µ n (A) ≥ 1/2, [START_REF] Barthe | Interpolated inequalities between exponential and gaussian, orlicz hypercontractivity and isoperimetry[END_REF] ∀h ≥ 0,

µ n A h ≥ 1 -e -K(C)h ,
where the set A h is the enlargement of A defined by

A h = y ∈ X n : inf x∈A n i=1 α(d(x i , y i )) ≤ h ,
where α(u) = min(|u|, u 2 ) for all u ∈ R.

The inequality (4) can be easily derived from Theorem 1 (see [START_REF] Bobkov | Poincaré's inequalities and Talagrand's concentration phenomenon for the exponential distribution[END_REF] or Section 2.2 of the present paper). Inequalities such as (4) were first obtained by M. Talagrand in different articles using completely different techniques (see e.g. [START_REF] Talagrand | Concentration of measure and isoperimetric inequalities in product spaces[END_REF]).

If µ satisfies (1) on R d equipped with its standard euclidean norm | • | 2 , then (4) can be rewritten in a more pleasant way: for all subset A of R d n with µ n (A) ≥ 1/2, (5) ∀h ≥ 0,

µ n A + √ hB 2 + hB 1 ≥ 1 -e -hK(C)
with the same constant K(C) as above. The archetypic example of a measure satisfying [START_REF] Aida | Logarithmic sobolev inequalities and exponential integrability[END_REF] is the exponential measure on R d ν d 1 , where dν 1 (x) = 1 2 e -|x| dx. For this probability, (5) cannot be improved (a version of [START_REF] Barthe | Sobolev inequalities for probability measures on the real line[END_REF] with sharp constants has been established by Talagrand in [START_REF] Talagrand | A new isoperimetric inequality and the concentration of measure phenomenon[END_REF] see also Maurey [19, Corollary 1]). Thus [START_REF] Barthe | Sobolev inequalities for probability measures on the real line[END_REF] expresses that the probability measures µ n concentrate at least as fast as the exponential measure on R d n . Some probability measures concentrate faster than the exponential measure. For example, the standard gaussian measure γ m on R m verifies for all A ⊂ R m with γ m (A) ≥ 1/2, [START_REF] Bobkov | Hypercontractivity of Hamilton-Jacobi equations[END_REF] ∀h ≥ 0,

γ m (A + hB 2 ) ≥ 1 -e -h 2 /2 .
There is absolutely no hope to derive such a bound from the classical Poincaré inequality (1) on R m equipped with the euclidean norm. The inequality (6) requires other tools. For example [START_REF] Bobkov | Hypercontractivity of Hamilton-Jacobi equations[END_REF] follows from the Logarithmic Sobolev inequality, introduced by L. Gross in [START_REF] Gross | Logarithmic sobolev inequalities[END_REF], which is strictly stronger than (1) (see [START_REF] Ledoux | The concentration of measure phenomenon, volume 89 of Mathematical Surveys and Monographs[END_REF]Chapter 5]).

1.2. Changing the metric improves the concentration. The aim of this paper is to show that replacing in (1) and (2) the standard euclidean norm | . | 2 by another metric makes possible to reach a large scope of concentration properties including gaussian or even stronger behaviors. The metrics we are going to equip R d with are of the form:

(7) ∀x, y ∈ R d , d ω (x, y) = d i=1 |ω(x i ) -ω(y i )| 2 1/2 ,
where, in all the paper, we will assume that ω : R → R verifies:

• ω is such that x → ω(x)/x is non decreasing on (0, +∞),

• ω is non negative on R + ,

• ω is such that ω(-x) = -ω(x), for all x ∈ R.

Note that the first assumption is verified as soon as ω is convex on R + with ω(0) = 0.

Definition 3. One says that a probability measure µ on R d satisfies the inequality SG(ω, C) (resp. SG(C)) if µ satisfies the Poincaré inequality (1) for the distance d ω ( . , . ) defined by (7) (resp. for the standard euclidean metric) with the constant C > 0.

Let us give a first example:

Proposition 4. Let ω p (x) = max(x, x p ) on R + with ω p (-x) = -ω p (x) for all x ∈ R.
Suppose that µ satisfies the inequality SG(ω p , C) on R d for some C > 0.

If p ∈ [1, 2], then for all n ≥ 1 and all A ⊂ R d n , ∀h ≥ 0, µ n A + 2 √ hB 2 + 2h 1/p B p ≥ 1 -e -K(C)h/d . If p ≥ 2, then for all n ≥ 1 and all A ⊂ R d n , ∀h ≥ 0, µ n A + 2 √ hB 2 ≥ 1 -e -K(C)h/d ,
and ∀h ≥ 0,

µ n A + 2h 1/p B p ≥ 1 -e -K(C)h/d .
(where

K(C) is defined in Corollary 2)
This result will be easily deduced from Corollary 2 and from an elementary comparison between the metric d ωp ( . , . ) and the norms | . | p . In particular, it will follow from our general sufficient conditions that, for all p ∈ [1, +∞), the probability measure dν p (x) = 1 Zp e -|x| p dx verifies SG(ω p , C) for some C. The interest of our approach is to give a somewhat unified picture of the concentration of measure phenomenon. 1.3. Presentation of the results. Before going into further details in the presentation of our results, let us introduce some notations and conventions. 1.3.1. Notations. The map ω is defined on R but we will also denote by ω the map defined on R m (for every m ≥ 1) by (x 1 , . . . , x m ) → (ω(x 1 ), . . . , ω(x n )). The image of a probability measure µ on a space X under a measurable map T : X → Y will be denoted by T ♯ µ. We recall that is is defined by (i) The probability measure µ verifies SG(ω, C).

∀A ⊂ Y, T ♯ µ(B) = µ T -1 (A) .
(ii) The probability measure ω ♯ µ verifies SG(C).

(iii) The probability measure µ satisfies the following weighted Poincaré inequality:

(8) ∀f, Var µ (f ) ≤ C d i=1 1 ω ′ (x i ) 2 ∂f ∂x i (x) 2 dµ(x), for all f : R d → R such that f • ω -1 is of class C 1 .
Observe that this proposition furnishes a huge collection of examples. Indeed, with a slight abuse of notations, one has

ω -1 ♯ SG(C) ⊂ SG(ω, C).
1.3.3. Sufficient conditions for SG(ω, C). In Section 3 we addressed the problem of finding workable sufficient conditions for Poincaré inequalities SG(ω, C). The strategy is dictated by Proposition 5. Namely, a probability µ satisfies SG(ω, C), if and only if the measure ω ♯ µ satisfies SG(C). So all we have to do is to apply to the measure ω ♯ µ one of the known criteria for the classical Poincaré inequality.

In dimension one, one has a necessary and sufficient condition for SG(ω, C): Proposition 6. A probability measure µ on R absolutely continuous with density h > 0 satisfies the inequality SG(ω, C) for some C > 0 if and only if (9)

D - ω = sup x≤m µ(-∞, x] m x ω ′ (u) 2 h(u) du < +∞ and D + ω = sup x≥m µ[x, +∞) x m ω ′ (u) 2 h(u) du < +∞,
where m denotes the median of µ. Moreover the optimal constant C in (1) denoted by

C opt verifies max(D - ω , D + ω ) ≤ C opt ≤ 4 max(D - ω , D + ω )
This proposition follows at once from the celebrated Muckenhoupt criteria for the classical Poincaré inequality (see [START_REF] Muckenhoupt | Hardy's inequality with weights[END_REF]). The following result completes the picture giving a large class of examples:

Proposition 7. Let µ be an absolutely continuous probability measure on R with density dµ(x) = e -V (x) dx. Assume that the potential V is of class C 1 and that ω verifies the following regularity condition:

ω ′′ (x) ω ′2 (x) ----→ x→+∞ 0.
If V is such that

(10) lim inf x→±∞ sgn(x)V ′ (x) ω ′ (x) > 0,
then the probability measure µ verifies the Poincaré inequality SG(ω, C) for some C > 0.

In dimension d, one gets: Proposition 8. Let µ be a probability measure on R d absolutely continuous with respect to the Lebesgues measure, with dµ(x) = e -V (x) dx with V a function of class C 2 . Suppose that ω is of class C 3 on R and such that ω ′ (0) > 0 and

∀x ∈ R, ω (3) (ω ′ ) 3 (x) ≤ M,
for some M > 0. If there is some constant u > 0 such that

lim inf |x|→+∞ 1 u 2 d i=1 1 4
∂V ∂x i 2 x u - ∂ 2 V ∂x 2 i x u 1 ω ′ (x i ) 2 > dM,
then the probability measure µ satisfies SG(ω, C) for some C, where ω(x) = ω(ux), for all x ∈ R. This condition will be easily derived from the condition lim inf |x|→+∞ |∇V |(x) 2 -∆V (x) > 0, which is known to imply the classical Poincaré inequality. 1.3.4. Links with Transportation-Cost inequalities. In Section 4, we show the equivalence between the Poincaré inequalities for the metric d ω and certain transportation-cost inequalities. Transportation-cost inequalities were first introduced by K. Marton and M. Talagrand in [START_REF] Marton | A simple proof of the blowing-up lemma[END_REF][START_REF] Marton | Bounding d-distance by informational divergence: a method to prove measure concentration[END_REF] and [START_REF] Talagrand | Transportation cost for Gaussian and other product measures[END_REF]. For recent advances in the understanding of these inequalities consult [START_REF] Cattiaux | Talagrand's like quadratic transportation cost inequalities[END_REF], [START_REF] Gentil | Modified logarithmic Sobolev inequalities and transportation inequalities[END_REF], [START_REF] Gozlan | Characterization of talagrand's like transportation-cost inequality on the real line[END_REF], [START_REF] Wang | Probability distance inequalities on riemannian manifolds and path spaces[END_REF][START_REF] Wang | Generalized transportation-cost inequalities and applications[END_REF]. In these inequalities one tries to bound an optimal transportation cost in the sens of Kantorovich by the relative entropy functional. More precisely, if c : X × X → R + is a measurable map on some metric space X , the optimal transportation cost between ν and µ ∈ P(X ) (the set of probability measures on X ) is defined by

T c (ν, µ) = inf π∈P (ν,µ) c(x, y) dπ,
where P (ν, µ) is the set of probability measures π on X × X such that π(dx, Y) = ν(dx) and π(X , dy) = µ(dy). One says that µ satisfies the transportation cost inequality with the cost function c(x, y) if [START_REF] Gozlan | Characterization of talagrand's like transportation-cost inequality on the real line[END_REF] ∀ν ∈ P(X ),

T c (ν, µ) ≤ H(ν | µ),
where H(ν | µ) denotes the relative entropy of ν with respect to µ and is defined by H(ν | µ) = log dν dµ dν if ν is absolutely continuous with respect to µ and H(ν | µ) = +∞ otherwise.

Transportation cost inequalities are known to have good tensorization properties and to yield concentration results independent of the dimension (all these facts are recalled in section 4). For example, the celebrated T 2 inequality which corresponds to cost functions of the form (x, y) → a|x -y| 2 2 gives gaussian concentration (see e.g [START_REF] Talagrand | Transportation cost for Gaussian and other product measures[END_REF]). A celebrated result of Otto and Villani shows that the Lograithmic Sobolev inequality implies T 2 (see [START_REF] Otto | Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality[END_REF]).

Let us say that µ ∈ P(R d ) satisfies the inequality T(ω, a) if it satisfies the transportation cost inequality [START_REF] Gozlan | Characterization of talagrand's like transportation-cost inequality on the real line[END_REF] with the cost function (x, y) → α (ad ω (x, y))

One proves the following Theorem 9. Let µ be a probability measure on R d absolutely continuous with respect to Lebesgues measure with a positive density. Then µ satisfies the Poincaré inequality SG(ω, C) for some C > 0 if and only if it satisfies the transportation-cost inequality T(ω, a) for some a > 0. More precisely,

• if µ satisfies SG(ω, C) then it satisfies T(ω, 1 √ Cκ ), with κ = 18e √ 5 .
• if µ satisfies the inequality T(ω, a), then µ satisfies the inequality SG(ω, 1 2a 2 ).

This theorem is an easy extension of a result by Bobkov, Gentil and Ledoux concerning the classical Poincaré inequality (see [START_REF] Bobkov | Hypercontractivity of Hamilton-Jacobi equations[END_REF]Corollary 5.1]). This extension is performed using a very simple contraction principle for transportation cost inequalities. The author previously used this technique in [START_REF] Gozlan | Characterization of talagrand's like transportation-cost inequality on the real line[END_REF] to characterize a large class of transportation cost inequalities on the real line.

1.3.5. Comparison with Latala-Oleszkiewicz inequalities. In Section 5, we compare the inequalities SG(ω, C) to other functional inequalities including the ones introduced by R. Latala and K. Oleszkiewicz in [START_REF] Latala | Between sobolev and poincaré. in geometric aspects of Functional Analysis[END_REF]. Let r ∈ [START_REF] Aida | Logarithmic sobolev inequalities and exponential integrability[END_REF][START_REF] Aida | Moment estimates derived from poincaré and logarithmic sobolev inequalities[END_REF], one says that a probability measure µ on R d satisfies the inequality LO(r, C) if

(12) sup p∈(1,2) f 2 dµ - f p dµ 2/p (2 -p) 2(1-1/r) ≤ C |∇f | 2 dµ.
It is well known that these inequalities interpolate between Poincaré and Log-Sobolev. For r = 1, the inequality ( 12) is Poincaré inequality SG(C) and for r = 2 it is equivalent to the Logarithmic-Sobolev inequality (see [START_REF] Latala | Between sobolev and poincaré. in geometric aspects of Functional Analysis[END_REF]Corollary 1]). The LO(r, C) inequalities on R were completely characterized by Barthe and Roberto in [START_REF] Barthe | Sobolev inequalities for probability measures on the real line[END_REF].

Recall that a probability measure µ on R d verifies the Logarithmic-Sobolev inequality with constant C, if for all smooth f ,

(13) Ent µ (f 2 ) ≤ C |∇f | 2 dµ where Ent µ (f 2 ) := f 2 log f 2 dµ -f 2 dµ log f 2 dµ . If µ verifies LO(r, C)
y→x |f (x) -f (y)| |x -y| 2 = d i=1 ∂f ∂x i 2 1/2 = |∇f | 2 (x),
for µ a.e. x ∈ R d , and so the length of the gradient equals the norm of the vector ∇f µ a.e.

Locally lipschitz function for d ω ( . , . ) and | . | 2 are related in the following way. A function

g : R d → R is locally Lipschitz for d ω ( . , . ) if and only if g • ω -1 is locally Lipschitz for | . | 2 . [(i)⇒(ii)] Define μ = ω ♯ µ. Let f : R d → R be locally Lipschitz for | . | 2 , then f • ω is locally Lipschitz for d ω ( . , .
), and

Var μ(f ) = Var µ (f • ω) ≤ |∇(f • ω)| 2 ω dµ ( * ) = |∇f | 2 2 • ω = |∇f | 2 2 dµ,
where ( * ) follows from the easy to check identity:

|∇(f • ω)| ω = |∇f | 2 • ω. [(ii)⇒(i)]
The proof is the same.

[(ii)⇒(iii)] Take f : R d → R such that f • ω -1 is of class C 1 . Then Var µ (f ) = Var μ(f • ω -1 ) ≤ |∇(f • ω -1 )| 2 2 • ω dµ = d i=1 1 ω ′ (x i ) 2 ∂f ∂x i (x) 2 dµ(x)
[(iii)⇒(ii)] Apply the weighted Poincaré inequality to the function f •ω with f of class C 1 .

2.2.

Poincaré inequalities and concentration -the abstract case. In order to recall how concentration estimates can be derived from the Poincaré inequality, let us briefly sketch the proof of Theorem 1.

Sketch of proof of Theorem 1.

[First step] According to [8, Theorem 3.1] (which is the main result of [START_REF] Bobkov | Poincaré's inequalities and Talagrand's concentration phenomenon for the exponential distribution[END_REF]), µ enjoys a modified Logarithmic-Sobolev inequality: for all 0 < s < 2

√

C and for all locally Lipschitz f : X → R such that |∇f | ≤ s µ a.e. one has [START_REF] Gross | Logarithmic sobolev inequalities[END_REF] Ent

µ (e f ) ≤ L(s) |∇f | 2 e f dµ, where L(s) = C 2 2+ √ Cs 2- √ Cs 2 e s √ 5C
.

[Second step] Tensorization. Thanks to the tensorization property of the entropy functional,

Ent µ n (e f ) ≤ n i=1 Ent µ (e f i ) dµ n , for all f : X n → R.
Applying this inequality together with ( 14) yields

(15) Ent µ n (e f ) ≤ L(s) n i=1 |∇ i f | 2 e f dµ,
for all 0 < s < 2 √ C and f : X n → R such that max 1≤i≤n |∇ i f | ≤ s µ n a.
e. [Third step] Herbst argument. Thanks to the homogeneity one can suppose that f :

X n → R is such that max 1≤i≤n |∇ i f | ≤ 1 (b = 1) and n i=1 |∇ i f | 2 ≤ a 2 .
Define Z(λ) = e λf dµ n . Then, applying [START_REF] Latala | Between sobolev and poincaré. in geometric aspects of Functional Analysis[END_REF] to λf , one easily obtains the following differential inequality

∀0 < λ ≤ s < 2 √ C , d dλ log(Z(λ)) λ ≤ L(s)a 2 ,
and since log(Z(λ))

λ ---→ λ→0 f dµ n , one gets ∀0 < λ ≤ s < 2 √ C , e λf dµ n ≤ e λ 2 L(s)a 2 +λ f dµ n [Fourth step]
Chebischev argument. This latter inequality on the Laplace transform yields via Chebischev argument:

∀t ≥ 0, µ n f ≥ f dµ n + t ≤ e -hs(t) ,
where

h s (t) = sup λ∈[0,s] {λt -L(s)a 2 λ 2 } = t 2 4L(s)a 2 if 0 ≤ t ≤ 2L(s)a 2 s st -L(s)a 2 s 2 if t ≥ 2L(s)a 2 s
Now it easy to see that, h s (t) ≥ min

t 2 4L(s)a 2 , st 2 . For s = 1/ √ C one obtains after some computations, h s (t) ≥ min t 2 Cκ 2 a 2 , t √ Cκ with κ = 18e √ 5 .

Sketch of proof of Corollary 2. Take

A ⊂ X n , such that µ n (A) ≥ 1/2 and define F (x) = inf a∈A n i=1 α(d(x i , a i ))
, where α(u) = min(|u|, u 2 ). Then for all r ≥ 0, the function f = min(F, r) verifies (see the details in [START_REF] Bobkov | Poincaré's inequalities and Talagrand's concentration phenomenon for the exponential distribution[END_REF]

): max 1≤i≤n |∇ i f | ≤ 2 and n i=1 |∇ i f | 2 ≤ 4r. Moreover since µ n (A) ≥ 1/2, one has f dµ n = f 1I A c dµ n ≤ r(1 -µ n (A)) ≤ r/2. Consequently, applying (3) to f yields: µ n (F ≥ r) = µ n (f ≥ r) ≤ µ n f ≥ f dµ n + r/2 ≤ e -rK(C) , with K(C) = 1 16 min 1 Cκ 2 , 1 √ Cκ = 1 16 α( 1 √ Cκ )
. This achieves the proof of (4).

2.3.

The SG(ω, C) inequality and concentration.

Proposition 11. Suppose that µ ∈ P(R d ) satisfies SG(ω, C) for some C > 0. Then for all n ≥ 1 and all A ⊂ R d n , one has

∀h ≥ 0, µ n A h ω ≥ 1 -e -K(C)h/d ,
where

K(C) = α 1 √
Cκ /16 and A h ω is defined by

A h ω =    (x 1 , . . . , x n ) ∈ R d n : inf a∈A n i=1 d j=1 α • ω |x i,j -a i,j | 2 ≤ h    . (For all 1 ≤ i ≤ n, x i,j , 1 ≤ j ≤ d are the coordinates of the vector x i ∈ R d .)
Remark 12. The fact that the dimension d appears in the preceding result is not important. The important thing is that the constants do not depend on the dimension n.

We need the following elementary lemmas:

Lemma 13. If f : R + → R is such that x → f (x)/x is non decreasing then f is super additive, that is to say: f (x + y) ≥ f (x) + f (y) for all x, y ≥ 0. Proof. Let 0 < x ≤ y ; f (x + y) = f (y(1 + x/y)) ≥ (1 + x/y)f (y) = f (y) + xf (y)/y ≥ f (y) + xf (x)/x = f (y) + f (x). Lemma 14. For all x, y ∈ R, |ω(x) -ω(y)| ≥ ω |x-y| 2 .
Proof. According to the Lemma 13, the function ω is super additive on R + . Let x ≥ y. If x ≥ y ≥ 0, then using the super additivity of ω, one gets ω(x) = ω((x -y) + y) ≥ ω(x -y) + ω(y), so ω(x) -ω(y) ≥ ω(x -y) ≥ ω((x -y)/2). If 0 ≥ x ≥ y, then, according to the preceding case, ω(x) -ω(y) = ω(-y) -ω(-x) ≥ ω((-y + x)/2) = ω((x -y)/2). If x ≥ 0 ≥ y, then ω(x) -ω(y) = ω(x) + ω(-y) ≥ ω(max(x, -y)) ≥ ω((x -y)/2).

Lemma 15. The function α(u) = min(|u|, u 2 ) is such that α(au) ≥ α(a)α(u), for all a, u ≥ 0.

Proof. If 0 < a ≤ 1, then α(au)/a = u 2 if u ≤ 1/a and α(au)/a = u/a if u ≥ 1/a. If u ≤ 1, one has α(au)/a = α(u). If u ∈ [1, 1/a],
then u 2 ≥ u and so α(au)/a ≥ α(u). If u ≥ 1/a, then u/a ≥ a and so α(au)/a ≥ α(u). The case a ≥ 1 can be handled in a similar way.

Proof of Proposition 11. First,

d ω (x, y) ≥ 1 √ d d i=1 |ω(x i ) -ω(y i )|, for all x, y ∈ R d . Now, α(d ω (x, y)) ≥ α d i=1 1 √ d |ω(x i ) -ω(y i )| (i) ≥ d i=1 α 1 √ d |ω(x i ) -ω(y i )| (ii) ≥ d i=1 α 1 √ d ω |x i -y i | 2 (iii) ≥ 1 d d i=1 α • ω |x i -y i | 2
where (i) comes from the super additivity of the function α, (ii) from Lemma 14 and (iii) from Lemma 15.

Consequently,

inf a∈A n i=1 α(d ω (x i , a i )) ≥ 1 d inf a∈A n i=1 α • ω |x i -y i | 2 .
Applying (4) yields immediately the desired result.

Proof of Proposition 4. Suppose p ∈ [START_REF] Aida | Logarithmic sobolev inequalities and exponential integrability[END_REF][START_REF] Aida | Moment estimates derived from poincaré and logarithmic sobolev inequalities[END_REF] ; in view of Theorem 11, it is enough to prove that

nd k=1 α • ω p (u k ) ≤ h ⇒ u = (u 1 , . . . , u nd ) ∈ √ hB 2 + h 1/p B p .
Let v = (v 1 , . . . , v nd ) and w = (w 1 , . . . , w nd ) be defined by

v k = u k if u k ∈ [-1, 1] and v k = 0 if |u k | > 1 and w = u -v. Then, nd k=1 α • ω p (u k ) = |v| 2 2 + |w| p p ≤ h. So, |v| 2 ≤ √ h and |w| p ≤ h 1/p . Since u = v + w, one concludes that u ∈ √ hB 2 + h 1/p B p . Now, if p ≥ 2, then ∀x ≥ 0, α • ω(x) ≥ x 2 and ∀x ≥ 0, α • ω(x) ≥ x p .
This observation together with Theorem 11 easily implies the result.

3. Workable sufficient conditions for SG(ω, C).

Dimension one.

Proof of Proposition 6. According to Muckenhoupt criterion, a probability measure dν = h dx having a positive continuous density with respect to Lebesgues measure, satisfies the classical Poincaré inequality if and only if

D -= sup x≤m ν(-∞, x]
μ = ω ♯ µ satisfies SG(C). The density of μ is h = h•ω -1 ω ′ •ω -1 .
Plugging h in Muckenhoupt conditions gives immediately the announced result.

Proof of Proposition 7. Let μ = ω ♯ µ and let ν be the symmetric exponential probability measure on R, that is the probability measure with density dν(x) = 1 2 e -|x| dx. It is well known that it verifies the following Poincaré inequality: [START_REF] Ledoux | The concentration of measure phenomenon, volume 89 of Mathematical Surveys and Monographs[END_REF] Var ν (g) ≤ 4 g ′2 (x) dν(x), for all smooth g (see for example [8, Lemma 2.1]). Let T : R → R be the map defined by

T (x) = F -1 μ • F ν (x), with F ν (x) = ν(-∞, x] and F μ(x) = μ(-∞, x]. It is well known that T
is increasing and transports ν on μ which means that T ♯ ν = μ. Let us apply inequality [START_REF] Ledoux | The concentration of measure phenomenon, volume 89 of Mathematical Surveys and Monographs[END_REF] to a function g = f • T . It yields immediately:

Var μ(f ) ≤ 4 f ′2 T ′ • T -1 2 dμ ≤ 4 sup x∈R T ′ (x) 2 f ′2 dμ
As a conclusion, if the map T is L Lipschtitz then μ verifies Poincaré inequality SG(4L 2 ).

The probability μ has density dμ(x) = e -Ṽ (x) dx, with Ṽ (x) = V (ω -1 (x))+ log ω ′ •ω -1 (x). It is proved in [START_REF] Gozlan | Characterization of talagrand's like transportation-cost inequality on the real line[END_REF] (see Proposition 34) that a sufficient condition for T to be Lipschitz is that

lim inf x→±∞ sgn(x) Ṽ ′ (x) > 0. But Ṽ ′ (ω(x)) = V ′ (x) ω ′ (x) + ω ′′ (x) ω ′2 (x)
and by assumption ω ′′ (x)

ω ′2 (x) → 0 when x goes to ∞. Thus lim inf x→±∞ sgn(x) Ṽ ′ (x) = lim inf x→±∞ sgn(x)V ′ (x) ω ′ (x)
, which achieves the proof.

Remark 16. The condition lim inf x→±∞ sgn(x)V ′ (x) ω ′ (x)
> 0 can also be derived from Proposition 6 using the same techniques as in e.g [START_REF] Ané | Sur les inégalités de Sobolev logarithmiques, volume 10 of Panoramas et Synthèses [Panoramas and Syntheses[END_REF]Theorem 6.4.3]. But this method has the disadvantage of introducing useless technical assumptions such as lim ±∞ V ′′ /(V ′2 ) = 0.

Remark 17. According to Theorem 10, the Logarithmic Sobolev inequality is stronger than the Poincaré inequality SG(ω 2 , C). In [START_REF] Cattiaux | Talagrand's like quadratic transportation cost inequalities[END_REF], P. Cattiaux and A. Guillin were able to construct a potential V on R satisfying V (-x) = V (x) and lim inf x→+∞ V ′ (x)/x > 0 but such that the probability measure dµ = e -V (x) dx does not satisfy the Bobkov-Gtze necessary and sufficient condition for the Logarithmic Sobolev inequality (see [START_REF] Bobkov | Exponential integrability and transportation cost related to logarithmic Sobolev inequalities[END_REF]). According to Proposition 7, this shows that the Logarithmic Sobolev inequality is strictly stronger than the inequality SG(ω 2 , C).

Dimension d.

Proof of Proposition 8. It is well known that a probability dν(x) = e -W (x) dx on R d satisfies the classical Poincaré inequality if W verifies the following condition: [START_REF] Marton | A simple proof of the blowing-up lemma[END_REF] lim inf

|x|→+∞ |∇W | 2 (x) -∆W (x) > 0
Suppose that µ is an absolutely continuous probability measure on R d with density dµ(x) = e -V (x) dx with V of class C 2 . Then μ = ω ♯ µ has density dμ(x) = e -Ṽ (x) dx, with

∀x ∈ R d , Ṽ (x) = V (ω -1 (x)) + d i=1 log ω ′ • ω -1 (x i ).
According to Proposition 5, to show that µ satisfies the inequality SG(ω, C) for some C > 0 it is enough to show that μ satisfies the inequality SG(C) and a sufficient condition for this is that Ṽ fulfills condition [START_REF] Marton | A simple proof of the blowing-up lemma[END_REF].

Elementary computations yield

∂ Ṽ ∂x i (ω(x)) = 1 ω ′ (x i ) ∂V ∂x i (x) + ω ′′ (x i ) ω ′2 (x i ) ∂ 2 Ṽ ∂x 2 i (ω(x)) = - ω ′′ (x i ) ω ′3 (x i ) ∂V ∂x i (x) + 1 ω ′2 (x i ) ∂ 2 V ∂x 2 i (x) + ω (3) (x i ) ω ′3 (x i ) -2 ω ′′2 (x i ) ω ′4 (x i ) Let I(x) = |∇ Ṽ | 2 (ω(x)) -∆ Ṽ (ω(x))
; one has:

I(x) = d i=1 1 ω ′2 (x i ) ∂V ∂x i 2 (x) - ∂ 2 V ∂x 2 i (x) +3 d i=1 ω ′′ (x i ) ω ′3 (x i ) ∂V ∂x i (x)+3 d i=1 ω ′′2 (x i ) ω ′4 (x i ) - d i=1 ω (3) (x i ) ω ′3 (x i ) .
Using the inequality uv ≥ -u 2 -v 2 /4, one has

3 d i=1 ω ′′ (x i ) ω ′3 (x i ) ∂V ∂x i (x) = 3 d i=1 ω ′′ (x i ) ω ′2 (x i ) • 1 ω ′ (x i ) ∂V ∂x i (x) ≥ -3 d i=1 ω ′′2 (x i ) ω ′4 (x i ) - 3 4 d i=1 1 ω ′2 (x i ) ∂V ∂x i 2 (x),
and so

I(x) ≥ d i=1 1 ω ′2 (x i ) 1 4 ∂V ∂x i 2 (x) - ∂ 2 V ∂x 2 i (x) - d i=1 ω (3) (x i ) ω ′3 (x i ) .
Since, lim inf |x|→+∞ I(x) = lim inf y→+∞ |∇ Ṽ | 2 (y) -∆ Ṽ (y) and

d i=1 ω (3) (x i ) ω ′3 (x i ) ≤ dM , one concludes that Ṽ satisfies (17) as soon as lim inf |x|→+∞ d i=1 1 ω ′2 (x i ) 1 4 ∂V ∂x i 2 (x) - ∂ 2 V ∂x 2 i (x) > dM.
Applying this latter condition to the probability measure µ u = (u Id) ♯ µ, (where Id is the identity function) which has density dµ u (x) = 1 u d e -V (x/u) dx gives the condition of Proposition 8.

Transportation-cost inequalities

Basic properties.

Proposition 18 (Tensorization). Suppose that µ ∈ P(X ) satisfies the transportation cost inequality [START_REF] Gozlan | Characterization of talagrand's like transportation-cost inequality on the real line[END_REF] with the cost function c(x, y), then µ n satisfies the transportation cost inequality on X n with the cost function c ⊕n (x, y) = n i=1 c(x i , y i ). In other words,

∀ν ∈ P(X n ), inf π∈P (ν,µ n ) n i=1 c(x i , y i ) dπ ≤ H(ν | µ n ),
where P (ν, µ n ) is the set of probability measures on X n × X n such that π(dx, X n ) = ν(dx) and π(X n , dy) = µ n (dy).

This result goes back to the first works of K. Marton on the subject (see [START_REF] Marton | A simple proof of the blowing-up lemma[END_REF][START_REF] Marton | Bounding d-distance by informational divergence: a method to prove measure concentration[END_REF]). A proof can be found in [START_REF] Gozlan | A large deviation approach to some transportation cost inequalities[END_REF].

Let us explain how to derive concentration inequalities from the inequality T(ω, a).

Proposition 19. If µ satisfies the transportation cost inequality T(ω, a), then for all n ≥ 1 and all A ⊂ R nd , ∀h ≥ 0,

µ n A h ω ≥ 1 - 1 µ n (A) e -hα(a/ √ d)/2 ,
where the enlargement is defined by

A h ω =    y = (y 1 , . . . , y n ) ∈ R d n : inf x∈A n i=1 n j=1 α • ω x i,j -y i,j 2 ≤ h    .
Remark 20. According to Theorem 9, if µ satisfies the inequality SG(ω, C) then it satisfies T(ω, a) with a = 1

√

Cκ . With this value of a the concentration inequality given by Proposition 19 is almost the same as the one derived in Proposition 11.

We will need the following lemma:

Lemma 21. The function α(u) = min(|u|, u 2 ) is such that α(x + y) ≤ 2(α(x) + α(y)), for all x, y ≥ 0. Proof. If x + y ≤ 1, then α(x + y) = (x + y) 2 ≤ 2(x 2 + y 2 ) = 2(α(x) + α(y)). Now, suppose that x + y ≥ 1. If x ≤ 1 and y ≤ 1, then α(x + y) = x + y ≤ (x + y) 2 ≤ 2(x 2 + y 2 ) = 2(α(x) + α(y)). If x ≤ 1 and y ≥ 1, then x ≤ y ⇒ x-2x 2 ≤ y ⇒ x+y ≤ 2(x 2 +y) ⇒ α(x+y) ≤ 2(α(x)+α(y)). If x ≥ 1 and y ≥ 1, then α(x + y) = x + y = α(x) + α(y) ≤ 2(α(x) + α(y)).
Proof of Proposition 19. If µ satisfies T(ω, a) on R d then according to Theorem [START_REF] Marton | Bounding d-distance by informational divergence: a method to prove measure concentration[END_REF], µ n satisfies the transportation cost inequality on R d n with the cost function c defined by

c : ((x 1 , . . . , x n ), (y 1 , . . . , y n )) ∈ R d n × R d n → n i=1 α(ad ω (x i , y i )).
Using the triangle inequality for the metric d ω ( . , . ) and Lemma 21, one has ∀x, y, z ∈ R d n , c(x, z) ≤ 2c(x, y) + 2c(y, z). Now, let ν 1 and ν 2 be two probability measures on R nd . Take π 1 ∈ P (ν 1 , µ n ) and π 2 ∈ P (µ n , ν 2 ), then one can construct three random variables X, Y, Z such that L(X, Y ) = π 1 and L(Y, Z) = π 2 (see for instance the Gluing Lemma of [START_REF] Villani | Topics in Optimal Transportation[END_REF] p. 208). Then, one has

T c (ν 1 , ν 2 ) ≤ E [c(X, Z)] ≤ 2E [c(X, Y )] + 2E [c(Y, Z)] = 2 c(x, y) dπ 1 (x, y) + 2 c(y, z) dπ 2 (y, z).
Optimizing on π 1 and π 2 gives

T c (ν 1 , ν 2 ) ≤ 2T c (ν 1 , µ n ) + 2T c (ν 2 , µ n )
Consequently, µ n satisfies the following symmetrized transportation cost inequality:

∀ν 1 , ν 2 ∈ P(R nd ), T c (ν 1 , ν 2 ) ≤ 2 H(ν 1 | µ n ) + 2 H(ν 2 | µ n ).
Take

dν 1 = 1I A dµ n and dν 2 = 1I B dµ n , then inf x∈A,y∈B c(x, y) ≤ T c (ν 1 , ν 2 ) ≤ 2 H(ν 1 | µ n ) + 2 H(ν 2 | µ n ) = 2 log(1/µ n (A)) + 2 log(1/µ n (B))
Letting c(A, B) = inf x∈A,y∈B c(x, y), one gets

µ (n) (A)µ (n) (B) ≤ e -c(A,B)/2 .
Defining B = {y : inf x∈A c(x, y) > h} one gets µ n (B) ≤ 1 µ n (A) e -h/2 . To obtain the announced inequality it is thus enough to compare A h ω and B. Take x = (x 1 , . . . , x n ) ∈ R d n and y = (y 1 , . . . , y n ) ∈ R d n ; then for all i ∈ 1, . . . , n, one has

α (ad ω (x i , y i )) (a) ≥ α   a √ d d j=1 |ω(x i,j ) -ω(y i,j )|   (b) ≥ d j=1 α a √ d |ω(x i,j ) -ω(y i,j )| (c) ≥ d j=1 α a √ d ω x i,j -y i,j 2 (d) ≥ α a/ √ d d j=1 α • ω x i,j -y i,j 2
Consequently, if inf x∈A n i=1 d j=1 α•ω x i,j -y i,j 2 √ d ≥ h/α(a/ √ d), then y belongs to B. From this follows that µ n (A h ω ) ≥ 1 -1 µ n (A) e -α(a/ √ d)h/2
, which achieves the proof.

Remark 22. The idea of deriving concentration estimates from transportation cost inequalities goes back to Marton seminal work [START_REF] Marton | A simple proof of the blowing-up lemma[END_REF]. The above proof is essentially due to Talagrand (see the proof of [25, Corollary

α s (t) = t 2 4L(s) if |t| ≤ 2L(s)s s|t| -L(s)s 2 otherwise with L(s) = C 2 2 + √ Cs 2 - √ Cs 2 e s √ 5C .
In particular, if one takes s = 1 √ C , then it is easy to check that α s (t) ≥ α t √ Cκ , where α(u) = min(|u|, u 2 ) and κ = 18e (where Id : R → R : x → x is the identity function.)

The converse is also true: Proposition 25. If µ satisfies T (Id, a) , for some a > 0, then µ satisfies the inequality SG( 1 2a 2 ).

The proof of Proposition 25 is classical and can be found in various places (see e.g the proofs of [6, Corollary 5.1] or [START_REF] Maurey | Some deviation inequalities[END_REF]Corollary 3]).

The second argument is a very simple contraction principle:

Proposition 26. Let µ be a probability measure on a metric space X ; if µ satisfies the transportation cost inequality with the cost function c : X × X → R + , and if T : X → Y is a measurable bijection then, T ♯ µ satisfies the transportation cost inequality with the cost function

(x, y) → c(T -1 (x), T -1 (y)).
This contraction principle goes back to Maurey's work on infimum convolution inequalities (see [START_REF] Maurey | Some deviation inequalities[END_REF]). A proof can also be found in [START_REF] Gozlan | Characterization of talagrand's like transportation-cost inequality on the real line[END_REF], where this simple property was intensively used to derive necessary and sufficient conditions for transportation cost inequalities on the real line.

Now let us apply the contraction principle together with Theorem 23 to prove that Poincaré inequalities SG(ω, C) and transportation-cost inequalities T(ω, a) are qualitatively equivalent.

Proof of Theorem 9. If µ satisfies SG(ω, C), then according to Proposition 5, ω ♯ µ satisfies the classical Poincaré inequality SG(C), and according to Theorem 23, this implies that ω ♯ µ satisfies T(Id, a), with a = 1

√

Cκ . According to the contraction principle, µ (which is the image of ω ♯ µ under the map ω -1 ) satisfies the transportation cost inequality with the cost function (x, y) → α (a|ω(x) -ω(y)| 2 ) = α (ad ω (x, y)) by definition of the metric d ω ( . , . ) (see [START_REF] Bobkov | Exponential integrability and transportation cost related to logarithmic Sobolev inequalities[END_REF]). Now suppose that µ satisfies T(ω, a) for some a > 0. According to the contraction principle, ω ♯ µ satisfies T(Id, a), and according to Proposition 25, this implies that ω ♯ µ satisfies SG( 1 2a 2 ). Using Proposition 5, one concludes that µ satisfies SG(ω, 1 2a 2 ). This achieves the proof. Remark 27. If µ satisfies the inequality T(ω, a), it is easy to show that it verifies the transportation cost inequality with the cost function

R d × R d → R + : (x, y) → α(a/ √ d) d i=1 α • ω x i -y i 2 .
In particular, the inequality SG(ω 2 , C) implies Talagrand's T 2 inequality, that is to say the transportation cost inequality with a cost function of the form (x, y) → a|x -y| 2 2 for some a > 0. We do not know if the converse is true.

Comparison with other functional inequalities

In this section we will perform a comparison between the inequalities SG(ω, C) and generalized Beckner-Latala-Oleszkiewicz inequalities introduced in [START_REF] Wang | A generalization of poincaré and log-sobolev inequalities[END_REF] and [START_REF] Barthe | Interpolated inequalities between exponential and gaussian, orlicz hypercontractivity and isoperimetry[END_REF]. Definition 28. Let T : [0, 1] → R + be a non decreasing function and µ be a probability measure on R d . One says that µ satisfies the generalized Beckner-Latala-Oleszkiewicz inequality with the function T and the constant C > 0, if for all smooth f , one has [START_REF] Marton | Bounding d-distance by informational divergence: a method to prove measure concentration[END_REF] sup

p∈(1,2) f 2 dµ - |f | p dµ 2/p T (2 -p) ≤ C |∇f | 2 dµ.
If µ verifies (18) one will say for short that µ satisfies the inequality BLO(T, C).

The LO(r, C) inequality corresponds to the function T (u) = u 2(1-1/r) .

Dimension free concentration results can be deduced from the inequality BLO(T, C). The following result follows easily from Proposition 29 and Corollary 30 of [START_REF] Barthe | Interpolated inequalities between exponential and gaussian, orlicz hypercontractivity and isoperimetry[END_REF].

Theorem 29. Let T : [0, 1] → R + be a non decreasing function. Define T (x) = T (1) for all x ≥ 1 and let ω T : R → R be such that ω T (-x) = -ω(x) for all x ∈ R and

(19) ∀t ≥ 0, ω -1 T (t) = t 0 √ T (1/u) du.
If µ satisfies the inequality BLO(T, C), then for all n ≥ 1 and for all 1-Lipschitz function f :

∀t ∈ R + \ T (1), 2 T (1) , µ n f ≥ f dµ + r ≤ e -α•ω T (t/(3 √ C)) .
We are going to prove the following result:

Theorem 30. Let T : [0, 1] → R + be a non-decreasing function such that x → T (x)/x is non-increasing. If the measure µ verifies the inequality BLO(T, C) for some constant C then it satisfies the inequality SG(ω T , C).

Let us admit Theorem 30 and let us prove Theorem 10.

Proof of Theorem 10. As noticed above, the inequality LO(r, C) is the same as BLO(T, C) with T (u) = u 2(1-1/r) . According to Theorem 30, µ verifies the inequality SG(ω T , C) for some C, where ω T is given by [START_REF] Maurey | Some deviation inequalities[END_REF]. A simple computation gives ω T (t) = t if t ∈ [0, 1] and ω T (t) = t r /r + 1 -1/r, if t ≥ 1. Thus, ω ′ T (t) = max(1, t r-1 ). On the other hand, ω ′ r (t) = 1, if t ∈ [0, 1] and ω ′ r (t) = rt r-1 . Thus, 1 r ω ′ r (t) ≤ ω ′ T (t) ≤ ω ′ r (t), for all t ≥ 0. Using [START_REF] Bobkov | Poincaré's inequalities and Talagrand's concentration phenomenon for the exponential distribution[END_REF], one concludes that µ verifies SG(ω T , C) for some C if and only if µ verifies SG(ω r , C) for some C. This achieves the proof.

The proof of this theorem relies on the capacity-measure formulation of the generalized Beckner-Latala-Oleszkiewicz inequalities due to Barthe, Cattiaux and Roberto [START_REF] Barthe | Interpolated inequalities between exponential and gaussian, orlicz hypercontractivity and isoperimetry[END_REF].

Let us recall the definition of a capacity-measure inequality (a good reference for this type of inequalities is the book of Maz'ja [START_REF] Mazja | Sobolev spaces[END_REF]).

Definition 31. Let µ be a probability measure on R d . Let A ⊂ Ω be Borel sets. One defines

Cap µ (A, Ω) = inf |∇f | 2 dµ; 1 I A ≤ f ≤ 1 I Ω .
The capacity of a set A with µ(A) ≤ 1/2 is defined by

Cap µ (A) = inf Cap µ (A, Ω) : A ⊂ Ω and µ(Ω) ≤ 1/2 = inf |∇f | 2 dµ; f : R d → [0, 1], f |A = 1 and µ(f = 0) ≥ 1/2
One says that µ satisfies a capacity-measure inequality if there is a function Θ : [0, 1] → R + and a constant D > 0 such that for all A with µ(A) ≤ 1/2, Θ(µ(A)) ≤ D Cap µ (A).

The following theorem due to Barthe, Cattiaux and Roberto (see Theorem 18 and Lemma 19 of [START_REF] Barthe | Interpolated inequalities between exponential and gaussian, orlicz hypercontractivity and isoperimetry[END_REF]) gives a capacity-measure transcription of the inequality BLO(T, C).

Theorem 32. Let T : [0, 1] → R + be a non-decreasing function such that x → T (x)/x is nonincreasing. Let C > 0 be the optimal constant such that µ verifies the inequality BLO(T, C).

Then 1/6D ≤ C ≤ 20D, where D is the optimal constant such that for all

A ⊂ R d with µ(A) ≤ 1/2, one has Θ(µ(A)) ≤ D Cap µ (A),
where Θ : R + → R + is defined by:

(20) ∀x ∈ R + , Θ(x) = x 1 T 1 log(1+ 1 x )
, with the convention that T (x) = T (1) for x ≥ 1.

Remark 33. In fact we will only use the fact that the inequality BLO(T, C) implies the measure-capacity inequality Θ(µ(A)) ≤ 6C Cap µ (A), for all A such that µ(A) ≤ 1/2. This is the easiest part of Theorem 32.

To prove Theorem 30, one needs the following basic properties: Lemma 34. If T : [0, 1] → R + is a non-decreasing function such that x → T (x)/x is nonincreasing then the function Θ defined by ( 20) is non-decreasing and verifies Θ(x + y) ≤ Θ(x) + Θ(y) for all x, y ∈ R + .

Proof. Let us write:

Θ(x) = x h(x) • h(x) T (h(x)) with h(x) = 1 log(1 + 1/x) .
The function h is non-decreasing, and since u → u T (u) is non-decreasing, one concludes that x → h(x) T (h(x)) is non decreasing. On the other hand, it is easy to see that the function x → x h(x) = x log(1+1/x) is non-decreasing. As a product of non-decreasing and non-negative functions, the function Θ is itself non-decreasing. Take x ≥ y > 0 ; using the fact that the function x → Θ(x)/x is non-increasing, one gets

Θ(x + y) = Θ(x(1 + y/x)) ≤ (1 + y/x)Θ(x) = Θ(x) + yΘ(x)/x ≤ Θ(x) + Θ(y).
This achieves the proof.

Another ingredient of the proof is the following lemma which explains how behave capacitymeasure inequalities under push-forward: Lemma 35. Suppose that µ satisfies the capacity-measure inequality

∀A with µ(A) ≤ 1/2, Ψ(µ(A)) ≤ D Cap µ (A). Then μ = ω ♯ µ verifies the inequality ∀A with μ(A) ≤ 1/2, Ψ(μ(A)) ≤ DCap μ(A),
where

Cap μ = inf d i=1 ω ′ • ω -1 (x i ) 2 ∂f ∂x i 2 (x) dμ; f : R d → [0, 1], f |A = 1 and μ(f = 0) ≥ 1/2 .
Proof. Let A be such that μ(A) ≤ 1/2, and f be such that f = 1 on A and μ(f = 0) ≥ 1/2. Define B = ω -1 (A) and g = f • ω. Then µ(B) = μ(A) ≤ 1/2, g ≥ 1 on B and {g = 0} = ω -1 {f = 0} and so µ(g = 0) = μ(g = 0) ≥ 1/2. Applying the capacity-measure inequality verified by µ to B and g yields

μ(A) = µ(B) ≤ D |∇g| 2 dµ = D d i=1 ω ′ • ω -1 (x i ) 2 ∂f ∂x i 2 (x) dμ.
Optimizing over such functions f gives the announced inequality for μ.

The next lemma explains how to compare the capacity Cap μ to the usual capacity Cap µ : Optimizing over f yields:

Lemma 36. Let B ∞ (r) = x ∈ R d : max 1≤i≤d |x i | ≤ r , for all r ≥ 0. If A ⊂ B ∞ (r) and µ(A) ≤ 1/2, then Cap μ(A) ≤ 2 ω ′ • ω -1 (r + 1) 2 Cap μ(A) + 8dμ(B ∞ (r) c ). Proof. Let Cap r μ(A) = inf |∇f | 2 dμ; 1I A ≤ f ≤ 1I B∞ (
Cap r μ(A) ≤ 2 Cap μ +8dμ(B ∞ (r) c ).

Proof of Theorem 30. Define μ = ω ♯ T µ. One wants to prove that μ verifies the classical Poincaré inequality. According to Theorem 32, the probability measure µ satisfies the capacity-measure inequality [START_REF] Muckenhoupt | Hardy's inequality with weights[END_REF] ∀A with µ(A) ≤ 1/2, Θ(µ(A)) ≤ 6C Cap µ (A).

According to Lemma 35, μ satisfies the capacity-measure type inequality:

∀A with μ(A) ≤ 1/2, Θ(μ(A)) ≤ 6CCap μ(A),

where Cap μ is defined in the lemma.

Let B ∞ (r) = x ∈ R d : max 1≤i≤d (|x i |) ≤ r , for all r ≥ 0. Let A ⊂ R d with μ(A) ≤ 1/2; one has Θ(μ(A)) where (i) follows from the sub-additivity and the monotonicity of Θ, (ii) from Lemma 35, (iii) from Lemma 36 and (iv) from the fact that the function A → Cap μ(A) is non decreasing and from the immediate inequality x ≤ T (1)Θ(x) which holds for all x ≤ 1. Using Theorem 29, it is not difficult to see that one can find K ≥ 1 and 1 ≥ u 0 > 0 such that μ (B ∞ (r) c ) ≤ Ke -u 0 r for all r ≥ 0. Thus Θ (μ (B ∞ (r) c )) ≤ Θ(Ke -u 0 r ) ≤ KΘ(e -u 0 r ) , where the last inequality follows from the sub-additivity of Θ. So, letting a 1 = 12C Cap μ(A), a 2 = (48dCT (1) + 1)K and t = μ(A) and using the definitions of Θ and ω T , one has:

t 1 T 1 log(1+1/t) ≤ a 1 1 T 1 1+r
+ a 2 e -u 0 r 1 T 1 log(1+e u 0 r ) .

Using the inequality 1 + u 0 r ≥ u 0 (1 + r) together with the sub-additivity property of the function T , one sees that

1 T ( 1 1+r ) ≤ 1 u 0 T 1 1+u 0 r
. Thus the preceding inequality implies:

∀v ≥ 0, t 1
T 1 log(1+1/t) ≤ a 1 u 0 1 T 1 1+v + a 2 e -v 1 T 1 log(1+e v )
. Now, observe that (1 + e v ) 3 ≥ 3e v , so 3 log(1 + e v ) ≥ log(3) + v ≥ 1 + v, and so

1 T ( 1 1+v ) ≤ 1 T 1 3 log(1+e v ) ≤ 3 T 1 log(1+e v )
where the last step follows from the sub-additivity property of T . So, ∀v ≥ 0, t 1

T 1 log(1+1/t) ≤ 3a 1 u 0 + a 2 e -v 1 T 1 log(1+e v )
.

Let n ∈ N * ; taking v = -n log(t) in the preceding inequality gives:

t

( 2 )

 2 |∇f |(x) := lim sup y→x |f (x) -f (y)| d(x, y) .

1. 3 . 2 .Proposition 5 .

 325 Links with the classical Poincaré inequality. In Section 2, we prove the concentration results and we relate the exotic Poincaré inequalities SG(ω, C) to (weighted) forms of the classical Poincaré inequality: Let µ be a probability measure on R d and C a positive number. The following properties are equivalent.

2 . 2 . 1 .

 221 then a concentration inequality of the same order as the one given in Proposition 4 holds (see[START_REF] Latala | Between sobolev and poincaré. in geometric aspects of Functional Analysis[END_REF] Theorem 1]). In fact, one has the following Theorem 10. Let r ∈[START_REF] Aida | Logarithmic sobolev inequalities and exponential integrability[END_REF][START_REF] Aida | Moment estimates derived from poincaré and logarithmic sobolev inequalities[END_REF] ; if µ verifies the Latala-Oleszkiewicz inequality LO(r, C) for some C > 0 then it satisfies the Poincaré inequality SG(ω r , C) for some constant C, where ω r (x) = x r on R + . Moreover, a counter example of Cattiaux and Guillin shows that the Logarithmic-Sobolev inequality is strictly stronger than the inequality SG(ω 2 , C) (seeRemark 17). Weighted forms of the Poincaré inequality Links with the classical Poincaré inequality.Proof of Proposition 5. Let us denote |∇f | ω (resp. |∇f | 2 ) the length of the gradient computed with respect to the metric d ω ( . , . ) (see[START_REF] Aida | Moment estimates derived from poincaré and logarithmic sobolev inequalities[END_REF]). If f : R d → R is locally Lipschitz for the euclidean metric, then according to Rademacher theorem, one has lim sup

  constant C opt verifies max(D -, D + ) ≤ C opt ≤ 4 max(D -, D + ). Now, according to Proposition (5) µ satisfies SG(ω, C) if and only if

  where (a) follows from the comparison between the norms | . | 2 and | . | 1 in R d , (b) from Lemma 13, (c) from Lemma 14 and (d) from Lemma 15.

. 2 √

 2 Links with Poincaré inequality. The proof of Theorem 9 relies on two ingredients. The first one is the following result by Bobkov, Gentil and Ledoux: Theorem 23 (Bobkov,Gentil, Ledoux). If a probability measure µ on R d satisfies SG(C) then it satisfies the transportation cost inequality for the cost function (x, y) → α s (|x -y| 2 ) for all s <

√ 5 . 2 √.

 52 Thus if µ satisfies SG(C) it satisfies the transportation cost inequality with the cost function (x, y) → α |x-y| Cκ In other words, with the definition of the transportation cost inequality T (ω, a), the preceding result can be restated as follows Corollary 24. If µ is a probability measure on R d satisfying the classical Poincaré inequality SG(C) for some C > 0, then it satisfies the transportation-cost inequality T Id, 1 √ Cκ .

2 .

 2 r+1) and μ(f = 0) ≥ 1/Using the fact that the function ω ′ • ω -1 is increasing on R + , one clearly has:Cap μ(A) ≤ ω ′ • ω -1 (r + 1) 2 Cap r μ(A).Now let f : R d → [0, 1] be such that f |A = 1 and μ(f = 0) ≥ 1/2. One can easily construct a cut-off function ϕ such that: 1I B∞(r) ≤ ϕ ≤ 1I B∞(r+1) , and such that ∂ϕ ∂x i (x) ≤ 2 for all x ∈ R d and all i.Let g = f ϕ; one has 1I A ≤ g ≤ 1I B∞(r+1) , μ(g = 0) ≥ μ(f = 0) ≥ 1/2 and Cap r μ(A) ≤ |∇g| 2 dμ = |∇f ϕ + f ∇ϕ| 2 dμ ≤ 2 |∇f | 2 ϕ 2 dμ + 2 f 2 |∇ϕ| 2 dμ ≤ 2 |∇f | 2 dμ + 8dμ(B ∞ (r) c ).

≤

  Θ (μ (A ∩ B ∞ (r))) + Θ (μ (B ∞ (r) c )) (ii) ≤ 6CCap μ(A ∩ B ∞ (r)) + Θ (μ (B ∞ (r) c )) .

≤

  12C ω ′ T • ω -1 T (r + 1) 2 Cap μ(A ∩ B ∞ (r)) + 48dC μ(B ∞ (r) c ) + Θ (μ (B ∞ (r) c )) .

≤

  12C ω ′ T • ω -1 T (r + 1) 2 Cap μ(A) + (48dCT (1) + 1) Θ (μ (B ∞ (r) c )) ,

  |∇ i f | ≤ b, µ n a.e. (where |∇ i f | denotes the length of the gradient with respect to ith the coordinate) one has

	(3)
	∀t ≥ 0,	µ n f ≥ f dµ n + t ≤ exp -min	t 2 Cκ 2 a 2 ,	t Cκb √	,	with κ = 18e
		n
	such that	i=1	|∇ i f | 2 ≤ a 2 and max i=1,...,n

and S.G. Bobkov proved the following theorem (see [8, Corollary 3.2]) Theorem 1 (Bobkov-Ledoux). If µ satisfies (1), then for every bounded function f on X n

  It is easy to check that if n is sufficiently large, there is m > 0 such that for all t ∈ [0, 1/2], one has t n -a 2 t n ≥ mt. So mt ≤ 3a 1 u 0 , that is to say Capacity-measure inequality of this form is well known to imply the Poincaré inequality (see e.g [4, Proposition 13 and Remark 20]).

	T	1 log(1+1/t) 1	≤	3a 1 u 0	+ a 2 t n	T	1 log(1+(1/t) n ) 1	.
	Now, (1 + (1/t) n ) ≤ (1 + 1/t) n , thus	T	1 1 log(1+(1/t) n )	≤	T	1 1 n log(1+1/t)	≤	T	n log(1+1/t) 1	and
	consequently,
			t n	≤		3a 1 u 0	+ a 2 t n .
			μ(A) ≤	36C u 0 m	Cap μ(A).

A


Vlasta Stavova
email: vlasta.stavova@mail.muni.cz

Vashek Matyas
email: matyas@fi.muni.cz

Mike Just
email: m.just@hw.ac.uk

A Comparative Usability Study of Two Password Recovery Mechanisms

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Nearly every website that enables users to create an account also provides a process to recover the account, in case of a forgotten password, for example. This process is referred to by many names, such as account recovery, password recovery, password reset, secondary authentication and last-resort authentication [START_REF] Bonneau | The Password Thicket: Technical and Market Failures in Human Authentication on the Web[END_REF][START_REF] Just | Personal choice and challenge questions: a security and usability assessment[END_REF][START_REF] Schechter | It's not what you know, but who you know: a social approach to last-resort authentication[END_REF]. The recovery process should be usable, and as secure as the access to the account via the primary authentication.

Researchers have shown that passwords, as a primary form of authentication, are indeed forgotten or lost, so that some form of recovery is required [START_REF] Florencio | A large-scale study of web password habits[END_REF][START_REF] Moallem | Did You Forget Your Password? In: Design, User Experience, and Usability[END_REF]. Though current recovery solutions, such as the answers to challenge questions, are proven not to be reliable and secure enough [START_REF] Bonneau | Secrets, lies, and account recovery: Lessons from the use of personal knowledge questions at google[END_REF]. Moreover, there are several examples of attackers gaining access to an account due to weak password recovery [START_REF] Cubrilovic | The Anatomy Of The Twitter Attack[END_REF][START_REF] Honan | How Apple and Amazon Security Flaws Led to My Epic Hacking[END_REF][START_REF]Wikipedia: Sarah Palin email hack -Wikipedia, The Free Encyclope[END_REF].

There are several ways in which password or account recovery can be performed, including the use of challenge questions, out-of-band communications (using email or SMS), calling a help-desk operator, using password hints or backup codes, or using a trusted person. Research in 2010 indicated that out-of-band communications and challenge questions were the most frequent methods used [START_REF] Bonneau | The Password Thicket: Technical and Market Failures in Human Authentication on the Web[END_REF]. For the most part, current password recovery processes have maintained this trend. For example, Dropbox's password recovery process consists of an out-ofband email with a link to reset user's password [START_REF]I forgot my password[END_REF]. Google services use a recovery email address or recovery phone number [START_REF]Set up a recovery phone number or email address[END_REF]. If a user has no access to his recovery email, phone or any other option, the user's identity can be verified by answering several questions about his account [START_REF]I'm having trouble resetting my password[END_REF].

Three security questions must be answered by a user to recover his password for Apple services (iCloud, the App Store, the iTunes Store and more) [START_REF]Security and your Apple ID[END_REF]. All previously mentioned web services also support two-factor authentication. Since this option usually requires the combination of a computer and a mobile phone, there must be an approach to when the mobile phone is lost, stolen, or outof-order. One common approach involves an emergency backup (QR) code. For example, after enabling two factor authentication in Dropbox 4 , a user receives a special 16-digit backup code. The user must write this key down and store it somewhere safe. In case of losing his phone, this code may be used for an emergency access to the system [START_REF]How do I enable two-step verification on my account[END_REF]. Google users who use two factor authentication may download a backup code too or may add a backup phone in addition to the standard one [START_REF]Set up a recovery phone number or email address[END_REF]. Very similarly, Apple users get a recovery key for two factor authentication to be used when the trusted device is lost [START_REF]Security and your Apple ID[END_REF]. As an alternative to a backup code, researchers have also investigated using trusted people to support recovery [START_REF] Schechter | It's not what you know, but who you know: a social approach to last-resort authentication[END_REF], and at least Facebook has deployed such a solution, referred to as "trusted contacts" 5 .

In this paper, we evaluate two password recovery methods based on the above-mentioned techniques: backup codes and cooperation of a trusted person. Both recovery methods were shortlisted by a company SODATSW. that offers secure data solutions. This company wanted to evaluate both solutions and compare them in terms of usability. The company agreed to use students as participants with the condition that both IT and non IT oriented students would be involved into study. Thus, our task was to evaluate the usability of these two methods in order to determine their suitability as a viable option for password recovery and discuss possible further research and deployment consideration for other methods of password recovery.

To achieve our goal, we conducted a study with 186 student participants in order to compare the two password recovery methods.

In Section 2 we describe the related work in the area of password recovery. Section 3 introduces our approach to the design of the two password recovery methods, while Section 4 specifies the experiment design. Section 5 explains the experiment analysis and we conclude in Section 6.

Related Research

In this section we highlight relevant research related to currently used techniques for the recovery (security questions, and out-of-band communications), as well as previous work on the two methods we investigate in this paper (backup codes and trusted people).

Current Recovery Techniques

A recent study by Google concluded that security questions are neither secure nor reliable enough to be used as a standalone account recovery mechanism [START_REF] Bonneau | Secrets, lies, and account recovery: Lessons from the use of personal knowledge questions at google[END_REF]. As a major issue, security questions might get successfully guessed. High guessability may be caused by using publicly available answers (16% of answer can be found in social network profiles [START_REF] Rabkin | Personal knowledge questions for fallback authentication: Security questions in the era of facebook[END_REF]), using answers available to user's family and close friends (they can guess 17% of answers correctly in less than five attempts [START_REF] Schechter | It's no secret. measuring the security and reliability of authentication via secret questions[END_REF]) or small answer spaces (more than 40% security questions have small answer spaces [START_REF] Just | Personal choice and challenge questions: a security and usability assessment[END_REF][START_REF] Rabkin | Personal knowledge questions for fallback authentication: Security questions in the era of facebook[END_REF]). The other disadvantage connected to security questions is that users tend to forget their own answers. Research [START_REF] Schechter | It's no secret. measuring the security and reliability of authentication via secret questions[END_REF] showed that participants forgot 20% of their own answers within six months. Considering the fact that password recovery is often a last-resort option to regain access to a system, this is a very serious drawback leading to user frustration and potentially to more expensive forms of recovery, such as through a help desk. As a solution to this issue, researchers have tested an approach where questions were chosen by users themselves [START_REF] Just | Personal choice and challenge questions: a security and usability assessment[END_REF]. The approach was based on the idea that users will choose questions familiar to them, and thus they will not have a problem to recall answers. Contrary to expectations, the approach did not bring the anticipated improvement.

Out-of-band communications for password recovery (also used for secondary authentication) have risen in popularity, for example Google strongly prefers out-of-band password recovery (via SMS or email) over security questions [START_REF] Bonneau | Secrets, lies, and account recovery: Lessons from the use of personal knowledge questions at google[END_REF].

Despite their importance for secondary authentication, and the fact that smart phones aggregate many potentially sensitive functions, more than 60% of smart phone users do not lock their device [START_REF]Smart phone thefts rose to 3.1 million in 2013[END_REF]. This poses a threat for password recovery based on out-of-band communication (via email or SMS). Further, smart phone theft is a serious issue. About 3.1 million smart phones were stolen in USA in 2013. Moreover, 1.4 million smart phones were lost and never recovered in the same year [START_REF]Smart phone thefts rose to 3.1 million in 2013[END_REF]. When the smart phone is stolen, an attacker may initiate the password recovery based on the SMS or gain free access to an email account which can be also be misused for password recovery. When a user does not react quickly and does not change all his secondary authentications connected with the smart phone, his accounts may become compromised. Recent research on two-factor authentication demonstrates that given one compromised device, either a PC or a mobile phone, an attacker is able to compromise another one by launching a cross-platform infection attack [START_REF] Dmitrienko | On the (in) security of mobile two-factor authentication[END_REF].

In terms of usability, Bonneau et al. [START_REF] Bonneau | Secrets, lies, and account recovery: Lessons from the use of personal knowledge questions at google[END_REF] compared the main account recovery methods (SMS reset code, email and security questions) used in a Google environment. While they showed that out-of-band communication channels like SMS and email have a higher success rate (respectively 80% and 74%) than security questions (ranges from 44% to 60%), the highest success rate still leaves a 20% failure.

Existing Research on Codes and People

Recovery based on a backup code is used by several account providers, especially for the recovery process for two-factor authentication. However, it has received only limited attention in the research literature. The use of a backup code should reduce the instances of "being forgotten" or of a smart device becoming lost or not working properly, as the code is typically stored offline. The backup code may be provided to the user in a plain text or shown in a more sophisticated way, for example as a QR code.

Saving a code as a QR code instead of a written, alphanumeric code may have several benefits. For example, it might avoid errors when entering the code during recovery, as it may simply be more convenient to scan rather than type.

A QR code is a two-dimensional barcode that can include up to 4296 alphanumerical characters -a string long enough to store a strong password. All devices equipped with a camera and a QR code decoding application can serve as a QR code reader. Authentication using a QR code has been already presented in the literature [START_REF] Lee | Online banking authentication system using mobile-OTP with QR-code[END_REF][START_REF] Liao | A novel user authentication scheme based on QR-code[END_REF], but it was mainly designed for primary authentication. One step of these authentication schemes is to send a QR code with encoded information from a service provider to a user. The user decodes information stored in the QR code and generates a one-time password. The use of the QR code serves as an alternative to a security card in both cases. Unfortunately, the approach from [START_REF] Liao | A novel user authentication scheme based on QR-code[END_REF] relies on the fact that user's smart phone must be well protected since the smart phone stores a user's long-term secret key. Similarly, another approach [START_REF] Lee | Online banking authentication system using mobile-OTP with QR-code[END_REF] also relies on information stored in a user's smart phone. Thus, smart phone theft poses a danger for both approaches.

A more recent approach for password recovery is to use a trusted party. This method relies on a user's trusted person or people to help him recover an account access.

This method seems to be a good match to use with social networks where trusted people are selected by the user from his trustworthy friends. For example, this method is used at Facebook and was studied in Microsoft Live ID [START_REF] Schechter | It's not what you know, but who you know: a social approach to last-resort authentication[END_REF]. The tested approach was based on requesting recovery codes by user's trusted friends via specialized web interface. The user must collect from them at least three codes out of four to regain access to the system.

When a Facebook user forgets his password, he must contact his trusted friends to send a recovery request to the provider and obtain the security code. The user must collect at least three codes from three to five selected trusted friends [START_REF] Gong | On the security of trustee-based social authentications[END_REF]. The trusted party based method is prone to Forest fire attack [START_REF] Gong | On the security of trustee-based social authentications[END_REF], which misuses the fact that the user and his trusted friends are all members of one single system. If a small subset of users are compromised, all friends who trust them can be compromised too. As the number of compromised accounts rises, even more users may be compromised. In other words, it spreads like a forest fire.

Our Password Recovery Approaches

When designing password recovery processes, we discussed all of our approaches with SODATSW company designing a new secure data storage solution. The company insisted on a balance between usability, security and resistance to a smart phone theft. Based on SODATSW requirements, a Master thesis [START_REF] Hamerník | Autentizační metody používané k obnově přihlašovacího hesla[END_REF] reviewing possible approaches to password recovery was written, also suggesting some new ones. After a final round of discussions with the company, we agreed to test the approach based on a QR code and the other based on a trusted person.

Password Recovery via One-Time Password Stored in a QR Code

We designed a simple password recovery process using the backup code in the form of the QR code. The steps of this process are as follows:

1. A user receives a QR code via a registered letter (or any other service that guaranteed delivery to the receiver) and hides it in a secret place. The QR code contains a backup code. 2. If the user forgets his password, the recovery process can be initiated. 3. To start the recovery, the user scans the QR code. 4. The user inserts his user name into a system and retypes the code from the QR code reader into the system. When the user has a smart phone with the QR code reader and Internet access, he may open the system in the smart phone and copy and paste the code directly. 5. The system requires setting a new password. 6. After setting a new password, the user gains access to the system. The QR code is not bound to a specific device, so when a user's own smart phone is stolen, the user can utilize any other QR code reader. It is also a disadvantage, because any QR code reader can read the QR code with the backup code. This increases requirements for the secret distribution and storage of the QR code. The user is instructed to securely store the QR code together with his important contracts. It is also strictly forbidden for the user to scan the QR code in an advance and store it in the smart phone (though this might be difficult to enforce).

Unlike a one-time password stored as text on a piece of paper, a one-time password stored as a QR code enables a user to copy a decoded password directly from a smart phone application to the system which can be opened in the smart phone. Of course, when the user has only a QR reader without an access to the Internet, password retyping is unavoidable. A possible drawback is when the recovery password from a QR code is used, a new QR code must be securely distributed to the user. Company SODATSW is aware of it and plans to use this solution only in countries that have necessary infrastructure. As far as costs are concerned, QR codes are not expensive to produce, but the price of secure distribution must be taken into account.

Trusted Party Based Password Recovery

Unlike the use of a QR backup code, the use of a trusted party is based on shared inter-personal trust. To balance usability and also take into account a potential problem with low willingness to provide a phone number of a user's friends, we decided to require only one trusted person for each user (and the user himself also actively participates in the recovery). The trusted person may or may not be another system user. The user is expected to set family members or co-workers as a trusted person to decrease the probability of a Forest fire attack [START_REF] Gong | On the security of trustee-based social authentications[END_REF].

A step-by-step password recovery process (see also Figure 1) was designed as follows:

1. During the registration process, a user registers his phone number and also the phone number of the person he trusts. 2. When a password is lost or forgotten, the user will call the client center. 3. If the phone number he used for a call matches with the phone number registered in the system, a client center operator sends him a first half of a backup code via SMS. 4. The user must instruct his trusted person to call the client center and ask for a second half of the password. 5. The trusted person who recognizes the user's voice or appearance will do the task. If the trusted person's phone number matches with the phone number registered in the system, the operator sends the other half of the code to the user. 6. The user inserts his user name and both codes into the system. 7. The system requires setting a new password. 8. After setting a new password, the user gains an access to the system.

If an attacker steals a user's mobile phone, he does not know which of his friends is the trusted person. Even if the attacker knows this information, he must convince the trusted person to call the client center. To increase overall security and to decrease the probability of impersonating the user by an attacker, users are encouraged to instruct their trusted party to proceed with a call to the client center only after proper identification. For example, the user should instruct the trusted party to call a client center only during a face-to-face meeting or a phone call.

One disadvantage of this process is that during registration users may not fully think about the prospect of a password recovery and might be less likely to submit the phone number of an appropriately reliable and trusted person. Further, this person may change during a user's life and it would be important to keep this information up-to-date. Also, it is not the most efficient recovery process due to the fact that the trusted person may be away (for example on business trip, on holiday) when his call is necessary. This recovery method is also based on the user's phone number being registered into the system. If a user loses his number and in the same time forgets his password, this password recovery can not be successfully processed. The other issue may be that people might forget which person they designated. But similarly, they can forget the response for a security question (as we mentioned in the previous section). Recovery costs are higher, because the client center must be available, but the interaction may be automated.

Experiment Design

To compare both approaches, an experiment in cooperation of Faculty of Social Studies and Faculty of Informatics was designed. The experiment design was undertaken in accordance with experimental and ethical regulations of our university.

The experiment ran in May and June 2015 and the main aim of the experiment was to compare both approaches. There were 186 participants in total (of the original 203 who underwent full registration), half of them from the Faculty of Informatics, the other half together from other faculties (mainly from Faculty of Social Studies, Faculty of Law and Faculty of Arts). We used a within-subject experiment design -all participants went through both recovery approaches, and we alternated the order of their encounter so that half started with backup codes, and half with the trusted person approach. We collected quantitative data (but not qualitative) from this experiment.

To support our recruitment, we made a short presentation to students from several faculties at the start of one of their lectures. After an initial experiment presentation, participants obtained an envelope with a letter describing the process of the entire experiment, with a login and password to the system and a QR code (14 characters, charset size is 62) to be used for one password recovery. Each participant went through a two-week process. We prepared two online tasks for participants and two password recoveries (see also Figure 2). We also separated participants into halves. Half of them went through the QR code recovery on the seventh day and the trusted person recovery on the day 15. The other half of participants used a an opposite recovery order. The experiment length was two weeks for each participant. We estimated that the time spent in the experiment would be 45 minutes for each participant.

-When participants first logged into the system, they filled an initial questionnaire, provided their demographics and information necessary for both recoveries (their phone number, their trusted person's phone number). We only mentioned that it should be a person of trust, for example, a good friend or a family member. -On the fourth day after the first login, participants were encouraged to log into the system and to execute a short task of computing a number of characters in an attached PDF file. The purpose of this step was to attempt to maintain an active, realistic environment for participants. -On the seventh day of the experiment, participants were asked to process a first recovery. Half of the participants went through a recovery using their QR code, and the other half used the trusted party based recovery. After completing the recovery, participants filled a questionnaire to evaluate it. -On the eleventh day participants were asked to complete a second task. The task was to find a concrete paper, read through it, find one particular piece of information and insert it into the system. -Fifteen days after the experiment started, participants completed their second password recovery and filled in a final, longer questionnaire where they evaluated and compared both recovery processes.

We sent email reminders to participants to remind them to perform the above tasks. As a motivation to join the experiment, we offered $400 and 25 32GB MicroSD cards to 26 randomly chosen participants who went through all experiment steps.

Experiment Results and Analyses

Participants

There were 186 participants in total (of the 203 undergoing full registration). All participants were students of our university (for a detailed breakdown see Table 1). All of them have at least secondary education. The experiment had 5 phases, and participants went through the initial questionnaire, two tasks and two password recoveries. 132 participants out of 186 finished all phases. Half of the 132 participants went through the QR code recovery first followed by the trusted party. The other half (also 66) went through the process in an alternate order.

The majority (117) of participants were aged 19-22 years, while 69 participants were between 23 and 26 years. For a detailed view of when participants decided to leave the experiment, see Table 2. The fact that all participants were students is a limitation, though participants were recruited from both IT and non IT related programs. Since all participants are young people, we expect that they are more technically skilled than older generation.

Recovery Method Evaluation

Participants went through two password recoveries in the experiment. After each recovery, participants evaluated the recovery in four categories. There were 132 participants who performed these evaluations (we involved only those who went through both recoveries). We did not observe any significant difference in answers between participants who had started with one recovery method versus the other.

-Difficulty: How difficult was it for you to use the recovery? The Likert scale was used for responses from 1 (totally easy) to 6 (totally difficult). We conducted a paired t-test analysis and it proved that the QR code password recovery is considered by participants to be less difficult (mean=1.72, SD=1.1) than the trusted party based recovery (mean=2.79, SD=1.56) (t(132)=7.37, p<0.001). We did not observe any significant difference between men (mean=2.57, SD=1.49) and women (mean=3.067, SD=1.60) in evaluating difficulty of the trusted party recovery (t(133)=-1.92, p=0.057) and also no significant difference between men (mean=1.71, SD=0.12) and women (mean=1.72, SD=0. IT and non IT participants had no difference in evaluating advanced security of both the QR code based recovery (t(147)=-1.61, p=0.108) and the trusted party based recovery (t(133)=-1.17, p=0.24).

There is no significant correlation for age and advanced security of the QR code based recovery (r=-0.007, p=0.929) and the trusted party based recovery (r=0.125, p=0.14). -User friendliness: How user friendly do you consider the recovery? The Likert scale was from 1 (totally user friendly) to 6 (totally user unfriendly). The paired t-test proved that the QR based password recovery is considered to be more user friendly (mean=2, SD=1.2) than the trusted party based recovery (mean=3.58, SD=1.57), (t(132)=9.83, p<0.001).

There is no significant difference in user friendliness of both recoveries for men and women (QR code recovery: (t(148)=0.00, p=1), trusted party based recovery (t(133)=0.44, p=0.65)). We observed significant difference in evaluating user friendliness of IT and non IT respondents in the QR code based recovery (t(148)=2.41, p=0.017), but no difference in the trusted party based recovery (t(133)=-0.628, p=0.531). IT participants (mean=1.77, SD=1.107) evaluated the QR code based recovery more user friendly than non IT participants (mean=2.25, SD=1.35).

There is also a significant but weak correlation between age and user friendliness for the trusted party based recovery (r=0.176, p=0.041) and the QR code based recovery (r=0.16, p=0.42).

Overall Views

At the end of the experiment, participants were asked about their opinion of the two recovery methods using categories similar to those above. We also asked for their overall recovery method preference. The questions they were asked were "Which recovery do you consider more easy to use/secure/user friendly?" and "Which recovery do you overall prefer more?" The possible responses were "QR code recovery", "Trusted party based recovery" and "Both similarly". We used answers only from those 132 participants who went through both recoveries.

-Ease to use: 113 (86%) participants considered the QR code recovery easier to use than the trusted party based recovery. Only 6 (4%) participants thought the opposite and 13 (10%) participants considered both methods similarly easy. -Security: 90 (68%) participants considered the trusted party based recovery more secure than the QR code based recovery. Only 14 (10%) participants had an opposite opinion and 28 (21%) did not see a difference between both methods. -User friendly: 100 (76%) participants considered the QR code based recovery more user friendly over the trusted party based recovery. Only 6 (5%) participants thought the opposite and 26 (20%) considered both recoveries to be equally user friendly. -Overall recovery preferences: When participants were ask to choose one recovery that they prefer, 76 (58%) participants preferred the QR based recovery whereas 35 (25%) participants preferred the trusted party based recovery. 21 (16%) participants preferred both recoveries equally.

We also conducted a χ 2 [START_REF] Corder | Nonparametric Statistics: A Step-by-Step Approach[END_REF] test and Fisher's exact test (when some crosstab cells remained empty) and we did not find (at the significance level α=0.05) any statistically significant differences in perceptions of security, user friendliness and overall preferences of these recovery methods between men and women or IT and non IT participants. The only statistically significant difference (p=0.03) is in easiness to use recoveries between IT and non IT participants. IT participants had higher tendency to choose "Both options were similarly easy to use" over "Trusted party based recovery was easiest to use" in comparison with non IT participants.

Other Observations

In terms of the effectiveness of both recovery methods, we can report that we observed some unsuccessful trials. 79% participants succeeded with a QR code based recovery at the first try. Moreover, 89% participants did a QR code based recovery with zero or one unsuccessful trial. Recovery with a trusted party had similar results. 75% of participants succeeded on their first attempt. In addition, 88% of the users processed a trusted party based recovery with zero or one unsuccessful trial. In comparison to earlier studies on currently used recovery techniques such as challenge questions where 20% of participants forget their answers after 6 months [START_REF] Schechter | It's no secret. measuring the security and reliability of authentication via secret questions[END_REF], our studied recovery methods show an improvement. We observed no significant difference in number of trials of men and women or IT and non IT participants.

The success rate (ratio between the number of successful attempts and the total number of attempts) of a trusted party based recovery is approximately 48%. The success rate for QR code based recovery is approximately 49%. This shows that both methods seem to be similarly prone to error. We had no limits in attempts to insert a code in the recovery. The ratios are particularly low due to few outliers who tried to insert a recovery code 10, 11, 12 or 13 times before they succeeded. The time between system request to start recovery and finishing the recovery was on average nearly 53 minutes for the trusted party based recovery, and 9 minutes for the QR code based recovery. From the user's point of view trusted party based recovery is slower than the other recovery method.

We also included a couple of additional questions related to the difficulty of carrying out the recovery processes. The first was related to the difficulty of finding a QR code reader. We used the Likert scale from 1 (totally easy) to 6 (totally difficult) for responses. In general, participants found it very easy to locate their QR code reader (mean=1.64, SD=1.17). We conducted a t-test and observed statistical significant differences (at the statistical significance level α=0.05, t(130)=2.86, p<0.05) between participants from the Faculty of Informatics (mean=1.36, SD=0.92) and participants from other faculties (mean=1.92, SD=1.33). Statistically significant differences (α=0.05, t(130)=-2.21, p<0.05) in this question were also observed between men (mean=1.49, SD=0.99) and women (mean=1.89, SD=1.33). To sum up, even with these relative differences, all participants found it easy (with mean scores less than 2).

The second question related to the difficulty of QR code scanning. We used the Likert scale from 1 (totally easy) to 6 (totally difficult) for responses. Generally speaking, participants considered this process easy (mean=1.35, SD=0.95), but we observed a significant difference (at the statistical significance level α=0.05, t(130)=3.72, p<0.001) between participants from the Faculty of Informatics (mean=1.06 SD=0.24) and participants from other faculties (mean=1.65, SD=1.27). Participants from the Faculty of Informatics considered the QR code scanning even easier than their colleagues from different faculties. Very similarly, participants considered it to be very easy to call a client center (mean=1.84, SD=1. [START_REF] Moallem | Did You Forget Your Password? In: Design, User Experience, and Usability[END_REF]), and we did not observe any statistically significant difference between IT and non IT students or men and women. On the other hand, we must take into account that if a participant had a serious problem to find the QR code reader or had a problem to call the client center, he may have stopped the experiment without completing the questionnaire.

Related to the use of the client center, there were several issues connected with password recoveries. The major flaw connected with the QR code recovery was that several QR code reading applications do not distinguish characters "l" and "I", "O" and "0". One participant also reported that his QR reading application showed the whole text in lower case. One solution may be to recommend a particular QR code reading application that would work correctly to avoid above mentioned issues. Another solution may be also to remove problematic characters out of the backup code. Of course, it could mean that codes would be lengthened.

The client center similarly observed issues connected with the trusted party based recovery. We have observed several difficulties in retyping SMS codes from a phone to the system. For participants was hard to recognize several problematic characters. For example "0" instead "O". The solution can be same as in the previous case.

Conclusion

We evaluated two alternate recovery solutions, using backup codes and trusted people. Despite the fact that both methods have expectable drawbacks, our research set out to confirm these issues to support our goal of promoting a discussion on other types of recovery processes. Despite the fact that the trusted party based recovery was considered by 90 (68%) participants to be more secure than the QR code based recovery (14 participants (11%)), the majority of participants gave their overall preferences to the solution that they consider easier to use and more user friendly: the QR code based recovery. 100 participants out of 132 considered the QR code based recovery more user friendly and 113 participants considered it easier to use than the trusted party based recovery. We observed that for the trusted party based recovery participants spent more time to perform the recovery (53 minutes for trusted party and 9 minutes for QR code) whereas the number of unsuccessful trials were nearly equal -89% participants processed the QR code recovery with one or zero unsuccessful trial and 88% did the same with the trusted party based recovery. We observed several interesting points such as that IT participants considered both recoveries as less difficult than non IT participants. Men (and IT participants) considered the QR code based recovery significantly less secure than women (and non IT participants).

We also observed that participants perceived a strong difference between an "ordinary" website level of security and the security good enough to be used for their online banking. When comparing both recovery methods, results for the "standard security" were nearly the same, but for security good enough for online banking there were significant differences in answers so that the trusted party based recovery was considered to be more secure. Our participants, who are university students, seemed to be well aware of possible secure drawbacks of our solutions.

As for the perception of password recovery difficulty, both recoveries scored similarly. We did not find (at the statistical significance level α=0.05) that there would be any difference in recovery preferences (security, user friendliness or in overall recovery preference) between men and women or the IT and non IT participants. The only significant difference was between IT and non IT participants in ease of use. IT participants tended to choose "Both recovery methods are similarly easy to use" more than non IT participants who slightly more preferred the trusted party recovery as easier to use.

We recommended to the company to offer the QR code solution as a default for all users. The trusted party based recovery should be suggested only to users who demand a higher level of security. The trusted party based recovery can be then used either instead or even in combination with the QR code based recovery.

Fig. 1 .

 1 Fig. 1. Trusted party based recovery.

Fig. 2 .

 2 Fig. 2. Experiment process.

Table 1 .

 1 Experiment participants overview.

	Faculty	Males Females Participants in total
	Faculty of Informatics	75	17	98
	Faculty of Social Studies	23	41	67
	Faculty of Law	8	9	17
	Faculty of Arts	1	5	10
	Other faculties	2	5	9

Table 2 .

 2 Experiment phases and dropped out participants. The table shows the number of participants who dropped before proceeding with each experiment phase. Group 1 has the QR code as 1 st recovery and trusted party based recovery as 2 nd recovery. Group 2 has alternate order of recoveries.

	Group	Initial questionnaire 1 st task 1 st recovery 2 nd task 2 nd recovery
	Group 1	5	4	3	15	-
	Group 2	4	21	0	2	-

  How secure do you consider to use this recovery for online banking? The Likert scale was used for responses from 1 (totally secure) to 6 (totally insecure). When considering a password recovery for a system with sensitive data, based on the paired t-test, the QR code based recovery is considered as less sufficient for online banking (mean=3.92, SD=1.34) than the trusted party based recovery (mean=2.89, SD=1.38) (t(132)=-7.62, p<0.001). However, the trusted party based recovery still only received a mean score between 2 and 3, and hence was not viewed as "totally secure".

	Men (mean=3.2, SD=1.22) and women (mean=2.7, SD=0.96) had signif-
	icant difference in evaluating security of the QR code based password re-
	covery (t(144)=2.94, p<0.004). Men considered the QR code based recov-
	ery significantly less secure than women. On the other hand, there is no
	significant difference observed in security of the trusted party based recov-
	ery (t(121)=0.24, p=0.8) between men (mean=2.41, SD=1.27) and women
	(mean=2.36, SD=1.07).
	Very similar results are obtained when comparing IT and non IT partici-
	pants. Non IT participants (mean=2.74, SD=1.00) considered the QR code
	based recovery significantly more secure (t(144)=-2.94, p=0.004) than IT
	participants (mean=3.29, SD=1.22). There is no difference in IT (mean=2.53,
	SD=1.18) and non IT participants (mean=2.25, SD=1.18) in evaluating se-
	curity of the trusted party based recovery (t(131)=-1.34, p=0.18).
	Correlation of age and the trusted party recovery security is not significant
	(r=0.14, p=0.1), similarly correlation of age and the QR code recovery se-
	curity (r=0.128, p=0.123).
	-Advanced security: Men (mean=4.17, SD=1.38) and women (mean=3.62, SD=1.24) evaluated
	differently advanced security of the QR code based password recovery (t(147)
	=2.46, p=0.015), but saw no difference in advanced security of the trusted
	party based recovery (t(133)=0.53, p=0.594, men:(mean=2.97, SD=1.39),
	women:(mean=2.84, SD=1.38)).
	14) in evaluating difficulty of the QR code recovery (t(148)=-0.054,
	p=0.957).
	We observed significant difference between IT (trusted party, mean= 2.32,
	SD=1.40), (QR code recovery, mean=1.48, SD=0.931) and non IT partici-
	pants (trusted party, mean=3.25, SD=1.56), (QR code recovery, mean=1.98,
	SD= 1.22) in both the trusted party (t(133)=3.59, p<0.001) and the QR code
	recovery (t(148)=2.85, p=0.005). IT participants considered both recoveries
	as less difficult than non IT participants.
	Correlation of age and the trusted party recovery difficulty is significant
	(r=0.22, p=0.011), similarly correlation of age and the QR code recovery
	difficulty (r=0.21, p=0.007). The older user is, the more difficult recovery is.
	-Security: How secure do you consider the recovery? The Likert scale was
	used for responses from 1 (totally secure) to 6 (totally insecure). The paired
	t-test proved that participants in this scale consider the QR code based re-
	covery less secure (mean=3, SD=1.15) than the trusted party based recovery
	(mean=2.38, SD=1.17) (t(129)=-5.25, p<0.001).

Dropbox has recently added an option to use Universal 2nd Factor (U2F) security keys to partially mitigate against mobile phone issues, though this too requires possession of a USB, which might become lost, stolen, or out-of-order. See https://blogs.dropbox.com/dropbox/2015/08/u2f-security-

keys/ 5 https://www.facebook.com/notes/facebook-security/introducing-trustedcontacts/10151362774980766

Acknowledgements. The authors acknowledge the support of the Masaryk University (MUNI/M/1052/ 2013). Authors would like to thank Department of social studies for a help with a data analysis.