Alexandre Munnier
email: alexandre.munnier@univ-lorraine.fr

Karim Ramdani
email: karim.ramdani@inria.fr

Conformal mapping for cavity inverse problem: an explicit reconstruction formula

In this paper, we address a classical case of the Calderón (or conductivity) inverse problem in dimension two. We aim to recover the location and the shape of a single cavity ω (with boundary γ) contained in a domain Ω (with boundary Γ) from the knowledge of the Dirichlet-to-

We obtain an explicit formula for the complex coefficients a m arising in the expression of the Riemann map z -→ a 1 z + a 0 + m -1 a m z m that conformally maps the exterior of the unit disk onto the exterior of ω. This formula is derived by using two ingredients: a new factorization result of the DtN map and the so-called generalized Pólia-Szegö tensors (GPST) of the cavity. As a byproduct of our analysis, we also prove the analytic dependence of the coefficients a m with respect to the DtN. Numerical results are provided to illustrate the efficiency and simplicity of the method.

Introduction

Let Ω be a simply connected open bounded set in R 2 with Lipschitz boundary Γ. Let σ be a positive function in L ∞ (Ω) and consider the elliptic boundary value problem:

-∇ • (σ∇u) = 0 in Ω (1.1a) u = f on Γ. (1.1b)
Calderón's inverse conductivity problem [START_REF] Calderón | On an inverse boundary value problem[END_REF] can be stated as follows: Knowing the Dirichlet-to-Neumann (DtN) map Λ : f -→ ∂ n u f , is it possible to recover the conductivity σ? In this work, we focus on the particular case of piecewise conductivity with infinitely high contrast (see for instance Friedman and Vogelius [START_REF] Friedman | Identification of small inhomogeneities of extreme conductivity by boundary measurements: a theorem on continuous dependence[END_REF] who considered this problem in the case of small inclusions). More precisely, we suppose that Ω contains a cavity ω, where ω is an open simply connected domain with Lipschitz boundary γ and such that ω ⊂ Ω (see Figure 1). We denote by n the unit normal to Γ ∪ γ directed towards the exterior of Ω \ ω.

For every f in H 1 2 (Γ), we denote by (u f , c f ) ∈ H 1 (Ω \ ω) × R the solution to the Dirichlet problem:

-∆u f = 0 in Ω \ ω (1.2a) u f = f on Γ (1.2b) u f = c f on γ, (1.2c)
where c f is the unique constant such that:

γ ∂ n u f dσ = 0. (1.2d) Problem (1.
2) is well-posed and its solution is the limit of the solution of (1.1) for piecewise constant conductivity, when the contrast between the cavity and the background tends to infinity (see Proposition A.1 of the Appendix for a precise statement of this classical result and for the proof, which is given for the sake of completeness).

Loosely speaking (the exact functional framework will be made precise later on), the inverse problem considered throughout this paper is the following: knowing the Dirichlet-to-Neumann (DtN) map Λ γ : f -→ ∂ n u f , how to reconstruct the cavity ω? Remark 1.1 In dimension 2, it is classical to see u f as the harmonic conjugate function of v g , the solution to (defined up to a constant):

-∆v g = 0 in Ω \ ω (1.3a)

∂ n v g = g on Γ (1.3b) ∂ n v g = 0 on γ, (1.3c)
where g = ∂ τ f and τ := n ⊥ is the unit tangent vector to Γ. The function u f is usually referred to as the stream function associated with the potential function v g and we have ∂ n u f = -∂ τ v g on Γ. According to the above relations, the knowledge of Λ γ (i.e. the DtN for u f ) is equivalent to the knowledge of the Neumann-to-Dirichlet map Λγ : g -→ v g for problem (1.3), as we have

Λ γ f = -∂ τ Λγ (∂ τ f ).
Classically for inverse problems, the questions of uniqueness, stability and reconstruction have been studied in the literature for cavities identification. Regarding uniqueness, it is well-known that one pair (f, ∂ n u f ) of Cauchy data uniquely determines the geometry of the cavity for a Dirichlet boundary condition (see Kress [START_REF] Kress | Inverse Dirichlet problem and conformal mapping[END_REF]) or a Neumann boundary condition (see Alessandrini and Rondi [START_REF] Alessandrini | Optimal stability for the inverse problemof multiple cavities[END_REF]). For Robin type condition, Bacchelli [START_REF] Bacchelli | Uniqueness for the determination of unknown boundary and impedance with the homogeneous Robin condition[END_REF] proved that two excitations f 1 and f 2 uniquely determine the cavity provided they are linearly independent and one of them is positive. Concerning stability, as shown by Mandache [START_REF] Mandache | Exponential instability in an inverse problem for the Schrödinger equation[END_REF], logarithmic stability is best possible (see also Alessandrini and Rondi [START_REF] Alessandrini | Optimal stability for the inverse problemof multiple cavities[END_REF] and references therein). Among the reconstruction methods available in the literature for shape identification, one can distinguish two classes of approaches: iterative and non iterative methods (see for instance the survey paper by Potthast [START_REF] Potthast | A survey on sampling and probe methods for inverse problems[END_REF] for an overview of reconstruction methods). In the first class of methods, one computes a sequence of approximating shapes, generally by solving at each step the direct problem and using minimal data (typically only one or several pairs of Cauchy data, and not the full DtN map). Among these approaches, we can mention those based on optimization [START_REF] Borcea | Electrical impedance tomography[END_REF][START_REF] Capdeboscq | Imaging by modification: numerical reconstruction of local conductivities from corresponding power density measurements[END_REF], on the reciprocity gap principle [START_REF] Kress | Nonlinear integral equations and the iterative solution for an inverse boundary value problem[END_REF][START_REF] Ivanyshyn | Nonlinear integral equations for solving inverse boundary value problems for inclusions and cracks[END_REF][START_REF] Cakoni | Integral equation methods for the inverse obstacle problem with generalized impedance boundary condition[END_REF], on the quasi-reversibility [START_REF] Bourgeois | A quasi-reversibility approach to solve the inverse obstacle problem[END_REF][START_REF] Bourgeois | The "exterior approach" to solve the inverse obstacle problem for the Stokes system[END_REF] or on conformal mapping [START_REF] Akduman | Electrostatic imaging via conformal mapping[END_REF][START_REF] Kress | Inverse Dirichlet problem and conformal mapping[END_REF][START_REF] Haddar | Conformal mappings and inverse boundary value problems[END_REF][START_REF] Haddar | Conformal mapping and an inverse impedance boundary value problem[END_REF][START_REF] Haddar | Conformal mapping and impedance tomography[END_REF][START_REF] Kress | Inverse problems and conformal mapping[END_REF][START_REF]A conformal mapping method in inverse obstacle scattering[END_REF].

The second class of methods covers non iterative methods which are generally based on the construction (from the measurements) of an indicator function of the inclusion(s). These sampling/probe methods do not need to solve the forward problem, but require the knowledge of the full DtN map. Among these reconstruction techniques, let us mention -with no claim as to completeness-the enclosure and probe method of Ikehata [START_REF] Ikehata | Reconstruction of the shape of the inclusion by boundary measurements[END_REF][START_REF] Ikehata | Reconstruction of the support function for inclusion from boundary measurements[END_REF][START_REF]On reconstruction in the inverse conductivity problem with one measurement[END_REF][START_REF] Ikehata | Numerical method for finding the convex hull of an inclusion in conductivity from boundary measurements[END_REF][START_REF] Erhard | A numerical study of the probe method[END_REF]], Kirsch's Factorization method [START_REF] Brühl | Numerical implementation of two noniterative methods for locating inclusions by impedance tomography[END_REF][START_REF] Hanke | Recent progress in electrical impedance tomography[END_REF][START_REF] Kirsch | The factorization method for a class of inverse elliptic problems[END_REF] and Generalized Polya-Szegö Tensors [START_REF] Ammari | Reconstruction of small inhomogeneities from boundary measurements[END_REF][START_REF]Generalized polarization tensors, inverse conductivity problems, and dilute composite materials: a review[END_REF][START_REF]Polarization and moment tensors[END_REF][START_REF] Ammari | Generalized polarization tensors for shape description[END_REF][START_REF] Kang | Construction of conformal mappings by generalized polarization tensors[END_REF].

Our purpose in this paper is to propose a new non iterative reconstruction method that combines some of the ingredients used in earlier works, namely: a new factorization result (Theorem 3.1), Generalized Polya-Szegö Tensors and conformal mapping. The main feature of our reconstruction method is that we end up with an explicit reconstruction formula (Theorem 3.4) for the complex coefficients a k arising in the expression of the Riemann map z -→ a 1 z + a 0 + m -1 a m z m that conformally maps the exterior of the unit disk onto the exterior of ω. Let us emphasize that these reconstruction formulae also yield the analytic dependence of the coefficients with respect to the DtN.

The closest results to our article are those obtained by Kang et al. [START_REF] Kang | Construction of conformal mappings by generalized polarization tensors[END_REF]. Although being close to the second part of our contribution (the recovery of the conformal map from the GPST), our improvements are twofold. First, we do not assume the GPST to be given. Indeed, the main advantage of our new factorization is that it allows one to recover very accurately these GPST from the DtN measurements. Second, even assuming the GPST to be known, Kang et al. obtain a recursive formula for the coefficients of the conformal mapping in terms of the coefficients of the GPST. In our work, we obtain for each of these coefficients an explicit and non recursive formula.

The proposed reconstruction algorithm can -in principle-be adapted to other boundary conditions. However, such as most direct reconstruction methods, it requires the knowledge of the full DtN map and so far, it is limited to the two-dimensional case due to the use of conformal mapping.

The paper is organized as follows: we present in Section 2 a boundary integral formulation of the problem. Section 3 is devoted to the derivation of the reconstruction formula, using a new factorization result and GPST. Some issues about stability are also discusses therein. Finally, some numerical results are given in Section 4.

Boundary integral formulation 2.1 Background on single layer potential

In this section, we collect some well known facts of potential theory, and more especially on single layer potential, that are crucial for our method. For more details and for the proofs, we refer the interested reader to the monographs of McLean [START_REF] Mclean | Strongly elliptic systems and boundary integral equations[END_REF], Steinbach [START_REF] Steinbach | Numerical approximation methods for elliptic boundary value problems[END_REF] or Hsiao and Wendland [START_REF] Hsiao | Boundary integral equations[END_REF].

Throughout the article, we shall denote by

G(x) = - 1 2π log |x| the fundamental solution of the operator -∆ in R 2 .
Let C i be a bounded, Lipschitz domain (see [START_REF] Mclean | Strongly elliptic systems and boundary integral equations[END_REF]Definition 3.28]) and denote by C its boundary. Let n be the unit normal to C directed towards the exterior of C i .

The exterior of C i is denoted C e := R 2 \ C i . Given a function u defined on R 2 \ C , we denote by u i and u e its restrictions respectively to C i and C e . Whenever the traces and the normal traces of u i and u e on C exist respectively in

H 1 2 (C ) and H -1 2 (C ), we denote by [u] C = u i | C -u e | C ∈ H 1 2 (C ) the jump of u across C and by [∂ n u] C = (∂ n u i )| C -(∂ n u e )| C ∈ H -1
2 (C ) the jump of the normal traces of u across C . Definition 2.1 For every q ∈ H -1 2 (C ), we denote by S C q the single layer potential associated with the density q.

The single layer potential S C q defines a harmonic function in R 2 \ C . The operator S C is an integral operator with weakly singular kernel, so that for q ∈ L ∞ (C ) for instance and x ∈ R 2 \ C , it reads:

S C q(x) = C G(x -y)q(y) dσ y .
Moreover, the single layer potential defines a bounded linear operator from

H -1 2 (C ) into H 1 oc (R 2 )
, and S C q admits the following asymptotic behavior at infinity (see for instance [40, p. 261])

S C q(x) = - 1 2π q, 1 -1 2 , 1 2 ,C log |x| + O(|x| -1 ), (2.1)
where

•, • -1 2 , 1
2 ,C stands for the duality brackets between H -1 2 (C ) and H 1 2 (C ). This shows in particular that ∇(S C q) belongs to L 2 if and only if q belongs to the function space

