Ahmad El

S A Ïd

LAPLACIAN EIGENVALUES FUNCTIONALS AND METRIC DEFORMATIONS ON COMPACT MANIFOLDS

Keywords: 2000 Mathematics Subject Classification. 49R50, 35P99, 58J50 Eigenvalues, Laplacian, critical metrics

In this paper, we investigate critical points of the Laplacian's eigenvalues considered as functionals on the space of Riemmannian metrics or a conformal class of metrics on a compact manifold. We obtain necessary and sufficient conditions for a metric to be a critical point of such a functional. We derive specific consequences concerning possible locally maximizing metrics. We also characterize critical metrics of the ratio of two consecutive eigenvalues.

Introduction

The eigenvalues of the Laplace-Beltrami operator associated with a Riemannian metric on a closed manifold are among the most natural global Riemannian invariants defined independently from curvature. One of the main topics in Spectral Geometry is the study of uniform boundedness of eigenvalues under some constraints and the finding out of eventual extremal metrics. Let us start by recalling some important results in this direction, where the eigenvalues are considered as functionals on the set of Riemannian metrics of fixed volume.

In all the sequel, we will denote by M a compact smooth manifold of dimension n ≥ 2 and, for any Riemannian metric g on M, by

0 < λ 1 (g) ≤ • • • ≤ λ k (g) ≤ • • • → ∞
the sequence of eigenvalues of the Laplacian ∆ g associated with g, repeated according to their multiplicities. Notice that λ k is not invariant under scaling (i.e., ∀c > 0, λ k (cg) = 1 c λ k (g)). Hence, a normalization is needed and it is common to restrict the functional λ k to the set R(M) of Riemannian metrics of fixed volume. We will denote by C(g) the set of Riemannian metrics conformal to g and having the same volume as g.

The result that, in dimension 2, ∀k ≥ 1, the functional λ k is uniformly bounded on the set of metrics of fixed area is due to Korevaar [START_REF] Korevaar | Upper bounds for eigenvalues of conformal metrics[END_REF], after been proved for k = 1, by Hersch [START_REF] Hersch | Quatre propriétés isopérimétriques de membranes sphériques homogènes[END_REF] in the case of the 2-sphere S 2 , and by Yang and Yau [START_REF] Yang | Eigenvalues of the Laplacian of compact Riemann surfaces and minimal submanifolds[END_REF] and Li and Yau [START_REF] Li | A new conformal invariant and its applications to the Willmore conjecture and the first eigenvalue of compact surfaces[END_REF] for all compact surfaces (see also [START_REF] Soufi | Le volume conforme et ses applications d'après Li et Yau[END_REF] for an improvement of the Yang-Yau upper bound of λ 1 in terms of the genus).

The situation differs in dimension n ≥ 3. Indeed, based on earlier results on spheres obtained by many authors [START_REF] Tanno | The first eigenvalue of the Laplacian on spheres[END_REF][START_REF] Mutô | The first eigenvalue of the Laplacian on even-dimensional spheres[END_REF][START_REF] Bérard | Laplacians and Riemannian submersions with totally geodesic fibres[END_REF][START_REF] Urakawa | On the least positive eigenvalue of the Laplacian for compact group manifolds[END_REF][START_REF] Mutō | Homogeneous minimal hypersurfaces in the unit spheres and the first eigenvalues of their Laplacian[END_REF], Colbois and Dodziuk [START_REF] Colbois | Riemannian metrics with large λ 1[END_REF] proved that, for any compact manifold M of dimension n ≥ 3, the functional λ 1 is unbounded on R(M).

However, ∀k ≥ 1, the functional λ k becomes uniformly bounded when restricted to a conformal class of metrics of fixed volume C(g). This result was first proved for k = 1 by the authors [START_REF] Soufi | Immersions minimales, première valeur propre du laplacien et volume conforme[END_REF] (see also [START_REF] Friedlander | A differential invariant related to the first eigenvalue of the Laplacian[END_REF]) and, for any k ≥ 1, by Korevaar [START_REF] Korevaar | Upper bounds for eigenvalues of conformal metrics[END_REF] (see also [START_REF] Grigoryan | Decomposition of a metric space by capacitors[END_REF]).

Existence results for maximizing metrics are available in only few situations and concern exclusively the first eigenvalue functional. Hersch [START_REF] Hersch | Quatre propriétés isopérimétriques de membranes sphériques homogènes[END_REF] proved that the standard metric is the only maximizing metric for λ 1 on the 2-sphere S 2 . The same result holds for the standard metric of the real projective plane RP 2 (Li and Yau [START_REF] Li | A new conformal invariant and its applications to the Willmore conjecture and the first eigenvalue of compact surfaces[END_REF]). Nadirashvili [START_REF] Nadirashvili | Berger's isoperimetric problem and minimal immersions of surfaces[END_REF] outlined a proof for the existence of maximizing metrics for λ 1 on the 2-Torus and the Klein bottle (see [START_REF] Girouard | Valeur propre fondamentale et divergence conforme sur le tore[END_REF][START_REF] Girouard | Fundamental tone, concentration of density to points and conformal degeneration on surfaces[END_REF] for additional details on Nadirashvili's paper).

In higher dimensions, the authors [START_REF] Soufi | Immersions minimales, première valeur propre du laplacien et volume conforme[END_REF] gave a sufficient condition for a metric g on M to maximize λ 1 in its the conformal class C(g). This condition is fulfilled in particular by the standard metric of the sphere S n (which enabled us to answer Berger's problem concerning the maximization of λ 1 restricted to the standard conformal class of S n ), and more generally, by the standard metric of any compact rankone symmetric space. The flat metrics g sq and g eq on the 2-Torus T 2 associated with the square lattice Z 2 and the equilateral lattice Z(1, 0) ⊕ Z(1/2, √ 3/2) respectively are also maximizing metrics of λ 1 in their conformal classes (see [START_REF] Soufi | Immersions minimales, première valeur propre du laplacien et volume conforme[END_REF][START_REF] Li | A new conformal invariant and its applications to the Willmore conjecture and the first eigenvalue of compact surfaces[END_REF]).

In this paper we address the following natural questions:

(1) What about critical points of the functional g → λ k (g) ? (2) How to deform a Riemannian metric g in order to increase, or decrease, the k-th eigenvalue λ k ?

Despite the non-differentiability of the functional λ k with respect to metric deformations, perturbation theory enables us to prove that, for any analytic deformation g t of a metric g, the function t → λ k (g t ) always admits left and right derivatives at t = 0 (see Theorem 2.1 (i) below). Moreover, these derivatives can be expressed in terms of the eigenvalues of the following quadratic form

Q h (u) = - M du ⊗ du + 1 4 ∆ g u 2 g, h v g , with h = d dt g t t=0
, restricted to the eigenspace E k (g) (Theorem 2.1 and Lemma 2.1). This enables us to give partial answers to Question [START_REF] Bérard | Laplacians and Riemannian submersions with totally geodesic fibres[END_REF] above (Corollary 2.1). In particular, if Q h is positive definite on E k (g), then λ k (g -t ) < λ k (g) < λ k (g t ) for all t ∈ (0, ε), for some positive ε.

Concerning Question (1), the existence of left and right derivatives for t → λ k (g t ), suggests the following natural notion of criticality. Indeed, a metric g will be termed critical for the functional λ k if, for any volume-preserving deformation g t of g, one has

d dt λ k (g t ) t=0 -× d dt λ k (g t ) t=0 + ≤ 0 ;
this means that either

λ k (g t ) ≤ λ k (g) + o(t) or λ k (g t ) ≥ λ k (g) + o(t).
It is clear that if g is a locally maximizing or a locally minimizing metric of λ k , then g is a critical metric for λ k in the previous sense.

In an earlier work ( [START_REF] Ilias | Riemannian manifolds admitting isometric immersions by their first eigenfunctions[END_REF] and [START_REF] Ilias | Extremal metrics for the first eigenvalue of the Laplacian in a conformal class[END_REF]), we treated the particular case k = 1 and gave a necessary condition ( [12, Theorem 1.1] and [14, Theorem 2.1]) as well as a sufficient condition ( [12, Proposition 1.1] and [14, Theorem 2.2]) for a metric g to be critical for the functional λ 1 or for the restriction of the λ 1 to a conformal class.

In section 3 and 4 below, we extend the results of [START_REF] Ilias | Riemannian manifolds admitting isometric immersions by their first eigenfunctions[END_REF] and [START_REF] Ilias | Extremal metrics for the first eigenvalue of the Laplacian in a conformal class[END_REF] to higher order eigenvalues, and weaken the sufficient conditions given there. Actually, as we will see, in many cases, the necessary condition of criticality is also sufficient (Theorem 3.1 and Theorem 4.1). Given a metric g on M, we will prove that

• Necessary conditions (Theorem 3.1(i) and Theorem 4.1(i)): i) If g is critical for the functional λ k , then there exists a finite family

{u 1 , • • • , u d } of eigenfunctions associated with λ k such that i≤d du i ⊗ du i = g.
ii) If g is a critical metric of the functional λ k restricted to the conformal class of g, then there exists a finite family

{u 1 , • • • , u d } of eigenfunctions associated with λ k such that i≤d u 2 i = 1.
• Sufficient conditions (Theorem 3.1(ii) and Theorem 4.

1(ii)): If λ k (g) > λ k-1 (g) or λ k (g) < λ k+1 (g) (which means that λ k (g)
corresponds to the first one or the last one of a cluster of equal eigenvalues), then the necessary conditions above are also sufficient. The condition (i) above means that the map u :

= (u 1 , • • • , u d ) : (M, g) -→ R d ,
is an isometric immersion, whose image is a minimally immersed submanifold of the Euclidean sphere S d-1 ( n λ k (g) ) of radius n λ k (g) (see [START_REF] Takahashi | Minimal immersions of Riemannian manifolds[END_REF]). In other words, a metric g is critical for the functional λ k , for some k ≥ 1, if and only if g is induced on M by a minimal immersion of M into a sphere. Therefore, the classification of critical metrics of eigenvalue functionals on M reduces to the classification of minimal immersions of M into spheres. The many existence and classification results (see for instance [START_REF] Ferus | S 1 -equivariant minimal tori in S 4 and S 1equivariant Willmore tori in S 3[END_REF][START_REF] Hsiang | Minimal cones and the spherical Bernstein problem[END_REF][START_REF] Eells | Harmonic maps and minimal immersions with symmetries[END_REF][START_REF] Toth | Finite Möbius groups, minimal immersions of spheres, and moduli[END_REF] and the references therein) of minimal immersions into spheres give examples of critical metrics for the eigenvalue functionals.

