Bertha Mayela

Toledo Acosta

Patrick Bouthemy

Charles Kervrann

A COMMON IMAGE REPRESENTATION AND A PATCH-BASED SEARCH FOR CORRELATIVE LIGHT-ELECTRON-MICROSCOPY (CLEM) REGISTRATION

Keywords: CLEM, LoG transform, histogram distance, patch search, image registration

Correlative light-electron microscopy (CLEM) enables to relate dynamics (or functions) with structure for a better understanding of cell mechanisms. However, the LM and EM images are of very different size, spatial resolution, field of view, and appearance. Registration of LM and EM modalities is then a timely, important but difficult open problem, which still requires some manual assistance. We have designed an original automated CLEM retracing-and-registration method involving a common representation with an adaptive associated scale (or blurring), the determination of the EM patch geometry, and the specification of appropriate descriptors and similarity criterion for the EM patch search. Its efficiency is demonstrated on real CLEM images.

Introduction

Light microscopy (LM) and electron microscopy (EM) are two fundamental investigation tools in cell biology. LM imaging allows the visualization of live cellular and subcellular behaviours but at relatively low spatial resolution. Different probes, dyes, fluorescent labels can be used to make the elements of interest visible. Phase-contrast LM images can also be used. In contrast, EM imaging enables the examination of the whole cellular ultrastructure at very high spatial resolution, but at the cost of fixating or freezing the cell. Correlative light-electron microscopy (CLEM) is then of key interest to combine the respective complementary strengths of LM and EM. However, managing to do it is not that straightforward. In recent years, research has been active in biology and microscopy to design efficient setups and protocols to achieve consecutive LM and EM acquisitions of the same sample [START_REF] Boer | Correlated light and electron microscopy: Ultastructure lights up![END_REF][START_REF] Giepmans | Bridging fluorescence microscopy and electron microscopy[END_REF][START_REF] Heiligenstein | The CryoCapsule: Simplifying correlative light to electron microscopy[END_REF][START_REF] Perkovic | Correlative light-and electron microscopy with chemical tags[END_REF][START_REF] Sartori | Correlative microscopy: bridging the gap between fluorescence light microscopy and cryo-electron tomography[END_REF][START_REF] Spiegelhalter | Correlative light and electron microscopy: from live cell dynamic to 3D ultrastructure[END_REF].

Broadly speaking, the usual workflow is to first acquire a LM image sequence of the living cell, to detect and locate the event of interest, then to chemically fixate or to freeze the sample and to acquire the EM image. Several variants *This work has been partly supported by the National Council of Science and Technology of Mexico (CONACYT) under the thesis grant no. 246372/384571. exist depending on the specific LM and EM modalities, the sample preparation (used probes), the image dimensions (2D or 3D), the overall setup to link up LM and EM acquisitions. The overall goal of CLEM is to relate dynamics (or functions) with structure for a better understanding of cell mechanisms.

Registering LM and EM images is then a key issue, but stands as a very difficult problem due to the big differences in spatial resolution, field of view and appearance. It usually requires manual interventions and the use of artificial landmarks (fiducial markers as beads, marker grids) at different stages of the overall CLEM workflow. The foreseen generalization of CLEM setups and the increasing mass of produced data impel to develop more automated workflows [START_REF] Hodgson | Retracing in correlative light electron microscopy: where is my object of interest?[END_REF].

In this paper, we present an original automated approach to search for the EM patch corresponding to the LM region of interest (ROI) and to register them. It involves a common representation for the LM and EM images with an adaptive associated scale (or blurring), the determination of the EM patch geometry, and appropriate descriptors and similarity criterion for the EM patch search. The paper is organized as follows. Section 2 is devoted to related work. We describe our CLEM registration method in Section 3. In Section 4, we report experimental results on two sets of real CLEM images, and we give concluding comments in Section 5.

Related Work

A CLEM experiment involves among others two important issues: guidance of EM image acquisition from the LM image, and registration of LM and EM images [START_REF] Boer | Correlated light and electron microscopy: Ultastructure lights up![END_REF]. Here, we are dealing with the second stage. The first stage aims at defining where the EM acquisition should be performed in the sample. The second stage can be further subdivided in the matching (or pairing, or retracing) step and the registration computation to overlay both images. Usually, manual interventions occur in these two stages, with the help of grids marked on the sample holder or the coverslip, and fiducial markers added in the sample.

The signals of fluospheres in the LM image are identified and manually assigned to the corresponding points in the averaged EM images in [START_REF] Kukulski | Precise, correlated fluorescence microscopy and electron tomography of lowicryl sections using fluorescent fiducial markers[END_REF]. The coordinates of the pairs are then used as landmarks for generating linear conformal transformations relating the LM image with the EM image. In [START_REF] Sartori | Correlative microscopy: bridging the gap between fluorescence light microscopy and cryo-electron tomography[END_REF], EM images are relocated in LM images using two procedures. Larger structures are retrieved manually by a visual comparison of the LM scan with the overview scan of EM. For smaller structures, three reference points are chosen, and with a coordinate transformation the marked positions on the LM scan can be retrieved in the EM map. A similar approach was adopted in [START_REF] Handschuh | A correlative approach for combining microCT, light and transmission electron microscopy in a single 3D scenario[END_REF].

Very few investigations have been undertaken so far from an image processing perspective to make the registration more automatic. In [START_REF] Perkovic | Correlative light-and electron microscopy with chemical tags[END_REF], the image superposition is achieved by exploiting the auto-fluorescence which exhibits strong enough contours. Following a template-based approach, affine transformations are then applied until the one supplying the highest cross-correlation score is found, first with an EM image at low magnification, then for progressively higher magnifications. In [START_REF] Nam | Feature-based registration for correlative light and electron microscopy images[END_REF], a method for feature-based registration is described, which exploits cell centroids and possibly nucleus. Yet, the registration accuracy heavily depends on the presence of sufficiently salient structures and their correct segmentation. A very different approach is proposed in [START_REF] Cao | Multi-modal registration for correlative microscopy using image analogies[END_REF]. It aims at transforming the two-modality issue into a single modality image registration problem. They introduce the so-called paradigm of image analogies and exploit a sparse representation model to obtain these image analogies. Convincing results are reported but this scheme requires a prior supervised learning stage which is not always affordable.

Automated CLEM Registration

We propose a novel method to achieve automatic pairing and registration between LM and EM images. It is able to manage significant differences in appearance, field of view, spatial resolution and content scale between both modalities. The overall workflow is divided into three main steps: 1) Common LoG representation for 2D EM and LM images with scale adaptation; 2) Fixing the EM patch geometry and seeking LM-ROI in EM; 3) Registering LM and EM patches and overlaying EM image onto LM image around ROI.

Common LOG representation for EM and LM

The idea is to find a transformation of both 2D LM and EM images which produces images of closer appearance. The Laplacian of Gaussian (LoG) transform is a good candidate, since it suppresses local linear intensity variations and enhances high spatial frequencies, while being linear, simple to apply, producing scalar values and enabling scale adaptation. The LoG transform of an image I can be written as follows:

L σ (I) = ∆(G σ * I). (1)
To compute the LoG of LM and EM images and select the right scales s LM and s EM given by the Gaussian variance σ 2 , we use the first stage of our spot detection method ATLAS [START_REF] Basset | Adaptive spot detection with optimal scale selection in fluorescence microscopy images[END_REF]. ATLAS automatically detects the characteristic scale of the objects of interest, by exploiting the Lindeberg's scale-space approach. The selected scale σ 2 is the one with the maximum number of blobs, a blob being defined as a local minimum in the constructed scale-space domain. The ability of fixing σ 2 values adapted to the LM and EM content respectively, will allow us to mitigate the difference in content scale of LM and EM images. The selected scale is expected to be higher for the EM image, yielding a stronger blurring of the EM image.

To match the LoG-LM ROI with the right patch in the LoG-EM image, we need first to delineate the ROI in the LoG-LM image. This ROI is supposed to encompass the dynamic event of interest, only observable through LM. In a given application, such an event could be automatically detected in the LM image sequence, using an appropiate method. Here, we assume that the ROI is already available.

Retracing LoG-LM-ROI in LoG-EM

To automatically retrace the LoG-LM-ROI in the LoG-EM image, we carry out a patch-based exhaustive search. There is a considerable transformation (combination of rotation, shift, magnification,...) between LM and EM images. Hence, we resort to histograms that are invariant to rotation and scale. We implement two histogram-based methods to measure the similarity between a patch in the LoG-EM image and the LoG-LM-ROI. The first one involves LoG-value histograms and the second one exploits Local Directional Pattern (LDP) [START_REF] Jabid | Facial expression recognition using Local Directional Pattern (LDP)[END_REF]. We tested several histogram distances to measure the similarity between LoG-LM-ROI and LoG-EM patch: KL-divergence, Jeffrey-divergence, cosine similarity, histogram intersection, χ 2 distance, Bhattacharyya distance and Kolmogorov-Smirnov distance [START_REF] Cha | Comprehensive survey on distance/similarity measures between probability density functions[END_REF]. The best resuts were obtained with the cosine similarity and the histogram intersection, respectively defined by:

d cos (H LM , H EM ) = ∑ V ν=1 H LM (ν)H EM (ν) ∑ V ν=1 H 2 LM (ν) ∑ V ν=1 H 2 EM (ν) , d hi (H LM , H EM ) = V ∑ ν=1 min(H LM (ν), H EM (ν)), (2)
where H LM , resp. H EM , is the histogram computed over the LoG-LM ROI, resp. on the LoG-EM patch, ν denotes the histogram bin and V the total number of bins. Histogram values are normalized over [0, 1]. Histograms of LoG values can be computed as explained above. A more elaborate descriptor may be necessary to capture more information. LDP is a local descriptor, used primarily for recognizing human faces [START_REF] Jabid | Facial expression recognition using Local Directional Pattern (LDP)[END_REF]. It creates a pattern from an eight-bit binary code at each pixel of the input image I. Using Kirsch masks, the code is calculated by comparing the edge response values of a pixel in eight different orientations. The pattern records only the k most significant directions (with the cooresponding bits) and the rest of the bits are set to 0. With k=3, the LDP may generate up to 56 distinct patterns, creating an encoded image D I . We apply this operation to the LoG-LM ROI and the LoG-EM patch, producing encoded subimages, respectively denoted D LM and D EM , and histograms of these values are computed. We use the same histogram distances as in [START_REF] Boer | Correlated light and electron microscopy: Ultastructure lights up![END_REF].

Since no a priori information is available on the possible location of the ROI in the EM image and the transformation of the ROI location between EM and LM can be considerable, there is no immediate way to reduce the search space. We implement a patch-based exhaustive search to explore all potential locations in the LoG EM image. To specify the patch to be searched in the LoG EM image, we start from the rectangular shape of the LM-ROI of length l and width w. Then, we take into account the (known) ratio r between the pixel sizes of the EM and LM images. More specifically, we conduct two searches with two orientations of LoG EM patches (i.e., with a very coarse quantization of the rotation angle at this stage, but easy to implement): horizontal rectangle of dimensions rl × rw and vertical rectangle of dimensions rw × rl (i.e., after a π/2 rotation). The selected patch will be the optimal one over the two searches.

Registration of LM-EM patches

The final selection of the LoG EM patch most similar to the LoG-LM-ROI also acts as a "pre-registration" step. Indeed, it provides with a combination of shift given by the difference in location of the LM-ROI and the selected LoG EM patch, magnification corresponding to the ratio between the EM patch size and the LM-ROI one, and possibly a π/2 rotation if the type (vertical/horizontal) of the selected LoG EM patch is different than the ROI one. After decimating the LoG EM patch and warping it onto the LoG LM-ROI with this combined transformation, we further estimate a 2D affine motion model to refine the registration between the LoG EM patch and the LoG LM-ROI. Since the residual affine motion is likely to be small, we employ the Motion2D software1 , implementing the robust gradient-based method described in [START_REF] Odobez | Robust multiresolution estimation of parametric motion models[END_REF]. Then, using the estimated transformation, we overlay the whole EM image onto the LM image around the ROI area.

Experimental Results