H(C ) := {q ∈ H -1 2 (C ) : q, 1 -1 2 , 1
2 ,C = 0}. We also recall that the single layer potential satisfies the following classical jump conditions

[S C q ] C = 0, [∂ n (S C q)] C = q. ( 2.2)
Let us focus now on the trace of the single layer potential.

Definition 2.2 For every q ∈ H -1 2 (C ), we denote by S C q the trace of the single layer operator S C q on C .

The operator S C is an integral operator with weakly singular kernel as well. For q ∈ L ∞ (C ) and for every x ∈ C , it reads:

S C q(x) = C G(x -y)q(y) dσ y .
The trace S C of the single layer operator defines a bounded linear operator from

H -1 2 (C ) into H 1 2 (
C ). Furthermore, using Green's formula and the asymptotics (2.1), we can easily prove the identity

q, S Γ q -1 2 , 1 2 ,C = R 2 |∇(S C q)| 2 dx < +∞, ∀q ∈ H(C ). (2.3)
Following [START_REF] Mclean | Strongly elliptic systems and boundary integral equations[END_REF]Theorem 8.15], we also introduce the following particular density and constant which will play a crucial role in our analysis.

Cap(C ) = exp (-2πS C êC ) . Setting H(C ) := {q ∈ H 1 2 (C ) : êC , q -1 2 , 1 2 ,C = 0}
we know, following McLean [START_REF] Mclean | Strongly elliptic systems and boundary integral equations[END_REF], that the linear operator:

S C : q ∈ H(C ) -→ q ∈ H(C ),
defines an isomorphism that extends into an isomorphism from [START_REF] Mclean | Strongly elliptic systems and boundary integral equations[END_REF]Theorem 8.16]). Under this condition, one can identify via this isomorphism any density q ∈ H(C ) with the trace q := S C q ∈ H(C ). This identification will be systematically used throughout the paper, using the notation with (respectively without) a hat on the density like quantities (respectively on traces). This isomorphism turns out to be an isometry provided the spaces H(C ) and H(C ) are endowed with the following inner products: Definition 2.4 For all q, p ∈ H(C ), we set:

H -1 2 (C ) onto H 1 2 (C ), if Cap(C ) = 1 (see
q, p -1 2 ,C = q, p 1 2 ,C = q, p -1 2 , 1 2 ,C .
According to (2.3), the inner products introduced in Definition 2.4 are related to the Dirichlet energy of the single layer potential through the following identities:

q 2 -1 2 ,C = q 2 1 2 ,C = R 2 |∇(S C q)| 2 dx, ∀q ∈ H(C ).
We also need in the sequel the following orthogonal projections.

Definition 2.5 Let Π C and Π C denote respectively the orthogonal projections from

H 1 2 (C ) into H(C ) and from H -1 2 (C ) into H(C ).
In particular, we have the following unique decompositions: Let us conclude this preliminary section by a useful characterization of the chosen norm on H(C ). Classically (see for instance [START_REF] Amrouche | Dirichlet and Neumann exterior problems for the n-dimensional Laplace operator: an approach in weighted Sobolev spaces[END_REF][START_REF] Girault | A stream-functionvorticity variational formulation for the exterior Stokes problem in weighted Sobolev spaces[END_REF]), we define the quotient weighted Sobolev space:

∀ q ∈ H -1 2 (C ) : q = q, 1 êC + q0 , q0 := Π C q ∈ H(C ), ∀ q ∈ H 1 2 (C ) : q = êC , q 1 + q 0 , q 0 := Π C q ∈ H(C ).
W 1 0 (R 2 ) = {u ∈ D (R 2 ) : ρu ∈ L 2 (R 2 ), ∇u ∈ (L 2 (R 2 )) 2 }/R,
where the weight is given by

ρ(x) := 1 + |x| 2 log(2 + |x| 2 ) -1 , x ∈ R 2 ,
and where the quotient means that functions of W 1 0 (R 2 ) are defined up to an additive constant. This space is a Hilbert space once equipped with the inner product:

u, v W 1 0 (R 2 ) := R 2 ∇u • ∇v dx.
In particular, according to (2.3), S C q ∈ W 1 0 (R 2 ) if and only if q ∈ H(C ), and moreover

q -1 2 ,C = q 1 2 ,C = S C q W 1 0 (R 2 ) , ∀q ∈ H(C ).
Lemma 2.7 For every q ∈ H(C ), we have

q 1 2 ,C = inf u W 1 0 (R 2 ) : u ∈ W 1 0 (R 2 ) and Tr 0 C u = q .
The infimum is a minimum which is uniquely achieved by u = S C q.

Proof : Given q ∈ H(C ), let us consider the orthogonal decomposition:

W 1 0 (R 2 ) = S C q ⊕ S C q ⊥ . Let u ∈ W 1 0 (R 2 ) be such that Tr 0 C u = q. Writing u in the form u = λS C q + v with λ ∈ R and v ∈ S C q ⊥ ,
and taking the projected trace on C we get:

q = λq + Tr 0 C v in H(C ).
Forming now the duality product with q and taking into account that:

q, Tr 0 C v -1 2 , 1 2 ,C = S C q, v W 1 0 (R 2 )
= 0, we deduce that λ = 1. Since we have now

u 2 W 1 0 (R 2 ) = q 2 1 2 ,C + v 2 W 1 0 (R 2 ) ,
with v such that Tr 0 C v = 0, the conclusion follows.

Boundary interaction and single layer potential

In this section, we are interested in quantifying the Dirichlet energy variation between S Γ q and S γ p where p = Tr 0 γ S Γ q (i.e. p is the trace of the single layer potential S Γ q on γ).

Definition 2.8

We define the boundary interaction operators K γ Γ and K Γ γ between Γ and γ by:

K γ Γ : q ∈ H(Γ) -→ Tr 0 γ (S Γ q) ∈ H(γ), K Γ γ : p ∈ H(γ) -→ Tr 0 Γ (S γ p) ∈ H(Γ),
where Tr 0 γ and Tr 0 Γ are given in Definition 2.6.

The next result shows that Tr 0 Γ can be replaced by Tr Γ in the definition of K Γ γ :

Lemma 2.9 If p ∈ H(γ), then q := Tr Γ (S γ p) belongs to H(Γ).

Proof : Let p and q be given as in the statement of the lemma and let us define the function w := (w i , w e ) in H 1 oc (R 2 ) by setting: w i = S Γ q in Ω and w e = S γ p in R 2 \ Ω. According to (2.3), the function w has finite Dirichlet energy since p ∈ H(γ). Thanks to (2.1), we see that w e (x) = O(|x| -1 ) at infinity, and this allows us to obtain the following classical integral representation formula for every x ∈ R 2 \ Ω (see for instance [43, p. 182] or [START_REF] Costabel | A direct boundary integral equation method for transmission problems[END_REF]Lemma 3.5])

w e (x) = ∂ n G(x -•), w e 1 2 ,Γ -∂ n w e , G(x -•) -1 2 , 1 2 ,Γ 0 = ∂ n G(x -•), w i -1 2 , 1 2 ,Γ -∂ n w i , G(x -•) -1 2 , 1
2 ,Γ . Since Tr Γ w i = Tr Γ w e = q, we get by subtracting these identities that:

w e (x) = r, G(x -•) -1 2 , 1 2 ,Γ = S Γ r(x), x ∈ R 2 \ Ω,
where the density r := ∂ n w i -∂ n w e belongs to H(Γ) since, as already mentioned, w has finite Dirichlet energy. Taking the trace on Γ, we deduce from the above relation that q = r ∈ H(Γ) and the proof is complete.

Proposition 2.10 The operators K γ Γ and K Γ γ are compact, one-to-one and dense-range operators. Moreover, for every functions q ∈ H(Γ) and p ∈ H(γ), we have:

K γ Γ q, p 1 2 ,γ = q, K Γ γ p 1 2 ,Γ .
Proof : The compactness follows from the regularity of the single layer potential away from the boundary, combined with [START_REF] Tucsnak | Observation and control for operator semigroups[END_REF]Proposition 13.5.8].

Addressing the symmetry property, consider q ∈ L ∞ (Γ) ∩ H(Γ) and p ∈ L ∞ (γ) ∩ H(γ). We can write that:

K γ Γ q, p 1 2 ,γ = γ Γ G(x -y)q(y)p(x) dσ y dσ x = Γ γ G(x -y)q(x)p(y) dσ y dσ x = K Γ γ p, q 1 2 ,Γ ,
and the conclusion follows by density. Assume now that q ∈ H(Γ) is such that K γ Γ q = 0. The function S Γ q is then constant on ω (as it is harmonic in ω and constant on γ). By the unique continuation property for harmonic functions, S Γ q is constant in Ω. On the other hand, S Γ q ≡ 0 on R 2 \ Ω (it is harmonic in R 2 \ Ω, constant on Γ and it behaves like O(|x| -1 ) at infinity since q ∈ Ĥ(Γ)). This yields q = [∂ n (S Γ q)] Γ = 0 and thus q = 0. Since Ran K Γ γ = Ker K γ Γ , we get the density result and the proof is completed.

Proposition 2.11

The norms of the operators K γ Γ and K Γ γ are strictly less that 1.

Proof : According to Lemma 2.7 we have, for every q ∈ H(Γ):

K γ Γ q 1 2 ,γ = inf u W 1 0 (R 2 ) : u ∈ W 1 0 (R 2 ) and Tr 0 γ u = Tr 0 γ (S Γ q) . We deduce that K γ Γ q 1 2 ,γ S Γ q W 1 0 (R 2 ) = q 1 2 ,Γ and the norm of K γ Γ is no greater than 1.
The operator K γ Γ being compact, its norm is achieved by some q Γ ∈ H(Γ).

If K γ Γ q Γ 1 2 ,γ = q Γ 1 2
,Γ , we would have, according to Lemma 2.7:

S γ qγ = S Γ qΓ , in R 2 ,
where q γ := K γ Γ q Γ . This identity implies that qΓ = [∂ n (S γ qγ )] Γ = 0, yielding the expected contradiction.

Integral formulation and well-posedness

Let us go back to Problem (1.2). Without loss of generality, let us assume from now on that the diameter of Ω is less than 1 (otherwise, it suffices to rescale the problem), which implies in particular that Cap(Γ) < 1 and Cap(γ) < 1 (see [43, p. 143] and references therein). Proposition 2.12 For every f ∈ H(Γ), denote by (u f , c f ) ∈ H 1 (Ω \ ω) × R the unique solution of System (1.2). The function u f can be represented as a superposition of single layer potentials as follows:

u f = S γ p + S Γ q, ( 2.4)
where p ∈ H(γ) and q ∈ H -1 2 (Γ) solve the following system of coupled integral equations on the boundaries γ and Γ:

p + Tr γ (S Γ q) = c f on γ (2.5a) Tr Γ (S γ p) + q = f on Γ. (2.

5b)

Proof : It is a consequence of [START_REF] Mclean | Strongly elliptic systems and boundary integral equations[END_REF]Theorem 8.16] that the unique solution to System (1.2) can be written as a superposition of two single layer potentials respectively supported on Γ and γ and respectively associated with the densities (p, q) ∈ H -1 2 (γ) × H -1 2 (Γ), as in (2.4). It only remains to verify that p is in fact in H(γ), i.e. that p, 1 -1 2 , 1 2 ,γ = 0. This is a straightforward consequence of (1.2d) and the jump relation for the normal derivative of the single layer potential.

The reconstruction formula

Going back to the DtN operator Λ γ of problem (1.2), and due to (1.2d), we have by Green's formula

∂ n u f , 1 -1 2 , 1 2 ,Γ = -∂ n u f , 1 -1 2 , 1
2 ,γ = 0, which shows that Λ γ is valued in H(Γ). Considering data f ∈ H(Γ), we can thus define the DtN operator Λ γ as follows:

Λ γ : f ∈ H(Γ) -→ ∂ n u f ∈ H(Γ). (3.1)
In the case where ω = ∅, we will denote respectively by u f 0 and Λ 0 the solution u f and the DtN Λ γ . Note that we have in particular

u f 0 = S Γ f .

Factorization of the DtN map