Notice that, for the first eigenvalue functional, the critical metrics are classified on surfaces of genus 0 and 1. Indeed, on S 2 and RP 2 , the standard metrics are the only critical ones ( [START_REF] Soufi | Immersions minimales, première valeur propre du laplacien et volume conforme[END_REF]). On the torus T 2 , the flat metrics g eq and g sq mentioned above are, up to dilatations, the only critical metrics for λ 1 ([12]). The metric g eq corresponds to a maximizer for λ 1 ([27]), while g sq is a saddle point. For the Klein bottle K, Jacobson, Nadirashvili and Polterovitch [START_REF] Jakobson | Extremal metric for the first eigenvalue on a Klein bottle[END_REF] showed the existence of a critical metric and El Soufi, Giacomini and Jazar [START_REF] Soufi | Greatest least eigenvalue of the laplacian on the klein bottle[END_REF] proved that this metric is, up to dilatations, the unique critical metric for λ 1 on K. Now, the condition (ii), concerning the criticality for λ k restricted to a conformal class, is equivalent to the fact that the map u :

= (u 1 , • • • , u d ) : (M, g) -→ S d-1
is a harmonic map with energy density e(u) = λ k (g) 2 (see for instance [START_REF] Eells | A report on harmonic maps[END_REF]). Thus, a metric g is critical for some λ k restricted to the conformal class of g if and only if (M, g) admits a harmonic map of constant energy density in a sphere. In particular, the metric of any homogeneous compact Riemannian space is critical for λ k restricted to its conformal class (for other examples see [START_REF] Park | Classification of harmonic mappings of constant energy density into spheres[END_REF][START_REF] Eells | Harmonic maps and minimal immersions with symmetries[END_REF][START_REF] Toth | Finite Möbius groups, minimal immersions of spheres, and moduli[END_REF] and the references therein).

A consequence of the necessary condition (ii) is that, if g is a critical metric of λ k restricted to C(g), then the multiplicity of λ k (g) is at least 2 (Corollary 4.2). This means that λ k (g) = λ k-1 (g) or λ k (g) = λ k+1 (g). In the case where the metric g is a local maximizer of λ k restricted to C(g), we prove that one necessarily has: λ k (g) = λ k+1 (g) (Corollary 4.2). For a local minimizer, one has λ k (g) = λ k-1 (g). Together with a recent result of Colbois and the first author [START_REF] Colbois | Extremal eigenvalues of the Laplacian in a conformal class of metrics: the 'conformal spectrum[END_REF], this result tells us that a Riemannian metric can never maximize two consecutive eigenvalues simultaneously on its conformal class (Corollary 4.3). In fact, if g maximizes λ k on C(g), then

λ k+1 (g) n 2 ≤ sup g ′ ∈C(g) λ k+1 (g ′ ) n 2 -n n 2 ω n ,
where ω n is the volume of the unit Euclidean n-sphere.

As an application of the results above, one can derive characterizations of the metrics which are critical for various functions of eigenvalues. To illustrate this, we treat in the last section of this paper, the case of the ratio functional λ k+1 λ k of two consecutive eigenvalues and give characterizations of critical metrics for these functionals.

Derivatives of eigenvalues with respect to metric deformations

Let M be a compact smooth manifold of dimension n ≥ 2. For any Riemannian metric g on M, we denote by 0 < λ 1 (g) ≤ λ 2 (g) ≤ • • • the eigenvalues of the Laplace-Beltrami operator ∆ g associated with g. For any k ∈ N, we denote by E k (g) = Ker(∆ g -λ k (g)I) the eigenspace corresponding to λ k (g) and by Π k : L 2 (M, g) -→ E k (g) the orthogonal projection on E k (g). Let us fix a positive integer k and consider the functional g -→ λ k (g). This functional is continuous but not differentiable in general. However, perturbation theory tells us that λ k is left and right differentiable along any analytic curve of metrics. The main purpose of this section is to express the derivatives of λ k with respect to analytic metric deformations, in terms of the eigenvalues of an explicit quadratic form on E k (g). Indeed, we have the following Theorem 2.1. Let g be a Riemannian metric on M and let (g t ) t be a family of Riemannian metrics analytically indexed by t ∈ (-ǫ, ǫ), such that g 0 = g. The following hold i) The function t ∈ (-ǫ, ǫ) -→ λ k (g t ) admits a left and a right derivatives at t = 0. ii) The derivatives d dt λ k (g t ) t=0 -and d dt λ k (g t ) t=0 + are eigenvalues of the operator

Π k •∆ ′ : E k (g) -→ E k (g), where ∆ ′ = d dt ∆ gt t=0 . iii) If λ k (g) > λ k-1 (g), then d dt λ k (g t ) t=0 -and d dt λ k (g t ) t=0 + are the greatest and the least eigenvalues of Π k • ∆ ′ on E k (g), respec- tively. iv) If λ k (g) < λ k+1 (g), then d dt λ k (g t ) t=0 -and d dt λ k (g t ) t=0 + are the least and the greatest eigenvalues of Π k • ∆ ′ on E k (g), respec- tively.
Proof. The family of operators ∆ t := ∆ gt depends analytically on t and, ∀t, ∆ t is self-adjoint with respect to the L 2 inner product induced by g t (but not necessarily to that induced by g). However, as done in [START_REF] Bando | Generic properties of the eigenvalue of the Laplacian for compact Riemannian manifolds[END_REF], after a conjugation by the unitary isomorphism

U t : L 2 (M, g) → L 2 (M, g t ) u → |g| |g t | 1/4 u,
where |g t | is the Riemannian volume density of g t , we obtain an analytic family

P t = U -1 t • ∆ t • U t of operators such that, ∀t ∈ (-ǫ, ǫ
), P t is self-adjoint with respect to the L 2 inner product induced by g. Moreover, P t and ∆ t have the same spectrum. In particular, λ k (g t ) is an eigenvalue of P t . The Rellich-Kato perturbation theory of unbounded self-adjoint operators applies to the analytic family of operators t → P t . Therefore, if we denote by m the dimension of E k (g), then there exist,

∀t ∈ (-ǫ, ǫ), m eigenvalues Λ 1 (t), • • • , Λ 1 (t) of P t associated with an L 2 (M, g)-orthonormal family of eigenfunctions v 1 (t), • • • , v m (t) of P t , that is P t v i (t) = Λ i (t)v i (t), so that Λ(0) = • • • = Λ m (0) = λ k (g), and ∀i ≤ m, both Λ i (t) and v i (t) depend analytically on t. Setting, ∀i ≤ m and ∀t ∈ (-ǫ, ǫ), u i (t) = U t v i (t), we get, ∀i ≤ m, (1) ∆ t u i (t) = Λ i (t)u i (t)
and the family {u

1 (t), • • • , u m (t)} is orthonormal in L 2 (M, g t ). Since t → λ k (t) is continuous and, ∀i ≤ m, t → Λ i (t) is analytic with Λ i (0) = λ k (g)
, there exist δ > 0 and two integers p, q ≤ m such that

λ k (g t ) = Λ p (t) for t ∈ (-δ, 0) Λ q (t) for t ∈ (0, δ).
Assertion (i) follows immediately. Moreover, one has

d dt λ k (t) t=0 -= Λ ′ p (0) and d dt λ k (t) t=0 + = Λ ′ q (0)
. Differentiating both sides of (1) at t = 0, we get

∆ ′ u i + ∆u ′ i = Λ ′ i (0)u i + λ k (g)u ′ i with u ′ i = d dt u i (t) t=0
and u i := u i (0). Multiplying this last equation by u j and integrating by parts with respect to the Riemannian volume element v g of g, we obtain

(2)

M u j ∆ ′ u i v g = Λ ′ i (0) if j = i 0 otherwise. Since {u 1 , • • • , u m } is an orthonormal basis of E k (g) with respect to the L 2 -inner product induced by g, we deduce that (Π k • ∆ ′ )u i = Λ ′ i (0)u i . In particular, Λ ′ p (0) and Λ ′ q (0) are eigenvalues of Π k • ∆ ′ , which proves Assertion (ii). Assume now λ k (g) > λ k-1 (g). Hence, ∀i ≤ m, Λ i (0) = λ k (g) > λ k-1 (g).
By continuity, we have Λ i (t) > λ k-1 (g t ) for sufficiently small t. Hence, there exists η > 0 such that, ∀t ∈ (-η, η) and ∀i ≤ m,

Λ i (t) ≥ λ k (g t ), which means that λ k (g t ) = min {Λ 1 (t), • • • , Λ m (t)} . This implies that d dt λ k (g t ) t=0 -= max {Λ ′ 1 (0), • • • , Λ ′ m (0)} and d dt λ k (g t ) t=0 + = min {Λ ′ 1 (0), • • • , Λ ′ m (0)} . Assertion (iii) is proved.
The proof of Assertion (iv) is similar. Indeed, if λ k (g) < λ k+1 (g), one has, for sufficiently small t, λ k (g

t ) = max {Λ 1 (t), • • • , Λ m (t)} and, then, d dt λ k (g t ) t=0 + = max {Λ ′ 1 (0), • • • , Λ ′ m (0)} and d dt λ k (g t ) t=0 -= min {Λ ′ 1 (0), • • • , Λ ′ m (0)} .
The quadratic form associated with the symmetric operator Π k • ∆ ′ acting on E k (g) can be expressed explicitely as follows:

Lemma 2.1. Let (g t ) t be an analytic deformation of the metric g and let h := d dt g t t=0 . The operator

P k,h := Π k • ∆ ′ : E k (g) → E k (g)
is a symmetric with respect to the L 2 -norm induced by g ; the corresponding quadratic form is given by, ∀u ∈ E k (g),

Q h (u) := M u P k,h u v g = - M du ⊗ du + 1 4 ∆ g u 2 g, h v g ,
where ( , ) is the pointwise inner product induced by g on covariant 2tensors. Moreover, if , ∀t ∈ (-ǫ, ǫ), g t = α t g is conformal to g, then h = ϕg with ϕ = d dt α t t=0 , and, ∀u ∈ E k (g),

Q h (u) = - M ϕ(|du| 2 + n 4 ∆ g u 2 )v g = - n 2 M ϕ(λ k (g)u 2 - n -2 n |du| 2 )v g .
Proof. The derivative at t = 0 of t → ∆ gt is given by the formula (see [START_REF] Berger | Sur les premières valeurs propres des variétés riemanniennes[END_REF]):

(3)

∆ ′ u := d dt ∆ gt u t=0 = (Ddu, h) -(du, δh + 1 2 d(trace g h)),
where D is the canonical covariant derivative induced by g. Thus,

M u ∆ ′ u v g = M u(Ddu, h)v g - 1 2 M (du 2 , δh + 1 2 d(trace g h))v g . (4)
One has, ∀u,

uDdu = 1 2 Ddu 2 -du ⊗ du. Hence, M u (Ddu, h) v g = 1 2 M (Ddu 2 , h)v g - M (du ⊗ du, h)v g .
Since δ is the adjoint of D w.r.t. the L 2 (g)-inner product, we obtain

M u (Ddu, h) v g = 1 2 M (du 2 , δh)v g - M (du ⊗ du, h)v g .
On the other hand

M (du 2 , d(trace g h))v g = M ∆ g u 2 trace g hv g = M (∆ g u 2 g, h)v g .
Replacing in (4) one immediately gets the desired identity.