We tested our method on two sets of LM and EM images acquired at Institut Curie2 . The LM image stacks (we will process a 2D projection) are acquired with epifluorescence Nikon Te2000, in five different channels, including transmitted illumination. We use the latter since it contains the most exploitable information to correlate with the EM image content. The section was then post-stained with Lead Citrate and imaged by a Tecnai Spirit FEI transmission electron microscopy (TEM) [START_REF] Heiligenstein | The CryoCapsule: Simplifying correlative light to electron microscopy[END_REF]. In the first experiment, the studied cell elements are melanosomes, which are dark, dense biological material stored in round bags, visible both in transmitted light and EM. The LM image depicts several cells while the EM image is focused on the cell of interest. In the second experiment, the subcellular elements of interest are endosomes. The LM image contains several cells. The image pairs are displayed in Fig. 1. We have framed the LM-ROI in blue and the ground-truth EM patch in red, both being defined by a biologist. The difference between LM and EM image contents is remarkable, both in appareance and size. As explained above, using ATLAS we get the appropriate scale for the LoG transform of the EM and LM images. For the first experiment, they are respectively estimated as s EM = 8.91 and s LM = 2.48. For the second one, s EM = 6.19 and s LM = 1.44. The LoG representation of the EM and LM images are shown in Fig. 2. As it can be observed, the appearance difference between the EM and LM images is significantly reduced. All the image contents will be better appreciated by zooming in the figures in the pdf file.

The first experiment involves a 512 × 383 LM image and a 4056 × 3970 EM image. Here, we designed the EM patch shape by hand. In the retracing stage, we exploit the LoGvalue histograms and the cosine distance. Similar results were obtained with the histogram intersection. We first tested EM patch locations at intervals of 2.3% of the x-dimension and 3.6% of the y-dimension (with 95% overlap). Then, we refined the search around the primarily selected location. By comparing Fig. 1b and2b, we can visually state that the EM patch location was correctly retrieved. The distance between the center of the ground-truth patch and the finally selected one is 66 pixels (i.e., 1.18% of the image diagonal).

The second experiment involves a 1392 × 1040 LM im-age and a 4008 × 2664 EM image, and the whole pipeline is fully automated. We used the LDP histograms, since the image content is less salient. We report results obtained with the histogram intersection. As the LM pixel size is 110 nm 2 , while the EM one is 11.3 nm 2 , we set r = 9.7 to define the EM patch dimensions. We proceed with a first exhaustive search using intervals of 1.7% of the x-dimension and of 5.1% of the y-dimension (with 90% overlap), followed again by a search refinement. A quite satisfactory retracing is obtained, as visually assessed by comparing Fig. 1d and2d. The selected EM patch is vertical as expected. The distance between the ground-truth patch center and the finally selected one is 17 pixels (0.35% of the image diagonal). The output of the search stage can be used to initialize the registration stage, where we estimate an affine motion model which accounts for both shift, rotation, scale and stretching. The estimated affine parameters are used to map the whole EM image (after decimation) over the LM image around the ROI area, and we come up with a rather accurate overlay as illustrated in Fig. 3. The accuracy can be appreciated (using magnification in the pdf file) through the close alignment between corresponding EM and LM dots.

Conclusion

We have defined a fully automated method for the retracing and registration stages in the CLEM framework, which is a very challenging task due the great differences in appearance, size and field of view between LM and EM images. To make matching manageable, we introduced a common representation supplied by the LoG transform. To be invariant to size, scaling and rotation, we adopted normalized histograms of LoG values or LDP values, in the retracing step. We reported convincing results on two real CLEM image sets. It yields a first validation of this novel approach. Future work will address the setting of a more comprehensive evaluation and a further improvement of the registration stage.

Fig. 1 :

 1 Fig. 1: Input LM and EM images for experiment 1 (top) and experiment 2 (bottom) with ROI and ground-truth EM patch.

  (a) LoG-LM1 and ROI (b) LoG-EM1 and patch. (c) LoG-LM2 and ROI (d) LoG-EM2 and patch.

Fig. 2 :

 2 Fig. 2: LoG transform of LM and EM images with the LM-ROI in blue and the selected EM patch framed in green, experiment 1 (top row) and experiment 2 (bottom row).

Fig. 3 :

 3 Fig. 3: Overlay of the whole (decimated and colorized) EM image onto the LM image for exp.1 (left), and exp.2 (right).

http://www.irisa.fr/vista/Motion2D/

We thank X. Heiligenstein and P. Paul-Gilloteaux from UMR 144, Institut Curie, Paris, for providing us the images and the associated explanations.


François Brunault

REGULATORS OF SIEGEL UNITS AND APPLICATIONS by

Keywords: 2000 Mathematics Subject Classification. -Primary : 19F27; Secondary 11F03, 11F11, 11F67, 11G16 Regulators, Modular units, Elliptic curves, L-functions, Mahler measures, Boyd's conjectures, Zagier's conjectures

We present a formula for the regulator of two arbitrary Siegel units in terms of L-values of pairwise products of Eisenstein series of weight one. We give applications to Boyd's conjectures and Zagier's conjectures for elliptic curves of conductors 14, 21, 35, 48 and 54.

Introduction

In a recent work [START_REF] Zudilin | Regulator of modular units and Mahler measures[END_REF], W. Zudilin proved a formula for the regulator of two modular units. The aim of this article is to generalize this result to arbitrary Siegel units and give applications to elliptic curves.

For any two holomorphic functions f and g on a Riemann surface, define the real 1-form η(f, g) = log f d arg glog g d arg f.

Note that if f and g are two holomorphic functions which do not vanish on the upper half-plane H, then η(f, g) is a well-defined 1-form on H. We prove the following theorem.

Theorem 1. -Let N ≥ 1 be an integer. Let u = (a, b) and v = (c, d) be two nonzero vectors in (Z N Z) 2 , and let g u and g v be the Siegel units associated to u and v (see Section 2 for the definition). We have q mnm,n≥1 m≡-a, n≡-b(N ) q mn (q = e 2πiτ ) with

α 0 (a, b) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0 if a = b = 0 1 2 -{ b N } if a = 0 and b ≠ 0 1 2 -{ a N } if a ≠ 0 and b = 0 0 if a ≠ 0 and b ≠ 0.
Here Λ * (f, 0) denotes the regularized value of the completed L-function Λ(f, s) at s = 0 (see Section 3 for the definition).

Remark 2. -Let Y (N ) be the affine modular curve of level N over Q, and let X(N ) be the smooth compactification of Y (N ). The homology group H = H 1 (X(N )(C), {cusps}, Z) is generated by the modular symbols ξ(γ) = {γ0, γ∞} with γ ∈ GL 2 (Z N Z). If c is an element of H, we may write c = ∑ i λ i ξ(γ i ), and it follows that

c η(g u , g v ) = i λ i ∞ 0 η(g uγ i , g vγ i ).
Moreover, the Siegel units generate (up to constants) the group O(Y (N )) × ⊗ Q. Therefore Theorem 1 (together with Lemma 5) gives a formula for all possible regulator integrals ∫ c η(u, v) with c ∈ H and u, v ∈ O(Y (N )) × .

Remark 3. -Theorem 1 is a generalization of [21, Thm 1]. More precisely, let ga , a ∈ Z N Z denote the modular units arising in [START_REF] Zudilin | Regulator of modular units and Mahler measures[END_REF]. Then for every c ∈ Z N Z, we have ga (c N + it) = g a,ac (iN t) (t > 0).

We recover [ It would be interesting to study further the properties of these modular forms and to understand their possible relations with the toric modular forms introduced by L. Borisov and P. Gunnells [START_REF] Borisov | Toric modular forms and nonvanishing of L-functions[END_REF].

The proof of Theorem 1 follows the strategy of [START_REF] Zudilin | Regulator of modular units and Mahler measures[END_REF]. We express the logarithms of Siegel units as a double infinite sum (Lemma 16) and deduce an expression for the regulator as a quadruple sum. We then perform the same analytical change of variables from [START_REF] Rogers | From L-series of elliptic curves to Mahler measures[END_REF], leading to the Mellin transform of a product of Eisenstein series. The key lemma to do this (Lemma 8) suggests that similar results should hold in higher weight.

We point out that the simple shape of the Eisenstein series e a,b makes Theorem 1 particularly amenable to explicit computations. We give some applications of Theorem 1 in Section 6, for elliptic curves which are parametrized by modular units [START_REF]Parametrizing elliptic curves by modular units[END_REF].

I would like to thank Wadim Zudilin for helpful exchanges related to this work. This work is partly supported by the research grant ANR Régulateurs (Grant Number ANR-12-BS01-0002).

Siegel units

We recall some basic definitions and results about Siegel units, for which we refer the reader to [9, §1] and [START_REF] Kubert | Grundlehren der Mathematischen Wissenschaften[END_REF].

Let B 2 = X 2 -X + 1 6 be the second Bernoulli polynomial. For x ∈ R, we define B(x) = B 2 ({x}) = {x} 2 -{x} + 1 6 , where {x} = x -⌊x⌋ denotes the fractional part of x. Let H be the upper half-plane. Let N ≥ 1 be an integer and

ζ N = e 2πi N . For any (a, b) ∈ (Z N Z) 2 , (a, b) ≠ (0, 0), the Siegel unit g a,b on H is defined by (3) g a,b (τ ) = q B(a N ) 2 n≥0 (1 -q n q ã N ζ b N ) n≥1 (1 -q n q -ã N ζ -b N ) (q = e 2πiτ )
where ã is the representative of a satisfying 0 ≤ ã < N . Here

q α = e 2πiατ for α ∈ Q. It is known that the function g 12N a,b is modular for the group Γ(N ) = {γ ∈ SL 2 (Z) ∶ γ ≡ I 2 (mod N )}.
In fact g a,b defines an element of O(Y (N )) × ⊗ Q, where Y (N ) denotes the affine modular curve of level N over Q. Recall that the group GL 2 (Z N Z) acts on Y (N ) by Q-automorphisms. For any γ ∈ GL 2 (Z N Z), we have the identity in

O(Y (N )) × ⊗ Q (4) g a,b γ = g (a,b)γ . Lemma 4. -Let (a, b) ∈ (Z N Z) 2 , (a, b) ≠ (0, 0). We have (5) g a,b (-1 τ ) = e -2πi({ a N }-1 2 )({ b N }-1 2 ) g b,-a (τ ) (τ ∈ H).
Proof.

-By taking the matrix γ = 0 -1 1 0 in (4), we see that g

∞ 0 d arg g a,b = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 0 if a = 0 or b = 0 2π({ a N } -1 2 )({ b N } -1 2 ) if a ≠ 0 and b ≠ 0. Proof. -If a = 0 or b = 0 then g a,b has constant argument on the imaginary axis τ = it, t > 0, hence ∫ ∞ 0 d arg g a,b = 0. If a ≠ 0 and b ≠ 0, it is easily seen that arg g a,b (it) t→∞ → 0. Moreover, by Lemma 4, we have arg g a,b (it) t→0 → -2π({ a N } -1 2 )({ b N } -1 2 ) (mod 2π (6)
). This proves (6) up to a multiple of 2π. In order to establish the exact equality, let us introduce the Klein forms [10, Chap. 2, §1, p. 27]:

k α,β (τ ) = e -1 2 η(ατ +β,τ )(ατ +β) σ(ατ + β, τ ) (α, β ∈ R; τ ∈ H)
where η and σ denote the Weierstrass functions. The link with Siegel units is given by

g a,b (τ ) = wk a N,b N (τ )∆(τ ) 1 12 (1 ≤ a, b ≤ N -1)
where w is a root of unity [10, p. 29]. Since ∆ is positive on the imaginary axis, it follows that

∞ 0 d arg g a,b = ∞ 0 d arg k a N,b N .
Using the q-product formula for the σ function [START_REF] Lang | Elliptic functions[END_REF]Chap. 18, §2] and the Legendre relation

η 2 ω 1 -η 1 ω 2 = 2πi, we find (7) k α,β (it) = 1 2πi e -πα 2 t e πiαβ (e πiβ e -παt -e -πiβ e παt ) n≥1 (1 -e -2π(n+α)t e 2πiβ )(1 -e -2π(n-α)t e -2πiβ ) (1 -e -2πnt ) 2 . Assume 0 < α, β < 1.
Then by [START_REF] Cremona | Algorithms for modular elliptic curves[END_REF], we have arg

k α,β (it) t→∞ → π(αβ -β + 1 2 )
. Moreover, the Klein forms are homogeneous of weight -1 [10, p. 27, K1], which implies

k α,β (-1 τ ) = 1 τ k β,-α (τ ).
From this we get arg k α,β (it)

t→0 → π(-αβ + α) (mod 2π) and ∞ 0 d arg k α,β ≡ 2π(α - 1 2 )(β - 1 2
) (mod 2π).

Moreover, using the fact that

∫ ∞ 0 d arg k α,β = ∫ ∞ i d arg k α,β -∫ ∞ i d arg k β,-α
and taking the imaginary part of the logarithm of (7), we may express ∫ ∞ 0 d arg k α,β as an infinite sum, which shows that it is a continuous function of (α, β) ∈ (0, 1) 2 . But for β = 1 2 , the Klein form