Theorem 3.1 The two following bounded linear operators in H(Γ):

R := S Γ (Λ γ -Λ 0 ) and K := K Γ γ K γ Γ , satisfy the following equivalent identities: R = (Id -K) -1 K, K = (Id + R) -1 R. (3.2)
Proof : Given f in H(Γ), let (p, q) ∈ H(γ)×H -1 2 (Γ) be the solution of System (2.5). According to Lemma 2.9, Tr Γ (S γ p) ∈ H(Γ) and hence Tr Γ (S γ p) = K Γ γ p. Since f ∈ H(Γ), we deduce from (2.5b) that q = f -K Γ γ p ∈ H(Γ). Applying the projector Π γ to (2.5a), we obtain the following system:

p + K γ Γ q = 0 on γ (3.3a) K Γ γ p + q = f on Γ. (3.3b)
Eliminating p, it follows that (Id -K)q = f and hence (Id -K)(q -f ) = Kf . The operator K being a contraction (see Propositon 2.11), we end up with:

q -f = (Id -K) -1 Kf. (3.4)
On the other hand, we have

(Λ γ -Λ 0 )f = ∂ n u f -∂ n u f 0 , (3.5)
where we recall that u f = S Γ q +S γ p and u f 0 = S Γ f . But outside Γ, these two single layer potentials both solve the well-posed Dirichlet exterior boundary value problem:

-∆v = 0 in R 2 \ Ω, v = f on Γ, v = O(|x| -1 ) |x| → +∞.
Hence (S Γ q + S γ p) = S Γ f in R 2 \ Ω, and in particular we can rewrite (3.5) as

(Λ γ -Λ 0 )f = [∂ n (S Γ q + S γ p)] Γ -[∂ n (S Γ f )] Γ = q -f ,
where the last equality follows from the jump relation (2.2). Comparing this relation and (3.4), we obtain that S Γ (Λ γ -Λ 0 )f = (Id -K) -1 Kf , which is exactly the first relation in (3.2). The second relation follows easily.

The first equation in (3.2) can be seen as a factorization of the (known) DtN operator Λ γ -Λ 0 in terms of the (unknown) boundary interaction operator K γ Γ and K Γ γ . Similarly, the second equation in (3.2) can be seen as a factorization of the boundary interaction operator K = K Γ γ K γ Γ in terms of the measurement operator R (which is entirely determined by the perturbed and unperturbed DtN maps and by the exterior boundary Γ). Using Proposition 2.10, it is worth reformulating this second equation in a variational form:

K γ Γ f, K γ Γ g 1 2 ,γ = (Id + R) -1 Rf, g 1 2 ,Γ , ∀ f, g ∈ H(Γ). (3.6)
This identity constitutes the first step towards the reconstruction of the unknown boundary γ. Indeed, the bilinear form

K γ Γ •, K γ Γ • 1 2
,γ turns out to encode the geometry of the inclusion, as shown in the next section.

Harmonic polynomials and GPST

Throughout the paper, we identify x = (x 1 , x 2 ) in R 2 with the complex number z = x 1 + ix 2 . Definition 3.2 For every m 1, we define the harmonic polynomials of degree m:

P m 1 (x) = Re (z m ) and P m 2 (x) = Im (z m ) .
We define as well

Q m 1,Γ (x) := P m 1 (x) + c m 1,Γ and Q m 2,Γ (x) := P m 2 (x) + c m 2,Γ (3.7)
where the constant c m ,Γ ∈ R, = 1, 2, are chosen such that the trace of Q m ,Γ

on Γ belongs to H(Γ).

Finally, we set

Q m Γ := Q m 1,Γ + iQ m 2,Γ . (3.8)
The crucial point about these polynomials Q m ,Γ , = 1, 2, lies in the fact that since they are harmonic, we have

K γ Γ (Q m ,Γ Γ ) = Q m ,γ γ ,
and hence, using these harmonic polynomials Q m ,Γ in formula (3.6) (and using for simplicity the same notation for the functions and their traces on the boundaries γ and Γ), we obtain that for all m, m 1 and all , = 1, 2:

K γ Γ Q m ,Γ , K γ Γ Q m ,Γ 1 2 ,γ = Q m ,γ , Q m ,γ 1 2 ,γ . Remark 3.3 The quantities Q m ,γ , Q m ,γ 1
2 ,γ are strongly connected with the so-called Generalized Pólya-Szegö Tensors (GPST) appearing in the high-order asymptotic expansion of the DtN map for small inclusions (see for instance the recent papers by Ammari et al. [START_REF] Ammari | Generalized polarization tensors for shape description[END_REF][START_REF] Ammari | Reconstruction of inhomogeneous conductivities via the concept of generalized polarization tensors[END_REF] and references therein). Our definition is somehow different from theirs, as they use real polynomials x m , while we use harmonic polynomials.

From the GPST to the geometry of the cavity: an explicit inversion formula

In this section, we are going to see that the quantities

Q m ,γ , Q m ,γ 1
2 ,γ for m, m 1 and , = 1, 2, which can be deduced from the measurements (see (3.6)), contain all the necessary information to reconstruct the cavity. We can even say more: the geometric information of γ is actually redundant in the GPST. As we shall see, the knowledge of the quantities

Q m γ , Q 1 γ 1 2 ,γ and
Q m γ , Q 1 γ 1
2 ,γ suffices to reconstruct the cavity. More precisely, according to Pommerenke [41, p. 5], there exists a mapping

φ : z → a 1 z + a 0 + m -1 a m z m ,
that maps the exterior of the unit disk D onto the exterior of ω (the assumption that ω is bounded and simply connected is crucial here). In particular, t ∈]π, π] → φ(e it ) provides a parameterization of γ. Notice that in this description, |a 1 | is the logarithmic capacity of γ and a 1 can be chosen as a positive real. The coefficient a 0 is the conformal center of ω. With these notation, we have the following result. Theorem 3.4 Let (Q m γ ) m 1 be the complex harmonic polynomials defined by (3.7)-(3.8). Define the two following sequences of complex numbers (1 m +∞):

µ m := 1 2 Q m γ , Q 1 γ 1 2 ,γ = 1 2 Q m Γ , (Id + R) -1 RQ 1 Γ 1 2 ,Γ , (3.9a)
ν m := 1 2 Q m γ , Q 1 γ 1 2 ,γ = 1 2 Q m Γ , (Id + R) -1 RQ 1 Γ 1 2 ,Γ , (3.9b)
with R := S Γ (Λ γ -Λ 0 ). Then, µ 1 > 0 and we have the explicit formulae:

a 1 = µ 1 2π 1 2 a 0 = µ 2 2µ 1 (3.9c) a -m = µ -m 2 1 α∈Am C α µ 2 µ 1 α 0 ν α 1 1 ν α 2 2 . . . ν αm m , m 1, (3.9d)
where

A m := {α ∈ N m+1 : α 0 + 2α 1 + 3α 2 + . . . + (m + 1)α m = (m + 1), α 0 = m + 1} (3.9e) and C α := (-1) |α|+1 2 α 0 m (2π) m 2 -(α 1 +•••+αm) 1 α 1 2 α 2 . . . m αm . (3.9f)
The rest of this section is devoted to the proof of this result.

To simplify the forthcoming computation, we complete the sequence of complex numbers (a k ) k 1 by setting a k = 0 for k 2. We denote a n k (n ∈ N, k ∈ Z) the kth coefficients of the Laurent's series of φ n :

a n k = |α|=k a α 1 a α 2 . . . a αn , (3.10)
where the sum ranges over all the multi-indices α = (α 1 , . . . , α n ) ∈ Z n whose length |α| = α 1 + . . . + α n is equal to k. We also introduce the quantities:

µ m,m := 1 2 Q m γ , Q m γ 1 2 ,γ = 1 2 Q m Γ , (Id + R) -1 RQ m Γ 1 2 ,Γ ν m,m := 1 2 Q m γ , Q m γ 1 2 ,γ = 1 2 Q m Γ , (Id + R) -1 RQ m Γ 1 2 ,Γ , so that µ m = µ m,1 and ν m = ν m,1 .
Lemma 3.5 Denoting, for every m 1:

φ m + (z) = k 1 a m k z k and φ m -(z) = k -1 a m k z k ,
the following identities hold true:

µ m,m = π -π e it (φ m + ) (e it )φ m (e it ) dt (3.11a) ν m,m = π -π e it (φ m + ) (e it )φ m (e it ) dt. ( 3

.11b)

Proof : Let m, m 1 and = 1, 2 be fixed. For the sake of simplicity, we drop in this proof the dependence with respect to γ and we denote Q m ,γ simply by Q m . We aim to compute the quantity:

Q m , Q m 1 2 ,γ = Q m , Q m -1 2 , 1 2 ,γ .
To do so, we recall that from the jump relation (2.2), we have

Q m = [∂ n U m ] γ ,
where U m := S γ Q m . Let us denote by U m e, and U m i, the restrictions of U m respectively to R 2 \ ω and ω.

We know that U m e, solves the following exterior Dirichlet boundary problem:

-∆U m e, = 0 in R 2 \ ω (3.12a) U m e, = Q m on γ, (3.12b) U m e, (x) = O(|x| -1 ) as |x| → +∞. (3.12c)
The functions u m e, := U m e, (φ) are harmonic in R 2 \ D (D denotes the unit disk) and satisfy:

u m e,1 (x) = Re (φ m (z)) + c m 1 and u m e,2 (x) = Im (φ m (z)) + c m 2 .
We can easily compute the constants c m 1 and c m 2 by writing that

c m 1 +ic m 2 = - γ (P m 1 (x)+i P m 2 (x))ê γ (x) dσ x = - π -π
φ m (e it )|φ (e it )|ê γ (e it ) dt.

But we know (from direct computations or from [START_REF] Hille | Analytic function theory[END_REF]Theorem 17.3.3]) that êγ (e it ) = 1/(2π|φ (e it )|). It follows that c m 1 + ic m 2 = -a m 0 and we have, on the boundary of D:

u m e,1 (x) = 1 2 φ m (z) + φ m (z) -Re (a m 0 ) u m e,2 (x) = - i 2 φ m (z) -φ m (z) -Im (a m 0 ).
This can be rewritten, using the identity z = 1/z on ∂D, as:

u m e,1 (x) = 1 2 φ m + (z -1 ) + φ m -(z) + φ m + (z -1 ) + φ m -(z) (3.13a) u m e,2 (x) = - i 2 -φ m + (z -1 ) + φ m -(z) --φ m + (z -1 ) + φ m -(z) . (3.13b)
These expressions lead us to introduce the following functions:

w m 1 (z) = φ m + (z -1 ) + φ m -(z) = φ m (z) -a m 0 + λ m 1 (z) (3.14a) w m 2 (z) = -φ m + (z -1 ) + φ m -(z) = φ m (z) -a m 0 + λ m 2 (z), (3.14b)
where

λ m 1 (z) = φ m + (z -1 ) -φ m + (z) and λ m 2 (z) = -φ m + (z -1 ) -φ m + (z). (3.15)
The functions w m 1 and w m 2 are holomorphic in C \ D and:

u m e,1 = Re (w m 1 ) and u m e,2 = Im (w m 2 ) on ∂D.

For every X = (X 1 , X 2 ) ∈ R 2 identified with Z = X 1 + iX 2 ∈ C, we have:

∇U m e,1 (φ(z)) • X = Re (w m 1 ) (z)Z/φ (z) ∇U m e,2 (φ(z)) • X = Im (w m 2 ) (z)Z/φ (z) .
On γ, the outer unit normal vector is parameterized by