A straightforward computation gives the expression of Q h for conformal deformations.

In relation to the question (2) of the introduction, we give the following result which is a direct consequence of Theorem 2.1 and Lemma 2.1.

Corollary 2.1. Let (g t ) t be an analytic deformation of a Riemannian metric g on M and let Q h be the associated quadratic form defined as in Lemma 2.1, with h

= d dt g t t=0 . i) If Q h is positive definite on E k (g), then there exists ε > 0 such that λ k (g -t ) < λ k (g) < λ k (g t ) for all t ∈ (0, ε). ii) Assume that λ k (g) > λ k-1 (g). If there exists u ∈ E k (g) such that Q h (u) < 0, then λ k (g t ) < λ k (g) for all t ∈ (0, ε), for some ε > 0. iii) Assume that λ k (g) < λ k+1 (g). If there exists u ∈ E k (g) such that Q h (u) > 0, then λ k (g t ) > λ k (g) for all t ∈ (0, ε), for some ε > 0.
In particular, if Q h (u) > 0 for a first eigenfunction u, then λ 1 (g t ) < λ 1 (g) for sufficiently small positive t.

Critical metrics of the eigenvalue functionals

Let M be a closed manifold of dimension n ≥ 2 and let k be a positive integer. Before introducing the notion of critical metric of the functional λ k , notice that this functional is not scaling invariant. Therefore, we will restrict λ k to the set of metrics of given volume. In view of Theorem 2.1, a natural way to introduce the notion of critical metric is the following: Definition 3.1. A metric g on M is said to be "critical" for the functional λ k if, for any volume-preserving analytic deformation (g t ) t of g with g 0 = g, the left and the right derivatives of λ k (g t ) at t = 0 satisfy

d dt λ k (g t ) t=0 -× d dt λ k (g t ) t=0 + ≤ 0.
It is easy to see that

d dt λ k (g t ) t=0 + ≤ 0 ≤ d dt λ k (g t ) t=0 -⇐⇒ λ k (t) ≤ λ k (0) + o(t) and d dt λ k (g t ) t=0 -≤ 0 ≤ d dt λ k (g t ) t=0 + ⇐⇒ λ k (t) ≥ λ k (0) + o(t).
Therefore, g is critical for λ k if, for any volume-preserving analytic deformation (g t ) t of g, one of the following inequalities holds:

λ k (g t ) ≤ λ k (g) + o(t) or λ k (g t ) ≥ λ k (g) + o(t).
Of course, if g is a local maximizer or a local minimizer of λ k , then g is critical in the sense of the previous definition. In all the sequel, we will denote by S 2 0 (M, g) the space of covariant 2-tensors h satisfying M trace g hv g = M (g, h)v g = 0, endowed with its natural L 2 norm induced by g. Proposition 3.1. If g is a critical metric for the functional λ k on M, then, ∀h ∈ S 2 0 (M, g), the quadratic form

Q h (u) = - M du ⊗ du + 1 4 ∆ g u 2 g, h v g is indefinite on E k (g).
Proof. Let h ∈ S 2 0 (M, g). The deformation of g defined for small t by g t = vol(g) vol(g + th)

2/n (g + th), where vol(g) is the Riemannian volume of (M, g), is volume-preserving and depends analytically on t with d dt g t t=0 = h. Using Theorem 2.1, we see that, if g is critical, then the operator P h,k admits a nonnegative and a nonpositive eigenvalues on E k (g) which means that the quadratic form Q h is indefinite (Lemma 2.1).

In the case where λ k (g) > λ k-1 (g) or λ k (g) < λ k+1 (g), one can show that the converse of Proposition 3.1 is also true. Indeed, we have the following Proposition 3.2. Let g be a Riemannian metric on M such that

λ k (g) > λ k-1 (g) or λ k (g) < λ k+1 (g). Then g is critical for the func- tional λ k if and only if, ∀h ∈ S 2 0 (M, g), the quadratic form Q h is in- definite on E k (g).
Proof. Let (g t ) t be an analytic volume-preserving deformation of g and let h = d dt g t t=0 . Since vol(g t ) is constant with respect to t, the tensor h belongs to S 2 0 (M, g) (indeed, M (g, h)v g = d dt vol(g t ) t=0 = 0). The indefiniteness of Q h implies that the operator P k,h = Π k • ∆ ′ admits both non-negative and non-positive eigenvalues on E k (g) (see Lemma 2.1). The result follows immediately from Theorem 2.1 (iii) and (iv).

The indefiniteness of Q h on E k (g) for all h ∈ S 2 0 (M, g), can be interpreted intrinsically in terms of the eigenfunctions of λ k (g) as follows.

Lemma 3.1. Let g be a Riemannian metric on M. The two following conditions are equivalent: i) ∀h ∈ S 2 0 (M, g), the quadratic form Q h is indefinite on E k (g). ii) There exists a finite family

{u 1 , • • • , u d } ⊂ E k (g) of eigenfunc- tions associated with λ k (g) such that i≤d du i ⊗ du i = g.
Proof. The proof of "(i) implies (ii)" uses the same arguments as in the proof of Theorem 1.1 of [START_REF] Ilias | Riemannian manifolds admitting isometric immersions by their first eigenfunctions[END_REF]. For the sake of completeness, we will recall the main steps. First, we introduce the convex set K ⊂ S 2 (M, g) given by

K = j∈J du j ⊗ du j + 1 4 ∆ g u 2 j g ; u j ∈ E k (g), J ⊂ N, J finite .
Let us first show that g ∈ K. Indeed, if g / ∈ K, then, applying classical separation theorem in the finite dimensional subspace of S 2 (M, g) generated by K and g, endowed with the L 2 inner product induced by g, we deduce the existence of a 2-tensor h ∈ S 2 (M, g) such that

M (g, h)v g > 0 and, ∀ T ∈ K, M (T, h)v g ≤ 0. The tensor h 0 = h - 1 n vol(g) M (g, h)v g g
belongs to S 2 0 (M, g) and we have, ∀u ∈ E k (g), u = 0,

Q h 0 (u) = - M (du ⊗ du + 1 4 ∆ g u 2 g, h)v g + M (g, h)v g n vol(g) M |du| 2 v g ≥ λ k (g) n vol(g) M (g, h)v g M u 2 v g .
Since M (g, h)v g > 0, the quadratic form Q h 0 is positive definite, which contradicts the assumption (i). Now, g ∈ K means that there exists

u 1 , • • • , u m ∈ E k (g) such that (5) i≤d (du i ⊗ du i + 1 4 ∆ g u 2 i )g = g.
Hence, since ∆u

2 i = 2(λ k (g)u 2 i -|du i | 2 )
, we obtain after taking the trace in [START_REF] Colbois | Extremal eigenvalues of the Laplacian in a conformal class of metrics: the 'conformal spectrum[END_REF],

λ k (g) 2 i≤d u 2 i = 1 + n -2 2n i≤d |du i | 2 .
For n = 2, we immediately get i≤d u 2 i = 2 λ k (g) and, for n ≥ 3, we consider the function f := i≤d u 2 i -n λ k (g) and observe that it satisfies (n -2)

∆ g f = 2(n -2)(λ k (g) i≤d u 2 i - i≤d |du i | 2 ) = -4λ k (g)f.
Thus, f = 0 (the Laplacian being a non-negative operator) and, then, ∀n ≥ 2, i≤d u 2 i = n λ k (g) . Replacing in (5), we obtain

i≤d du i ⊗ du i = g.
Conversely, let u 1 , • • • , u d be as in (ii). This means that the map

x ∈ M -→ u(x) = (u 1 (x), • • • , u d (x)) ∈ R d is an isometric immersion. The vector ∆u(x) = (∆u 1 (x), • • • , ∆u d (x)) = λ k (g)u(x)
represents the mean curvature vectorfield of the immersed submanifold u(M). Hence, ∀x ∈ M, the position vector u(x) is normal to u(M) which implies that u(M) is contained in a sphere of R d centered at the origin. Thus, ii) Assume that λ k (g) > λ k-1 (g) or λ k (g) < λ k+1 (g). Then g is a critical metric of the functional λ k if and only if there exists a finite family