k α, 1 2 (it) has constant argument. This implies that ∫ ∞ 0 d arg k α,β = 2π(α -1 2 )(β - 1
2 ) for any 0 < α, β < 1.

L-functions of modular forms

In this section we recall basic results on the functional equation satisfied by L-functions of modular forms.

Let f (τ ) = ∑ ∞ n=0 a n q n be a modular form of weight k ≥ 1 on the group Γ 1 (N ). The L-function of f is defined by

L(f, s) = ∑ ∞ n=1 a n n -s , R(s) > k. Define the completed L-function Λ(f, s) ∶= N s 2 (2π) -s Γ(s)L(f, s) = N s 2 ∞ 0 (f (iy) -a 0 )y s dy y .
Recall that the Atkin-Lehner involution W N on M k (Γ 1 (N )) is defined by

(W N f )(τ ) = i k N -k 2 τ -k f (-1 (N τ )).
Note that in the case k = 2 this W N is the opposite of the usual involution acting on differential 1-forms. The following theorem is classical (see [START_REF] Miyake | Modular forms[END_REF]Thm 4.3.5]).

Theorem 6. -Let f = ∑ ∞ n=0 a n q n ∈ M k (Γ 1 (N )).
The function Λ(f, s) can be analytically continued to the whole s-plane, and satisfies the functional equation

Λ(f, s) = Λ(W N f, k -s). Moreover, write W N f = ∑ ∞ n=0 b n q n . Then the function Λ(f, s) + a 0 s + b 0 k -s is holomorphic on the whole s-plane. Definition 7.
-The notations being as in Theorem 6, we define the regularized values of Λ(f, s) at s = 0 and s = k by

Λ * (f, 0) ∶= lim s→0 Λ(f, s) + a 0 s (8) Λ * (f, k) ∶= lim s→k Λ(f, s) + b 0 k -s . ( 9
)
Note that the functional equation translates into the equalities of regularized values

(10) Λ * (f, 0) = Λ * (W N f, k) Λ * (f, k) = Λ * (W N f, 0).
We will need the following lemma.

Lemma 8. -Let f = ∑ ∞ n=0 a n q n ∈ M k (Γ 1 (N )) and g = ∑ ∞ n=0 b n q n ∈ M (Γ 1 (N )) with k, ≥ 1. Let h = W N (g). Write f * = f -a 0 and g * = g -b 0 . Then for any s ∈ C, we have (11) N s 2 ∞ 0 f * (iy)g * i N y y s dy y = Λ(f h, s + ) -a 0 Λ(h, s + ) -b 0 Λ(f, s).
Proof. -Note that the integral in [START_REF] Lang | Elliptic functions[END_REF] is absolutely convergent because f * (τ ) and g * (τ ) have exponential decay when I(τ ) tends to +∞. Moreover, it is easy to check, using Theorem 6, that the right hand side of ( 11) is holomorphic on the whole s-plane. Therefore it suffices to establish (11) when R(s) > k. Since W N g = h, we have

N s 2 ∞ 0 f * (iy)g * i N y y s dy y = N s 2 ∞ 0 f * (iy) g i N y -b 0 y s dy y = N s 2 ∞ 0 f * (iy)(N 2 y h(iy) -b 0 )y s dy y . Now, we remark that f * h = f h -a 0 h = (f h) * -a 0 h * . Thus N s 2 ∞ 0 f * (iy)g * i N y y s dy y = N s 2 ∞ 0 N 2 y ((f h) * (iy) -a 0 h * (iy)) -b 0 f * (iy) y s dy y = Λ(f h, s + ) -a 0 Λ(h, s + ) -b 0 Λ(f, s).
Specializing Lemma 8 to the (regularized) value at s = k, we get the following formula.

Lemma 9. -Let f = ∑ ∞ n=0 a n q n ∈ M k (Γ 1 (N )) and g = ∑ ∞ n=0 b n q n ∈ M (Γ 1 (N )) with k, ≥ 1. Let h = W N (g). Write f * = f -a 0 and g * = g -b 0 . Then we have (12) N k 2 ∞ 0 f * (iy)g * i N y y k dy y = Λ * (f h, k + ) -a 0 Λ(h, k + ) -b 0 Λ * (f, k).

Eisenstein series of weight 1

In this section we define some Eisenstein series of weight 1. These are the same as those arising in [START_REF] Zudilin | Regulator of modular units and Mahler measures[END_REF]. (a,b) is an Eisenstein series of weight 1 on the group Γ(N ). We have

Definition 10. -For any a, b ∈ Z N Z, we let (13) e a,b = α 0 (a, b) + m,n≥1 m≡a, n≡b(N ) q mn - m,n≥1 m≡-a, n≡-b(N ) q mn where α 0 (a, b) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0 if a = b = 0 1 2 -{ b N } if a = 0 and b ≠ 0 1 2 -{ a N } if a ≠ 0 and b = 0 0 if a ≠ 0 and b ≠ 0.
G 1,(a,b) (τ ) = - 2πi N γ 0 (a, b) + m,n≥1 n≡a(N ) ζ bm N q mn N - m,n≥1 n≡-a(N ) ζ -bm N q mn N where γ 0 (a, b) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0 if a = b = 0 1 2 1+ζ b N 1-ζ b N if a = 0 and b ≠ 0 1 2 -{ a N } if a ≠ 0. The function G 1,
e a,b τ N = α 0 (a, b) + m,n≥1 m≡a, n≡b(N ) q mn N - m,n≥1 m≡-a, n≡-b(N ) q mn N = α 0 (a, b) + 1 N N -1 c=0 ζ ca N ⎛ ⎝ m,n≥1 n≡b(N ) ζ -cm N q mn N - m,n≥1 n≡-b(N ) ζ cm N q mn N ⎞ ⎠ = α 0 (a, b) - 1 N N -1 c=0 ζ ca N γ 0 (b, -c) - 1 2πi N -1 c=0 ζ ca N G 1,(b,-c) . If b ≠ 0 then 1 N N -1 c=0 ζ ca N γ 0 (b, -c) = 1 N N -1 c=0 ζ ca N 1 2 -{ b N } = α 0 (a, b), hence e a,b (τ N ) is an Eisenstein series of weight 1 on Γ(N ). If a ≠ 0 then the same is true because e a,b = e b,a . Finally if a = b = 0 then α 0 (a, b) - 1 N N -1 c=0 ζ ca N γ 0 (b, -c) = - 1 N N -1 c=0 γ 0 (0, c) = 0 because γ 0 (0, -c) = -γ 0 (0, c).
The second assertion follows from the fact that

N 0 0 1 Γ 1 (N 2 ) N 0 0 1 -1 ⊂ Γ(N ). Definition 12. -For any a, b ∈ Z N Z, we let (14) f a,b = β 0 (a, b) + m,n≥1 (ζ am+bn N -ζ -am-bn N )q mn where β 0 (a, b) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0 if a = b = 0 1 2 1+ζ b N 1-ζ b N if a = 0 and b ≠ 0 1 2 1+ζ a N 1-ζ a N if a ≠ 0 and b = 0 1 2 1+ζ a N 1-ζ a N + 1+ζ b N 1-ζ b N if a ≠ 0 and b ≠ 0.
As the next lemma shows, the functions f a,b are also Eisenstein series; they relate to e a,b by the Atkin-Lehner involution of level N 2 . Lemma 13. -We have the relation

(15) e a,b - 1 N τ = - τ N f a,b τ N (τ ∈ H).
(16) Λ(f a,b + f -a,b , s) = N s Γ(s)(2π) -s m≥1 ζ am N + ζ -am N m s n≥1 ζ bn N -ζ -bn N n s . Proof. -See the proof of [21, Lemma 3].
In the special cases s = 1 and s = 2, this gives the following formulas. Note that formula (18) is none other than [21, Lemma 3].

Lemma 15. -We have Λ * (f a,b + f -a,b , 1) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0 if b = 0 2iN γ ⋅ ( 1 2 -{ b N }) if a = 0 and b ≠ 0 -2iN log 1 -ζ a N ⋅ ( 1 2 -{ b N }) if a ≠ 0 and b ≠ 0 (17) Λ(f a,b + f -a,b , 2) = iN 2 B a N Cl 2 2πb N ( 18
)
where γ is Euler's constant and

Cl 2 (x) = ∞ m=1 sin(mx) m 2 (x ∈ R)
denotes the Clausen dilogarithmic function.

Proof.

-If a = 0 then ∑ ∞ n=1 ζ an N n -s = ζ(s) = 1 s-1 + γ + O s→1 (s -1). If a ≠ 0 then ∑ ∞ n=1 ζ an N n = -log(1 -ζ a N )
where we use the principal value of the logarithm. Formula ( 17) follows, noting thatlog 18) is [21, Lemma 3].