t ∈ [-π, π[ -→ e it φ (e it )/|φ (e it )|,
and therefore, for every m 1:

γ ∂ n U m e,1 (x) Q m 1 (x)dσ x = π -π
Re e it (w m 1 ) (e it ) Re φ m (e it ) dt. (3.16) On the other hand, U m i, solves the following interior problem:

-∆U m i, = 0 in ω U m i, = Q m on γ,
whose unique solution is merely U m i, = Q m , so that:

γ ∂ n U m i,1 (x)Q m 1 (x)dσ x = π -π
Re e it (φ m ) (e it ) Re φ m (e it ) dt.

(3.17)

Gathering now (3.16), (3.17) and taking into account the expressions (3.14), we infer that:

Q m 1 , Q m 1 1 2 ,γ = γ [∂ n U m 1 (x)] γ Q m 1 (x)dσ x (3.18a) = - π -π
Re e it (λ m 1 ) (e it ) Re φ m (e it ) dt.

(3.18b)

Notice now that, on ∂D, we have:

Re e it (λ m 1 ) (e it ) = -e it (φ m + ) (e it ) + e it (φ m + ) (e it ) = -2Re e it (φ m + ) (e it ) ,
and therefore, (3.18) can be rewritten as:

Q m 1 , Q m 1 1 2 ,γ = 2 π -π
Re e it (φ m + ) (e it ) Re φ m (e it ) dt.

Using similar arguments, lengthy but straightforward computations lead to:

Q m 1 , Q m 2 1 2 ,γ = 2 π -π Re e it (φ m + ) (e it ) Im φ m (e it ) dt = 2 π -π Im e it (φ m + ) (e it ) Re φ m (e it ) dt and Q m 2 , Q m 2 1 2 ,γ = 2 π -π Im e it (φ m + ) (e it ) Im φ m (e it ) dt.
Formulae (3.11) follow.

Lemma 3.6

The following relations hold true:

a 1 = µ 1 2π and a 0 = µ 2 2µ 1 .
Proof : For every z ∈ C \ D (recall that D denotes the unit disk), we have

φ 1 + (z) = φ + (z) = a 1 z and φ 2 + (z) = (a 1 ) 2 z 2 + 2a 1 a 0 z, and hence zφ + (z) = a 1 z and z(φ 2 + ) (z) = 2(a 1 ) 2 z 2 + 2a 1 a 0 .
Applying formulae (3.11), we obtain:

µ 1 = 2π(a 1 ) 2 and µ 2 = 4π(a 1 ) 2 a 0 .
The conclusion of the lemma follows.

The conformal mapping φ -1 can be expanded as follows:

φ -1 (z) = b 1 z + b 0 + k -1 b k z k ,
outside a disk D centered at the origin and containing ω. This follows from the fact that φ -1 (z) admits a Laurent's series expansion as being the inverse of a holomorphic function. Moreover, the series has no terms of degree k > 1 since φ (and thus φ -1 ) behaves like O(|z|) at infinity. The complex coefficients b k (k 1) can be deduced on the one hand from the coefficients a k of and on the other hand from the values of ν m , (m 1), as claimed in the following lemma:

Lemma 3.7 The following relations hold true:

b 1 = 1/a 1 and b 0 = -a 0 /a 1 . (3.19)
For every m 1, we have:

b -m = - ν m 2πa 1 m = - 1 m |β|=-1 a β 1 . . . a βm , m 1. (3.20)
Proof : Identities (3.19) follow straightforwardly because φ and φ -1 are inverse mappings. Integrating by part the expression of ν m = ν m,1 obtained from (3.11), we get:

ν m = a 1 π -π e it φ m (e it ) dt = -a 1 m π -π e it φ (e it )e it φ m-1 (e it ) dt. (3.21)
Since t → e it is a parameterization of ∂D, applying Cauchy's integral formula we get on the one hand

π -π e it φ m (e it ) dt = -i ∂D φ m (ξ)dξ = 2πa m -1 .
On the other hand, since t → φ(e it ) is a parameterization of γ and the function φ -1 being holomorphic in C \ ω, we have:

π -π e it φ (e it )e it φ m-1 (e it ) dt = -i γ φ -1 (ξ)ξ m-1 dξ = -i ∂D φ -1 (ξ)ξ m-1 dξ = 2πb -m .
Identity (3.21) can thus be rewritten as:

ν m = 2πa 1 a m -1 = -2πa 1 mb -m ,
and identity (3.20) follows according to (3.10).

Using the above lemmas, we are in position to prove the main result of this section, namely Theorem 3.4.

Proof of Theorem 3.4: Since φ and φ -1 play symmetric roles, we can exchange a m and b m in Formula (3.20) to obtain:

a -m = - 1 m |β|=-1 b β 1 . . . b βm , m 1.
Reordering the terms of the above sum, we get that

a -m = - 1 m (θ,α)∈Bm b θ 1 b α 0 0 b α 1 -1 . . . b αm -m (3.22)
where B m is the set of (θ, α) ∈ N × N m+1 such that

θ + α 0 + α 1 + • • • + α m = m θ -(α 1 + 2α 2 + • • • + mα m ) = -1.
Now, one can easily check that (θ, α) ∈ B m if and only if α belongs to the set A m defined by (3.9e) and θ = m -

(α 0 + α 1 + • • • + α m ). Therefore, (3.22) also reads a -m = - 1 m α∈Am b m-(α 0 +α 1 +•••+αm) 1 b α 0 0 b α 1 -1 . . . b αm -m
Using (3.19) and the first equality of (3.20) in the above relation, we obtain that

a -m = - 1 m a -m 1 α∈Am (-a 0 ) α 0 - ν 1 2π α 1 . . . - ν m 2πm αm ,
and the conclusion follows immediately.

About stability

It is well-known that logarithmic stability is best possible for Calderón's inverse problem. In the particular case of cavities, this result is proved in [START_REF] Alessandrini | Optimal stability for the inverse problemof multiple cavities[END_REF]Theorem 4.1] where the error on the geometry (measured using the Hausdorff distance) is estimated in terms of the error of the DtN (measured in operator norm). However, as suggested by Alessandrini and Vessella [START_REF] Alessandrini | Lipschitz stability for the inverse conductivity problem[END_REF], one can try to construct stable functionals, namely Lipschitz-continuous functions of the data carrying relevant information on the geometry of the obstacle. According to formula (3.9), each coefficient a k , k 1, yields an example of such functional. Actually, we can prove that each coefficient is not only a Lipschitz-continuous function of the data, but is analytic. Let us define the following open subspace of L(H(Γ)):

U Γ = {R ∈ L(H(Γ)) : Id + R invertible and µ 1 (R) > 0},
where

µ 1 (R) := Q 1 Γ , (Id + R) -1 RQ 1 Γ 1
2 ,Γ . Notice in particular that, for every Lipschitz Jordan curve γ, the continuous linear mapping R = S Γ (Λ γ -Λ 0 ) belongs to U Γ . We deduce straightforwardly the following analyticity result: Theorem 3.8 On the open subset U Γ of L(H(Γ)) define the sequence of analytic functions a k : U Γ → C (k 1) as given by the formulae (3.9). If R = S Γ (Λ γ -Λ 0 ) for some Lipschitz Jordan curve γ, a parameterization of γ is given by:

t ∈] -π, π] → k 1 a k (R)e ikt ∈ C.
At least theoretically, each coefficient a k can be computed in a stable way from a given noisy data using formulae (3.9). However, one cannot expect to recover in a stable way the whole sequence (a k ) k 1 (and thus the geometry of the cavity). In practice, the level of noise limits the number of coefficients that can be accurately recovered.

Numerical results

We present in this section some numerical experiments meant to illustrate the feasibility of the proposed reconstruction method. For the sake of clarity, let us first sum up the different steps of the simple reconstruction algorithm:

1. Compute a numerical approximation of the operator R = S Γ (Λ γ -Λ 0 ).

Fix an integer M and compute for 1 m M µ

m := 1 2 Q m γ , Q 1 γ 1 2 ,γ = 1 2 Q m Γ , (Id + R) -1 RQ 1 Γ 1 2 ,Γ ν m := 1 2 Q m γ , Q 1 γ 1 2 ,γ = 1 2 Q m Γ , (Id + R) -1 RQ 1 Γ 1 2 ,Γ .
3. Compute (a -m ) -1 m M via formulae (3.9).

4. Plot the image of the unit circle by

φ M (z) = a 1 z + a 0 + 1 m M a -m z -m .
Let us give some details about the implementation. We use the finite dimensional approximation space spanned by the family

Q M Γ := {Q m Γ , Q m Γ , 1 m M }.
We denote by Q Γ the 2M × 2M complex matrix whose entries are the f, g 1 2 ,Γ , where (f, g)

∈ Q M Γ × Q M Γ .
Note that Q Γ is nothing but the Generalized Polya-Szegö Tensor (GPST) associated with Γ. Obviously, a similar matrix Q γ can be defined for the boundary γ. We denote by R the matrix whose entries are f, Rg

1 2 ,Γ = (Λ γ -Λ 0 )g, f -1 2 , 1 2 ,Γ , for (f, g) ∈ Q M Γ × Q M Γ .
With this notation, the reader can easily check that formula (3.6) admits the following discrete version:

Q γ Q γ := Q Γ (Q Γ + R) -1 R. (4.1)
This formula relates in a very simple way, through the measurement operator R, the GPST of γ to the GPST of Γ. In particular, the coefficients µ m and ν m are particular entries of 1 2 Q γ . We consider now a test configuration in which Γ is an ellipse centered at the origin and of major axis [-1.9, 1.9] and minor axis [-1.1, 1.1]. The boundary γ of the obstacle is parameterized by:

t ∈] -π, π] → 1 k=-7
a k e ikt , where the complex coefficients a k are given in the following table:

a 1 a 0 a -1 a -2 a -3 a -4 a -5 a -6 a -7
0.5 -1 0.085 -0.06i -0.035 0.06i 0 -0.01i -0.005

The data are generated using the Matlab Laplace boundary integral equation solver (for more information, see this link: IES). Taking M = 12, we first show on Figure 2 the reconstructed cavity for exact data and using the eight coefficients a 1 , . . . , a -6 .

Instead of using the harmonic polynomials z n in Definition 3.2, one can use the shifted harmonic polynomials (z -r) n , for some given r ∈ C. This additional parameter turns out to have some influence on the quality of the reconstructed cavities, as shown in Figure 3. For instance, choosing r in the neighborhood of -0.5, one can recover the six coefficients a 1 , . . . , a -4 with a relative error less than 2%, while for r = 0 this accuracy is achieved only for the coefficients a 1 , . . . , a -2 .

Let us take now r = -0.5 and consider a more realistic configuration of noisy data. We generate a random matrix N having the same size as R and whose coefficients are uniformly distributed between -1 and 1. For δ = 0.05, 0.15, 0.25, 0.35, we compute the matrix R N whose coefficients are:

R N ij = (1 + δN ij )R ij , 1 i, j 2M,
and we replace R by R N in formula (4.1). We show on figures 4-7 examples of reconstructed cavities respectively with 5%, 15%, 25% and 35% of noise. The number of correctly recovered coefficients decreases with the level of noise and only those coefficients are used in the reconstruction. We plot on Figure 8 the dependence of the mean relative error with respect to the level of noise and we notice a good stability of the first three coefficients a 1 , a 0 and a -1 .

Finally, we illustrate on Figure 9 the efficiency of the method for more complex geometries (non convex outer boundary Γ and a non centered cavity). The choice of the parameter r to obtain good reconstructions is not clear so far and this would need to be further investigated.

A Appendix

Consider problem (1.1) with a piecewise conductivity σ(x) = 1 + (α -1)1 ω (x) (where 1 ω denotes the characteristic function of ω and α a positive constant). The function u f can be considered as a function of H 1 (Ω) by setting u f = c f in ω.

For every α > 0, System (1.1) admits a unique solution u f α ∈ H 1 (Ω). This function achieves: The following convergence result holds true for every f ∈ H where we have used the fact that u f = c f in ω. The existence and uniqueness for such a problem is straightforward and we denote by w f α the minimizer. Introducing

min u∈H 1 (Ω)
w f α = 1 mes(ω) ω w f α dx,
and taking into account the condition (1.2d), the last term in the right hand side can be rewritten as:

γ ∂ n u f w f α dσ = γ ∂ n u f (w f α -w f α ) dσ.
Invoking the Poincaré-Wirtinger inequality in ω, we get the estimate: Remarking again that the minimum (A.4) is negative and using the estimate (A.5) together with the convergence result (A.6), we deduce that:

∇w f α L 2 (Ω\ω) → 0 as α → +∞,
and the proof is completed.

Figure 1 :

 1 Figure 1: The geometry.