i≤d u 2 i is constant on M. Consequently, ∀h ∈ S 2 (M, g), i≤d Q h (u i ) = • • • = 0. It follows that Q h is indefinite on E k (g).
{u 1 , • • • , u d } ⊂ E k (g) of eigenfunctions associated with λ k (g) such that i≤d du i ⊗ du i = g.
According to Theorem 3.1 (ii), the standard metrics g of compact rank one symmetric spaces are critical metrics of the functionals λ k , for any k such that λ k (g) > λ k-1 (g) or λ k (g) < λ k+1 (g). More generally, this is the case of all compact Riemannian homogeneous spaces with irreducible isotropy representation. Indeed, if {u 1 , • • • , u d } is an L 2 (g)orthonormal basis of E k (g), then the tensor i≤d du i ⊗ du i is invariant under the isometry group action which implies that it is proportional to g (Schur's Lemma).

In [START_REF] Ilias | Critical metrics of the trace of the heat kernel on a compact manifold[END_REF], we studied the notion of critical metrics of the trace of the heat kernel Z g (t) = e -λ k (g)t , considered as a functional on the set of metrics of given volume. We obtain various characterizations of these critical metrics. An immediate consequence of Theorem 3.1 and [13, Theorem 2.2], is the following Corollary 3.1. Let g be a Riemannian metric on M. If g is a critical metric of the trace of the heat kernel at any time t > 0, then g is a critical metric of the functional λ k for all k such that λ k (g) > λ k-1 (g) or λ k (g) < λ k+1 (g).

In particular, the flat metrics g sq and g eq on the 2-Torus T 2 associated with the square lattice Z 2 and the equilateral lattice Z(1, 0) ⊕ Z(1/2, √ 3/2), respectively, are critical metrics of the functionals λ k for all k such that λ k (g sq ) > λ k-1 (g sq ) or λ k (g sq ) < λ k+1 (g sq ) and such that λ k (g eq ) > λ k-1 (g eq ) or λ k (g eq ) < λ k+1 (g eq ) respectively (see [START_REF] Ilias | Critical metrics of the trace of the heat kernel on a compact manifold[END_REF]). Other examples of critical metrics can be obtained as Riemannian products of previous examples (see [START_REF] Ilias | Critical metrics of the trace of the heat kernel on a compact manifold[END_REF]).

As we noticed in the proof of Lemma 3.1, the condition i≤d du i ⊗ du i = g, with u i ∈ E k (g), implies that the map u = (u 1 , • • • , u d ) is an isometric immersion of (M, g) into a (d -1)-dimensional sphere. In particular, the rank of u is at least n. Therefore we have the following

Corollary 3.2. If g is a critical metric of the functional λ k , then dim E k (g) ≥ dim M + 1.
Moreover, the equality implies that (M, g) is isometric to an Euclidean sphere.

In the particular case where a metric g is a local maximizer of λ k (that is λ k (g t ) ≤ λ k (g) for any volume-preserving deformation (g t ) t of g), we have the additional necessary condition that λ k (g) = λ k+1 (g) (see Proposition 4.2 below). For a local minimizer, we have λ k (g) = λ k-1 (g). In particular, the functional λ 1 admits no local minimizing metric. This result have been obtained by us in [START_REF] Ilias | Riemannian manifolds admitting isometric immersions by their first eigenfunctions[END_REF] using different arguments.

We end this section with the following result in the spirit of Berger's work [START_REF] Berger | Sur les premières valeurs propres des variétés riemanniennes[END_REF]: Corollary 3.3. Let g be a Riemannian metric on M. Let p ≥ 1 and q ≥ p be two natural integers such that

λ p-1 (g) < λ p (g) = λ p+1 (g) = • • • = λ q (g) < λ q+1 (g).
The metric g is critical for the functional q i=p λ i if and only if there exists an L 2 (M, g)-orthonormal basis u 1 , u 2 , . . . , u m of E p (g) such that m i=1 du i ⊗ du i is proportional to g. Proof. The multiplicity of λ p (g) is m = q -p+1. Let (g t ) t be a volumepreserving analytic deformation of g and h = d dt g t t=0 ∈ S 2 0 (M, g). Let Λ 1 (t), • • • , Λ m (t) and v 1 (t), • • • , v m (t) be the families of eigenvalues and orthonormal eigenfunctions of ∆ gt depending analytically on t and such that Λ 1 (0) = • • • = Λ m (0) = λ p (g), as in the proof of Theorem 2.1. For sufficiently small t, one has

q i=p λ i (g t ) = m i=1 Λ i (t).
Hence, q i=p λ i (g t ) is differentiable at t = 0 and one has (see the proof of Theorem 2.1 and Lemma 2.1),

d dt q i=p λ i (g t ) t=0 = m i=1 Λ ′ i (0) = m i=1 Q h (v i ), with v i := v i (0). Therefore, g is critical for q i=p λ i if and only if, ∀h ∈ S 2 0 (M, g), m i=1 Q h (v i ) = 0.
As in the proof of Lemma 3.1, this last condition means that i≤m dv i ⊗ dv i is proportional to g.

Critical metrics of the eigenvalue functionals in a conformal class

Let M be a closed manifold of dimension n ≥ 2. For any Riemannian metric g on M, we will denote by C(g) the set of metrics which are conformal to g and have the same volume as g, i.e

C(g) = {e α g ; α ∈ C ∞ (M) and vol(e α g) = vol(g)} .
Let k be a positive integer. The purpose of this section is to study critical metrics of the functional λ k restricted to a conformal class C(g). Definition 4.1. A metric g is said to be critical for the functional λ k restricted to C(g) if, for any analytic deformation {g t = e αt g} ⊂ C(g) with g 0 = g, we have

d dt λ k (g t ) t=0 -× d dt λ k (g t ) t=0 + ≤ 0.
In the sequel, we denote by A 0 (M, g) the set of regular functions ϕ with zero mean on M, that is, M ϕ v g = 0. In the spirit of Propositions 3.1 and 3.2, we obtain in the conformal setting, the following Proposition 4.1. Let g be a Riemannian metric on M.

i) If g is a critical metric of the functional λ k restricted to C(g), then, ∀ϕ ∈ A 0 (M, g), the quadratic form

q ϕ (u) = M (λ k (g)u 2 - n -2 n |du| 2 )ϕ v g is indefinite on E k (g). ii) Assume that λ k (g) > λ k-1 (g) or λ k (g) < λ k+1 (g). The metric g
is critical for the functional λ k restricted to C(g) if and only if, ∀ϕ ∈ A 0 (M, g), the quadratic form q ϕ is indefinite on E k (g).

Proof. i) Let ϕ ∈ A 0 (M, g). The conformal deformation of g given by g t := vol(g) vol(e tϕ g)

2 n
e tϕ g, belongs to C(g) and depends analytically on t with d dt g t t=0 = ϕg. Following the arguments of the proof of Proposition 3.1, we show that the criticality of g for λ k restricted to C(g) implies the indefiniteness of the quadratic form Q ϕg on E k (g). Applying Lemma 2.1, we observe that Q ϕg = -n 2 q ϕ . ii) Let g t = e αtg ∈ C(g) be an analytic deformation of g. Since vol(g t ) is constant with respect to t, the function ϕ = d dt α t t=0 belongs A 0 (M, g). Applying Theorem 2.1 (iii) and (iv) and Lemma 2.1 with h = ϕg, we get the result. Lemma 4.1. Let g be a Riemannian metric on M. The two following conditions are equivalent: i) ∀ ϕ ∈ A 0 (M, g), the quadratic form q ϕ is indefinite on E k (g).

ii) There exists a finite family

{u 1 , • • • , u d } ⊂ E k (g) of eigenfunc- tions associated with λ k (g) such that i≤d u 2 i = 1.
Proof. "(i) implies (ii)": We introduce the convex set

H = i∈I λ k (g)u 2 i - n -2 n |du i | 2 ; u i ∈ E k (g), I ⊂ N, I finite .
Using the same arguments as in the proof of Lemma 3.1, we show that the constant function 1 belongs to H. Hence, there exist

u 1 , • • • , u d ∈ E k (g) such that i≤d (λ k (g)u 2 i - n -2 n |du i | 2 ) = 2 n λ k (g).
For n = 2, we immediately get i≤d u 2 i = 1. For n ≥ 3, we set f = i≤d u 2 i -1 and get, after a straightforward calculation,

n -2 4 ∆ g f = -λ k (g)f.
Thus, f = 0 and i≤d u

2 i = 1. "(ii) implies (i)": let u 1 , • • • , u d ∈ E k (g) be such that i≤d u 2 i = 1. One has i≤d |du i | 2 = - 1 2 ∆ g i≤d u 2 i + λ k (g) i≤d u 2 i = λ k (g).
Therefore, ∀ϕ ∈ A 0 (M, g),

i≤d q ϕ (u i ) = 2 n M λ k (g)ϕv g = 0
which implies the indefiniteness of q ϕ . Proposition 4.1 and Lemma 4.1 lead to the following Theorem 4.1. Let g be a Riemannian metric on M. i) If g is a critical metric of the functional λ k restricted to C(g), then there exists a finite family

{u 1 , • • • , u d } ⊂ E k (g) of eigen- functions associated with λ k such that i≤d u 2 i = 1. ii) Assume that λ k (g) > λ k-1 (g) or λ k (g) < λ k+1 (g).
Then, g is critical for the functional λ k restricted to C(g) if and only if, there exists a finite family

{u 1 , • • • , u d } ⊂ E k (g) of eigenfunc- tions associated with λ k (g) such that i≤d u 2 i = 1.
The Riemannian metric g of any homogeneous Riemannian space (M, g) is a critical metric of the functional λ k restricted to C(g) for all k such that λ k (g) > λ k-1 (g) or λ k (g) < λ k+1 (g). Indeed, any L 2 (g)orthonormal basis {u i } i≤d of E k (g) is such that i≤d u 2 i is constant on M. In [13, Theorem 4.1], we proved that a metric g is critical for the trace of the heat kernel restricted to C(g) if and only if its heat kernel K is constant on the diagonal of M × M. This last condition implies that, ∀k ∈ N * , any L 2 (g)-orthonormal basis

{u i } i≤d of E k (g) is such that i≤d u 2
i is constant on M. Hence, we have the following Corollary 4.1. Let g be a Riemannian metric on M and let K be the heat kernel of (M, g). Assume that, ∀t > 0, the function x ∈ M -→ K(t, x, x) is constant, then the metric g is critical for the functional λ k restricted to C(g) for all k such that λ k (g) > λ k-1 (g) or λ k (g) < λ k+1 (g).

An immediate consequence of Theorem 4.1 is the following

Corollary 4.2. If g is a critical metric of the functional λ k restricted to C(g), then λ k (g) is a degenerate eigenvalue, that is dim E k (g) ≥ 2.
This last condition means that at least one of the following holds: λ k (g) = λ k-1 (g) or λ k (g) = λ k+1 (g). In the case when g is a local maximizer or a local minimizer, we have the following more precise result

Proposition 4.2. i) If g is a local maximizer of the functional λ k restricted to C(g), then λ k (g) = λ k+1 (g). ii) If g is a local minimizer of the functional λ k restricted to C(g), then λ k (g) = λ k-1 (g).
Proof. Assume that g is a local maximizer and that λ k (g) < λ k+1 (g). Let ϕ ∈ A 0 (M, g) and let g t = e αt g ∈ C(g) be a volume-preserving analytic deformation of g such that d dt g t t=0 = ϕg. Denote by Λ 1 (t), • • • , Λ m (t), with m = dim E k (g), the associated family of eigenvalues of ∆ gt , depending analytically on t and such that Λ

1 (0) = • • • = Λ m (0) = λ k (g)
(see the proof of Theorem 2.1). For continuity reasons, we have, for sufficiently small t and all i ≤ m,

Λ i (t) < λ k+1 (g t ).
Hence, ∀i ≤ m and ∀t sufficiently small,

Λ i (t) ≤ λ k (t) ≤ λ k (g) = Λ i (0). Consequently, Λ ′ i (0) = 0 for all i ≤ m. Since Λ ′ 1 (0), • • • , Λ ′ m (
0) are eigenvalues of the operator Π k • ∆ ′ (by Theorem 2.1), this operator is identically zero on E k (g). Applying Lemma 2.1, we deduce that, ∀ϕ ∈ A 0 (M, g), Q ϕg ≡ 0 on E k (g). Thus, ∀u ∈ E k (g), there exists a constant c so that

|du| 2 + n 4 ∆ g u 2 = c. Integrating, we get c = λ k (g) vol(g) M u 2 v g . Since ∆ g u 2 = 2(λ k u 2 -|du| 2 ), we obtain n 2 u 2 - n -2 2λ k (g) |du| 2 = 1 vol(g) M u 2 v g .
Let x 0 ∈ M be a point where u 2 achieves its maximum. At x 0 , we have du(x 0 ) = 0 and, then,

n 2 max u 2 = n 2 u 2 (x 0 ) = 1 vol(g) M u 2 v g
which leads to a contradiction (since u is not constant and n 2 ≥ 1). A similar proof works for (ii).

In [START_REF] Colbois | Extremal eigenvalues of the Laplacian in a conformal class of metrics: the 'conformal spectrum[END_REF], Colbois and the first author proved that [START_REF] Verdière | Construction de laplaciens dont une partie finie du spectre est donnée[END_REF] sup

g ′ ∈C(g) λ k+1 (g ′ ) n 2 -sup g ′ ∈C(g) λ k (g ′ ) n 2 ≥ n n 2 ω n ,
where ω n is the volume of the unit euclidean sphere of dimension n.

An immediate consequence of this result and Proposition 4.2 is the following Corollary 4.3. Let g be a Riemannian metric on M. Assume that g maximizes the functional λ k restricted to C(g), that is