1-ζ b N 1-ζ -b N = 2πi( 1 2 -{ b N }). Formula (

The computation

Lemma 16. -For any (a, b) ∈ (Z N Z) 2 , (a, b) ≠ (0, 0), we have log g a,b (it) = -πB(a N )t + C a,b - m≥1 n≥1 n≡a(N ) ζ bm N m e -2πmnt N - m≥1 n≥1 n≡-a(N ) ζ -bm N m e -2πmnt N (19) = - πB(b N ) t + C b,-a + iθ a,b - m≥1 n≥1 n≡b(N ) ζ -am N m e -2πmn N t - m≥1 n≥1 n≡-b(N ) ζ am N m e -2πmn N t ( 20
)
where

θ a,b = 2π({ a N } -1 2 )({ b N } -1 2 ) and (21) C a,b = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ log(1 -ζ b N ) if a = 0, 0 if a ≠ 0.
Proof. -By the definition of Siegel units, we have

log g a,b = πiB(a N )τ + n≥0 log(1 -q n q ã N ζ b N ) + n≥1 log(1 -q n q -ã N ζ -b N )
Using the identity log(1

-x) = -∑ ∞ m=1
x m m and substituting τ = it, we get [START_REF] Vélu | Isogénies entre courbes elliptiques[END_REF]. Applying Lemma 4 with τ = i t, we have g a,b (it) = e iθ a,b g b,-a (i t), whence [START_REF] Villegas | Modular Mahler measures. I[END_REF].

We will need the following lemma from [START_REF] Zudilin | Regulator of modular units and Mahler measures[END_REF].

Lemma 17. -(See [21, Lemma 4].) For any a, b ∈ Z N Z, we have I(a, b) ∶= ∞ 0 1 it d ∞ m=1 ζ am N -ζ -am N m ⎛ ⎝ n≥1 n≡b(N ) - n≥1 n≡-b(N ) ⎞ ⎠ exp - 2πmn N t = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 0 if a = 0 or b = 0 -i Cl 2 ( 2πa N ) 1+ζ b N 1-ζ b N if a ≠ 0 and b ≠ 0. ( 22
)
Proof of Theorem 1. -By Lemma 16, we get

(23) log g u (it) = - πB(b N ) t + R(C b,-a ) - 1 2 m≥1 ζ am N + ζ -am N m ⎛ ⎝ n≥1 n≡b(N ) + n≥1 n≡-b(N ) ⎞ ⎠ e -2πmn N t and d arg g u (it) = - 1 2i d m≥1 ζ bm N -ζ -bm N m ⎛ ⎝ n≥1 n≡a(N ) - n≥1 n≡-a(N ) ⎞ ⎠ e -2πmnt N (24) = 1 2i d m≥1 ζ am N -ζ -am N m ⎛ ⎝ n≥1 n≡b(N ) - n≥1 n≡-b(N ) ⎞ ⎠ e -2πmn N t . (25) Let u = (a, b), v = (c, d) ∈ (Z N Z) 2 , u, v ≠ (0, 0). We have η(g u , g v ) = - πB(b N ) t + R(C b,-a ) ⋅ 1 2i d m≥1 ζ cm N -ζ -cm N m ⎛ ⎝ n≥1 n≡d(N ) - n≥1 n≡-d(N ) ⎞ ⎠ e -2πmn N t - 1 2 m 1 ≥1 ζ am 1 N + ζ -am 1 N m 1 ⎛ ⎝ n 1 ≥1 n 1 ≡b(N ) + n 1 ≥1 n 1 ≡-b(N ) ⎞ ⎠ e -2πm 1 n 1 N t × - 1 2i d m 2 ≥1 ζ dm 2 N -ζ -dm 2 N m 2 ⎛ ⎝ n 2 ≥1 n 2 ≡c(N )
-

n 2 ≥1 n 2 ≡-c(N ) ⎞ ⎠ e -2πm 2 n 2 t N -- πB(d N ) t + R(C d,-c ) ⋅ 1 2i d m≥1 ζ am N -ζ -am N m ⎛ ⎝ n≥1 n≡b(N ) - n≥1 n≡-b(N ) ⎞ ⎠ e -2πmn N t + 1 2 m 1 ≥1 ζ cm 1 N + ζ -cm 1 N m 1 ⎛ ⎝ n 1 ≥1 n 1 ≡d(N ) + n 1 ≥1 n 1 ≡-d(N ) ⎞ ⎠ e -2πm 1 n 1 N t × - 1 2i d m 2 ≥1 ζ bm 2 N -ζ -bm 2 N m 2 ⎛ ⎝ n 2 ≥1 n 2 ≡a(N )
-

n 2 ≥1 n 2 ≡-a(N ) ⎞ ⎠ e -2πm 2 n 2 t N . ( 26
)
The terms involving double sums can be integrated using Lemmas 5 and 17. This gives

∞ 0 η(g u , g v ) = - π 2 B b N I(c, d) + π 2 B d N I(a, b) + R(C b,-a ) ∞ 0 d arg g v -R(C d,-c ) ∞ 0 d arg g u + I (27)
with

I = πi 2N m 1 ,m 2 ≥1 ⎛ ⎝ (ζ am 1 N + ζ -am 1 N )(ζ dm 2 N -ζ -dm 2 N ) ⎛ ⎝ n 1 ≥1 n 1 ≡b(N ) + n 1 ≥1 n 1 ≡-b(N ) ⎞ ⎠ ⎛ ⎝ n 2 ≥1 n 2 ≡c(N ) - n 2 ≥1 n 2 ≡-c(N ) ⎞ ⎠ -(ζ cm 1 N + ζ -cm 1 N )(ζ bm 2 N -ζ -bm 2 N ) ⎛ ⎝ n 1 ≥1 n 1 ≡d(N ) + n 1 ≥1 n 1 ≡-d(N ) ⎞ ⎠ ⎛ ⎝ n 2 ≥1 n 2 ≡a(N ) - n 2 ≥1 n 2 ≡-a(N ) ⎞ ⎠ ⎞ ⎠ ⋅ ⋅ n 2 m 1 ∞ 0 exp -2π m 1 n 1 N t + m 2 n 2 t N dt. ( 28
)
Making the change of variables t ′ = n 2 m 1 t, we have

(29) n 2 m 1 ∞ 0 exp -2π m 1 n 1 N t + m 2 n 2 t N dt = ∞ 0 exp -2π n 1 n 2 N t ′ + m 1 m 2 t ′ N dt ′ .
Replacing in (28) and interchanging integral and summation, we get

I = πi 2N ∞ 0 m 1 ,m 2 ≥1 (ζ am 1 N + ζ -am 1 N )(ζ dm 2 N -ζ -dm 2 N )e -2πm 1 m 2 t ′ N ⋅ ⋅ ⎛ ⎝ n 1 ≥1 n 1 ≡b(N ) + n 1 ≥1 n 1 ≡-b(N ) ⎞ ⎠ ⎛ ⎝ n 2 ≥1 n 2 ≡c(N ) - n 2 ≥1 n 2 ≡-c(N ) ⎞ ⎠ e -2πn 1 n 2 N t ′ - m 1 ,m 2 ≥1 (ζ cm 1 N + ζ -cm 1 N )(ζ bm 2 N -ζ -bm 2 N )e -2πm 1 m 2 t ′ N ⋅ ⋅ ⎛ ⎝ n 1 ≥1 n 1 ≡d(N ) + n 1 ≥1 n 1 ≡-d(N ) ⎞ ⎠ ⎛ ⎝ n 2 ≥1 n 2 ≡a(N ) - n 2 ≥1 n 2 ≡-a(N ) ⎞ ⎠ e -2πn 1 n 2 N t ′ dt ′ . (30)
Making the change of variables y = t ′ N , we obtain

I = πi 2 ∞ 0 (f * a,d + f * -a,d )(iy) ⋅ (e * b,c + e * -b,c ) i N 2 y -(f * c,b + f * -c,b )(iy) ⋅ (e * d,a + e * -d,a ) i N 2 y dy. ( 31
)
We compute this integral using Lemma 9 with k = = 1, taking into account Lemma 13: for any a, b, c, d ∈ Z N Z, we have

(32) ∞ 0 f * a,b (iy)e * c,d i N 2 y dy = - i N 2 Λ * (f a,b f c,d , 2) -β 0 (a, b)Λ(f c,d , 2) - α 0 (c, d) N Λ * (f a,b , 1).
Replacing in (31), we get I = I 1 + I 2 + I 3 with

I 1 = π 2N 2 Λ * ((f a,d + f -a,d )(f b,c + f -b,c ) -(f c,b + f -c,b )(f d,a + f -d,a ), 2) (33)
I 2 = - π 2N 2 (β 0 (a, d) + β 0 (-a, d))Λ(f b,c + f -b,c , 2) -(β 0 (c, b) + β 0 (-c, b))Λ(f d,a + f -d,a , 2)
(34)

I 3 = - πi 2N (α 0 (b, c) + α 0 (-b, c))Λ * (f a,d + f -a,d , 1) -(α 0 (d, a) + α 0 (-d, a))Λ * (f c,b + f -c,b , 1) (35)
Using the fact that f a,b = f b,a = -f -a,-b , I 1 simplifies to (36)

I 1 = π N 2 Λ * (f a,d f -b,c -f a,-d f b,c , 2).
The terms involving Λ(f a,b , 2) can be evaluated with [START_REF] Bordeaux | PARI/GP version 2.7.3[END_REF]; they simplify with the terms involving I(a, b) in ( 27):

(37)

I 2 = π 2 B b N I(c, d) - π 2 B d N I(a, b).
The terms involving Λ * (f a,b , 1) can be evaluated with [START_REF] Schoeneberg | Elliptic modular functions: an introduction[END_REF]. Note that α 0 (b, c) + α 0 (-b, c) is nonzero only in the case b = 0 and c ≠ 0. Since we assumed u ≠ 0, this implies a ≠ 0 and the case of Lemma 15 involving Euler's constant does not happen. Anyway I 3 simplifies with the terms involving ∫ ∞ 0 d arg g u in (27):

(38)

I 3 = -R(C b,-a ) ∞ 0 d arg g v + R(C d,-c ) ∞ 0 d arg g u .
Putting everything together, we get (39

) ∞ 0 η(g u , g v ) = I 1 = π N 2 Λ * (f a,d f -b,c -f a,-d f b,c , 2)
. Theorem 1 now follows from [START_REF] Kubert | Grundlehren der Mathematischen Wissenschaften[END_REF], taking into account the fact that

W N 2 (f a,b f c,d ) = W N 2 (f a,b )W N 2 (f c,d ) = -N 2 e a,b e c,d .
Remark 18. -It would be interesting to find a definition of g 0,0 so that Theorem 1 holds for any vectors u, v ∈ (Z N Z) 2 .

Applications

In this section we investigate the applications of Theorem 1 to elliptic curves. Our strategy can be explained as follows. In [START_REF]Parametrizing elliptic curves by modular units[END_REF], we determined a list of elliptic curves defined over Q which can be parametrized by modular units. Let E be such an elliptic curve, with modular parametrization ϕ ∶ X 1 (N ) → E. Let x, y be functions on E such that u ∶= ϕ * (x) and v ∶= ϕ * (y) are modular units. Assume that {x, y} ∈ K 2 (E) ⊗ Q. Then the minimal polynomial P of (x, y) is tempered and in favorable cases, the Mahler measure of P can be expressed in terms of a regulator integral ∫ γ η(x, y) where γ is a (non necessarily closed) path on E. Using the techniques of [START_REF]Parametrizing elliptic curves by modular units[END_REF], we compute the images of the various cusps under ϕ and deduce the divisors of u and v. Since the divisors of Siegel units are easily computed using ( 3) and ( 4), we get an expression of u and v in terms of Siegel units, and may apply Theorem 1.

We will need the following expression for the regulator integral in terms of Bloch's elliptic dilogarithm. Let E Q be an elliptic curve, and let D E ∶ E(C) → R be the elliptic dilogarithm associated to a chosen orientation of E(R). Extend D E by linearity to a function Z[E(C)] → R. Let γ + E be the generator of H 1 (E(C), Z) + corresponding to the chosen orientation. Proposition 19. -Let x ∈ K 2 (E) ⊗ Q. Choose rational functions f i , g i on E such that x = ∑ i {f i , g i }, and define η(x) = ∑ i η(f i , g i ). Then for every γ ∈ H 1 (E(C), Z), we have

γ η(x) = -(γ + E • γ)D E (β)
where • denotes the intersection product on H 1 (E(C), Z), and β is the divisor given by

β = i p,q∈E(C) ord p (f i ) ord q (g i )(p -q).
Proof. -Since x ∈ K 2 (E) ⊗ Q, the integral of η(x) over a closed path γ avoiding the zeros and poles of f i , g i depends only on the class of γ in H 1 (E(C), Z). Let δ be an element of

H 1 (E(C), Z) such that γ + E • δ = 1. Let c denote the complex conjugation on E(C). Since c * η(x) = -η(x), we have ∫ γ + E η(x) = 0
and it suffices to prove the formula for γ = δ. Choose an isomorphism E(C) ≅ C (Z + τ Z) which is compatible with complex conjugation. We have

E(C) η(x) ∧ dz = E(C) η(x) ∧ dz = E(C) c * (-η(x) ∧ dz) = E(C) η(x) ∧ dz so that ∫ E(C) η(x) ∧ dz ∈ R. By [5, Prop. 6], we get E(C) η(x) ∧ dz = D E (β). Since (γ + E , δ) is a symplectic basis of H 1 (E(C), Z), we have [3, A.2.5] E(C) η(x) ∧ dz = γ + E η(x) ⋅ δ dz - γ + E dz ⋅ δ η(x) = - δ η(x).
The following proposition is a slight generalization of a technique introduced by A. Mellit [START_REF] Mellit | Elliptic dilogarithm and parallel lines[END_REF] to prove identities involving elliptic dilogarithms. Let E Q be an elliptic curve, which we view as a smooth cubic in P 2 . Definition 20. -For any lines and m in P 2 , let β E ( , m) be the divisor of degree 9 on E(C) defined by β E ( , m) = ∑ x∈ ∩E ∑ y∈m∩E (x -y).

Proposition 21. -Let 1 , 2 , 3 be three incident lines in P 2 . Then

(40) D E (β E ( 1 , 2 )) + D E (β E ( 2 , 3 )) + D E (β E ( 3 , 1 )) = 0. Proof. -Let f 1 , f 2 , f 3 be equations of 1 , 2 , 3 such that f 1 + f 2 = f 3 . Using the Steinberg relation { f 1 f 3 , f 2 f 3 } = 0, we deduce {f 1 , f 2 } + {f 2 , f 3 } + {f 3 , f 1 } = 0 in K 2 (C(E)) ⊗ Q.
Applying the regulator map and taking the real part [5, Prop. 6], we deduce

D E (β(f 1 , 2 )) + D E (β(f 2 , f 3 )) + D E (β(f 3 , f 1 )) = 0 where β(f i , f i+1 ) is defined as in Proposition 19. We have div(f i ) = ( i ∩ E) -3(0) so that β(f i , f i+1 ) = β E ( i , i+1 ) -3( i ∩ E) -3ι * ( i+1 ∩ E) + 9(0)
where ι denotes the map p ↦ -p on E(C). Since D E is odd, the proposition follows.

Remark 22. -If the incidence point of 1 , 2 , 3 lies on E, then the relation ( 40) is trivial in the sense that it is a consequence of the fact that D E is odd.

We will also need the following lemma to relate elliptic dilogarithms on isogenous curves.

Lemma 23. -Let ϕ ∶ E → E ′ be an isogeny between elliptic curves defined over Q. Choose orientations of E(R) and E ′ (R) which are compatible under ϕ, and let d ϕ be the topological degree of the map E(R) 0 → E ′ (R) 0 , where (⋅) 0 denotes the connected component of the origin. Then for any point P ′ ∈ E ′ (C), we have

(41) D E ′ (P ′ ) = d ϕ ⋅ ϕ(P )=P ′ D E (P ). Proof. -Choose isomorphisms E(C) ≅ C (Z + τ Z) and E ′ (C) ≅ C (Z + τ ′ Z) which are compatible with complex conjugation. Then E(R) 0 = R Z and E ′ (R) 0 = R Z so that ϕ is given by [z] ↦ [d ϕ z]. We have isomorphisms E(C) ≅ C × q Z and E ′ (C) ≅ C × (q ′ ) Z with q = e 2πiτ and q ′ = e 2πiτ ′ . Let π ∶ C × → E(C) and π ′ ∶ C × → E ′ (C) be the canonical maps. Let P ′ be a point of E ′ (C). By definition D E ′ (P ′ ) = ∑ π ′ (x ′ )=P ′ D(x ′ )
where D is the Bloch-Wigner function, and similarly D E (P ) = ∑ π(x)=P D(x). Now ϕ is induced by the map x ↦ x dϕ , so that (41) follows from the usual functional equation D(x r ) = r ∑ u r =1 D(ux) for any r ≥ 1 [15, (21)].

Note that in the particular case ϕ is the multiplication-by-n map on E, Lemma 23 gives the usual functional equation 5, k = -1, -2, -3]. Note that the case of conductor 14 was proved by A. Mellit [START_REF] Mellit | Elliptic dilogarithm and parallel lines[END_REF].