Definition 2 . 3 1 2 , 1 2 ,C = 1 .

 23111 The equilibrium density for C is the unique density êC ∈ H -1 2 (C ) such that S C êC is constant on C and êC , 1 -The logarithmic capacity Cap(C ) of C is defined as being the positive constant:

Definition 2 . 6 1 2

 261 We denote by Tr C the classical trace operator (valued into H (C )), and by Tr 0 C when it is left-composed with the orthogonal projection onto H(C ): Tr 0 C := Π C Tr C .

Figure 2 :Figure 3 :

 23 Figure 2: Typical configuration: reconstruction with a 1 , . . . , a -6 (in red) and actual inclusion (in gray). The blue point stands for the position of the origin r.

Figure 4 :

 4 Figure 4: Reconstruction (in red) with a 1 , . . . , a -4 and actual inclusion (in gray) with 5% noise.

Figure 5 :

 5 Figure 5: Reconstruction (in red) with a 1 , . . . , a -4 and actual inclusion (in gray) with 15% noise.

Proposition A. 1 1 2 2 Figure 6 :

 1126 Figure 6: Reconstruction (in red) with a 1 , . . . , a -2 and actual inclusion (in gray) with 25% noise.

Figure 7 :

 7 Figure 7: Reconstruction (in red) with a 1 , . . . , a -1 and actual inclusion (in gray) with 35% noise.

1 2 |∇u| 2 dx + α 2 ω |∇u| 2

 122 Ω\ω dx : u| Γ = f . (A.2)

  f in H 1 (Ω) as α → +∞. Proof : The minimization problem (A.1) can be reformulated as: min (w,c)∈H 1 0 (Ω\ω)×R Ω\ω |∇(w + e f + cv)| 2 dx, (A.3)

Figure 8 :Figure 9 :Ω\ω |∇w| 2 dx + Ω\ω |∇e f | 2 dx + c 2 Ω\ω |∇v| 2 ∂ n e f dσ Ω\ω |∇v| 2 dx - 1 .

 89221 Figure 8: Relative error of the retrieved coefficients (in %) with respect to the level of noise (in %) of the data. The point r is the center of the ellipse. Notice the stability of the conformal center a 0 and the logarithmic capacity a 1 .

γ ∂ n u f w f α dσ C ∇w f α L 2 2

 22 (ω) , (A.[START_REF] Ammari | Generalized polarization tensors for shape description[END_REF] where the constant C > 0 depends only upon ω. The minimum (A.4) is negative (w = 0 is an admissible function), whence we deduce that: (ω) → 0 as α → +∞.(A.6)


Jie Chen

Benoît Libert
email: benoit.libert@ens-lyon.fr

Somindu C Ramanna
email: somindu.ramanna@ens-lyon.fr

Non-Zero Inner Product Encryption with Short Ciphertexts and Private Keys

Keywords: Functional encryption, non-zero inner products, (identity-based) revocation

We describe two constructions of non-zero inner product encryption (NIPE) systems in the public index setting, both having ciphertexts and secret keys of constant size. Both schemes are obtained by tweaking the Boneh-Gentry-Waters broadcast encryption system (Crypto 2005) and are proved selectively secure without random oracles under previously considered assumptions in groups with a bilinear map. Our first realization builds on prime-order bilinear groups and is proved secure under the Decisional Bilinear Diffie-Hellman Exponent assumption, which is parameterized by the length n of vectors over which the inner product is defined. By moving to composite order bilinear groups, we are able to obtain security under static subgroup decision assumptions following the Déjà Q framework of Chase and Meiklejohn (Eurocrypt 2014) and its extension by Wee (TCC 2016). Our schemes are the first NIPE systems to achieve such parameters, even in the selective security setting. Moreover, they are the first proposals to feature optimally short private keys, which only consist of one group element. Our prime-order-group realization is also the first one with a deterministic key generation mechanism.

Introduction

Attribute-based encryption (ABE) [START_REF] Sahai | Fuzzy Identity-Based Encryption In Eurocrypt'05[END_REF][START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] allows fine-grained access control to encrypted data. In an ABE system, a ciphertext has an associated attribute x and a secret key for a user associated to some attribute y can successfully decrypt iff some relation R on x, y holds true i.e., R( x, y) = 1. An ABE scheme is said to be secure if a collusion attack by a group of users does not compromise the security of a ciphertext they are not allowed to decrypt. In this work, we consider attributes belonging to some inner product space V and the relation is given by R( x, y) = 1 iff x, y = 0, for x, y ∈ V . Such an ABE (referred to as non-zero inner product encryption scheme or NIPE) is known to imply identity-based revocation, an important cryptographic primitive in its own right.

Identity-based revocation (IBR) allows a sender to encrypt and broadcast a message to a number of identities, given a set of revoked users R, so that only secret keys associated with identities outside of R can decrypt the message. NIPE systems are known to imply IBR -the attribute associated with the ciphertext (of length n) is nothing but the vector of coefficients of the polynomial p R (Z) = id i ∈R (Z -id i ) where |R| ≤ n and the secret key for an identity id corresponds to the vector (1, id, . . . , id n ). The inner product is non-zero if and only if p R (id) = 0 or equivalently id / ∈ R, in which case decryption succeeds.

In this paper, our main goal is to design NIPE (and thus revocation) schemes that simultaneously provide short ciphertexts and private keys. We will also seek to prove security under well-studied hardness assumptions.

Our Contribution. We first present a NIPE system employing prime-order bilinear groups where ciphertexts and secret keys both have constant3 size. Our scheme is the first one where both sizes can be constant. Indeed, all earlier realizations [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF][START_REF] Attrapadung | Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[END_REF][START_REF] Okamoto | Achieving short ciphertexts or short secret-keys for adaptively secure general innerproduct encryption[END_REF] providing O(1)-size ciphertexts (resp. O(1)-size private keys) indeed required O(n) group elements in private keys (resp. in ciphertexts), where n denotes the dimension of the inner product space which is fixed at setup time. Even in the selective model [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF][START_REF] Attrapadung | Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[END_REF], all previous constructions thus had linear complexities in the size of ciphertexts or private keys.

The scheme is also the first NIPE realization to feature optimally short private keys -which only consist of onz group element -via a deterministic private key extraction algorithm. In particular, our NIPE scheme implies the first (identity-based) revocation system that simultaneously provides O(1)-size ciphertexts and private keys. It thus performs in the same way as the Boneh-Gentry-Waters (BGW) broadcast encryption [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF] system and relies on the same assumption. Like earlier NIPE proposals, our scheme requires O(n) group elements in the public parameters. In the broadcast revocation setting, this translates into a linear public key size in the maximal number of revoked users per ciphertext, which is on par with existing solutions [START_REF] Wee | Threshold and Revocation Cryptosystems via Extractable Hash Proofs[END_REF][START_REF] Naor | Efficient Trace and Revoke Schemes[END_REF] based on the Naor-Pinkas technique [START_REF] Naor | Efficient Trace and Revoke Schemes[END_REF].

The security of our scheme is proved against selective adversaries under the n-Decisional Bilinear Diffie-Hellman (n-DBDHE) assumption, the strength of which depends on the dimension n of handled vectors. While relying on such a parameterized assumption is certainly a caveat [START_REF] Cheon | Security Analysis of the Strong Diffie-Hellman Problem[END_REF], our scheme can be modified so as to dispense with variable-size assumptions.

Our second contribution is a NIPE system based on composite order pairing groups with security under constant-size subgroup decision assumptions. The proof follows the Déjà Q framework of [START_REF] Chase | Déjà Q: Using Dual Systems to Revisit q-Type Assumptions In Eurocrypt 2014[END_REF][START_REF] Wee | Déjà Q Encore! Un petit IBE[END_REF]. Even in the restrictive selective model of security, our scheme is the first one to achieve constant size ciphertexts and keys under static assumptions.

In the context of revocation, not only do we provide the first identity-based revocation systems with constant-size ciphertexts and keys, but we also give a solution based on fairly well-studied subgroup assumptions in composite order groups. It remains a challenging open problem (at least without using a complexity leveraging argument [START_REF] Boneh | Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles[END_REF] entailing an exponential security loss) to achieve similar efficiency tradeoffs while proving security against adaptive adversaries.

Outline of the constructions and proofs. We begin with the first construction based on an asymmetric prime-order pairing e : G × Ĝ → G T with group prder p. The public key consists of g α i , ĝα i for i ∈ [1, 2n] \ {n + 1} along with g γ where g and α, γ are sampled at random from G and Z p , respectively. In addition the element e(g, ĝ) α n+1 is provided. A ciphertext for an attribute vector x ∈ Z n p and message m consists of (m • e(g, ĝ)

α n+1 s , g s , (v • g n i=1 α i x i ) s ).
Secret key associated with a vector y is computed deterministically as ĝγ n i=1 α n-i+1 y i . The structure is reminiscent of the Boneh-Gentry-Waters broadcast encryption scheme [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF]. The proof is a reduction from the hardness of the n-DBDHE problem -an instance consists of g α i , ĝα i for i ∈ [1, 2n] \ {n + 1}, g s ∈ G, T ∈ G T and asks to decide whether T = e(g, ĝ) α n+1 s or T R ← G T . The attacker declares a target vector x * which is used to program γ = n i=1 α i x * i . For any y ∈ Z n p with x * , y = 0, secret keys can be simulated using the elements provided in the instance because the coefficient of α n+1 in the exponent of ĝ would be x * , y which is zero. The challenge T is embedded in the first component of the challenge ciphertext.

We then consider a variant in the setting of a composite-order symmetric pairing e : G×G → G T of common group order N = p 1 p 2 p 3 , similar to Wee's composite-order variant [START_REF] Wee | Déjà Q Encore! Un petit IBE[END_REF] of the broadcast encryption in [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF]. (Let G q denote the subgroup of G of order q where q would be of the form p e 1 1 p e 2 2 p e 3 3 for e 1 , e 2 , e 3 ∈ {0, 1}). The public key is composed of v = g γ , (g

α i ) n i=1 , U j = u α j , j ∈ [1, 2n] \ {n + 1} for some g, u R
← G and α, γ ∈ Z N along with a pairwise-independent hash function H : G T → {0, 1} λ . Decryption key for a vector y is defined as u γ n i=1 α n-i+1 y i and the ciphertext for attribute x and message M is defined as (M ⊕ H(e(g, u) α n+1 s ), g s , (v • g n i=1 α i x i ) s ). In addition, the parameters U j and secret keys are randomized with G p 3 -components. The security is reduced to two standard subgroup decision assumptions, denoted (p 1 → p 1 p 2 ) and (p 1 p 3 → p 1 p 2 p 3 ), where (q 1 → q 2 ) subgroup decision problem asks to distinguish between random elements of G q 1 from random elements of G q 2 . The reduction gradually adds G p 2 -components to the challenge ciphertext as well as elements (U j ) 2n