λ k (g) = sup g ′ ∈C(g) λ k (g ′ ).
Then g cannot maximize neither λ k+1 nor λ k-1 (for k ≥ 2) on C(g).

More precisely, if g maximizes λ k on C(g), then, using Proposition 4.2 and (6), λ k+1 (g)

n 2 ≤ sup g ′ ∈C(g) λ k+1 (g ′ ) n 2 -n n 2 ω n .
Finally we have the following conformal version of Corollary 3.3

Corollary 4.4. Let g be a Riemannian metric on M. Let p ≥ 1 and q ≥ p be two natural integers such that

λ p-1 (g) < λ p (g) = λ p+1 (g) = • • • = λ q (g) < λ q+1 (g).
The metric g is critical for the functional q i=p λ i restricted to C(g) if and only if there exists an L 2 (M, g)-orthonormal basis u 1 , u 2 , . . . , u m of E p (g) such that m i=1 u 2 i is constant on M.

Critical metrics of the eigenvalue ratios functionals

Let M be a closed manifold of dimension n ≥ 2 and let k be a positive integer. This section deals with the functional g -→ λ k+1 (g) λ k (g) .

This functional is invariant under scaling, so it is not necessary to fix the volume of metrics under consideration. If (g t ) t is any analytic deformation of a metric g, then t -→ λ k+1 (g t ) λ k (g t ) admits left and right derivatives at t = 0 (Theorem 2.1).

Definition 5.1. i) A metric g is said to be critical for the ratio λ k+1 λ k if, for any analytic deformation (g t ) of g, the left and right derivatives of λ k+1 (g t ) λ k (g t ) at t = 0 have opposite signs.

ii) The metric g is said to be critical for the ratio functional λ k+1 λ k restricted to the conformal class C(g) if the condition above holds for any conformal analytic deformation g t = e αt g of g.

Let g be a Riemannian metric on M. For any covariant 2-tensor h ∈ S 2 (M), we introduce the following operator Pk,h :

E k (g) ⊗ E k+1 (g) -→ E k (g) ⊗ E k+1 (g) defined by Pk,h = λ k+1 (g)P h,k ⊗ Id E k+1 (g) -λ k (g)Id E k (g) ⊗ P k+1,h ,
where P k,h is defined in Lemma 2.1. The quadratic form naturally associated with Pk,h is denoted by Qk,h and is given by, ∀u ∈ E k (g) and ∀v ∈

E k+1 (g), Qk,h (u ⊗ v) = λ k+1 (g) v 2 L 2 (g) Q h (u) -λ k (g) u 2 L 2 (g) Q h (v), where Q h (u) = -M (du ⊗ du + 1 4 ∆ g u 2 g, h)v g . Of course, if λ k+1 (g) = λ k (g),
then g is a global minimizer of the ratio λ k+1 λ k . Notice that, thanks to Colin de Verdière's result [START_REF] Verdière | Construction de laplaciens dont une partie finie du spectre est donnée[END_REF], ∀k ≥ 1, any closed manifold M carries a metric g such that λ k+1 (g) = λ k (g). A general characterization of critical metrics of λ k+1 λ k is given in what follows Proposition 5.1. A Riemannian metric g on M is critical for the functional λ k+1 λ k if and only if, ∀h ∈ S 2 (M), the quadratic form Qk,h is indefinite on E k (g) ⊗ E k+1 (g).

Proof. The case where λ k+1 (g) = λ k (g) is obvious ( Qk,h (u ⊗ u) = 0). Assume that λ k+1 (g) > λ k (g) and let (g t ) t be an analytic deformation of g. From Theorem 2.1, d dt λ k (g t ) t=0 -and d dt λ k (g t ) t=0 + are the least and the greatest eigenvalues of P k,h on E k (g) respectively. Similarly, d dt λ k (g t ) t=0 -and d dt λ k (g t ) t=0 + are the greatest and the least eigenvalues of P k+1 on E k (g). Therefore,

λ k (g) 2 d dt λ k+1 (g t ) λ k (g t ) t=0 -= λ k (g) d dt λ k+1 (g t ) t=0 --λ k+1 (g) d dt λ k (g t ) t=0 -
is the greatest eigenvalue of Pk,h on E k (g) ⊗ E k+1 (g), and

λ k (g) 2 d dt λ k+1 (g t ) λ k (g t ) t=0 + = λ k (g) d dt λ k+1 (g t ) t=0 + -λ k+1 (g) d dt λ k (g t ) t=0 +
is the least eigenvalue of Pk,h on E k (g) ⊗ E k+1 (g). Hence, the criticality of g for λ k+1 /λ k is equivalent to the fact that Pk,h admits eigenvalues of both signs, which is equivalent to the indefiniteness of Qk,h .

Lemma 5.1. Let g be a Riemannian metric on M. The two following conditions are equivalent: i) ∀h ∈ S 2 (M), the quadratic form Qk,h is indefinite on E k (g) ⊗ E k+1 (g). ii) There exist two finite families {u

1 , • • • , u p } ⊂ E k (g) and {v 1 , • • • , v q } ⊂ E k+1 (
g) of eigenfunctions associated with λ k (g) and λ k+1 (g) respectively, such that i≤p

(du i ⊗ du i + 1 4 ∆ g u 2 i g) = j≤q (dv j ⊗ dv j + 1 4 ∆ g v 2 j g).
Proof. "(i) implies (ii)": Let us introduce the two following convex cones

K 1 = i∈I (du i ⊗ du i + 1 4 ∆ g u 2 i g); u i ∈ E k (g), I ⊂ N, I finite ⊂ S 2 (M)
and

K 2 = j∈J (dv j ⊗ dv j + 1 4 ∆ g v 2 j g); v j ∈ E k+1 (g), J ⊂ N, J finite ⊂ S 2 (M).
It suffices to prove that K 1 and K 2 have a nontrivial intersection. Indeed, otherwise, applying classical separation theorems, we show the existence of a 2-tensor h ∈ S 2 (M) such that, ∀ T

1 ∈ K 1 , T 1 = 0, M (T 1 , h)v g > 0 and, ∀ T 2 ∈ K 2 , M (T 2 , h)v g ≤ 0.
Therefore, ∀u ∈ E k (g) and ∀v ∈ E k+1 (g), with u = 0 and v = 0, one has

Q h (u) < 0, Q h (v) ≥ 0 and Qk,h (u ⊗ v) = λ k+1 (g) v 2 L 2 (g) Q h (u) -λ k (g) u 2 L 2 (g) Q h (v) ≤ λ k+1 (g) v 2 L 2 (g) Q h (u) < 0, which implies that Qk,h is negative definite on E k (g) ⊗ E k+1 (g).
"(ii) implies (i)": Let {u i } i≤p and {v j } j≤q be as in (ii). From the identity in (ii), we get, after taking the trace and integrating,

i≤p M |du i | 2 v g = j≤q M |dv j | 2 v g , which gives, λ k (g) i≤p u i 2 L 2 (g) = λ k+1 (g) j≤q v j 2 L 2 (g) . Now, i,j Qk,h (u i ⊗v j ) = i,j λ k+1 (g) v j 2 L 2 (g) Q h (u i )-λ k (g) u i 2 L 2 (g) Q h (v j ).
Assumption (ii) implies that i≤p Q h (u i ) = j≤q Q h (v j ). Therefore, Indeed, a straightforward calculation shows that the two equations ( 7) and ( 8) are equivalent to the condition (ii) of Lemma 5.1.

Corollary 5.1. If g is a critical metric of the functional λ k+1 λ k , with λ k+1 (g) = λ k (g), then

inf {dim E k (g), dim E k+1 (g)} ≥ 2.

Proof. Let {u i } i≤p ⊂ E k (g) and {v j } j≤q ⊂ E k+1 (g) be two families of eigenfunctions satisfying [START_REF] Eells | A report on harmonic maps[END_REF] and ( 8) above. Taking the trace in [START_REF] Eells | A report on harmonic maps[END_REF] and using [START_REF] Eells | Harmonic maps and minimal immersions with symmetries[END_REF] we get [START_REF] Soufi | Greatest least eigenvalue of the laplacian on the klein bottle[END_REF] α = 1 n (

i≤p |du i | 2 - j≤q |dv j | 2 ) = 1 4 ∆ g ( j≤q v 2 j - i≤p u 2 i ).
Assume that α = 0. Using ( 8) and ( 9), we deduce that both i≤p u 2 i and j≤q v 2 j are constant on M. Since the u i 's and the v j 's are not constant, we get the result. Assume now α = 0. Since M α v g = 0 (see [START_REF] Soufi | Greatest least eigenvalue of the laplacian on the klein bottle[END_REF]), the function α takes both positive and negative values. Let x ∈ M such that α(x) > 0. From [START_REF] Eells | A report on harmonic maps[END_REF], the quadratic form i≤p du i ⊗ du i is clearly positive definite on T x M. Hence, the family {du i } has maximal rank at x. This shows that dim E k (g) ≥ n. At a point x ∈ M where α(x) < 0, the quadratic form j≤q dv j ⊗ dv j is positive definite on T x M and, then, dim E k+1 (g) ≥ n.

When we deal with critical metrics of the functional λ k+1 λ k restricted to C(g), only tensors of the form h = ϕ g, with ϕ ∈ C ∞ (M), are involved. The corresponding quadratic forms on E k (g) ⊗ E k+1 (g) are given by qk,ϕ (u ⊗ v) = λ k+1 (g) v 2

L 2 (g) q ϕ (u) -λ k (g) u 2 L 2 (g) q ϕ (v). Following the steps of the proof of Proposition 5.1, we can show that: Proposition 5.2. A Riemannian metric g on M is critical for the functional λ k+1 λ k restricted to C(g) if and only if, ∀ϕ ∈ C ∞ (M), the quadratic form qk,ϕ is indefinite on E k (g) ⊗ E k+1 (g).

Replacing the convex cones K 1 and K 2 in the proof of Lemma 5.1 by

H 1 = i∈I (λ k (g)u 2 i - n -2 n |du i | 2 ); u i ∈ E k (g), I ⊂ N, I finite ⊂ L 2 (M, g)
and

H 2 = j∈J (λ k+1 (g)v 2 j - n -2 n |dv j | 2 ); v j ∈ E k+1 (g), J ⊂ N, J finite ⊂ L 2 (M, g),
we can show, by the same arguments, that the indefiniteness of qk,ϕ for all ϕ ∈ C ∞ (M), is equivalent to the fact that H 1 and H 2 have a non-trivial intersection. Therefore, one has: Theorem 5.2. A Riemannian metric g on M is critical for the functional λ k+1 λ k restricted to C(g) if and only if, there exist two families {u 1 , • • • , u p } ⊂ E k (g) and {v 1 , • • • , v q } ⊂ E k+1 (g) of eigenfunctions associated with λ k (g) and λ k+1 (g), respectively, such that λ k (g) It is clear that in this case, if λ k+1 (g) = λ k (g), then at least one of the eigenvalues λ k (g) and λ k+1 (g) is degenerate.