D E (nP ) = n Q∈E[n] D E (P + Q).
Theorem 24. -Let P k be the polynomial P k (x, y) = y 2 +kxy +y -x 3 , and let E k be the elliptic curve defined by the equation P k (x, y) = 0. We have the identities

m(P -1 ) = 2L ′ (E -1 , 0) (42) m(P -2 ) = L ′ (E -2 , 0) (43) m(P -3 ) = L ′ (E -3 , 0). ( 44
)
By the discussion in [4, p. 62], the polynomial P k does not vanish on the torus for k ∈ R, k < -1. For these values of k we thus have

m(P k ) = 1 2π γ k η(x, y)
where γ k is the closed path on E k (C) defined by

γ k = {(x, y) ∈ E k (C) ∶ x = 1, y ≤ 1}.
The point A = (0, 0) on E k has order 3 and the divisors of x and y are given by div

(x) = (A) + (-A) -2(0) div(y) = 3(A) -3(0).
The tame symbols of {x, y} at 0, A, -A are respectively equal to 1, -1, -1, so that {x, y} defines an element of

K 2 (E k ) ⊗ Q. Moreover γ k is a generator of H 1 (E k (C), Z) -which satisfies γ + E k • γ k = -2, so that Proposition 19 gives (45) m(P k ) = 1 π D E k (β(x, y)) = 9 π D E k (A) (k < -1).
Note that by continuity (45) also holds for k = -1. Now assume k ∈ {-1, -2, -3}. The elliptic curves E -1 , E -2 , E -3 are respectively isomorphic to 14a4, 35a3 and 54a3. By [START_REF]Parametrizing elliptic curves by modular units[END_REF], these curves are parametrized by modular units. Since the functions x and y are supported in the rational torsion subgroup, their pull-back u = ϕ * x and v = ϕ * y are modular units, and we may express them in terms of Siegel units. For brevity, we put g b = g 0,b in what follows. We also let f -k be the newform associated to E -k , and we define

ω f -k = 2πif -k (τ )dτ .
In the case k = -1, N = 14, we find explicitly

u = g 5 g 6 g 1 g 2 v = - g 3 g 5 g 2 6 g 2 1 g 2 g 4
.

We now wish to express the Deninger path γ -1 in terms of modular symbols. Using Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] and Pari/GP [START_REF] Bordeaux | PARI/GP version 2.7.3[END_REF], we compute

∫ -2 7 2 7 ω f -1 = -Ω - E -1 , where Ω - E -1 ∈ iR >0
is the imaginary period of E -1 . The Magma and Pari/GP codes to evaluate numerically both sides of this identity are as follows:

// Magma code to evaluate the left hand side E:=EllipticCurve("14a4"); M:=ModularSymbols(E); phi:=PeriodMapping(M,1000); phi(M!<1,[Cusps()|2/7,-2/7]>); \\ Pari/GP code to evaluate the right hand side e=ellinit("14a4"); -(e.omega [START_REF] Borisov | Toric modular forms and nonvanishing of L-functions[END_REF]-2*e.omega [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF])

Thus we get γ -1 = ϕ * 2 7 , - 2 7 = ϕ * -ξ 2 1 7 4 -ξ 1 0 4 1 + ξ 1 0 -4 1 + ξ -2 1 7 -4 .
Using Theorem 1, we obtain

γ -1 η(x, y) = -2 7 2 7 η(u, v) = πL ′ (4f -1 , 0).
This proves (42).

In the case k = -2, N = 35, we find explicitly .

u = g 2 g
Moreover the Deninger path is the following sum of modular symbols

γ -2 = ϕ * 1 5 , - 1 5 = ϕ * ξ 1 0 -5 1 -ξ 1 0 5 1 .
Using Theorem 1, we obtain

γ -2 η(x, y) = -1 5 1 5 η(u, v) = πL ′ (2f -2 , 0).
This proves (43).

In the case k = -3, N = 54, we find explicitly .

u = g 2 g 4 g 2
Moreover the Deninger path is the following sum of modular symbols

γ -3 = ϕ * - 1 8 , 1 8 = ϕ * ξ 1 0 8 1 -ξ 1 0 - 8 1
.

Using Theorem 1, we obtain

γ -3 η(x, y) = 1 8 -1 8 η(u, v) = πL ′ (2f -3 , 0).
This proves (43). Using (45), we also deduce Zagier's conjectures for these elliptic curves.

Theorem 25. -We have the identities

(46) L(E -1 , 2) = 9π 7 D E -1 (A) L(E -2 , 2) = 36π 35 D E -2 (A) L(E -3 , 2) = 2π 3 D E -3 (A).
6.2. Conductor 21. -The modular curve X 0 (21) has genus 1 and is isomorphic to the elliptic curve E 0 = 21a1 with minimal equation

y 2 + xy = x 3 -4x -1. The Mordell-Weil group E 0 (Q) is isomorphic to Z 4Z × Z 2Z
and is generated by the points P = (5, 8) and Q = (-2, 1), with respective orders 4 and 2. The modular curve X 0 (21) has 4 cusps: 0, 1 3, 1 7, ∞ and we may choose the isomorphism ϕ 0 ∶ X 0 (

≅ → E 0 so that ϕ 0 (0) = 0, ϕ 0 (1 3) = (-1, -1) = P + Q, ϕ 0 (1 7) = Q and ϕ 0 (∞) = P . Let f P and f Q be functions on E with divisors

(f P ) = 4(P ) -4(0) (f Q ) = 2(Q) -2(0).
These modular units can be expressed in terms of the Dedekind η function [12, §3.2]:

f P ∼ Q × η(3τ )η(21τ ) 5 η(τ ) 5 η(7τ ) f Q ∼ Q × η(3τ )η(7τ ) 3 η(τ ) 3 η(21τ ) .
They can in turn be expressed in terms of Siegel units using the formula

η(dτ ) η(τ ) = C d (d-1) 2 k=1 g 0,kN d (τ ) (C d ∈ C × ).
Thus we can take f P = g 0,7 (∏ 10 b=1 g 0,b ) 5 g 0,3 g 0,6 g 0,9

f Q = g 0,7 (g 0,3 g 0,6 g 0,9 ) 3

∏ 10 b=1 g 0,b
.

The homology group H 1 (E 0 (C), Z) -is generated by the modular symbol γ = {-

1 3 , 1 3 } = ξ 1 0 3 1 -ξ 1 0 - 3 1
. Using Theorem 1 and a computer algebra system, we find

γ η(f P , f Q ) = πΛ * (F, 0)
where F is the modular form of weight 2 and level 21 given by

F = 68q + 220q 2 + 68q 3 + 508q 4 + 440q 5 + 220q 6 + 508q 7 + 1068q 8 + 68q 9 + ⋯
The space M 2 (Γ 0 (21)) has dimension 4 and is generated by f 0 , E 2,3 , E 2,7 and E 2,21 where f 0 is the newform associated to E 0 and E 2,d (τ ) = E 2 (τ ) -dE 2 (dτ ). We find explicitly

F = -4f 0 + 72E 2,3 + 72 7 E 2,7 - 72 7 E 2,21
We have

L(E 2,d , s) = (1 -d 1-s )ζ(s)ζ(s -1
) and a little computation gives

L(F, s) = -4L(E 0 , s) + 72 7 ⋅ 21 s (7 ⋅ 21 s -21 ⋅ 7 s -7 ⋅ 3 s + 21)ζ(s)ζ(s -1). Thus L(F, 0) = 0 and using ζ(0) = -1 2 and ζ(-1) = -1 12, we find Λ * (F, 0) = Λ(F, 0) = L ′ (F, 0) = -4L ′ (E 0 , 0) -6 log 7.
The extraneous term 6 log 7 stems from the fact that the Milnor symbol {f P , f Q } does not extend to K 2 (E 0 ) ⊗ Q. Indeed, the tame symbols are given by

∂ 0 {f P , f Q } = 1 ∂ P {f P , f Q } = f Q (P ) -4 = ζ -4 7 7 -4 ∂ Q {f P , f Q } = ζ -4 7 7 4
. Since f P and f Q are supported in torsion points, there is a standard trick (due to Bloch) to alter the symbol {f P , f Q } to make an element of K 2 (E 0 ) ⊗ Q. We will see that the corresponding regulator integral is proportional to L ′ (E 0 , 0) alone. We put x ∶= {f P , f Q } + {7, f P f 2 Q }, which belongs to K 2 (E 0 ) ⊗ Q, and we define

η(x) ∶= η(f P , f Q ) + η(7, f P f 2 Q ) = η(f P , f Q ) + log 7 ⋅ d arg(f P f 2 Q ). We can compute the integral of d arg(f P f 2 Q ) using Lemma 5, which results in γ η(x) = -4πL ′ (E 0 , 0).
On the other hand, we have ∫ γ ω f 0 ≈ 1.91099i which shows that γ + E 0 • γ > 0. Since E 0 (R) has two connected components, this implies γ + E 0 • γ = 1 and Proposition 19 gives

γ η(x) = -D E 0 (β).
We have β = 8(P + Q) -8(P ) -8(Q) + 8(0). Since D E 0 is odd, this gives

γ η(x) = -8 D E 0 (P + Q) -D E 0 (P ) .
Taking into account the functional equation L ′ (E 0 , 0) = 21 4π 2 L(E 0 , 2), we have thus shown Zagier's conjecture for E 0 .

Theorem 26. -We have the identity L(E 0 , 2) = 8π

21 D E 0 (P + Q) -D E 0 (P ) .

We will now deduce Boyd's conjecture [4, Table 1, k = 3] for the elliptic curve E 1 of conductor 21 given by the equation P (x, y) = x + 1

x + y + 1 y + 3 = 0.

Theorem 27. -We have the identity m(x

+ 1 x + y + 1 y + 3) = 2L ′ (E 1 , 0).
The change of variables

X = x(x + y + 3) + 1 Y = x(x + 1)(x + y + 3) + 1
puts E 1 in the Weierstrass form Y 2 + XY = X 3 + X. This is the elliptic curve labelled 21a4 in Cremona's tables [START_REF] Cremona | Algorithms for modular elliptic curves[END_REF]. The Mordell-Weil group E 1 (Q) is isomorphic to Z 4Z and is generated by P 1 = (1, 1). The polynomial P satisfies Deninger's conditions [8, 3.2], so we have

m(P ) = 1 2π γ P η(x, y)
where γ P is the path defined by γ P = {(x, y) ∈ E 1 (C) ∶ x = 1, y ≤ 1}. The path γ P joins the point Ā = ( ζ3 , -1) to A = (ζ 3 , -1). Note that these points have last coordinate -1, so the discussion in [8, p. 272] applies and γ P defines an element of H 1 (E 1 (C), Q). After some computation, we find that γ P = 1 2 γ 1 where γ 1 is a generator of

H 1 (E 1 (C), Z) -such that γ + E 1 •γ 1 = 2 (note that E 1 (R) is connected). Using Proposition 19, it follows that γ P η(x, y) = 1 2 γ 1 η(x, y) = -D E 1 (β)
where β = div(x) * div(y) -is the convolution of the divisors of x and y. We have div(x) = (P 1 ) + (2P 1 ) -(-P 1 ) -(0) div(y) = (P 1 ) -(2P 1 ) -(-P 1 ) + (0) so that β = 4(P 1 ) -4(-P 1 ). This gives γ P η(x, y) = -8D E 1 (P 1 ).

We are now going to relate elliptic dilogarithms on E 1 and E 0 using Proposition 21 and Lemma 23. The curve E 1 is the X 1 (21)-optimal elliptic curve in the isogeny class of E 0 . We have a 2-isogeny λ ∶ E 1 → E 0 whose kernel is generated by 2P 1 = (0, 0). Using Vélu's formulas [START_REF] Vélu | Isogénies entre courbes elliptiques[END_REF], we find that an equation of λ is ). Using Theorem 26 and Lemma 23, we have

λ(X, Y ) = X 2 + 1 X , - 1 X + X 2 -1 X 2 Y
L ′ (E 0 , 0) = 4 π D E 1 (A) + D E 1 ( Ā) -D E 1 (B) -D E 1 (B ′ )
so that Theorem 27 reduces to show

D E 1 (P 1 ) = -2 2D E 1 (A) -D E 1 (B) -D E 1 (B ′ ) .
We look for lines in P 2 such that ∩ E 1 is contained in the subgroup generated by A and B. Using a computer search, we find that the tangents to E at A and -A and the line ∶ Y + 1 2 X = 0 passing through the 2-torsion points of E are incident. By Proposition 21, we deduce the relation

4D E 1 (2A) + 4D E 1 (3A) + D E 1 (4A) + 2D E 1 (-2A) + 4D E 1 (-A) + 2D E 1 (2A + C) + 4D E 1 (3A + C) + 2D E 1 (-2A + C) + 4D E 1 (-A + C) = 0. Since D E 1 is odd and D E 1 (3A) = -D E 1 ( Ā) = -D E 1 (A), this simplifies to 2D E 1 (2A) -8D E 1 (A) + 4D E 1 (B) + 4D E 1 (B ′ ) = 0
which is the desired equality.

+ 12) = 2L ′ (E, 0)
, where E is the elliptic curve defined by x + 1