j=1 so that at the end, each U j has in its exponent a pseudorandom function RF : [1, 2n] → Z p 2 evaluated at j. The element v = g γ is programmed based on the challenge attribute x * in a manner similar to the reduction in the prime-order case. Additionally, this ensures that the challenge ciphertext components are independent of α mod p 2 . Given this and the fact that keys are generated only for vectors y with x * , y = 0, α n+1 does not appear in the exponent of u in any of the keys. On the other hand, the message is masked by the hash of an element of G T determined by RF (n + 1). Since all information provided to the attacker is independent of RF (n + 1), we use the left over hash lemma to argue that the mask on the message is uniformly distributed and hence statistically hides the message from the attacker. Related Work. The inner product functionality was first considered by Katz, Sahai and Waters [START_REF] Katz | Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products[END_REF] in the design of predicate encryption systems (i.e., ABE schemes in the private index setting). Their construction [START_REF] Katz | Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products[END_REF] initiated a large body of work [START_REF] Okamoto | Hierarchical Predicate Encryption for Inner-Products[END_REF][START_REF] Shen | Predicate Privacy in Encryption Systems[END_REF][START_REF] Okamoto | Fully Secure Unbounded Inner-Product and Attribute-Based Encryption[END_REF][START_REF] Agrawal | Functional Encryption for Inner Product Predicates from Learning with Errors[END_REF][START_REF] Lewko | Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption[END_REF][START_REF] Okamoto | Fully secure functional encryption with general relations from the decisional linear assumption[END_REF][START_REF] Okamoto | Adaptively Attribute-Hiding (Hierarchical) Inner Product Encryption[END_REF][START_REF] Okamoto | Fully Secure Unbounded Inner-Product and Attribute-Based Encryption[END_REF][START_REF] Okamoto | Achieving short ciphertexts or short secret-keys for adaptively secure general innerproduct encryption[END_REF] which considered hierarchical extensions [START_REF] Okamoto | Hierarchical Predicate Encryption for Inner-Products[END_REF][START_REF] Okamoto | Fully Secure Unbounded Inner-Product and Attribute-Based Encryption[END_REF], additional properties in the secret-key setting [START_REF] Shen | Predicate Privacy in Encryption Systems[END_REF] and adaptively secure realizations [START_REF] Lewko | Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption[END_REF][START_REF] Okamoto | Fully secure functional encryption with general relations from the decisional linear assumption[END_REF][START_REF] Okamoto | Adaptively Attribute-Hiding (Hierarchical) Inner Product Encryption[END_REF][START_REF] Okamoto | Fully Secure Unbounded Inner-Product and Attribute-Based Encryption[END_REF][START_REF] Okamoto | Achieving short ciphertexts or short secret-keys for adaptively secure general innerproduct encryption[END_REF].

In the public-index setting, inner products also proved useful [START_REF] Attrapadung | Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[END_REF] to build adaptively secure identity-based broadcast encryption (IBBE) and revocation schemes with short ciphertexts under simple assumptions. The first construction of non-zero IPE appeared in [START_REF] Attrapadung | Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[END_REF] with security in the coselective model under the Decision Linear [START_REF] Boneh | Short Group Signatures[END_REF] and Decisional Bilinear Diffie-Hellman assumptions. Co-selective security requires an adversary to commit to the attributes corresponding to private key queries before seeing the public parameters of the scheme, as opposed to target attribute set in the selective model. It is slightly stronger than the selective model but weaker than the adaptive model. The scheme has constant-size ciphertexts whereas its public parameters and keys are of size linear in n. More efficient realizations (but with asymptotically similar parameters) were put forth by Attrapadung et al. [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF] and Yamada et al. [START_REF] Yamada | A Framework and Compact Constructions for Nonmonotonic Attribute-Based Encryption[END_REF] under the n-DBDHE assumption. While some of the NIPE constructions of [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF][START_REF] Yamada | A Framework and Compact Constructions for Nonmonotonic Attribute-Based Encryption[END_REF] have exactly the same ciphertext length (resp. private key length) as our scheme, they require O(n)-size private keys (resp. O(n)-size ciphertexts). We thus prove security under the same assumption as [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF][START_REF] Yamada | A Framework and Compact Constructions for Nonmonotonic Attribute-Based Encryption[END_REF] with only one group element per private key and 3 group elements per ciphertext.

The first adaptively secure NIPE scheme was proposed in [START_REF] Okamoto | Achieving short ciphertexts or short secret-keys for adaptively secure general innerproduct encryption[END_REF] with O(n) group elements in the public parameters and either O(1)-size ciphertexts or O(1)-size keys with a security reduction to the Decision Linear assumption. A more efficient construction was provided in [START_REF] Chen | Improved Dual System ABE in Prime-Order Groups via Predicate Encodings[END_REF] via an instantiation of predicate encodings [START_REF] Wee | Dual System Encryption via Predicate Encodings[END_REF] in prime-order groups. On the other hand, either ciphertexts or secret keys had size linear in n. Previously known constructions did not consider simultaneously achieving constant size ciphertexts and secret keys.

More recently, Abdalla et al. [START_REF] Abdalla | Simple Functional Encryption Schemes for Inner Products[END_REF] suggested a different inner product functionality which evaluates linear functions of encrypted data (i.e., their inner product with a vector associated with the private key), instead of only testing if they evaluate to 0 as in [START_REF] Katz | Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products[END_REF][START_REF] Lewko | Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption[END_REF][START_REF] Okamoto | Fully secure functional encryption with general relations from the decisional linear assumption[END_REF][START_REF] Okamoto | Adaptively Attribute-Hiding (Hierarchical) Inner Product Encryption[END_REF][START_REF] Okamoto | Fully Secure Unbounded Inner-Product and Attribute-Based Encryption[END_REF][START_REF] Okamoto | Achieving short ciphertexts or short secret-keys for adaptively secure general innerproduct encryption[END_REF]. Under simple assumptions, they obtained practical solutions based on the standard Decision Diffie-Hellman and Learning-With-Errors assumptions. Their results were extended to handle adaptive adversaries [START_REF] Agrawal | Fully Secure Functional Encryption for Inner Products, from Standard Assumptions[END_REF] and functionprivacy in the secret-key setting [START_REF] Bishop | Function-Hiding Inner Product Encryption[END_REF].

In the context of IBBE scheme, Delerablée [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF] suggested a selectively secure construction with constant-size ciphertexts and private keys based on strong q-type assumptions. Her construction actually remains the most efficient IBBE in the literature to date. The IBR system implied by our first NIPE construction can be seen as the revocation analogue of Delerablée's IBBE as it simultaneously provides O(1)-size ciphertexts and keys (the public parameters also have linear length in the maximal number of receivers per ciphertext in [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF]). Unlike our IBR system, however, [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF] is not known to have a counterpart based on simple assumptions in composite order groups. In the identity-based revocation setting, the constructions of Lewko, Sahai and Waters [START_REF] Lewko | Revocation Systems with Very Small Private Keys[END_REF] feature constant-size private keys and public parameters, but their ciphertext size is linear in the number of revoked users. While their first construction has very short private keys and public parameters (made of 3 and 4 group elements, respectively), its underlying complexity assumption is very ad hoc and even stronger than n-DBDHE.

The Déjà Q framework, introduced by Chase and Meiklejohn [START_REF] Chase | Déjà Q: Using Dual Systems to Revisit q-Type Assumptions In Eurocrypt 2014[END_REF], allows reducing well-studied fixed-size assumptions, such as the Subgroup Decision assumption [START_REF] Boneh | Evaluating 2-DNF Formulas on Ciphertexts[END_REF] to some families of parameterized assumptions in composite-order groups. As a result, some well-known constructions such as Dodis-Yampolskiy PRF [START_REF] Dodis | A Verifiable Random Function with Short Proofs and Keys[END_REF] and Boneh-Boyen signatures [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF], when instantiated in composite order groups, could be shown secure under subgroup decision assumptions. Wee [START_REF] Wee | Déjà Q Encore! Un petit IBE[END_REF] further advanced the framework to cover certain encryption primitives as well, in addition to removing the restriction to work with asymmetric composite order groups. The primitives include adaptively secure identitybased encryption and selectively secure broadcast encryption. Recently, Libert et al. [START_REF] Libert | Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions (Full Version)[END_REF] applied Wee's framework to obtain functional commitment schemes for linear functions and accumulators from simple assumptions.

Background

Bilinear Maps and Complexity Assumptions

Assumptions in prime order groups. Let (G, Ĝ, G T ) be cyclic groups of prime order p with a bilinear map e : G × Ĝ → G T . We rely on a parameterized assumption which was introduced by Boneh, Gentry and Waters [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF]. While this assumption was originally defined using symmetric pairings [START_REF] Boneh | Hierarchical Identity-Based encryption with Constant Size Ciphertext[END_REF][START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF], we consider a natural extension to asymmetric pairings, which will enable our most efficient construction. Definition 1. Let (G, Ĝ, G T ) be asymmetric bilinear groups of prime order p. The n-Decision Bilinear Diffie-Hellman Exponent (n-DBDHE) problem is, given

(g, g α , g (α 2 ) , . . . , g (α n ) , g (α n+2 ) , . . . , g (α 2n ) , h, ĝ, ĝα , ĝ(α 2 ) , . . . , ĝ(α n ) , ĝ(α n+2 ) , T ) where α R ← Z p , g, h R ← G, ĝ R ← Ĝ and T ∈ R G T , to decide if T = e(h, ĝ) (α n+1 ) or if T is a random element of G T .
Assumptions in composite order groups. We use groups (G, G T ) of composite order N = p 1 p 2 p 3 endowed with an efficiently computable map (a.k.a. pairing) e : G × G → G T such that: (1) e(g a , h b ) = e(g, h) ab for any (g, h) ∈ G × G and a, b ∈ Z; (2) if e(g, h) = 1 G T for each h ∈ G, then g = 1 G . An important property of composite order groups is that pairing two elements of order p i and p j , with i = j, always gives the identity element 1 G T .

In the following, for each i ∈ {1, 2, 3}, we denote by G p i the subgroup of order p i . For all distinct i, j ∈ {1, 2, 3}, we call G p i p j the subgroup of order p i p j . In this setting, we rely on the following assumptions introduced in [START_REF] Lewko | New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts[END_REF].

Assumption 1 Given a description of (G, G T , e) as well as

g R ← G p 1 , g 3 R ← G p 3 and T ∈ G, it is infeasible to efficiently decide if T ∈ G p 1 p 2 or T ∈ G p 1 . Assumption 2 Let g, X 1 R ← G p 1 , X 2 , Y 2 R ← G p 2 , g 3 , Y 3 R ← G p 3 . Given a description of (G, G T , e), a set of group elements (g, X 1 X 2 , g 3 , Y 2 Y 3 ) and T , it is hard to decide if T ∈ R G p 1 p 3 or T ∈ R G.
These assumptions are non-interactive and falsifiable [START_REF] Naor | On Cryptographic Assumptions and Challenges[END_REF]. Moreover, in both of them, the number of input elements is constant (i.e., independent of the number of adversarial queries).

Non-Zero Inner Product Encryption (IPE)

Definition 2 (NIPE). Let V denote an inner product space of dimension n and M denote the message space. A non-zero inner product encryption (NIPE) scheme for inner products over V , is defined by four probabilistic algorithms -Setup, Encrypt, KeyGen and Decrypt.

Setup(λ, n): Takes as input a security parameter λ and the dimension of V . It outputs the public parameters mpk and the master secret msk. KeyGen(msk, y): On input a vector y ∈ V and the master secret msk; this algorithm outputs a secret key d y for y. Encrypt(mpk, m, x): Takes as input a message m and an attribute vector x ∈ V and outputs a ciphertext C. Decrypt(mpk, C, d y ): If x, y = 0, this algorithm returns the message m and ⊥ otherwise.

Correctness. A NIPE scheme satisfies the correctness condition if for all vectors x, y ∈ V with x, y = 0 and for any message m ∈ M, any keys (mpk, msk) ← Setup(λ, n), d y ← KeyGen(msk, y) and any ciphertext C ← Encrypt(mpk, m, x), then Pr[m = Decrypt(mpk, C, d y )] = 1.

Definition 3 (Selective Security). Selective security of a non-zero inner product encryption scheme is formalized in terms of the following game between an adversary A and a challenger.

Initialization:

The adversary A declares a challenge vector x .

Setup: The challenger runs the Setup algorithm of the NIPE and gives the public parameters to the adversary A. Key Extraction Phase 1: The adversary makes a number of key extraction queries adaptively. For a query on a vector y with the restriction that x , y = 0, the challenger responds with a private key d y for y.

Challenge:

The adversary A provides two equal-length messages M 0 , M 1 . The challenger chooses a bit β uniformly at random from {0, 1}, encrypts M β to x and returns the resulting ciphertext C to the adversary A.

Key Extraction Phase 2:

A makes more key extraction queries under the same restriction that it can only query a key for any vector y with x , y = 0. Guess: A outputs a bit β .

If β = β , then A wins the game. The advantage of A in winning the above game is defined as

Adv NIPE,A (λ) = Pr[β = β ] - 1 2 .
The NIPE scheme is said to be secure if every PPT adversary has negligible advantage in winning the above game.

A Construction for Non-Zero Inner Products with Constant-Size Ciphertexts and Private Keys

Our scheme builds on the Boneh-Gentry-Waters broadcast encryption [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF] and inherits its efficiency.