Propositions 3 . 1 , 3 . 2 andTheorem 3 . 1 .

 313231 Lemma 3.1 lead to the following characterization of critical metrics of λ k : Let g be a Riemannian metric on M. i) If g is a critical metric of the functional λ k , then there exists a finite family {u 1 , • • • , u d } ⊂ E k (g) of eigenfunctions associated with λ k (g) such that i≤d du i ⊗ du i = g.

2 L 2

 22 Qk,h (ui ⊗v j ) = j≤q λ k+1 (g) v j (g) -i≤p λ k (g) u i 2 L 2 (g) i≤p Q h (u i ) = 0. Hence, Qk,h is indefinite on E k (g) ⊗ E k+1 (g).Consequently, we have proved the following Theorem 5.1. A metric g on M is critical for the functional λ k+1 λ k if and only if there exist two families{u 1 , • • • , u p } ⊂ E k (g) and {v 1 , • • • , v q } ⊂ E k+1(g) of eigenfunctions associated with λ k (g) and λ k+1 (g), respectively, such that (7) i≤p du i ⊗ du i -j≤q dv j ⊗ dv j = αg for some α ∈ C ∞ (M), and (8) λ k (g)

Remark 5 . 1 .

 51 In dimension 2, the condition of Theorem 5


Diop Ibrahima

Pierre-Yvan Liardet

Yanis Linge

Stmicroelectronics Philippe

Collision Based Attacks in Practice

Chosen-Message Simple Power Analysis, also called Collision Based Attacks (CBA), have been proposed by Fouque, Yen and Homma. These attacks aim at inducing and detecting collisions during modular operations. However, detecting collisions is a challenging task in real environments. Doing it in an automated manner is even more challenging. In this paper, we propose and compare some methods and criteria allowing to automatically (without any visual inspection) detect the occurrence of collisions in leakage traces acquired on modern (and thus noisy) circuits.

I. INTRODUCTION

Modular exponentiation plays a fundamental role in public key cryptosystems, such as RSA [START_REF] Ronald L Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]. Unfortunately the implementation of most of the modular exponentiation algorithms are vulnerable to Side Channel Attacks (SCA) exploiting the power consumption [START_REF] Paul | Differential power analysis[END_REF], the electromagnetic radiations [START_REF] Gandolfi | Electromagnetic analysis: Concrete results[END_REF] or the computation times [START_REF] Paul | Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems[END_REF] if the designers does not implement ad-hoc countermeasures.

Over the last few years, several works have highlighted the threat constituted by chosen message attacks which can be viewed as an enhanced Simple Power Analysis (SPA) [START_REF] Fouque | The doubling attack -why upwards is better than downwards[END_REF], [START_REF] Yen | Power analysis by exploiting chosen message and internal collisionsvulnerability of checking mechanism for rsa-decryption[END_REF], [START_REF] Yen | Relative doubling attack against montgomery ladder[END_REF], [START_REF] Homma | Comparative power analysis of modular exponentiation algorithms[END_REF], [START_REF] Homma | Collision-based power analysis of modular exponentiation using chosen-message pairs[END_REF], [START_REF] Sung-Ming | Modified doubling attack by exploiting chosen ciphertext of small order[END_REF] or as a Differential Power Analysis [START_REF] Paul | Differential power analysis[END_REF] conducted in an horizontal manner [START_REF] Clavier | Horizontal correlation analysis on exponentiation[END_REF], [START_REF] Walter | Sliding windows succumbs to big mac attack[END_REF], [START_REF] Clavier | Rosetta for single trace analysis[END_REF], [START_REF] Bauer | Horizontal and vertical side-channel attacks against secure rsa implementations[END_REF]. The related techniques, categorized under the terms 'Comparative Power Analysis' or 'Collision Based Attacks' (CBA), compare two segments (time frames) of two leakage traces and then use the results in order to decide whether the operation processed during these two time frames are the same or not, i.e. to decide whether there is a collision or not.

To be able to interpret the occurrence of a collision, i.e. to reveal some secrets, the occurrence of a collision must be controlled but must also depend on a secret information value (e.g. an exponent bit value). At this aim, the idea is to choose message pairs expected to produce a collision at known steps of private or public key algorithms, i.e. at some known (adjacent or not) leakage patterns of the two related SCA traces.

To apply a CBA, the execution of the target cryptographic algorithm must be regular in time because adversaries must be able to distinguish one leakage pattern from another. Except this constraint which is met on public key algorithms to thwart SPA, CBA is considered applicable to all standard exponentiation algorithms including the binary methods [START_REF] Alfred J Menezes | Handbook of applied cryptography[END_REF], m-ary (window) methods [START_REF] Kaya | High-speed rsa implementation[END_REF], sliding window methods [START_REF] Kaya | High-speed rsa implementation[END_REF], and their variants [START_REF] Kaya | High-speed rsa implementation[END_REF], which are resistant to previously proposed attacks [START_REF] Paul | Differential power analysis[END_REF].

As a result, CBA has been demonstrated efficient against symmetric cryptographic algorithms in [START_REF] Schramm | A new class of collision attacks and its application to des[END_REF], [START_REF] Bogdanov | Improved side-channel collision attacks on aes[END_REF], and asymmetric cryptographic algorithms using modular exponentiation in [START_REF] Fouque | The doubling attack -why upwards is better than downwards[END_REF], [START_REF] Yen | Power analysis by exploiting chosen message and internal collisionsvulnerability of checking mechanism for rsa-decryption[END_REF], [START_REF] Homma | Comparative power analysis of modular exponentiation algorithms[END_REF] as detailed in section II.

However in real environment, the collision detection is a challenging task because of trace misalignment and reduced Signal-to-Noise Ratio (SNR). This is especially true if one aims at doing it in an automated and relevant manner on modern micro-controllers or smart-cards. In order to meet this challenge, Chen et al. proposed in [START_REF] Aidong | Collision-based chosen-message simple power clustering attack algorithm[END_REF] an automated solution based on clustering while in [START_REF] Perin | Practical analysis of rsa countermeasures against side-channel electromagnetic attacks[END_REF] Perin et al. defined a detection criterion in order to ease the detection of collisions. Within this context, this paper tackles the collision detection problem by combining and comparing some solutions to finally introduce a practical and efficient solution. The latter is based both on leakage trace compression and on a bounded collision detection criterion.

The rest of the paper is organized as follows. In section II, some preliminaries related to the RSA implementations are given as well as a summary of previous works on Collision Based Analysis applied to public key cryptosystems. Section III proposes an analysis of some general and specific techniques that can ease the detection of collisions. Additionally a bounded collision detection criterion is also introduced and justified in this section. Experimental results using the different techniques and the proposed collision detection criterion are given in section IV. It is important to notice that experiments described in section IV were done with one shot leakage traces measured on modern micro-controllers. This constraint was imposed by the jitter of modern circuits we considered but also in view of the frequent use of countermeasures such as shuffling and dummy operation insertion. Finally a conclusion is drawn in last section.

II. PRELIMINARIES, RELATED WORKS

A. RSA and modular exponentiation 1) The RSA cryptosystem: RSA is an algorithm for publickey cryptosystem and was first publicly described by Rivest, Shamir and Adleman in 1978 [START_REF] Ronald L Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]. The RSA algorithm is designed as follows: Let n be a product of two large prime integers p and q.

To cipher( resp. to decipher) a message M (resp. a cipher C) with RSA, the algorithm computes C = M e mod n (resp. D = C d mod n) where e is a public exponent (resp. d is private exponent). The security of the algorithm stems from the hard problem of factoring the modulus n.

2) The Binary exponentiation method: The binary method is an efficient exponentiation algorithm. It performs multiplication and squaring operations according to the bit pattern of the exponent. There exist two variations of the algorithm. The left-to-right binary method (algorithm 1), which starts from the exponent's MSB (the Most Significant Bit) to its LSB (the Last Significant Bit), and the right-to-left binary method (algorithm 2), which operates in the opposite direction. In these algorithms k is the bit length of the secret key. Because of its higher performance and low resource requirements the left-to-right binary method is the mostly used. We therefore consider only this exponentiation method.

Algorithm 1 LEFT-TO-RIGHT BINARY METHOD Require: M, d = (d k-1 , ..., d 1 , d 0 ), d i ∈ {0, 1} ∀ i, n Ensure: C = M d mod n 1: C = 1 2: for i = k -1 downto 0 do 3: C = C × C mod n 4: if d i = 1 then 5: C = C × M mod n 6:
end if 7: end for B = B × B mod n 8: end for 9: return C

B. Collision Based Analysis and public key algorithms

One of the first examples of a CBA applicable to public key cryptographic algorithms is the Doubling Attack (DA). It was introduced by Fouque and Valette in [START_REF] Fouque | The doubling attack -why upwards is better than downwards[END_REF]. The DA requires acquiring two leakage traces during the computation of two modular exponentiation with two chosen messages. Typically, an attacker uses: M mod n and M 2 mod n, as input messages. The secret is disclosed by detecting or not a collision between a squaring operation at (i + 1) th iteration loop in the leakage trace of M and a squaring operation at the i th iteration loop in that of M 2 . Indeed, the collision occurs Fig. 1: Illustration of the principle of the Doubling Attack if and only if the equivalent exponent bit d i is 0. Figure 1 illustrates the principle of the DA which is applicable to any modular exponentiation based on a left-to-right binary method even if the Device Under Test (DUT) features one of the popular blinding countermeasures [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF].

Yen et al. extended the DA in [START_REF] Yen | Power analysis by exploiting chosen message and internal collisionsvulnerability of checking mechanism for rsa-decryption[END_REF]. They proposed to choose a single input:

-1 mod n, as the chosen message to induce a strong differences between the processing of a modular multiplication and of the modular squaring. They also discussed in their paper the possibility of defeating one of the most popular SPA countermeasure: the insertion of dummy multiplications [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF]. Yen et al. also proposed in [START_REF] Yen | Power analysis by exploiting chosen message and internal collisionsvulnerability of checking mechanism for rsa-decryption[END_REF] to exploit the two leakage traces associated to the processing of:

M mod n and -M = (n -M ) mod n
For the rest of this paper we will refers to this attack as Opposite Attack (OA). This proposal is entrenched in the fact that the processing of M and -M are identical if (d k-1 ...d 0 ) 2 is an even integer after the iteration i. Therefore, d i can be identified by detecting the occurrence or not of a collision (Figure 2). In the above, the processing of the chosen messages induces a collision of squaring at the adjacent or at the same time frames in the two related leakage traces and can only be applied to implementations based on the left-to-right binary method.

In contrast, the CBA proposed by Homma et al. in [START_REF] Homma | Comparative power analysis of modular exponentiation algorithms[END_REF], [START_REF] Homma | Collision-based power analysis of modular exponentiation using chosen-message pairs[END_REF], can generate a collision between two leakage traces at two arbitrary time frames by choosing two input messages in a more flexible relationship. The idea is to use two input messages Y and Z satisfying the equation:

Y α = Z β mod n,
where α and β are constants. The value of α is chosen to provide information on a certain bit, and β ≤ α is chosen arbitrarily. This attack requires two leakage traces to disclose each bit of the exponent. Contrarily to their first proposal, this attack can be applied to all standard exponentiation algorithms. Some further extensions have recently been proposed by Yen et al. [START_REF] Sung-Ming | Modified doubling attack by exploiting chosen ciphertext of small order[END_REF] who provide some simulated results of their attacks.

By considering the attacks we have shortly described, one may thus conclude that literature provides several efficient Fig. 2: Illustration of the principle of the Opposite Attack solutions to induce collisions. However, to the best of our knowledge there are only few works proposing solutions to detect efficiently and automatically collisions; a key problem to enable an efficient practice of CBA on modern smart cards or micro-controllers. Among them, Chen et al. recently proposed in [START_REF] Aidong | Collision-based chosen-message simple power clustering attack algorithm[END_REF] an automated solution based on clustering while in [START_REF] Perin | Practical analysis of rsa countermeasures against side-channel electromagnetic attacks[END_REF] Perin et al. defined a detection criterion to ease the detection of collisions in practice. Within this context, this paper extends these methods in order to automatically detect the occurrence of collision in leakage traces acquired on modern (and thus noisy) circuits.

III. CRITERIA AND PRACTICAL TECHNIQUES FOR COLLISION BASED ATTACKS

In real environment, the collision searching is a challenging task because of trace misalignment, reduced Signal-to-Noise Ratio (SNR) or because of the occurrence of outlier events in the observed trace recorded (e.g. the firing of a pump charge). Countermeasures, like the random insertion of dummy operations and shuffling, are just some of the additional and possible reasons [START_REF] Mangard | Power analysis attacks: Revealing the secrets of smart cards[END_REF] explaining the difficulty of detecting collision. The fact whether the recorded leakage traces are aligned or not, essentially depends on the signal used (usually the communication I/O of a smart card) to trigger the oscilloscope. Several techniques were proposed to improve SCA efficiency in presence of misaligned leakage traces. In [START_REF] Homma | High-resolution side-channel attack using phase-based waveform matching[END_REF] a high resolution waveform matching method based on Phase-Only Correlation (POC) is proposed. this method is particularly efficient because of its robustness to outliers (Peaks included by the firing of a pomp charger). This explains why we privileged it in this paper. The POC computes the difference of phase between two traces using the cross-phase spectrum of the Discrete Fourier Transform (DFT) of these traces (see [START_REF] Homma | High-resolution side-channel attack using phase-based waveform matching[END_REF] for survey).

As an illustration, Figure 3a shows three traces we measured above a modern micro-controller before application of any alignment method. Figure 3b shows the same traces after application of the POC. As shown, even if the leakage traces collected above a modern micro-controller are quite noisy, POC is efficient in suppressing (or in reducing) the misalignment between traces. This technique is therefore considered as an unavoidable pre-processing step in the remainder of the paper; pre-processing systematically applied prior to launch any collision detection technique.

A. Collision Detection Techniques

Chen et al. proposed in [START_REF] Aidong | Collision-based chosen-message simple power clustering attack algorithm[END_REF] an automated solution based on clustering to automatically detect the occurrence of a collision. However, their iterative solution requires the definition of a threshold value by the adversary. The definition of this a priori unknown threshold constitutes a limit of their proposal. Indeed, fixing the threshold value to a too high or low value can lead to long processing times or to a poor discrimination capability of collisions.

B. Detection Criteria

More recently Perin et al. defined a collision detection criterion in [START_REF] Perin | Practical analysis of rsa countermeasures against side-channel electromagnetic attacks[END_REF]. This criterion, the P CDC, is based on engineering intuition. Let us remind the basis on which is entrenched this criterion. At this end let:

• T i = [t i 1 , • • • , t i w ]
be a vector of samples, collected with an oscilloscope, representing the leakage pattern i. This pattern could correspond to a squaring (resp. a multiply), in that case we use to denote it by T S (resp. T M ),

• P (T E , M, d) represent the leakage trace of the complete modular exponentiation with message M and exponent d,

• P (T M , M, d i ) stand for the specific leakage pattern of a multiply done during the time frames T M with exponent bit d i ,

• P (T S , M, d i ) stand for the specific leakage pattern of a squaring done during the time frames T S with exponent bit d i

With such definitions, P CDC is expressed as follows:

P CDC(T 1 , T 2 ) = σ (T1) σ (T1-T2) . (1)
In this expression, σ (T1) denotes the standard deviation of the leakage vector T 1 while σ (T1-T2) is the standard deviation of the difference T 1 -T 2 . It should be noticed that T 1 = P (T S , M 2 , d i-1 ) and T 2 = P (T S , M, d i ) if the adversary aims at applying the DA. If he prefers the OA then

T 1 = P (T S , -M, d i ) and T 2 = P (T S , M, d i ).
The idea on which the P CDC is based is simple. If a collision occurs, P CDC is expected to be really high because σ (T1-T2) is low while in the opposite case P CDC is expected to be significantly smaller. If the results reported in [START_REF] Perin | Practical analysis of rsa countermeasures against side-channel electromagnetic attacks[END_REF] are convincing, demonstrating de facto the interest of this criterion, one should note that these results were obtained with averaged leakage traces, and it's not clear information of what means a low or a high P CDC value is given. These latter points constitute important limitations and this especially as the P CDC is an unbounded figure of merit.

To circumvent these issues, following the intuition of [START_REF] Perin | Practical analysis of rsa countermeasures against side-channel electromagnetic attacks[END_REF], we derived from equation 1 a criterion called Bounded Collision Detection Criterion afterward (BCDC), whose values are in ]0,1]:

BCDC(T 1 , T 2 ) = 1 √ 2 × σ (T1-T2) σ (T1) (2)

Property

Let us consider two patterns T 1 and T 2 , we have: 1) a) Asymptotically

0 < BCDC(T 1 , T 2 ) ≤ 1 (3)
b) Moreover in case of collision:

BCDC(T 1 , T 2 ) → 0, (4)
when the SNR is high. 2) In the case of non-collision:

BCDC(T 1 , T 2 ) = 1 (5)

Proof

Each point of the pattern T i (i=1,2), t i j (with i ∈ [1, 2] and j ∈ [1, w]) is equal to the sum of :

• a deterministic value (s i j ) representing the leakage of the DUT during the processing of the message.

•

a random value representing the measurement noise (η i j ) drawn in a normal distribution with mean 0 and standard deviation σ and independent of s i j . Note that in the following we consider that the measurement noise is independent of leakage (s i j ) in each point. Considering:

∆T = T 1 -T 2 = [δ t1 , • • • , δ tw ] (6)
we can write each point:

δ tj = t 1 j -t 2 j = s 1 j + η 1 j -(s 2 j + η 2 j ). (7)
Considering the nature of the terms involved in equation 7, it appears that ∆T is a realization of a random variable with unknown mean but with a variance equal to:

σ 2 (T1-T2) = σ 2 ([s 1 1 -s 2 1 , • • • , s 1 w -s 2 w ]) + σ 2 ([η 1 1 -η 2 1 , • • • , η 1 w -η 2 w ]) (8)
which can be rewritten, defining σ s as the standard deviation of

s i = [s i 1 , • • • , s i w ]
, as follows:

σ (T1-T2) = 2 • σ 2 s + 2 • σ 2 = √ 2 • σ 2 s + σ 2 (9)
1) From equation 9, one may express the asymptotic BCDC values when a collision occurs or not.

In case of a collision, because t 1 j = t 2 j , and therefore because σ

(T1-T2) = √ 2 • √ σ 2 , equation 2 becomes: BCDC(T 1 , T 2 ) = 1 √ 2 σ(∆T ) σ(T 1 ) = 1 √ 2 √ 2.σ σ 2 s + σ 2 = 1 1 + σ 2 s σ 2 , ( 10
)
expression which tends towards 0 when the SNR is high ( σ s >> σ) or when pre-processing techniques are applied to increase the SNR value. It should be noticed that in our practical experiments (some examples are given in section IV-B), one shot leakage traces measured on a modern micro-controller are characterized by σ values close to that of σ s resulting in BCDC values close to 1 2 in case of collisions. 2) In the opposite case, i.e. when no collision occurs, the expression of the BCDC criterion is :

BCDC(T 1 , T 2 ) = 1 √ 2 . √ 2. σ 2 s + σ 2 σ 2 s + σ 2 = 1 (11)
Here it should be noticed that all the above calculations do not take into account other electrical activities of the device under test. It should therefore be possible to observe some values slightly higher than 1 in practice. This could even occurs without any additional activity of the circuit because each pair of trace will give an estimation of σ(T 1 ) and σ(T 2 ) and therefore of the BCDC. The criterion should be considered as asymptotically bounded between 0 and 1.

C. Decision Making: collision or not

At that stage, we have at disposal a criterion that takes two leakage patterns and provides as a result a scalar value between [0, 1]. A BCDC equal to 0 means that a perfect collision occurs while a value of 1 means that there is no collision. However, 0 and 1 are asymptotic values and in practice BCDC values range between 0 and 1. A decision tool is mandatory to automatically classify the obtained BCDC values and thus decide who pairs of patterns are colliding.

At that end one can use the k-means algorithm (a standard clustering algorithm) with k = 2 in order to distinguish collision or not collision, as described by algorithm 3 and algorithm 4 for the DA and the OA respectively. end if 12: end for 13: return S

A i = BCDC(T i 1 , T i 2 ) 3: end for 4: R = k-means (A = [A 1 , • • • , A l ]), with k = 2, R i ∈ {N, C} 5: S 0 = Square 6: for i = 1 to length(R)
A i = BCDC(T (i+1) 1 , T i 2 ) 3: end for 4: R = k-means (A = [A 1 , • • • , A l ]), with k = 2, R i ∈ {N, C} 5: S 0 = Square 6: for i = 1 to length(R)

D. Enhancing SNR

In the preceding paragraphs, one could have noticed the importance of the measurement quality, i.e. the SNR, on the BCDC values in case of a collision. It is therefore interesting to take a look to practical techniques for enhancing the SNR. Among the methods targeting the SNR improvement we have chosen filtering and trace compression. The averaging technique has not been considered because not applicable due to misalignment of traces. This technique is indeed not applicable in many cases due to misalignment of traces or again to the more and more common usage of multiple clocks within smart-cards.

1) Filtering: Filtering techniques are efficient if one knows which frequency bandwidths must be kept and which must be attenuated during in the considered side channel. In [START_REF] Tiran | A model of the leakage in the frequency domain and its application to cpa and dpa[END_REF] a method has been proposed to select which frequencies must be kept or not during SCA. This method is based on a selection criterion called the Leakage to Noise Ratio (LNR). When leakage traces are power measurements, its expression is:

LN R(f ) = 1 f 2 P SD(f ) σ P SD(f ) (12)
where < P SD(f ) > is the mean Power Spectral Density at the frequency f and σ P SD(f ) the standard deviation of PSD(f). This technique can be used to enhance the detection of collisions as it will shown in section IV-B.

2) Trace compression: Another method would to apply the compression method on both curves. In this work we have chosen the compression method which consists in summing each set of c consecutive samples into one to obtain a compressed trace. Choosing a suitable value for c is therefore crucial for the efficiency of this compression technique. In practice, usually time intervals up to the length of a single clock cycle are used. These settings given, let us show why and how the compression enhances the contrast between collisions and no collision when the adversary uses the BCDC.

Compressing a leakage trace T i by a factor c results in the getting of the compressed trace:

C c (T i ) =    t i l = (l+1)c-1 k=lc t i k , l ∈ [0, w/c] ∩ N N N    (13)
Assuming the realizations of the noise are independent from one sample to another, one may consider the central limit theorem and express the standard deviation of the compressed trace:

σ C c (Ti) = σ 2 s + σ 2 c ( 14
)
where σ s is the standard deviation of compressed deterministic part s i j of T i on which the central limit theorem can not be applied because the computations are deterministic and therefore independent. As shown, compressing by a factor c the leakage trace T i results in dividing the standard deviation of the noise by 1 √ c . This reduction does not change the value of the BCDC when there is no collision because the reduction of the noise standard deviation is involved in both the numerator and in the denominator of equation 11). However, when there is a collision compressing by a factor c results in dividing significantly the value of the BCDC. One may therefore conclude that compressing traces allows increasing the contrast between the BCDC values associated to the occurrence or not of a collision and therefore helps the k-means in partitioning accurately collisions for non-collisions.

IV. EXPERIMENTAL RESULTS

This section gives some of the results obtained during many experimental campaigns. The results we have chosen to report aims at sustaining the theoretical efficiency of our automated collision detection technique which is based on the joint usage of the BCDC and of the k-means. Some results showing the efficiency of the LN R but also of the compression technique are also given. This subsection present results obtained on different products (DUTs). The DUT references are kept confidential even if these products can be purchase on the web. All DUTs are open development platforms where it is possible to call the Crypto routines with our own inputs (Messages). To test the efficiency of CBA but also of our detection technique, we performed many analysis using the platform shown Figure 4. This platform features a LeCroy TELEDYNE HD04096 oscilloscope to collect the power consumption traces. The computer sends instructions and data to a modern micro-controller interface, and receive the output data.

During all experiments, the DUT was executing an Exponentiation with the exponent value d = AE8F 8A89632F 1EE49A13548690183427. Only one shot traces were collected during our experiments considering that exponent randomization is now a standard countermeasure. Traces were collected using a sampling rate of 2.5 GS/s (or 500 MS/s) resulting in patterns of 24000 samples (or 4850 respectively).

B. Experimental results

1) Setting a reference using the Difference of Traces (DoT):

To evaluate the efficiency of the detection technique introduced above, we first set an efficiency reference. This reference corresponds to the capability of detecting collision using only the difference between the two traces (DoT) i.e. using the solution introduced in the seminal works about CBA [START_REF] Fouque | The doubling attack -why upwards is better than downwards[END_REF], [START_REF] Yen | Power analysis by exploiting chosen message and internal collisionsvulnerability of checking mechanism for rsa-decryption[END_REF].

We therefore collected pairs of traces corresponding to the processing of M and M 2 mod n or to that of M and -M mod n, for several values of M selected randomly and we searched for collisions on the third byte ( 8A = 10001010 2 ). After alignment of traces and patterns with the POC method, we computed the DoT directly to draw Figure 5a and5b. As shown, even if the difference is low on some time frames, it is difficult to detect with a high level of confidence any collision.

2) Efficiency of the compression technique: The reference being set, we applied on the same traces a compression of factor c = 100 and then recomputed the difference. Figures 6a 3) Efficiency of the LNR filtering: The same experiment than in the preceding section was conducted using the LN R instead of the compression technique. Figures 7a and7b give the results for the DA and OA. As for Figures 5a and5b, collisions can be detected by visual inspection. However, the contrast between collision and no collision is not as high than when using compression.

4) Efficiency of the BCDC: In this paragraph some results corresponding to the direct application of our detection technique, which is based on the joint usage of the BCDC and of the k-means, are given. It should be noticed that no technique to enhance the SNR was used to obtained these results. In these figures, each bar represents a BCDC of two adjacent modular operations and its color shows its membership to the cluster of collision (red)or to that of non collision (blue). Comparing figures 5a and 5b with figures 8a and 8b highlights a first key advantage of using the BCDC which is the association of a scalar value to each modular operation. In addition the BCDC eases the detection of collisions by simple visual inspection because its values are bounded and the bounds are easily interpretable ('1' no collision, '0' collision).

One can also remark in figure 8 that BCDC values associated to no collision are close to one as expected from the given in section III. One can also notice that BCDC values in case of collision range between 0.6 and 0.8. Collisions can easily be distinguished from non-collision using the k-means. An adversary can therefore easily recover the sequence of operations. In Figure 8a, he obtains the following sequence N N CCCN N CN N , where N means non-collision, C collision. Applying algorithm 4 finally provides the exponents bits (1000101x) 2 where x is the LSB of the Byte to recover.

5) Combining BCDC and compression: If the results introduced in the preceding paragraphs are sufficient to validate the correctness of the proposed detection criterion, we can combining BCDC and Compression, once again on the same measurements, after application of a compression by a factor c = 100. The comparison of figures 9a and 9b with figures 8a and 8b respectively clearly shows that the usage of the compression technique significantly increases the contrast between collision and no-collision. The BCDC values in case of collision are now ranging between 0.2 and 0.4.

6) Combining BCDC and LNR filtering: All the experiments described in the preceding section were re-done using LNR filtering rather than compression. Figures 10a and10b give the results for the DA and OA respectively. As expected from [START_REF] Tiran | A model of the leakage in the frequency domain and its application to cpa and dpa[END_REF], giving more importance to low frequencies than to high frequencies allows increasing significantly the SNR.

7) Overall efficiency estimation (Success Rate): To definitively validate the interest of the proposed detection technique (BCDC and k-means), we estimated the probability to detect a collision knowing the exponent. This was done by considering a set of 100 pairs of traces for the DA and the OA. This As shown, the application of compression or LNR filtering has a moderated effect on the Success Rate value when the scope was set with a high sampling rate value (here 2.5 GS/s) to collect traces. It should be noticed that high sampling rate values can not be used for long secret exponents because of memory limitations of oscilloscopes. One can also observe that compressing too much the leakage traces could be counterproductive. One may therefore conclude that the usage of the BCDC coupled with that of the k-means is sufficient to automatically detect collisions with a Success Rate values higher than 99% when leakage traces are acquired with a sampling rate.

Table II also shows that when the sampling rate is low, LNR filtering and compression enhance the results and that the Success Rate reaches 100%. However, it should be noticed once again than compressing too much the leakage traces is counterproductive.

V. CONCLUSION

In this paper we have introduced a new evaluation collision criterion called BCDC. This criterion has been proposed to first make collision attack much practical. Some experiments are presented to compare this criterion with the already published in [START_REF] Mangard | Power analysis attacks: Revealing the secrets of smart cards[END_REF]. As a clear result our new criterion is much more efficient to find and exploit collisions using Collision Based Attack (CBA) from the literature [START_REF] Fouque | The doubling attack -why upwards is better than downwards[END_REF], [START_REF] Yen | Power analysis by exploiting chosen message and internal collisionsvulnerability of checking mechanism for rsa-decryption[END_REF], [START_REF] Yen | Relative doubling attack against montgomery ladder[END_REF], [START_REF] Homma | Comparative power analysis of modular exponentiation algorithms[END_REF], [START_REF] Homma | Collision-based power analysis of modular exponentiation using chosen-message pairs[END_REF], [START_REF] Sung-Ming | Modified doubling attack by exploiting chosen ciphertext of small order[END_REF]. Even if the result presented in the paper are focusing on modular exponentiation [START_REF] Fouque | The doubling attack -why upwards is better than downwards[END_REF], [START_REF] Yen | Power analysis by exploiting chosen message and internal collisionsvulnerability of checking mechanism for rsa-decryption[END_REF] our criteria is also effective on Symmetric Cryptosystems. In addition some pre-processing techniques has been investigated (Filtering and Compression) with both a theoretical and a practical statement showing concrete elements. The presented methodology based on both the new criterion coupled with a k-means processing shown as demonstrated, determinant practical way to exploit collisions.

8 : return C Algorithm 2 1 : C = 1 2 : B = M 3 :

 82123 RIGHT-TO-LEFT BINARY METHOD Require: M, d = (d k-1 , ..., d 1 , d 0 ), d i ∈ {0, 1} ∀ i, n Ensure: C = M d mod n for i = 0 to k -

Fig. 3 :

 3 Fig. 3: Measured power traces on a product before and after application of alignment technique

Algorithm 3

 3 Collision detection method for Opposite Attack Require: T i 1 : the (i) th pattern of M , T i 2 : the i th pattern of -M mod n, l:Number of operations Ensure: Sequence of Modular Operations S = [S 1 , • • • , S l ] 1: for i = 1 to l do 2:

  do

7 :Algorithm 4

 74 if (R i == N ) and (S i-1 == Square) then Collision detection method for Doubling Attack Require:T (i+1) 1 : the (i+1) th pattern of M , T i 2 : the i th pattern of M 2 mod n, l:Number of operations Ensure: Sequence of Modular Operations S = [S 1 , • • • , S l ]1: for i = 1 to l -1 do 2:

  do

7 :

 7 if (R i-1 == N ) and (S i-1 == Square) then

Fig. 4 :

 4 Fig. 4: Power Analysis materials

Fig. 5 :Fig. 6 :

 56 Fig. 5: Absolute value of the DoT obtained when applying the CBA on the third byte of the exponent

Fig. 7 :Fig. 8 :

 78 Fig. 7: Absolute value of the DoT obtained when applying the CBA on the third byte of the exponent after LNR filtering of traces

Fig. 9 :

 9 Fig. 9: Results obtained by combining the proposed detection technique (BCDC and k-means) and of compression (c = 100)

TABLE I :

 I Success Rate using the detection technique with the P CDC and BCDC on traces collected with a sampling rate equal to 2.5 GS/s

	Sampling Rate		500 MS/s
	Method	Doubling Attack	Opposite Attack
		PCDC BCDC	PCDC BCDC
	No Trace pre-processing	87%	99%	75%	97%
	c = 10	92%	100%	90%	100%
	c = 20	90%	100%	90%	100%
	c = 50	74%	100%	71%	100%
	c = 100	68%	96%	68%	85%
	c = 200	67%	74%	61%	70%
	LNR	82%	100%	80%	100%

TABLE II :

 II Success Rate using the detection technique with the P CDC and BCDC on traces collected with a sampling rate equal to 500 MS/s

(a) Measured power traces on a product before application of any alignment technique (b) Measured power traces on a product after application of the POC