x + y + 1 y + 12 = 0.

The curve x + 1

x + y + 1 y + 12 = 0 is isomorphic to the elliptic curve E = 48a5. We have a commutative diagram (47) X 1 (48)

X 0 (48)

E 1 E 0 E. π ϕ1 ϕ0 λ0 λ
Here E 1 = 48a4 is the X 1 (48)-optimal elliptic curve and E 0 = 48a1 is the strong Weil curve in the isogeny class of E. They are given by the equations

(48) E 1 ∶ y 2 = x 3 + x 2 + x E 0 ∶ y 2 = x 3 + x 2 -4x -4.
The isogeny λ 0 has degree 2 and its kernel is generated by P 1 = (0, 0). Using Vélu's formulas, we find an explicit equation for λ 0 :

(49) λ 0 (x, y) = x + 1 x , (1 -1

x 2 )y . The modular parametrization ϕ 0 has degree 2 and we have

ϕ 0 (0) = ϕ 0 (1 2) = 0 ϕ 0 (1 3) = ϕ 0 (1 6) = (-1, 0) ϕ 0 (1 8) = ϕ 0 (1 16) = (-2, 0) ϕ 0 (1 24) = ϕ 0 (1 48) = (2, 0) ϕ 0 (1 4) = (0, 2i) ϕ 0 (-1 4) = (0, -2i) ϕ 0 (1 12) = (-4, -6i) ϕ 0 (-1 12) = (-4, 6i).
Moreover the ramification indices of ϕ 0 at the cusps 1 4 , -1 4 , 1 12 , -1 12 are equal to 2. Let S 0 be the set of points P of E 0 (C) such that ϕ -1 0 (P ) is contained in the set of cusps of X 0 (48), and similarly let S 1 be the set of points P of E 1 (C) such that ϕ -1 1 (P ) is contained in the set of cusps of X 1 (48). By the previous computation, we have (50)

S 0 = E 0 [2] ∪ {(0, ±2i), (-4, ±6i)}.
The curve E 0 doesn't admit a parametrization by modular units, but the curve E 1 does. Indeed, consider the point A = (i, i) ∈ E 1 (C). It has order 8 and satisfies Ā = 3A and 4A = P 1 . Moreover λ 0 (A) = (0, 2i). Because of the commutative diagram (47), we know that S 1 contains λ -1 0 (S 0 ); in particular S 1 contains the subgroup generated by A. Therefore the following functions on E 1 are modular units

(51) (f ) = 2(P 1 ) -2(0) (g) = 2(A) + 2( Ā) -4(0).
We may take f = x and g = x 2 -2y + 2x + 1. It is plain that f and g parametrize E 1 . Moreover the tame symbols of {f, g} at 0, P 1 , A, Ā are equal to 1, 1, -1, - A generator γ 1 of H 1 (E 1 (C), Z) -is given by

γ 1 = (ϕ 1 ) * - 1 7 , 1 7 = (ϕ 1 ) * ξ 1 0 7 1 -ξ 1 0 - 7 1
.

Using Theorem 1, we find (53)

γ 1 η(f, g) = 1 7 -1 7 η(ϕ * 1 f, ϕ * 1 g) = πL ′ (F 1 , 0)
where F 1 is the modular form of weight 2 and level 48 given by

F 1 = 4q 2 + 8q 3 -4q 6 -
γ 2 = (ϕ 1 ) * - 2 11 , 2 11 = (ϕ 1 ) * ξ 2 1 11 6 + ξ 1 0 6 1 -ξ -2 1 11 -6 -ξ 1 0 - 6 1
.

Using Theorem 1, we find (54)

γ 2 η(f, g) = 2 11 -2 11 η(ϕ * 1 f, ϕ * 1 g) = πL ′ (F 2 , 0)
where F 2 is the modular form of weight 2 and level 48 given by F 2 = -4q + 8q 2 + 12q 3 + 8q 5 -8q 6 -4q 9 -16q 10 -48q 11 + 8q 13 -24q 15 -8q 17 + 8q 18 + 48q 19 + . . .

A computation reveals that 2F 1 -F 2 = 4f E 1 . Summing (53) and (54), we get (55) Proposition 30. -Let k be a real number such that k > 4. We have

2γ 1 -γ 2 η(f, g) = 4πL ′ (E 1 , 0). Since γ + E 1 • γ 1 = γ + E 1 • γ 2 = 2,
m(P k ) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ -4 π D C k (Q) if k > 0, 4 π D C k (Q) if k < 0.
Proof. -Since k > 4, the polynomial P k doesn't vanish on the torus, so that Remark 31. -The fact that m(P k ) can be expressed as an Eisenstein-Kronecker series was also proved by F. Rodriguez-Villegas [START_REF] Villegas | Modular Mahler measures. I[END_REF].

We are now going to relate elliptic dilogarithms on E = C 12 and E 1 . Let λ ′ ∶ E 1 → E be the isogeny λ ○ λ 0 from (47). It is cyclic of degree 8 and its kernel is generated by the point B = (-2 -√ 3, 3i + 2i √ 3). A preimage of Q under λ ′ is given by [P + Q] (P, Q ∈ T ).

C = 1 2 (α 3 + α 2 + α -1), 1 2 (α 3
The group R triv has rank 26 and by Lemma 23, we have D E 1 (R triv ) = 0. Moreover R + R triv has rank 27 and a generator of (R + R triv ) R triv is given (for example) by the divisor

β = β E 1 ( 1 , 2 ) + β E 1 ( 2 , 3 ) + β E 1 ( 3 , 1 )
where 1 , 2 , 3 are the lines defined by Using the functional equations (59) of D E 1 , we obtain (58).

  u , g v ) = πΛ * (e a,d e b,-c + e a,-d e b,c , 0) where e a,b is the Eisenstein series of weight 1 and level N 2 defined by (2) e a,b (τ ) = α 0 (a, b) + m,n≥1 m≡a, n≡b(N )

  21, Thm 1] by taking u = (a, ac) and v = (b, bc) in Theorem 1. Note that in this case f a,b,c = e a,bc e ac,-b + e a,-bc e ac,b belongs to Q[[q N ]], and f a,b,c (τ N ) is a modular form on Γ 1 (N ). More generally, if M = a b c d ∈ M 2 (Z N Z) is any matrix such that det(M ) = 0, then F M (τ N ) = (e a,d e b,-c + e a,-d e b,c )(τ N ) is a modular form of weight 2 on Γ 1 (N ).

  a,b (-1 τ ) = w a,b g b,-a (τ ) for some root of unity w a,b . The formula for w a,b follows from [10, Chap. 2, §1, K1, K4]. Lemma 5. -For any a, b ∈ Z N Z, we have

Lemma 11 .

 11 -The function e a,b (τ N ) is an Eisenstein series of weight 1 on the group Γ(N ), and the function e a,b is an Eisenstein series of weight 1 on Γ 1 (N 2 ). Proof. -In [17, Chap. VII, §2.3], for any (a, b) ∈ (Z N Z) 2 the following Eisenstein series are introduced

  The function f a,b (τ N ) is an Eisenstein series of weight 1 on Γ(N ), and the function f a,b is an Eisenstein series of weight 1 on Γ 1 (N 2 ). Moreover, we have W N 2 (e a,b ) = -i N f a,b . Proof. -The relation (15) follows from [21, Lemma 2] (the proof there works for arbitrary a, b ∈ Z N Z). We deduce that f a,b (τ N ) is a multiple of the function obtained from e a,b (τ N ) by applying the slash operator 0 -1 1 0 in weight 1. Hence f a,b (τ N ) is an Eisenstein series of weight 1 on Γ(N ). The last assertion follows from replacing τ by N τ in (15). We will need the following formula for the completed L-function of f a,b . Lemma 14. -For any a, b ∈ Z N Z, we have

6. 1 .

 1 Conductors 14, 35 and 54. -We prove the following cases of Boyd's conjectures[START_REF] Boyd | Mahler's measure and special values of L-functions[END_REF] Table