In particular, the public parameters are exactly those of the BGW construction. In order to adapt it in the context of non-zero inner product encryption, we extend earlier observations which leveraged the BGW technique in the design of accumulators [START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF] and vector commitments [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF][START_REF] Izabachène | Blockwise P-Signatures and Non-Interactive Anonymous Credentials with Efficient Attributes[END_REF]. It was shown in [START_REF] Izabachène | Blockwise P-Signatures and Non-Interactive Anonymous Credentials with Efficient Attributes[END_REF] that a public key of the form {(g i = g (α i ) , ĝi = ĝ(α i ) )} i∈ [1,2n]\{n+1} allows committing to a vector x = (x 1 , . . . , x n ) in such a way that the commitment string C = g γ • n j=1 g

x j j

makes it possible to convincingly reveal the partial information z = x, y about the committed message x. Namely, a single group element

W z = n i=1,i =j (ĝ γ n+1-i n j=1 ĝx j n+1+j-i ) y i ∈ Ĝ (1)
can serve as a witness that z = x, y , for public x ∈ Z n p and z ∈ Z p , and the verifier accepts (z, W z ) if and only if the following relation holds:

e(C, n j=1 ĝy j n+1-j ) = e(g 1 , ĝn ) z • e(g, W z ) (2)
The binding property of the commitment scheme relies on the fact that neither g n+1 = g (α n+1 ) nor ĝn+1 = ĝ(α n+1 ) is publicly available. Our non-zero IPE scheme proceeds by randomizing both members of (2) -by raising them to a random power s ∈ Z p -so that the randomized C can be embedded in the ciphertext (together with g s ) while W z serves as a decryption token. The decryption operation then computes e(g 1 , ĝn ) s• x, y , which uncovers e(g 1 , ĝn ) s whenever x, y = 0.

In our scheme, ciphertexts are of the form

(C 0 , C 1 , C 2 ) = M • e(g 1 , ĝn ) s , g s , (g γ • n j=1 g x j j
) s and the challenge is thus to associate each vector y ∈ Z p with a short private key d y so as to enable decryption. To achieve this, we observe that (1) can be re-written as

W z = ( i=1 ĝy i n+1-i ) γ • n i=1,i =j n j=1 ĝx j y i n+1+j-i ∈ Ĝ,
where the second term is publicly computable as it does not depend on ĝn+1 = ĝ(α n+1 ) . This implies that, if γ ∈ Z p is the master secret key, the private key for a vector y can only consist of a single group element d y = ( n j=1 ĝy j n+1-j ) γ ∈ Ĝ. Somewhat surprisingly, private keys are generated in a deterministic manner and, at first glance, their shape seems at odds with the collusion-resistance requirement: if d y 1 is a private key for y 1 ∈ Z p and d y 2 is a private key for y 2 ∈ Z p , the product d y 1 • d y 2 is a valid private key for y 1 + y 2 . However, this does not affect the NIPE functionality since any ciphertext that neither d y 1 nor d y 2 can decrypt must be labeled with a vector x such that x, y 1 = x, y 2 = 0, which implies x, y 1 + y 2 = 0. Said otherwise, combining several keys that cannot decrypt a given ciphertext only yields another key that remains unable to decrypt.

Setup(λ, n): Choose bilinear groups (G, Ĝ, G T ) of prime order p > 2 λ and define the bilinear map e. Choose g R ← G, ĝ R ← Ĝ, α, γ R ← Z p at random in order to define v = g γ ∈ G and

g 1 = g α , . . . g n = g (α n ) g n+2 = g (α n+2 ) , . . . g 2n = g (α 2n
) and ĝ1 = ĝα , . . .

ĝn = ĝ(α n ) ĝn+2 = ĝ(α n+2 ) , . . . ĝ2n = ĝ(α 2n )
Define the master public key to consist of

mpk := (G, Ĝ, G T , e), g, ĝ, v, {(g j , ĝj )} j∈[1,2n]\{n+1} .
The master secret key is msk := γ.

KeyGen(msk, y):

To generate a key for the vector y = (y 1 , . . . , y n ) ∈ Z n p , compute and output

d y = n i=1 ĝy i n+1-i γ ∈ Ĝ. Encrypt(mpk, x, M ): To encrypt M ∈ G T under x = (x 1 , . . . , x n ) ∈ Z n p , choose s R ← Z p in order to compute and output C = (C 0 , C 1 , C 2 ) = M • e(g 1 , ĝn ) s , g s , (v • n j=1 g x j j ) s .
Decrypt(mpk, C, x, d y , y): Given a ciphertext C labeled with x = (x 1 , . . . , x n ) ∈ Z n p and a private key d y associated with the vector y = (y 1 , . . . , y n ) ∈ Z n p , return ⊥ if x• y = 0. Otherwise, conduct the following steps. (3)

Compute and output

M = C 0 • e(C 1 , d y • n i=1 Ây i i ) e(C 2 , n i=1 ĝy i n+1-i ) 1/( x• y) . ( 4
)
The correctness of the scheme is easily verified by observing that e g, ( n i=1

ĝy i n+1-i ) γ • n i=1 n j=1,j =i ĝx j y i n+1-i+j e g γ • n j=1 g x j j , n i=1 ĝy i n+1-i ) = e g, ( n i=1 ĝy i n+1-i ) γ • n i=1 n j=1,j =i ĝx j y i n+1-i+j e(g γ • n j=1 ĝy i n+1-i ) • e g, n i=1 n j=1 g x j y i n+1-i+j ) = e(g, ĝn+1 ) -n i=1 x i y i . (5)
By raising both members of (5) to the power s ∈ Z p and using (3), we obtain the equality

e(C 1 , d y • n i=1 Ây i i )/e(C 2 , n i=1 ĝy i n+1-i ) = e(g 1 , ĝn ) -s• x, y ,
which explains why M can be computed as per (4) whenever x • y = 0. From an efficiency point of view, the receiver has to compute a product of only two pairings (which is faster than two individual pairing evaluations) while the encryption and decryption algorithms both require at most O(n) exponentiations. Indeed, the value d y • n i=1 Ây i i is computable via a multi-exponentiation involving 2n -1 base elements (rather than n 2 in a naive computation). Theorem 1. The scheme is selectively secure under the n-DBDHE assumption.

Proof. For the sake of contradiction, let A be a PPT adversary with non-negligible advantage ε in the selective security game. We build a reduction algorithm that takes as input ((G, Ĝ, G T , e), g, h,

{(g i , ĝi ) = (g (α i ) , ĝ(α i ) )} i∈[1,2n]\{n+1} , T ) and uses A to decide if T = e(h, ĝ) (α n+1 ) or T ∈ R G T .
The adversary A first chooses a target vector x = (x 1 , . . . , x n ) ∈ Z n p . To construct the master public key mpk, B chooses γ R ← Z p and computes

v = g γ • n j=1 g -x j j ∈ G,
which implicitly defines the master secret key msk to be γ = γ -n j=1 x j • α j . The adversary A is run on input of mpk := g, ĝ, v, {(g i , ĝi ) = (g

(α i ) , ĝ(α i ) )} i∈[1,2n]\{n+1} .
Observe that mpk is distributed as in the real scheme as v is uniformly distributed over G. At any time, A can request a private key d y for any vector y ∈ Z N p such that x • y = 0. To generate the private key

d y = n i=1 ĝy i n+1-i γ ∈ Ĝ, algorithm B can exploit the fact that, in the product, n i=1 y i • α n+1-i • n j=1 x j • α j = n i=1 n j=1 x j • y i • α n+1-i+j ,
the coefficient of α n+1 is exactly x , y , which must be zero in any legal private key query y ∈ Z n p . Specifically, B can compute

d y = n i=1 ĝy i n+1-i γ / n i=1 n j=1,j =i ĝx j •y i n+1-i+j . (6)
For any vector y ∈ Z n p such that x , y = 0, B can thus compute the private key d y as per ( 6). In the challenge phase, A chooses messages M 0 , M 1 ∈ G T and expects to receive an encryption of one of these. At this point, B flips a fair coin β R ← {0, 1} and computes

C = (C 0 , C 1 , C 2 ) = M β • T, h, h γ ,
which is returned as a challenge to B. It is easy to see that, if T = e(h, ĝ) (α n+1 ) , then C is a valid encryption of M β for the vector x = (x 1 , . . . , x n ) and the encryption exponent s = log g (h). In contrast, if T ∈ R G T , the ciphertext carries no information about β ∈ {0, 1}.

When A halts, it outputs a bit β ∈ {0, 1}. If β = β, the reduction B outputs 1 (meaning that T = e(h, ĝ) (α n+1 ) ). Otherwise, it outputs 0.

NIPE from Constant-Size Subgroup Assumptions

In this section, we present a non-zero inner-product encryption (NIPE) scheme based on composite order pairings e : G×G → G T of common group order N = p 1 p 2 p 3 , with security under the subgroup decision assumptions. For inner products over length-n vectors in Z N , the public parameter size is linear in n while ciphertexts and keys have constant size (independent of n). The resulting scheme is the first to achieve such parameters with selective security under constant size assumptions.

Similar to the prime-order case, it seems possible to derive this construction from a functional commitment scheme for linear functions [START_REF] Libert | Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions (Full Version)[END_REF] by randomizing commitments and the verification equation. However, the transformation is not generic. A commitment C to a message x ∈ Z n N in [START_REF] Libert | Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions (Full Version)[END_REF] is computed as

C = g γ • g n i=1 α i •x i . Elements g γ , {g α i } n
i=1 are made available in the public parameters along with elements U j = u α j • R 3,j for j ∈ [1, 2n] \ {n + 1} with R 3,j being randomly distributed in G p 3 . The U j 's allow creating a short witness W z for the statement z = x, y (for some y ∈ Z n N ) using the secret random exponent γ.

W z = n i=1 W y i i , where W i = U γ n-i+1 n j=1,j =i U n+1+j-i .
Consolidating all the terms that depend on γ into W z,1 , write

W z = W z,1 • W z,2 .
More precisely, we have

W z,1 = n i=1 U γ n-i+1 and W z,2 = n i=1   n j=1,j =i U n+1+j-i   y i .
Observe that the computation of W z,2 is solely based on information available in the public parameters and W z,1 is independent of x. One can verify the validity of the witness W z by simply checking whether the following equation holds.

e(C,

n i=1 U y i i ) = e(g α , U n ) z • e(g, W z ).
Randomizing both sides of the above equation with s ∈ Z N in the exponent leads us to the nonzero IPE. Namely, a ciphertext for a vector x and a message M ∈ {0, 1} λ would consist of C s , g s and M ⊕ H e(g α , U n ) s , where H : G T → {0, 1} λ is a pairwise-independent hash function. The decryption key for a vector y is nothing but W z,1 . For a valid key, the fact that z = x, y = 0 enables us to recover the blinding factor on the message from e(g α , U n ) zs .

Setup(λ, n): Takes as input n, the dimension of the inner product space. Choose bilinear groups (G, G T ) of composite order N = p 1 p 2 p 3 , where p i > 2 l(λ) for each i ∈ {1, 2, 3}, for a suitable polynomial l : N → N. Define the bilinear map e : G × G → G T . We consider inner products defined over

Z n N . Choose g, u R ← G p 1 , R 3 R ← G p 3 and α, γ R ← Z N at random in order to define G 1 = g α , G 2 = g (α 2 ) , . . . , G n = g (α n )
and

U 1 = u α • R 3,1 , U 2 = u (α 2 ) • R 3,2 , . . . , U n = u (α n ) • R 3,n U n+2 = u (α n+2 ) • R 3,n+2 , . . . , U 2n = u (α 2n ) • R 3,2n , where R 3,j R ← G p 3 for each j ∈ [1, 2n]\{n + 1}. Define the public parameters to consist of mpk := (G, G T , e), g, g γ , {G j } n j=1 , {U j } j∈[1,2n]\{n+1} , H ,
where H : G T → {0, 1} λ is a pairwise-independent hash function. The master secret key is given by msk := (u, R

Encrypt(mpk, M, x = (x 1 , . . . , x n )): To encrypt M ∈ {0, 1} λ under x ∈ Z n N , choose s R ← Z N and define the ciphertext C to consist of three components -one from G T and two from G given by

C 0 = M ⊕ H(e(g, u) α n+1 s ), C 1 = g s , C 2 = g s•(γ+ n i=1 α i •x i ) ,
where C 0 and C 2 are computed as

M ⊕ H e(G 1 , U n ) s and (g γ • n i=1 G x i i ) s , respectively. The algorithm outputs C = (C 0 , C 1 , C 2 ).
KeyGen(msk, y): The secret key for y = (y 1 , . . . , y n ) ∈ Z n N is given by

d y = n i=1 u α i •y i γ • X 3 , where X 3 R ← G p 3 is sampled using R 3 . Decrypt(C, x, y, d y ): Let w = x, y mod N . If w = 0 the algorithm computes A i = n j=1,j =i U x j n+1+j-i
for all i ∈ [1, n], and recovers M ∈ {0, 1} λ as

M = C 0 ⊕ H e(C 1 , d y • n i=1 A y i i ) e(C 2 , n i=1 U y i n-i+1 ) 1/w .
Correctness. Correctness follows from the observation that

e(C 2 , U n-i+1 ) = e g s•(γ+ n i=1 α i x i ) , u (α n-i+1 ) • R 3,n+2 = e g γ • n i=1 G x i i , u (α n-i+1 ) s = e g γ • n i=1 g α i •x i , u (α n-i+1 ) s = e(g, u) α n+1 •s•x i • e   g, u γ n-i+1 • n j=1,j =i u α n+1+j-i •x j   s = e(g, u) α n+1 •s•x i • e g, u γ n-i+1 • A i s .
Raising both sides of the above equality to y i and taking a product over all i ∈ [1, n] gives us

e C 2 , n i=1 U y i n-i+1 = n i=1 e(g, u) α n+1 •s•x i •y i • n i=1 e g, u (α n-i+1 )•γ • A i s•y i = e(g, u) α n+1 •s• x, y • e g s , n i=1 u (α n-i+1 )•γ•y i • A y i i = e(g, u) α n+1 •s•w • e C 1 , d y • n i=1 A y i i ,
as required. Note that in the last step, we replaced n i=1 u (α n-i+1 )•γ•y i by d y as the G p 3 component vanishes upon pairing.

Theorem 2. The NIPE construction is selectively secure if Assumption 1 and Assumption 2 hold.

Proof. The proof relies on a series of modifications to the distribution of public parameters. To define these alternative distributions, we use a family of functions

{F k : [1, 2n] → Z p 2 } 2n k=0 such that for all j ∈ [1, 2n], F k (j) = 0 if k = 0 k i=1 r j • α j i mod p 2 if k ∈ [1, 2n]
where r 1 , . . . , r 2n , α 1 , . . . , α 2n are randomly distributed in Z p 2 . The modified distributions are defined on the parameters {U j } 2n j=1 .

Type k parameters (0 ≤ k ≤ 2n): are parameters where elements {U i } i∈ [1,2n] have a G p 2 component determined by the function F k (.): namely,

U i = u (α i ) • g F k (i) 2 • R 3,i ∀i ∈ [1, 2n].
The proof proceeds through a sequence of 2n + 4 games denoted G 0 , G 1 , G 2 , G 3,1 , . . . , G 3,2n , G 4 as defined below. Let win denote the event that the adversary A wins in game G .

Game G 0 : is the real attack game (described in Section 2.

2).

Game G 1 : This game is similar to G 0 except for the following changes. At the beginning of the game, the challenger chooses γ R ← Z N and sets γ = γ -n i=1 α i x i where x = (x 1 , . . . , x n ) is the challenge vector. The public parameter g γ is generated as

g γ • n i=1 G -x i i
. The challenge ciphertext is computed as:

C 1 R ← G p 1 , C 2 = C γ 1 , C 0 = M β ⊕ H e(C 1 , U n+1 ) .
Since γ is known to the challenger, secret key queries can be answered by running the KeyGen algorithm.

3,k-1 ] -Pr[win 3,k ]| is negligible for each k ∈ [1, 2n].
In game G 3,2n the parameters U j have their G p 2 components defined by F 2n (j), which is a 2nwise independent function from [1, 2n] Game G 4 : This game is identical to game G 3,2n with the difference that, in the challenge ciphertext, C 0 is chosen as a random string in {0, 1} λ . We argue that any legitimate adversary's view remains statistically close to that of game G 3,2n . To see this, we first note that the G p 2 components of the secret keys contain linear combinations of RF (j) in the exponent excluding RF (n + 1). Indeed, recall that the adversary can only make private key queries on vectors y such that y, x = 0. Programming γ as γ = γ -n i=1 α i • x i requires the creation of a G p 1 component with the exponent

n i=1 y i • α n-i+1 • γ - n i=1 α i • x i ,
in order to generate a secret key for y. Note that the coefficient of α n+1 is y, x which is 0 for all legal private key queries. Hence, the private key d y can be computed without using U n+1 , ensuring that RF (n + 1) remains completely independent of any information revealed to A. As a result, the distribution of

H e(C 1 , U n+1 ) = H e(C 1 , u α n+1 ) • e(C 1 , g RF (n+1) 2
) is statistically uniform over {0, 1} λ as long as C 1 as a non-trivial G p 2 component (which occurs with probability 1 -1/p 2 ). This follows from the fact that, if e(C 1 , g

2 ) = 1 G T , the G p 2 compo- nent of e(C 1 , g RF (n+1) 2
) has log(p 2 ) bits of min-entropy. Since H : G T → {0, 1} λ is a pairwiseindependent hash function, the Leftover Hash Lemma ensures that, conditionally on the adversary's view, the distribution of H e(C 1 , u α n+1 ) • e(C 1 , g

RF (n+1) 2
) is within distance 2 -λ from the uniform distribution over {0, 1} λ . This implies that | Pr[win 3,2n ]-Pr[win 4 ]| ≤ 1/p 2 +1/2 λ , which is statistically negligible as claimed. Since β ∈ {0, 1} is perfectly hidden from the adversary in G 4 , we have Pr[win 4 ] = 1/2.

Combining the above, we find

Adv NIPE,A (λ) = |Pr[win 0 ] -Pr[win 4 ]| ≤ Adv 1 G,B (λ) + 2n • Adv 2 G,B (λ) + 1 p 2 + 1 2 λ
which is negligible in the security parameter λ provided Assumption 1 and Assumption 2 both hold in (G, G T ).

Proof (of Lemma 1). Let (g, g 3 , T ) be an instance of Assumption 1. We show how B simulates the different stages of the security game.

Initialize: A commits to the challenge vector x = (x 1 , . . . , x n ). Setup: Pick u R ← G p 1 , α R ← Z N and compute G j = g α j for j = 1, . . . , n, U j = u α j •R 3,j for j ∈ [1, 2n] where R 3,j 's are sampled from G p 3 using g 3 . Choose γ R ← Z N and set γ = γ -n i=1 α i • x i . The adversary is given the following public parameters mpk := g, g γ , {G j } n j=1 , {U j } j∈ [1,2n] Proof (of Lemma 2). Using A show how to construct an algorithm B that breaks Assumption 2.

B receives an instance (g, X 1 X 2 , g 3 , Y 2 Y 3 , T ) of the problem and simulates the game as follows.

Suppose that T = u • g r 2 2 • g r 3 3 where either r 2 = 0 or r 2 R ← Z p 2 .

Initialize: A commits to the challenge vector x = (x 1 , . . . , x n ). Setup: Pick α R ← Z N , r 1 , . . . , r k-1 R ← Z N and compute G j = g α j for j = 1, . . . , n and

U j = T α j • (Y 2 Y 3 ) k-1 i=1 r i •α j i • R 3,j
for j ∈ [1, 2n] where R 3,j R ← G p 3 . Choose γ R ← Z N and set γ = γ -n i=1 α i x i . The adversary is given the following public parameters mpk := g, g γ , {G j } n j=1 , {U j } j∈ [1,2n]

C 1 = X 1 X 2 , C 2 = (X 1 X 2 ) γ , C 0 = M β ⊕ H e(C 1 , U n+1 ) .
Guess: A returns a bit β . B returns 1 if β = β and 0 otherwise.

If r 2 = 0, then the parameters have the Type k -1 distribution. Otherwise, r 2 R ← Z p 2 and the parameters have the Type k distribution for reasons explained next. The G p 2 -components of U j (for j ∈ [1, 2n]) would be given by

g r 2 •α j 2 • Y k-1 i=1 r i •α j i 2 . (7)
All the information provided to A is independent of α mod p 2 (by the Chinese Remainder Theorem) and hence we can substitute α mod p 2 with a uniformly random α k ∈ Z p 2 . The G p 2 component of U j in [START_REF] Bishop | Function-Hiding Inner Product Encryption[END_REF] can thus be replaced by

  , . . . , n}.

  to Z p 2 . The adversary's view thus remains identical if we replace the function F 2n by a truly random function RF : [1, 2n] → Z p 2 which allows defining the G p 2 component of U j as g RF (j) 2 for each j ∈ [1, 2n].

•X 3 , where X 3 R← G p 3 .

 333 \{n+1} , H . Key Extraction: Upon a query on vector y ∈ Z n N , the adversary is given d y = u n i=1 α n-i+1 •y i γ Challenge: A provides two messages M 0 , M 1 . B picks β R ← {0, 1} and computes the ciphertext C = (C 0 , C 1 , C 2 ), where,C 1 = T, C 2 = T γ , C 0 = M β ⊕ H e(C 1 , U n+1 ) .Guess: A returns a bit β . B returns 1 if β = β and 0 otherwise.If T R ← G p 1 , then C is distributed as in G 1 . Otherwise, T R ← G p 1 p 2 and B simulates G 2 . We have | Pr[win 1 ] -Pr[win 2 ]| = | Pr[β = β |T R ← G p 1 ] -Pr[β = β |T R ← G p 1 p 2 ]| = | Pr[B returns 1|T R ← G p 1 ] -Pr[B returns 1|T R ← G p 1 p 2 ]| = Adv 1 G,B (λ) ,which is negligible under Assumption 1.

3 R← G p 3 .

 33 \{n+1} , H . Key Extraction: Upon a query on vector y ∈ Z n N , the adversary is given d y = Challenge: A provides two messages M 0 , M 1 . B picks β R ← {0, 1} and computes the ciphertext C = (C 0 , C 1 , C 2 ), where,

g k i=1 r i •α j i 2 .

 2 as required. Moreover, the G p 3 component of U j is uniformly distributed since we randomize it by R 3,j . We thus have| Pr[win 3,k-1 ] -Pr[win 3,k ]| ≤ Adv 2 G,B(λ), which is negligible under Assumption 2.

  The change is only conceptual and hence Pr[win 0 ] = Pr[win 1 ]. Game G 2 : In this game, we start modifying the distribution of the challenge ciphertext. Namely, the challenger now picks C 1 uniformly at random in G p 1 p 2 instead of G p 1 . The adversary's ability to distinguish between games G 1 and G 2 can be leveraged to break Assumption 1 as formalized in the following lemma. Lemma 1. If Assumption 1 holds, then | Pr[win 1 ] -Pr[win 2 ]| is negligible. Game G 3,k for k = 1, . . . , 2n: We let game G 3,0 be identical to G 2 for notational convenience. In game G 3,k the adversary is given Type k parameters. We argue that the adversary can detect this change with negligible probability if Assumption 2 holds.

Lemma 2. If Assumption 2 holds, then the distance | Pr[win

One may object saying the linear-length vector x still has to be appended to the ciphertext. Nevertheless, in many applications the description of x can be very short. For example, in an ordinary (i.e., non-identity-based) broadcast encryption scheme for n users, x is uniquely determined by the n-bit word that specifies which users are in the revoked set. In this case, our ciphertexts reduce the communication overhead from O(nλ) to O(n + λ) bits if λ is the security parameter.

Acknowledgements

The authors were funded by the "Programme Avenir Lyon Saint-Etienne de l'Université de Lyon" in the framework of the programme "Investissements d'Avenir" (ANR-11-IDEX-0007). Jie Chen was also supported in part by the National Natural Science Foundation of China (Grant No. 61472142).