.

  The preimages of P + Q under λ are the points A = (ζ 3 , -1 -ζ 3 ) and Ā = ( ζ3 , -1 -ζ3 ), while the preimages of P are given by B = ( that 2A = -P 1 and 2B = P 1 so that A and B have order 8 and we have the relations Ā = A + 2P 1 = 5A and B ′ = 5B. Moreover C = A + B is the 2-torsion point given by C = (

2 η 1 .

 21 (f, g) = -2D E 1 (β(f, g)) = -32D E 1 (A).Combining (55) and (56), we have thus shown Zagier's conjecture for E Theorem 29. -We have the identitiesL ′ (E 1 , 0) = -8 π D E 1 (A) and L(E 1 , 2) = -2π 3 D E 1 (A).Let us now turn to the elliptic curve E. Let P k be the polynomial P k (x, y) = x+1 x+y+1 y+k. For k ∈ {0, ±4}, let C k be the elliptic curve defined by P k (x, y) = 0. The change of variablesX = 4x(x + y + k) Y = 8x 2 (x + y + k) puts C k in Weierstrass form Y 2 + 2kXY + 8kY = X 3 + 4X 2 .The point Q = (0, 0) on C k has order 4. We show that the Mahler measure of P k can be expressed in terms of the elliptic dilogarithm.

  where γ k is the closed path on C k (C) defined byγ k = {(x, y) ∈ C k (C) ∶ x = 1, y ≤ 1}. It turns out that γ k is a generator of H 1 (C k (C), Z) -which satisfies γ + C k • γ k = sgn(k). The divisors of x and y are given by div(x) = (Q) + (2Q) -(-Q) -(0) div(y) = (Q) -(2Q) -(-Q) + (0). Since P k is tempered, we have {x, y} ∈ K 2 (C k ) ⊗ Q,and Proposition 19 gives γ k η(x, y) = -sgn(k)D C k (β(x, y)) = -8 sgn(k)D C k (Q).

+ α 2 -α - 3 ) with α = 4 √ - 3 .

 2343 The point C has order 4 and we have A = B + 2C. By Lemma 23, we have(57) D E (Q) = 2 k∈Z 8Z D E 1 (C + kB).Combining Theorem 29, Proposition 30 and (57), Theorem 28 reduces to show (58)k∈Z 8Z D E 1 (C + kB) = 2D E 1 (A).Let T be the subgroup generated by B and C. It is isomorphic to Z 8Z × Z 4Z. There are 187 lines of P 2 such that ∩ E 1 is contained in T . A computer search reveals that among them, there are 691 unordered triples of lines meeting at a point outside E 1 . These incident lines yield a subgroup R of Z[T ] of rank 18 such that D E 1 (R) = 0. Let R triv be the subgroup of Z[T ] generated by the following elements

1 ∩

 1 E 1 = (B) + (-B) + (0) 2 ∩ E 1 = (B + 2C) + (B -C) + (-2B -C) 3 ∩ E 1 = (4B + C) + (-3B + 2C) + (-B + C).Computing explicitly, this givesβ = 2 ⎛ ⎝ k∈Z 8Z (2C + kB) + (3C + kB) ⎞ ⎠ -2(-A) -2(-Ā) + (4B) -(2C) -(4B + 2C).

  9 g 12 g 15 g 16 g 3 g 4 g 10 g 11 g 17 g 3 g 4 g 6 g 8 g 2 10 g 11 g 13 g 17

	v = -	g 1	g 2 2 g 5 g 2 9 g 2 12 g 15 g 2 16

  5 g 2 13 g 14 g 16 g 20 g 21 g 22 g 2 23 g 24 g 1 g 7 g 2 8 g 2 10 g 11 g 12 g 15 g 17 g 19 g 25 g 2

	26	v = -	g 3 2 g 3 g 3 5 g 3 13 g 3 16 g 3 20 g 21 g 3 23 g 2 24 g 3 1 g 6 g 3 8 g 3 10 g 12 g 2 15 g 3 17 g 3 19 g 3 26

  6.3. Conductor 48. -We prove the following case of Boyd's conjectures [4, Table 1, k = 12].

	Theorem 28. -We have the identity m(x + 1 x + y + 1 y

  1 so that {f, g} belongs to K 2 (E 1 ) ⊗ Q. The expression of f and g in terms of Siegel units is

	(52)	ϕ * 1 f =	g 2 g 20 g 22 g 4 g 10 g 14	ϕ * 1 g =	g 2 1 g 2 g 10 g 2 11 g 4 12 g 2 13 g 14 g 22 g 2 23 g 3 4 g 2 5 g 2 6 g 2 7 g 2 17 g 2 18 g 2 19 g 20	.

  8q 10 -32q 11 -16q 15 + 4q 18 + 32q 19 + . . . This time F 1 is not a multiple of the newform f E 1 associated to E 1 . We look for another modular symbol. Another generator γ 2 of H 1 (E 1 (C), Z) -is given by

F. Brunault, ÉNS Lyon, UMPA, 46 allée d'Italie, 69007 Lyon, France E-mail : francois.brunault@ens-lyon.fr • Url : http://perso.ens-lyon.fr/francois.brunault


Ju-Sung Kang
email: jskang@kookmin.ac.kr

Nayoung Kim

Wangho Ju

Ok-Yeon Yi
email: oyyi@kookmin.ac.kr

A Security Analysis of Key Expansion Functions Using Pseudorandom Permutations

Keywords: Privacy, Authenticity, Key expansion function, Keying material, Provable security, Pseudorandomness, PRF, PRP

Within many cryptographic systems a key expansion function is used in order to derive more keying material from the master secret. The derived additional keys may be needed for multiple entities or for different cryptographic purposes such as privacy and authenticity. In this paper we wish to examine the soundness of the key expansion functions on the view point of provable security framework. Especially we focus on the key expansion functions using PRFs(pseudorandom functions) which are recommended by NIST, and show that the variant of Double-Pipeline Iteration mode using PRPs(pseudorandom permutations) is secure, while the variants of Counter and Feedback modes using PRPs are insecure. In practice secure block ciphers such as AES can be regarded as PRPs.

Introduction

Cryptographic keys are essential to the security of all cryptographic algorithms and protocols for some information security objectives, such as privacy or confidentiality, authenticity, digital signature, and non-repudiation in the presence of adversaries. Key management is an indispensable part of the cryptographic system and this includes dealing with the generation, exchange, storage, use, and replacement of keys. Cryptographic systems may use some kinds of keys more than one master key, so key derivation mechanism is contained in the key management part. Key derivation mechanism derives one or more secret keys from a shared secret such as a master key. Thus any key derivation mechanism has the key expansion step. For example, NIST SP 800-56C [START_REF]C[END_REF] specifies a key derivation mechanism that is an extraction-then-expansion procedure. This procedure consists of a randomness extraction step and a key expansion step. The randomness extraction step outputs a key derivation key from a master key. A key derivation key is then used as input to the key expansion step that derives keying material and can also be used to derive more keying material from derived keys of key expansion step. The derived additional keys from a key expansion step may be used for multiple entities or for different cryptographic objectives. Our research interest is to examine the soundness of some key expansion functions (KEFs) for key expansion steps on the view point of provable security framework.

Related Work

Although a key derivation mechanism has the central role in applied cryptography, there has been relatively little formal work addressing the design and security analysis. Krawczyk[6] associated the notion of cryptographically strong secret keys with that of pseudorandom keys, namely, indistinguishable by feasible computation from a uniformly distributed string of the same length, and provided detailed rationale for the hash-based design of key derivation mechanisms based on the extract-then-expand approach. The extraction step generates a uniformly random or pseudorandom seed key from the master key that may be an output of an imperfect physical random number generator, and the expansion step derives several additional pseudorandom cryptographic keys from the seed key.

Gilbert [START_REF] Gilbert | The security of one-block-to-many modes of operation[END_REF] investigated the security of block cipher modes of operation allowing to expand an one-block input into a longer t-block output, under the Luby-Rackoff security paradigm [START_REF] Luby | How to construct pseudorandom permutations and pseudorandom functions[END_REF][START_REF] Naor | On the construction of pseudorandom permutations: Luby-Rackoff revisited[END_REF] which is originally due to the indistinguishability in Goldreich-Goldwasser-Micali [START_REF] Goldreich | How to construct random functions[END_REF]. A KEF in a key derivation mechanism is a typical example of the one-block-to-many modes of operation. In [START_REF] Gilbert | The security of one-block-to-many modes of operation[END_REF], the author showed that, under the Luby-Rackoff security model, the key expansion function MILENAGE of 3GPP [START_REF]3rd Generation Partnership Project, Specification of the MILENAGE algorithm set: An example algorithm set for the 3GPP authentication[END_REF] is pseudorandom.

On the other hand NIST has specified three KEFs using pseudorandom functions (PRFs) in SP 800-108 [START_REF]Recommendation for Key Derivation Using Pseudorandom Functions[END_REF]. A PRF family {P RF s (•)|s ∈ S} consists of polynomial time computable functions with an index s, a seed, such that when s is randomly selected from S and not known to adversaries, P RF s (•) is computationally indistinguishable from a random function defined on the same domain and range [START_REF] Goldreich | How to construct random functions[END_REF]. In [START_REF]Recommendation for Key Derivation Using Pseudorandom Functions[END_REF], several families of PRF-based key expansion functions are defined without describing the internal structure of the PRF, and recommended the use of either HMAC[3] or CMAC [9] as the PRF.

Our Contribution

In spite of several years after the publication of NIST SP 800-108 [START_REF]Recommendation for Key Derivation Using Pseudorandom Functions[END_REF], as far as we know there is no noticeable result that deals with a security analysis for three KEFs of this document. It seems that if a PRF, such as HMAC or CMAC, is used as the building block of the three KEFs in [START_REF]Recommendation for Key Derivation Using Pseudorandom Functions[END_REF], we have difficulty in investigating the soundness of the given schemes. Hence we add a constraint condition that a pseudorandom permutation (PRP), such as AES, is used as the building block of the given KEFs. A PRP family is a special case of PRF families and computationally indistinguishable from a random permutation defined on the same domain. Once we regard the given KEFs of [START_REF]Recommendation for Key Derivation Using Pseudorandom Functions[END_REF] as PRP-based schemes, we can investigate the security of these variant schemes in the Luby-Rackoff security model which is similar to the context of Gilbert [START_REF] Gilbert | The security of one-block-to-many modes of operation[END_REF].

In fact NIST SP 800-108 [START_REF]Recommendation for Key Derivation Using Pseudorandom Functions[END_REF] defines three families of PRF-based KEFs, so called, Counter mode, Feedback mode and Double-Pipeline Iteration mode. In this work we consider the variant schemes of three KEFs that use PRPs, and show that the variant of Double-Pipeline Iteration mode using PRPs is pseudorandom, while the variants of Counter and Feedback modes using PRPs are insecure. Moreover we provide a concrete security bound for the variant of Double-Pipeline Iteration mode where the underlying PRP is a practical block cipher. This concrete security approach is based on the security model of Bellare-Killian-Rogaway [START_REF] Bellare | The security of the cipher block chaining message authentication code[END_REF] and Bellare-Rogaway [START_REF] Bellare | Introduction to Mordern Cryptography[END_REF].

Notions of PRF and PRP

In order to examine the soundness of some KEFs, we need to introduce the rigorous notions of PRF and PRP. These are useful conceptual starting points to enable the security analysis in the design of some cryptographic functions. Cryptographic functions such as block ciphers or their modes of operation can be regarded as a pseudorandom function family indexed by a uniformly distributed key space. It is natural that we also consider a KEF as a pseudorandom function family because it is an example of block cipher modes of operation where a PRP is used as an underlying primitive in the KEF. We have to recognize that a KEF is an instance of a PRF to obtain the theoretical upper bound for the provable security. No computationally efficient adversary can distinguish with significant advantage between a randomly chosen instance of a PRF and a uniformly selected random function of the same domain and range. In this section we describe concrete security approach which is based on the Bellare-Rogaway [START_REF] Bellare | Introduction to Mordern Cryptography[END_REF] security model.

Function Families

A function family is a map Λ : K × D → R, where K is the keyspace, D is the domain and R is the range of Λ. The two-input function Λ takes a key K and an input x to return a point y we denote by Λ(K, x). For any key K ∈ K we define the map Λ K : D → R by Λ K (x) = Λ(K, x). We call the function Λ K an instance of the function family Λ. Thus Λ specifies a collection of maps indexed by the key space. Usually the probability distribution of a function family comes from some probability distributions on the keyspace K. Unless otherwise indicated, this distribution will be the uniform distribution.

We use the following notation in this paper. For any positive integer k, n and m, we denote K = {0, 1} k , D = {0, 1} n and R = {0, 1} m , where k, n, and m are called the key-length, the input-length and the output-length, respectively. We denote by K $ ← K the operation of selecting a random string K from K. The notation f $ ← Λ means the operation K $ ← K and f = Λ K . In other words, let f be the function Λ K where K is a randomly chosen key. We are interested in the input-output behavior of this randomly chosen instance of the family.

There are two particular function families that we need to consider in order to define PRFs and PRPs. One is F(D, R) the family of all functions from domain D to range R, the other is P(D) the family of all permutations on D. A uniformly chosen instance of F(D, R) is called a random function from D to R, and a uniformly chosen instance of P(D) is called a random permutation on D. The key describing any particular instance function is simply a description of this instance function in some canonical notation. For example, order the domain D lexicographically as x 1 , x 2 , . . ., and let the key for a function f be the list of values (f (x 1 ), f (x 2 ), . . .). The keyspace of F(D, R) is simply the set of all these keys, under the uniform distribution. The key for a function in this family is a list of all the output values of the function as its input ranges over {0, 1} n . Namely, the key describing a particular instance function is exactly corresponding to the function itself. Note that the size of the key spaces of F(D, R) and P(D) are (2 m ) 2 n and (2 n )!, respectively.

Pseudorandom Functions and Permutations

A pseudorandom function is a function family with the property that the inputoutput behavior of a random instance of the family is computationally indistinguishable from that of a random function. Similarly, a function family is a pseudorandom permutation if the input-output behavior of a random instance of the family is computationally indistinguishable from that of a random permutation. In order to introduce the notions of PRF and PRP, we consider the following security model. The notion of PRP is very similar to the one of PRF. Thus we only consider the notion of PRF. Let any adversary A be an algorithm to distinguish a random instance of a function family from a random function.

The adversary A has access to an oracle. The oracle will be chosen either as a random instance of a function family or as a random function by coin tossing. When the oracle selects a fuction as G we consider two different worlds. Usually in World 0, G will be chosen as a random function, while in World 1, G will be chosen as a random instance of a function family. And the adversary must determine in which world it is placed, and at the end of its computation outputs a bit.

In the formalization, we consider two different ways in which G will be chosen, giving rise to two different worlds.

World 0. The function G is drawn at random from F(D, R), namely, the func- tion G is selected via G $ ← F(D, R) . World 1. The function G is drawn at random from Λ, namely, the function G is selected via G $ ← Λ.
Definition 1. Let Λ : K × D → R be a function family, and A be an algorithm that takes an oracle for a function G : D → R, and returns a bit. We consider two experiments:

Experiment Exp prf -1 F (A) Experiment Exp prf -0 F (A) K $ ← K G $ ← F(D, R) b $ ← A Λ K b $ ← A G Return b Return b
The prf-advantage of A is defined by

Adv prf Λ (A) = P r Exp prf -1 F (A) = 1 -P r Exp prf -0 F (A) = 1 = P r A G = 1 | G ← Λ -P r A G = 1 | G ← F(D, R) .

PRP-based KEFs of NIST SP 800-108

NIST has specified three KEFs using PRFs in SP 800-108 [START_REF]Recommendation for Key Derivation Using Pseudorandom Functions[END_REF] without describing the internal structure of the PRF, and recommended the use of either HMAC[3] or CMAC [9] as the underlying PRF. However we have difficulty in analyzing the provable security of the given KEFs where the underlying primitives are PRFs. Thus we change this PRF condition to the PRP one because a PRP family is a special case of PRF families. That is, hereafter we consider only PRP-based KEFs of the NIST recomendations. Once we regard the given KEFs of [START_REF]Recommendation for Key Derivation Using Pseudorandom Functions[END_REF] as PRP-based schemes, we can investigate the provable security of these variant schemes in the Luby-Rackoff security model which is similar to the context of Gilbert [START_REF] Gilbert | The security of one-block-to-many modes of operation[END_REF].

PRP-based Counter mode

Let G be a PRP on {0, 1} n , then the PRP-based Counter mode is defined in Definition 2 and illustrated in Figure 1.

Definition 2. For any permutation g ∈ G and integer t ≥ 2, CN T [g] is called a PRP-based Counter mode if

CN T [g] : {0, 1} n → {0, 1} nt , CN T [g](x) = (z 1 , z 2 , . . . , z t ) = (g(x ⊕ c 1 ), g(x ⊕ c 2 ), . . . , g(x ⊕ c t )) ,
where c 1 , c 2 , . . . , c t are constants of {0, 1} n .

PRP-based Feedback mode

PRP-based Feedback mode is defined in Definition 3 and illustrated in Figure 2.

Definition 3. For any permutation g ∈ G and integer

t ≥ 2, F B[g] is called a PRP-based Feedback mode if F B[g] : {0, 1} n → {0, 1} nt , F B[g](x) = (z 1 , z 2 , . . . , z t ) = (g(x ⊕ c 1 ), g(x ⊕ z 1 ⊕ c 2 ), . . . , g(x ⊕ z t-1 ⊕ c t )) ,
where c 1 , c 2 , . . . , c t are constants of {0, 1} n .

DP [g] : {0, 1} n → {0, 1} nt , DP [g](x) = (z 1 , z 2 , . . . , z t ) = g (g(x) ⊕ x ⊕ c 1 ) , g g 2 (x) ⊕ x ⊕ c 2 , . . . , g g t (x) ⊕ x ⊕ c t ,
where for each 1 ≤ k ≤ t, g k denotes k times iteration of g and c 1 , c 2 , . . . , c t are constants of {0, 1} n .

Provable Security of PRP-based KEFs

In this section we show that the PRP-based Double-Pipeline Iteration mode is secure, while the PRP-based Counter mode and Feedback mode are insecure. Since a secure block cipher, such as AES, is regarded as the underlying PRP in practice, the PRP-based Double-Pipeline Iteration mode can be recommended

Insecurity of PRP-based Counter mode

Now we consider the case that CN T [π] is derived from a random permutation π ∈ P({0, 1} n ). Then it is simple that CN T [π] is insecure.

Theorem 1. For any random permutation π ∈ P, CN T [π] is not a secure PRF.

Proof. In order to show that CN T [π] is not a secure PRF we specify an adversary attacking CN T [π]. Since an instance of CN T [π] is a function from {0, 1} n to {0, 1} nt , the adversary A will get an oracle for a function G that maps {0, 1} n to {0, 1} nt . In World 0, G will be chosen as a random function from F = F({0, 1} n , {0, 1} nt ), while in World 1, G will be set to CN T [π] where π is a random permutation from P({0, 1} n ). The adversary A must determine in which world it is placed. Let us show how the adversary A works.

Adversary A G (z (1)
1 , . . . , z

t ) ← G x (1) (z (2) 1 , . . . , z (1)
t ) ← G x (2) = x (1) ⊕ c 1 ⊕ c 2 if z (1) 1 = z (2) 2 and z (1) 2 = z (2) 1 then return 1 else return 0 If G = CN T [π] for some π, it is certainly true that z (1) 1 = z (2) 2 and z (1) 2 = z (2) 1 . (2)
On the other hand if G is a random function from F, the probability of the event that z

(1)

1 = z (2) 2 and z (1) 2 = z (2) 1
will be 2 -2n , the probability that A will return 1. Therefore the advantage of A is as follows:

Adv prf CN T [π] (A) = P r Exp prf -1 CN T [π] (A) = 1 -P r Exp prf -0 CN T [π] (A) = 1 = P r A G = 1 | G ← CN T [π] -P r A G = 1 | G ← F = 1 -2 -2n .
From the above formula we obtain that there exists an extremely efficient adversary whose prf-advantage against CN T [π] is almost one. This means that CN T [π] is not a secure PRF.

Insecurity of PRP-based Feedback mode

We investigate the provable security of the PRP-based Feedback mode F B[π] derived from a random permutation π. It is also a simple argument similar to the case of PRP-based Counter mode that F B[π] is insecure.

Theorem 2. For any random permutation π ∈ P, F B[π] is not a secure PRF.

Proof. We find an adversary with a high advantage attacking F B[π] in order to prove that F B[π] is not a secure PRF. Since an instance of F B[π] is a function from {0, 1} n to {0, 1} nt , the adversary A will get an oracle for a function G that maps {0, 1} n to {0, 1} nt . In World 0, G will be chosen as a random function of F = F({0, 1} n , {0, 1} nt ), while in World 1, G will be set to F B[π] where π is a random permutation from P({0, 1} n ). The adversary A must determine in which world it is placed. In this case A queries its oracle at the x (1) to get back (z

(1) 1 , . . . , z (1)
t ) and then queries its oracle at the x (2) to get back (z

(2) 1 , . . . , z (2)
t ). The adversary A works as follows:

Adversary A G (z (1)
1 , . . . , z

t ) ← G x (1) (z (2) 1 , . . . , z (1)
t ) ← G x (2) = x (1) ⊕ c 1 ⊕ c 2 ⊕ z (1) 1 if z (2) 1 = z (1) 2 then return 1 else return 0 If G = F B[π] for some π, it is obvious that z (2) 1 = π((x (1) ⊕ c 1 ⊕ c 2 ⊕ z (1) 1 ) ⊕ c 1 ) = π(x (1) ⊕ c 2 ⊕ z (1) 1 ) = z (1) 2 . (2)
On the other hand if G is a random function, the probability that z will be 2 -n , the probability that A will return 1. Thus Adv prf F B[π] (A) = 1 -2 -n , this shows that F B[π] is not a secure PRF.

Provable security of PRP-based Double-Pipeline Iteration mode

Now we examine the provable security of the PRP-based Double-Pipeline Iteration mode. We consider the case where DP [π] is derived from a random permutation π and prove that DP [π] is a secure PRF. At first we introduce a very useful fact of [START_REF] Patarin | How to construct pseudorandom and super pseudorandom permutations from one single pseudorandom function[END_REF] and [START_REF] Gilbert | The security of one-block-to-many modes of operation[END_REF] for obtaining an upper bound on Adv prf (A) based on the transition probability P r(x→y).

Proposition 1. Let E be a randomly chosen instance of a function family Λ with the domain {0, 1} n and the range {0, 1} m , F be a random function from F = F({0, 1} n , {0, 1} m ) and q be an integer. An adversary A will get an oracle for a function G. In World 0, G will be chosen from F, while in World 1, G will be set to E that is a randomly drawn from Λ. The adversary must determine in which world it is placed. Denote by X the subset of ({0, 1} n ) q containing all pairwise distinct q-tuples x = (x (1) , • • • , x (q) ). If there exist a subset Y of ({0, 1} m ) q and two positive real numbers ε 1 and ε 2 such that

(a) |Y | ≥ (1 -ε 1 ) • 2 mq (b) for each x ∈ X and y ∈ Y, P r x E → y ≥ (1 -ε 2 ) • 1 2 mq ,
then for any adversary A using q queries

Adv prf Λ (A) = P r A G = 1|G ← Λ -P r A G = 1|G ← F ≤ ε 1 + ε 2 .
By the argument using Proposition 1, in the following Theorem 3 we obtain an upper bound on Adv prf DP [π] (A). From this we know the fact that the PRPbased Double-Pipeline Iteration mode is a secure PRF.

Theorem 3. For any PRP-based Double-Pipeline Iteration mode DP [π] : {0, 1} n → {0, 1} nt , ∀π ∈ P({0, 1} n ) , let A be an adversary with q queries such that t 2 q 2 2 n ≤ 2 3 . Then we obtain that

Adv prf DP [π] (A) ≤ 7t 2 q 2 2 n+1 .
Proof. Let X denote the subset of ({0, 1} n ) q containing all pairwise distinct q-tuples x = (x (1) , . . . , x (q) ) and Z be the set of q-tuples z = ((z

1 , . . . , z

t ), (z

(2) 1 , . . . , z (2)
t ), . . . , (z (q) 1 , . . . , z (q) t )) ∈ ({0, 1} nt ) q , where all tq values of z (i) k , 1 ≤ k ≤ t and 1 ≤ i ≤ q, are distinct. By Proposition 1, it suffices to show that there exist positive real numbers ε 1 and ε 2 such that

|Z| ≥ (1 -ε 1 ) • 2 ntq (1)
In this paper we have examined the soundness of the PRP-based KEFs, variant schemes of PRF-base schemes of NIST SP 800-108, on the view point of provable security framework, and proved that the variant of Double-Pipeline Iteration mode using PRPs is secure, while the variants of Counter and Feedback modes using PRPs are insecure. Moreover we have provided a concrete security bound for the variant of Double-Pipeline Iteration mode where the underlying PRP is a practical block cipher, since in practice a secure block cipher such as AES can be regarded as a PRP. As far as we know our results are the first work related to the security analysis for the KEFs within NIST SP 800-108.

Fig. 1 .Fig. 2 .Definition 4 .

 124 Fig. 1. PRP-based Counter mode

Fig. 3 .

 3 Fig. 3. PRP-based Double-Pipeline Iteration mode

Acknowledgements: This research was partially supported by BK21PLUS through the National Research Foundation of Korea(NRF) funded by the Ministry of Education, Science and Technology (Grant No. 31Z20130012918) and the IT R&D program of MSIP/KEIT[10041864, development on Spectrum Efficient Multiband WPAN System for Smart Home Networks].

and ∀x ∈ X, ∀z ∈ Z, P r x

(

Note that

Then the inequality ( 1) is established, if we set ε 1 = t 2 q 2 2 n+1 > 0. In order to estimate the transition probability of (2), we have to consider somewhat complicated cases changed by some input-output conditions associated with π's of DP [π]. For any fixed x ∈ X ⊂ ({0, 1} n ) q and z ∈ Z ⊂ ({0, 1} nt ) q , the transition probability P r x

-→ z can be estimated by investigating the intermediate value y ∈ ({0, 1} nt ) q of DP [π] depicted in Figure 3. The values of the input x and the corresponding output z are known, while the exact value of the intermediate value y is unknown. Hence we have to collect all possible candidates about the unknown intermediate value. Let Y ⊂ ({0, 1} nt ) q be the set of all these possible candidates;

t ), . . . , (y

where for each 1 ≤ k ≤ t and 1 ≤ i ≤ q, y

(3)

where y

In order to obtain a lower bound on |Y |, we count |Y -A|, |Y -B| and |Y -C|. At the first step we represent the set Y -A with three subsets to count |Y -A|. For any element of Y -A, we consider three cases according to the condition of indexes.

Case 1.

l . In this case the number of y such that

since by (3), for any fixed i, j and l, (2

l . In this case the number of y such that y

, since by (3), for any fixed i, k and l, (2

l . In this case the number of y such that y

, since by (3), for any fixed i, j, k and l, (2

Therefore we obtain that

By the similar argument, we have

and

Now we have a lower bound on |Y | as follows:

By (3), ( 4) and ( 5), we obtain that

Hence we show that (2) is established with ε 2 = 6q 2 t 2 2 n+1 . Consequentially, we obtain the upper bound on advantage of adversary A

On the other hand, any random permutation π ∈ P({0, 1} n ) in Theorem 3 is implemented by a secure block cipher in the real field. Hence it is important to investigate the concrete security analysis for the PRP-based Double-Pipeline Iteration mode where the underlying PRP is a practical block cipher such as AES. Theorem 4 shows that the Double-Pipeline Iteration mode using a block cipher is also secure, if the underlying block cipher is secure on the view point of concrete security paradigm. Let E K be a permutation family where K is randomly chosen from K. Then a block cipher with key is regarded as a instance of the E K . Theorem 4. Let A be any prf-adversary attacking DP [E K ] with any q queries such that t 2 q 2 2 n ≤ 2 3 . Then there exists an prp-adversary B attacking E K with 2tq queries such that

. Proof. We specify an adversary B attacking E K . Let E K be a permutation family with induced distibution from K , π be a random permutation from P = P({0, 1} n ). The adversary B will get an oracle for a permutation g on {0, 1} n . In World 0, g will be chosen from P, that is, g = π, while in World 1, g will be set to E K where K is a randomly chosen key. The adversary B will run A as a subroutine. The B work like this:

Adversary B g

Run adversary A, replying to its oracle queries as follows For i = 1, • • • , q do When A makes an oracle query

. By Theorem 3, we obtain that