Amaël Delaunoy
email: amael.delaunoy@inf.ethz.ch

Marc Pollefeys
email: marc.pollefeys@inf.ethz.ch

Photometric Bundle Adjustment for Dense Multi-View 3D Modeling

published or not. The documents may come

Photometric Bundle Adjustment for Dense Multi-View 3D Modeling

Amaël Delaunoy, Marc

Introduction

Reconstructing the 3D shape from multiple images has been one of the main challenges in computer vision and has been widely studied. A Bayesian way of addressing the multi-view reconstruction problem is to see it as the inverse problem of the image formation process. This process of image generation implies being able to derive a model of such a scene, denoted by Ω. This typically contains the scene geometry (i.e. the surface S), a camera model (i.e. the pinhole camera model Π), the surface properties (i.e. the reflectance), the lighting conditions, etc. If, given those parameters of Ω, we are able to generate an image R, we can compare it to the observed images I = {I 1 , I 2 , . . . , I m }. The best scene Ω can be found by maximizing the joint probability of a scene given the images:

Ω = arg max Ω {p(Ω|I)} = arg max Ω {p(I|Ω) p(Ω)} . (1)
The terms p(Ω)is the prior term on the scene (which may typically correspond to surface smoothing criteria, constrains on the surface texture or the camera parameters, or simply an initial guess for the model). p(I|Ω) corresponds to the likelihood of a generated image for a given shape, appearance and cameras. It measures the similarity between the generated images and the observed images.

A simplification of the generative model is to consider as observation previously detected 2D features in images, along with their corresponding matches in other images. Finding the camera parameters from such information is known as structure-from-motion [4,[START_REF] Pollefeys | Self-calibration and metric reconstruction inspite of varying and unknown intrinsic camera parameters[END_REF]. Such a model could be estimated by finding the calibration Π and a set of 3D points x whose projections in the images are as close as possible from the original observations. If we consider a Gaussian noise model in the observation, maximizing this likelihood naturally leads to minimizing the geometric error between the projection of the 3D points and their corresponding 2D measurements (e.g. , 2D feature positions) to refine both the camera parameters and a sparse reconstruction in a single framework. This is known as Geometric Bundle Adjustment (BA) [START_REF] Triggs | Bundle adjustment -a modern synthesis[END_REF][START_REF] Lourakis | SBA: A Software Package for Generic Sparse Bundle Adjustment[END_REF], and has been successfully applied to various sparse 3D reconstruction scenari, mostly minimizing a Geometric Reprojection Error:

E(x, Π) = i f i (x, Π) 2 ,
where f i is the geometric error between observation i and the projection of the 3D point into the image.

In contrast, an alternative way is to directly consider the maximum likelihood of the generative model described in Equation [START_REF] Aubry | Decoupling photometry and geometry in dense variational camera calibration[END_REF], by finding a model that best explains the observed images. In this case, the observed data no longer consists of extracted features like in the case of GBA, but directly comes from the image measurements. In computer vision, this typically corresponds to intensity values of a color image, but the concept naturally generalizes to any 2dimensional signals coming from vision sensors. p(I|Ω) is typically derived from an image noise model, and is often represented as a Normal (or Gaussian) distribution function, e.g. p(I|Ω) ∝ i p e -(Ii(p)-R S,Π i (p)) 2 , where 1 R S,Πi (p) is the intensity pixel value induced by the generative model for image i. The reconstruction problem can naturally be formulated as minimizing the following "photometric" energy functional [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF][START_REF] Faugeras | Variational-principles, surface evolution, pdes, level set methods, and the stereo problem[END_REF][START_REF] Gargallo | Minimizing the reprojection error in surface reconstruction from images[END_REF][START_REF] Soatto | Tales of shape and radiance in multi-view stereo[END_REF]:

E(Ω) = i Ii 1 2 I i (p) -R Ω,i (p) 2 dp , ( 2
)
where dp is the area measure on the image i. In the rest of the paper, we omit the dependency on i since this is just a sum over all available images. Note that, in contrast with GBA, the error measure between the predicted pixel values and the observed ones is carried out over all pixels of all input images. Instead of the geometric information only (i.e. extracted image feature positions), this paper aims at accounting for the photometric information, referred to as photometric bundle adjustment (PBA).

Related Work

In recent decades, dense geometry recovery has lead to a large number of efficient techniques in order to obtain dense and accurate 3D models, e.g. see [START_REF] Seitz | A comparison and evaluation of multi-view stereo reconstruction algorithms[END_REF][START_REF] Strecha | On benchmarking camera calibration and multi-view stereo for high resolution imagery[END_REF] for a comparison of recent approaches in the context of multi-view stereo. While some algorithms are based on dense features or patches [START_REF] Furukawa | Accurate camera calibration from multi-view stereo and bundle adjustment[END_REF] others are based on energy minimization techniques. Among those techniques, variational methods have become popular. They differ from the kind of energy they minimize, the way they minimize it or the surface representation they choose. For example [START_REF] Pons | Multi-view stereo reconstruction and scene flow estimation with a global image-based matching score[END_REF] uses the Level Set framework using a global image score, [START_REF] Kolev | Continuous global optimization in multiview 3d reconstruction[END_REF] uses a convex formulation minimizing a photometric error defined over a discretized grid. In [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF] and [START_REF] Vu | High accuracy and visibility-consistent dense multiview stereo[END_REF], a mesh refinement technique is proposed, minimizing a photometric cost measure. While all those methods return good results in recovering the 3D shape, only a few of them address the problem of camera calibration from dense data. In the following, we describe related work regarding efforts in joint calibration/geometry estimation focusing on the resolution of reprojection error functionals, i.e. Equation [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF].

Calibration and Dense Geometry Estimation

It is well established that 3D reconstruction and camera estimation are tightly linked together, bundle adjustment problems being a good example of how calibration can be improved by jointly estimating the 3D structure and the camera parameters. Surprisingly, until recently, dense surface reconstruction was only considered as a next and/or independent step from the calibration problem. It would be more elegant if one could directly minimize the photometric reprojection error to estimate both shape and camera parameters (and eventually the scene radiance) at the same time.

Georgel et al. [START_REF] Georgel | A unified approach combining photometric and geometric information for pose estimation[END_REF] propose a unified framework to combine both the geometric and photometric information. As both terms are not homogeneous, it is not clear how to combine and weight them efficiently. In this work, we propose to use the photometric information only, assuming an initial calibration is already provided. It is also worth mentioning the work of [START_REF] Furukawa | Accurate camera calibration from multi-view stereo and bundle adjustment[END_REF], which estimates 3D oriented patches, and then minimizes the reprojection error to refine both patches and camera parameters. They show substantial improvements in accuracy for 3D reconstruction, hence showing a photometric-based refinement of the calibration is necessary for high quality multi-view stereo. Both [START_REF] Georgel | A unified approach combining photometric and geometric information for pose estimation[END_REF] and [START_REF] Furukawa | Accurate camera calibration from multi-view stereo and bundle adjustment[END_REF] assume the surface can be represented by planar local patches. Here, we represent the surface as an arbitrary triangular mesh. Real-time structure-from-motion is also possible by using dense tracking and mapping [START_REF] Newcombe | Dtam: Dense tracking and mapping in real-time[END_REF]. In [START_REF] Newcombe | Dtam: Dense tracking and mapping in real-time[END_REF], the authors use a dense photometric cost to refine the camera poses. Our model extends naturally to intrinsic calibration.

Recently, several authors have been interested in addressing the problem of improving both the calibration and the dense reconstruction in the context of minimizing an energy functional of the type [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF]. The work in this paper is closely related to the ones described in [START_REF] Unal | A variational approach to problems in calibration of multiple cameras[END_REF][START_REF] Yezzi | Structure from motion for scenes without features[END_REF]. In these papers, the authors propose to refine the calibration in the context of multi-view modeling using a variational approach. In [START_REF] Unal | A variational approach to problems in calibration of multiple cameras[END_REF], only the calibration is optimized, and the equations are derived in the context of uniformly colored shapes. Therefore, it is not possible to refine the camera parameters if a segmentation of the object or the visual hull is not available and does not fall into "binary" images. Similarly, [START_REF] Yezzi | Structure from motion for scenes without features[END_REF] also only works for uniformly colored objects. Instead, we propose a generalization of [START_REF] Unal | A variational approach to problems in calibration of multiple cameras[END_REF] and [START_REF] Yezzi | Structure from motion for scenes without features[END_REF] to deal with textured and more complex objects.

Aubry et al. [START_REF] Aubry | Decoupling photometry and geometry in dense variational camera calibration[END_REF][START_REF] Goldluecke | A super-resolution framework for high-accuracy multiview reconstruction[END_REF] proposes a different approach. Without solving the problem in a direct way, they relax the problem between correspondence estimation and camera calibration. They decouple the minimization by first estimating the optical flow between a generated image and the observed one, and then refine the camera poses. The process is iterated using a fixed geometry. While this alternate process allows faster convergence and reduce local minima, unlike [START_REF] Aubry | Decoupling photometry and geometry in dense variational camera calibration[END_REF][START_REF] Goldluecke | A super-resolution framework for high-accuracy multiview reconstruction[END_REF], we directly solve for both the calibration and the 3D reconstruction in a single framework by directly minimizing the reprojection error. While the underlying energy functional is similar, the proposed optimization is fundamentally different as the parameters (Mesh, Cameras and Texture) are optimized jointly in a single framework, and do not use separate independent steps.

Visibility

One of 3D reconstruction's (and more generally computer vision) most challenging problems is the visibility information. While most techniques deal with visibility more or less explicitly (usually as fixed function updates between iterations), very few of them consider the visibility variation in their formulation. Some consider additional terms such as ballooning terms or silhouette constraints. However, the correct minimization of Equation ( 2) already contain terms that avoid the empty set to be the optimal solution.

Yezzi and Soatto [24] use the concept of oriented visibility, which implicitly constrains the minimization to make it consistent with the image silhouettes. However their work is limited to convex shapes, and while there is no need for additional constraints during the evolution of the surface, it does not handle self occlusions. Gargallo et al. [START_REF] Gargallo | Minimizing the reprojection error in surface reconstruction from images[END_REF][START_REF] Gargallo | Contributions to the Bayesian approach to Multi-view Stereo[END_REF] generalized this idea to non-convex surfaces in the framework of Level-Sets. Delaunoy and Prados [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF] extend this concept to discrete polyhedral surfaces, allowing to constrain mesh-based evolution. However, none of the above techniques deal with camera calibration and focus on 3D reconstruction only. In this work, we build on [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF] to account for visibility when cameras parameters are optimized as well.

The visibility issue while refining the calibration is partially solved in [START_REF] Unal | A variational approach to problems in calibration of multiple cameras[END_REF]. However, similarly as in [24], the additional constraint only accounts for silhouette points, and is only valid for convex shapes. We extend this to arbitrary shapes and derive a similar strategy as in [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF].

Contribution

In this paper we focus on the last stage of the 3D modeling pipeline, i.e. the dense reconstruction using a similar model as [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF][START_REF] Goldluecke | A super-resolution framework for high-accuracy multiview reconstruction[END_REF]. We propose to jointly refine the dense geometry and the camera parameters using the photometric error. This error is simply the reprojection error between images of a generative model and the observed images which is directly minimized in the image domain (Equation 2). In order to achieve that goal, we derive equations of the gradient of the energy functional we minimize, accounting for visibility changes [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF][START_REF] Gargallo | Minimizing the reprojection error in surface reconstruction from images[END_REF]24]. The shape is represented as a triangular mesh, allowing an easier handling of the texture which is also jointly optimized.

In this work, we propose a direct pixel-based bundle adjustment minimization of the photometric reprojection error in order to jointly optimize the full and dense 3D shape as well as the camera parameters and the scene radiance (the texture) by exploiting an image-based reprojection error.

Full BA: Problem Formulation

We propose to refine the scene Ω(S, Π) from some initial scene Ω 0 , parametrized by its surface S and calibration Π. While this section describes a variational formulation that is valid for general generative scene models (including depth map integration, shape-from-shading, photometric stereo, etc), Section 3 focuses on the case of a Lambertian scene reconstructed with a generative model including texture, shape and camera parameters.

Functionals Defined on Visible Surfaces

Equation ( 2) is minimized on the whole image. However, in order to generate R Ω,i , one needs to consider the background B, in order to explain parts of the images where the surface of interest to be modeled does not project into the images. Equation ( 2) becomes (see [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF]):

E(S, Π) = Π(S) I -R S,Π 2 + Ii-Π(S) I -B 2 = Π(S) I -R S,Π 2 -I -B 2 + I I -B 2 .
(3) Minimizing the data fidelity term of Equation ( 3) is rather difficult and similarly to previous works we use a gradient descent strategy [START_REF] Gargallo | Minimizing the reprojection error in surface reconstruction from images[END_REF][START_REF] Soatto | Tales of shape and radiance in multi-view stereo[END_REF]24]. This is due to the fact that the generative model (mostly the projection and occlusions created by the surface) implicitly accounts for visibility. It is then important to know how the updates on the scene parameters affect the changes in visibility. This function is illustrated in Figure 1. Let ν S,Π (x) be the visibility function ν S,Π : R 3 → [0, 1] such that:

ν S,Πi (x) = 1 if x is visible from the camera i, 0 otherwise. (4)
In order to minimize Equation (3), let us first rewrite the equation over the (visible) surface. Note that the second term is constant and can be left out in the minimization. Denoting the part in brackets by f Ω , this gives, by a simple change of variables [START_REF] Soatto | Tales of shape and radiance in multi-view stereo[END_REF]24]:

E(S, Π) = S∪B f Ω (x, n(x)) α • n ν S (x) ds , (5)
where we have

dp = f x f y d • n d 3 z ν S (x)
ds for a pinhole camera model, e.g. see [START_REF] Soatto | Tales of shape and radiance in multi-view stereo[END_REF]. f x and f y are the focal parameters in x and y respectively, n is the surface normal at point x and d is the vector pointing from the camera center to x. B is the background surface (either a previously estimated surface or a plane behind the object of interest). This generalizes to other parametric camera models. In the following

we denote α = f x f y d d 3 z .

Variational Refinement of the Surface

The choice of the surface representation is rather important and conditions the rest of the minimization. We choose a triangular mesh as it was recently proven to give accurate and impressive results [START_REF] Vu | High accuracy and visibility-consistent dense multiview stereo[END_REF]. It also has the advantage to move vertices at their correct location as the final gradient flow is allowed to have tangential components in the evolution of the vertices, and to provide a manifold watertight mesh, suitable for further processing or applications.

Similarly as in [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF][START_REF] Vu | High accuracy and visibility-consistent dense multiview stereo[END_REF], we follow a discretize then minimize strategy by discretizing the energy functional over polyhedral representation X of the surface S. Let X = {x 1 . . . x n } be a piecewise planar triangular mesh, x k being the k th vertex of X, and let S j be the j th triangle of X. The energy functional (2) we finally minimize is:

E(X, Π) = j A j T f Ω (x(u)) α(u) • n j ν S (x(u)) du , (6)
where n j is the normal of the triangle S j parametrized by u of surface area A j and where the sum is over all the triangles of the mesh X. Over each triangle, points are parametrized using barycentric coordinates u

= (u, v) ∈ T = {(u, v)|u ∈ [0, 1] and v ∈ [0, 1 -u]}.
The term du = 2 A j ds corresponds to the surface area element on the triangle. In the following, in order to simplify notations, we omit the dependency in u.

In order to compute the gradient of Equation ( 6), we consider the evolution of the energy under a small evolution of the surface X[t] = X 0 + tV, where V is a vector field defined on all the vertices x of the mesh X. The directional derivative of E(X), i.e. d dt E(S[t]) t=0 is used to compute the final gradient of the energy E(X). The mesh evolution equation is given by the following L 2 gradient descent flow:

   X[0] = X 0 , X[t + 1] = X[t] -dt M -1 ∂E ∂X (X[t]) , (7)
where X 0 is an initial mesh and M is the mass matrix containing the area around a particular vertex. This means that the velocity of one particular vertex depends on the integrated cost on neighboring facets, hence allowing consistent vertex displacements. This gradient descent scheme contains typically two elements: one corresponding to occluding contours, and one for the vertices that do not make strong changes in the visibility. This second part of the gradient typically describes the gradient of vertices on the occluding contours (called the horizon term). The way visibility changes at occluding contours is illustrated in Figure 2 and we follow the gradient computations detailed in [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF].

Camera Refinement

We now consider the same energy functional as a function of the camera parameters Π. We consider a standard pinhole camera model, and parametrize π using a set of parameters (g i ), accounting for the intrinsics (focal, skew parameter and principal point) and extrinsics of the camera.

The extrinsics are the rotation R(ω) and translation in SE(3) that are parametrized using an angle-axis representation for the rotation ω, and the optical center of the camera C. It is worth to mention that among the calibration parameters, only the camera center induces changes in the visibility function ν S,Π . Figure 2 gives a geometric intuition of what is happening to the visibility interface during the optimization. For a rotation update, the gradient of the visibility function is zero. The camera updates are computed using the following partial differential equations:

∂E(X, Π) ∂Π = j A j T ∂ ∂Π f Ω (x) α • n j ν S (x) du . ( 8
)
The resolution of Eq. ( 8) implies classical derivations and standard chain rules and follows similar strategies as described in [START_REF] Goldluecke | A super-resolution framework for high-accuracy multiview reconstruction[END_REF][START_REF] Unal | A variational approach to problems in calibration of multiple cameras[END_REF]. For the visibility gradient on the camera center, we first rewrite Eq. ( 8) as an energy over the volume. We derive how the energy changes when moving the camera similar as for the horizon term in the mesh optimization [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF]. The difference is on the volume parametrization which in this case follows the shape in Fig. 2. In practice, this term has less influence as it is computed over the whole image and most points are not on occluding contours.

While we focus on classical pinhole camera intrinsics and extrinsics, we could add more complete calibration models by adapting α and its associated derivatives.

Multi-view Stereo Application

In multi-view stereo, the generative model of a scene Ω depends not only on the surface shape and camera parameters, but also on the scene radiance, i.e. the texture of the surface. Let T : R 2 → R 3 be the texture map to optimize. Let the mesh X be the mesh representation of the surface S(X, T). The associated generative model can be defined as R Ω,i (p) = T (Π -1 i,S (p)), where T is the Lambertian texture of the surface. Π -1 S (p) is the back-projection of pixel p onto the surface if it exists, or onto the background B otherwise. The energy we minimize in this context is very similar to reprojection errors used in other related works [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF][START_REF] Gargallo | Minimizing the reprojection error in surface reconstruction from images[END_REF][START_REF] Goldluecke | A super-resolution framework for high-accuracy multiview reconstruction[END_REF]:

E(X, T, Π) = i Ii 1 2 I i (p) T (Π -1 i,X (p)) 2 dp , (9)

Geometry, Calibration and Texture Recovery

Similarly as in the previous section, we minimize the following energy defined over the surface: [START_REF] Kolev | Continuous global optimization in multiview 3d reconstruction[END_REF] which is minimized as previously described. The only difference is that the sampling of the residuals (the numerical integration over the triangles) is performed on the texture space rather than the triangles directly. This allows us to control the sampling and make sure it is coherent with the image resolution (details in the experimental section).

E(X, T, Π) = j A j T (I i (Π i (x(u))) -T (u)) 2 α • n j ν S (x(u)) du,
A natural shape prior is to penalize non-smooth surfaces. Instead of minimizing the surface area which introduces bias towards minimal surfaces, one may add a smoothness term to penalize variations on the surface normals. This can be achieved by minimizing the following energy functional:

E reg (X) = λ S j A j T |n j -h j | 2 du, (11)
where h j is an unit vector. Typically h j is the average normal on a local neighborhood around the facet j. λ S is a smoothing parameter. Similarly as in [START_REF] Vu | High accuracy and visibility-consistent dense multiview stereo[END_REF], we weight the data term by the squared ratio between the average image depth and the focal length in order to get the energy homogeneous in squared world units, hence having a smoothness parameter stable across different datasets.

Texture Estimation

As mentioned above, T : S → R 3 is the estimated radiance on the surface. An obvious choice for the texture T (x) is the closed form solution of Equation (10):

T (x) = i I i (Π i (x)) w i (x) i w i (x) . (12)
T (x) corresponds to the weighted mean color at point x of the images where x is visible. We have w i (x) = α • n j ν S (x(u)). Since we want to minimize X, T, Π at the same time, we use the following texture evolution:

T t+1 (u) = T t (u) + dt i (I i (Π i (x(u))) -T t ) w i (x) .
(13) While one could plug Equation ( 13) directly in Equation ( 9) and get rid of the texture, handling the texture separately offers significant advantages. For example, it becomes necessary if one wants to optimize more complete reflectance models (albedo, specular coefficient, etc), or want to add more realistic image formation models.

Experiments and Results

The proposed photometric bundle adjustment approach is evaluated on several publicly available datasets. We show improvements not only on the dense 3D geometry, but also in the estimated texture of the surface.

The algorithm has been implemented in C++ and is running on a standard 3GHz Linux machine. We use the GPU (using OpenGL Shading Language) for computing visibility by rendering depth maps and for computing parts of the gradient. In the following, the rendering of the shape is displayed with flat shading on the facets.

Initialization The initial calibration Π 0 is assumed to be given, either by a pre-calibrated multi-view setup, or after classical structure-from-motion. For the geometry estimation, we first apply the same algorithm described in this paper without the camera parameters updates. Then the PBA is performed by optimizing all parameters, X, Π and T.

Texture mapping and super-resolution In order to efficiently handle the texture, a texture atlas is generated. This allows easier access to neighboring texture values of a given point in order to easily compute gradients over the texture.

First, a labeling of each facet based on camera visibility information is computed, by finding the best frontal camera. In order to favor larger texture segments, a graph cut is performed on the mesh using alpha expansion. This gives a facet to camera mapping. The visible facets are projected on the corresponding images, and those coordinates are used for the texture mapping. This allows us to obtain a texture sampling coherent with the image resolution. Texture intensity values are computed by using Equation [START_REF] Lourakis | SBA: A Software Package for Generic Sparse Bundle Adjustment[END_REF].

During the optimization, a coarse to fine strategy is also used in order to avoid local minima. This includes dealing with the resolution of the images, the resolution of the mesh and the resolution of the estimated texture. We make sure that the resolution of the texture is higher than the sampling over each triangle so that we have at least a few residual samples per triangle (the texture sampling is consistent with the input image resolution by construction of the texture map). By choosing a higher texture resolution, we can improve the texture estimation. This actually corresponds in performing super-resolution with a simple bilinear convolution kernel which is naturally handled in our case. We could straight-forwardly extend this concept to arbitrary convolution kernels [START_REF] Goldluecke | A super-resolution framework for high-accuracy multiview reconstruction[END_REF] without changing our approach.

Remeshing In order to avoid self-intersections during the mesh optimization, we use the topology-adaptive meshes described in [START_REF] Pons | Delaunay deformable models: Topology-adaptive meshes based on the restricted delaunay triangulation[END_REF]. Keeping track of the texture optimization while remeshing is rather difficult. To simplify the algorithm, the texture is reinitialized after remeshing using Equation [START_REF] Lourakis | SBA: A Software Package for Generic Sparse Bundle Adjustment[END_REF]. In practice we remesh every 20 iterations. We first evaluate our approach on synthetic data. It consists of 24 images of an imbricated cube and ball with Lambertian texture. We add Gaussian noise on the camera poses. We first run the baseline method without the camera updates (standard multi-view stereo) from the noisy data (starting from a simple sphere), and then we run the PBA. See Figure 3 for results. In this experiment, the algorithm converges in 300 iterations in about 30 minutes. Note that minimizing a discrete energy over a triangular mesh with a coherent gradient descent flow allows vertices to move in their correct location, and allows to preserve sharp edges which most previous methods are not able to achieve.

Pose and Shape Estimation

We evaluated on the classical Middlebury Temple and Dino datasets (See Figure 4). The accuracy is improved in both datasets, showing the advantage of jointly estimating the geometry and the calibration. Our approach is compara- ble to the state-of-the-art, and visually looks more appealing than some of the best methods as some details are nicely visible. For example holes in the columns are correctly reconstructed where many methods tend to oversmooth the surface. Similarly as described in [START_REF] Aubry | Decoupling photometry and geometry in dense variational camera calibration[END_REF][START_REF] Furukawa | Accurate camera calibration from multi-view stereo and bundle adjustment[END_REF], we observe an improvement in both accuracy and completeness due to the camera refinement (See results Table 1). Fig 5 shows an additional results of a statue in the Rietberg Museum, Zurich, where we initialize the camera calibration with structurefrom-motion [START_REF] Zach | Practical methods for convex multi-view reconstruction[END_REF][START_REF] Zach | V3D[END_REF] and compute an initial mesh via [START_REF] Labatut | Efficient multi-view reconstruction of large-scale scenes using interest points, delaunay triangulation and graph cuts[END_REF]. Then we use the PBA approach described in this paper.

Intrinsics Estimation

Similarly as before, we used the same simulated data and added a Gaussian noise to all camera parameters, this time including the intrinsics as well (focal length and principal point). Results are shown in Figure 6.

Figure 7 shows results on a publicly available dataset [START_REF] Kolev | Anisotropic minimal surfaces integrating photoconsistency and normal information for multiview stereo[END_REF], were we tested our PBA using all parameters. While the intrinsic calibration does not change for most of the images, two views (namely #9 and #20) have a particularly wrong focal length. For the bird data, before the camera refinement with the baseline method (see Figure 8), the reprojection error is 3.2707 (average error per point on the surface in term of intensity values). After the photometric bundle adjustment, the reprojection error drops to 2.1359.

Perspectives

Even though the minimized error is rather simple (per pixel squared error), we are able to achieve high quality reconstructions comparable to previous techniques using more robust cost measures. While some parts of the surface contain flaws, we believe those problems come from the presence of local minima mostly due to non-Lambertian surfaces or matching ambiguities. A robust image similarity measure ( [START_REF] Vu | High accuracy and visibility-consistent dense multiview stereo[END_REF]), or taking more parameters in the camera calibration (geometric distortions, radiometric models) would probably improve the reconstruction. However it is clear that the reprojection error is reduced showing significant improvements on the reconstructed surface and texture.

Conclusion

A dense image-based photometric bundle adjustment is presented, minimizing the reprojection error between a generated image and an observed image. The error is a simple image error motivated by a Bayesian vision of the multiview reconstruction problem. It jointly refines the geometry (mesh) and calibration, leading to notable improvements both in the reconstructed geometry and the estimated texture on several datasets. The discrete gradient descent flow allows vertices to be moved at their correct location and to preserve surface edges (as in [START_REF] Delaunoy | Gradient flows for optimizing triangular mesh-based surfaces: Applications to 3d reconstruction problems dealing with visibility[END_REF][START_REF] Vu | High accuracy and visibility-consistent dense multiview stereo[END_REF]). This paper is a first and necessary step towards full dense multi-view bundle adjustment problems dealing with more complete generative models such as convolution or radiometry (reflectance, illumination), and can straight-forwardly be applied to any generative approaches dealing with multi-view reconstruction settings minimizing reprojection errors (i.e. multi-view range maps integration, multi-view photometric stereo).

Figure 1 .

 1 Figure 1. 3D surface S seen from a camera showing visible and occluded volumes. Only the visibility interface ∂νS can be explained the images.

Figure 2 .

 2 Figure 2. Left: Original discrete mesh and its visibility interface; Middle: Change of the visibility interface when moving a vertex of the mesh X [2, 7]; Right: Influence of camera center update on the horizon. Moving points on occluding contours or moving the camera center drastically changes the visibility function.

Figure 3 .

 3 Figure 3. Evolution of the minimization at different iterations on a synthetic data (24 images of 640 × 480). From top to bottom: 5 of the input images; 3D triangular mesh X; Photometric reprojection error; Textured mesh using the estimated texture T.

Figure 4 .

 4 Figure 4. Results on the Middlebury stereo benchmark [18]. for DinoRing and TempleRing data (47 images) before (Left) and after (Right) the refinement with the proposed PBA method.

Figure 5 .

 5 Figure 5. "Seated Bodhisattva" (50 images). Textured (mid.) and shaded (right) reconstructed surface with the proposed refinement.

Figure 6 .

 6 Figure 6. Results on PBA with both intrinsics and extrinsics refinement (estimated mesh, reprojection error and estimated texture, respectively). Left: Initial shape estimated without calibration refinement; Right: result of our PBA method.

Figure 7 .

 7 Figure 7. Bird shape (21 images) from [11]. Top: reconstructed surface and texture map. Bottom: details (3D geometry, color coded surface normals, textured mesh, reprojection error).

Table 1 .

 1 Temple Sparse Ring(16 images) Temple Ring (47 images) Dino Ring (48 images) accu.(mm) compl.(%) photo.err. accu.(mm) compl.(%) photo.err. accu.(mm) compl.(%) photo.err. Numerical evaluation of the proposed method for Middlebury Dino and Temple data sets[START_REF] Seitz | A comparison and evaluation of multi-view stereo reconstruction algorithms[END_REF] (Baseline: Multi-view stereo without calibration; Proposed: Same as before with calibration -Photometric Bundle Adjustment)). The table shows accuracy at 90% and completeness at 1.25mm, and err, the mean photometric reprojection error (in term of intensity values).

	Baseline	0.78	96.2	5.3238	0.59	99.0	5.8669	0.51	97.2	1.7154
	Proposed PBA	0.7	96.6	3.6024	0.51	99.1	3.7566	0.51	98.7	1.0863

Acknowledgements We gratefully acknowledge the support of the 4DVideo ERC Starting Grant Nr. 210806. We would like to thank [11,18] for sharing data, and in particular D. Scharstein for the Middlebury evaluation [18].


Olivier Cailloux
email: olivier.cailloux@ulb.ac.be

Nicolás González-Deleito

Olivier Markowitch
email: olivier.markowitch@ulb.ac.be

FAIRNESS IN CERTIFIED ELECTRONIC MAIL

Keywords: computer security, certified email, security protocols, network security

The growing use of the Internet promotes the replacement of traditional manual transactions by equivalent electronic services. Research was carried out to investigate enhanced services related to electronic mail. This paper points out that a certified email protocol has to provide the sender of a certified email with an evidence that this email has been either received or refused by its recipient, and proposes a new definition of the fairness property, specific to the certified email field. Finally, a new efficient certified email protocol respecting this property is presented.

Introduction

The development of the Internet is increasingly promoting the replacement of traditional manual transactions by equivalent electronic services. In the traditional certified mail service, a postman physically ensures that a message is exchanged for a signed receipt of this message. The postman delivers the mail to the recipient only after the latter has signed a receipt, and the recipient is sure that once he has signed the receipt he will receive the mail. In an electronic environment, this exchange process is not trivial. If we use techniques classically used in the traditional mail environment, we may face one of the following problems. On the one hand, if Bob receives an email from Alice, after having read it he would have the ability to decide whether to acknowledge the receipt of the email or not. On the other hand, if we ask Bob to send a receipt before Alice sends the email, Alice would get the receipt allowing her to claim that Bob received the email and would have thus the ability to decide whether to send the email or not.

In order to overcome these two problems, several specialised exchange protocols have been proposed during the last decade. Informally, in these two-party exchange protocols two entities want to exchange one or several items for one or several other items in such a way that, at the end of the protocol, either both parties get their expected items, or neither get any valuable information [1,[START_REF] Asokan | Fairness in Electronic Commerce[END_REF][START_REF] Markowitch | On fairness in exchange protocols[END_REF]. This property is called fairness. Until now, certified email protocols were considered as a particular instance of two-party fair exchange protocols, in which an email is exchanged for an evidence of its correct receipt. However, we suggest here to require that, even in the presence of dishonest recipients, an exchange must always take place, allowing therefore the sender to receive either an evidence attesting that the email was received, or an evidence attesting that the email was refused.

There are many ways to realise a fair exchange protocol. The most practical solutions make use of a trusted third party (TTP) that helps the protocol to always end in a fair way. Depending on its involvement, a TTP can be classified as follows [START_REF] Menezes | Handbook of applied cryptography[END_REF]. If it is used in each step of the protocol [START_REF] Bahreman | Certified electronic mail[END_REF][START_REF] Coffey | Non-repudiation with mandatory proof of receipt[END_REF][START_REF] Zhou | Certified electronic mail[END_REF], the TTP is said to be inline. If the TTP is used in each protocol run but not necessarily in each step [START_REF] Robert | Practical protocols for certified electronic mail[END_REF][START_REF] Zhang | Achieving non-repudiation of receipt[END_REF]1,[START_REF] Schneier | A certified e-mail protocol[END_REF], the TTP is said to be online. Finally, if the TTP intervenes in the protocol only in case of problems between Alice and Bob (for example if Alice or Bob tries to cheat, or if a communication fails at a crucial moment) [START_REF] Micali | Simultaneous electronic transactions[END_REF][START_REF] Zhou | An efficient non-repudiation protocol[END_REF][START_REF] Asokan | Fairness in Electronic Commerce[END_REF][START_REF] Ateniese | TRICERT: A distributed certified e-mail scheme[END_REF][START_REF] Kremer | Selective receipt in certified e-mail[END_REF], the TTP is said to be offline.

In this paper, we discuss in section 2 the existing properties related to certified email protocols. We point out that this kind of protocols have to provide the sender of a certified email with an evidence that this email has been either received or refused by its receipient, and we propose a new definition of fairness dealing with the case (curiously neglected in the literature) where Bob is reluctant to accept an incoming certified email. In section 3 we discuss on the required quality of the underlying communication channels, and in section 4 we compare some well-known certified email protocols on the basis of the discussion provided in section 2. Finally, we propose in section 5 a realistic and efficient protocol that respects all the properties that we show a certified email protocol should satisfy.

Properties

Classical properties

Before reviewing and discussing the different properties that a certified email protocol should respect, let us first define the main types of evidences that are commonly exchanged during a successful protocol run [START_REF] Zhou | Certified electronic mail[END_REF]. Through the paper we will call Alice the sender of a certified email, and Bob the intended recipient. Moreover, we will denote by m the email that Alice aims to send to Bob.

An evidence of submission is a proof that Alice has tried to send m to Bob. An evidence of receipt is a proof that Bob has received m. An evidence of origin is a proof that Alice is at the origin of m. Providing this last evidence is sometimes considered as optional, since it is rarely provided in the traditional certified postal mail system.

The exchanged evidences can be used during a dispute resolution protocol that can possibly take place after the execution of the certified email protocol, if an entity claims that the exchange succeeded while the other entity does not agree. During this dispute resolution protocol, an adjudicator evaluates the evidences produced throughout the certified email protocol and, depending on the result, accepts or rejects the claim [1,[START_REF] Kremer | An intensive survey of fair non-repudiation protocols[END_REF].

On the other hand, several properties are usually considered as mandatory in the literature on certified email protocols. The first one is fairness [1,[START_REF] Asokan | Fairness in Electronic Commerce[END_REF][START_REF] Markowitch | On fairness in exchange protocols[END_REF].

Property 1 A certified email protocol is said to be fair if and only if at the end of a protocol execution either (1) Alice has received her expected evidence of receipt and Bob has received m (as well as the possibly corresponding evidence of origin), or (2) Alice has not received her evidence of receipt and Bob has not received any information regarding m (nor the possible evidence of origin).

Another essential property, sometimes silently neglected, is timeliness [START_REF] Markowitch | On fairness in exchange protocols[END_REF].

Property 2 A certified email protocol respects the timeliness property if and only if each honest participant is always able to reach, in a finite amount of time, a point in the protocol where he can stop the protocol without losing fairness.

The viability property [START_REF] Markowitch | On fairness in exchange protocols[END_REF] guarantees that the considered protocol achieves its goal. Property 3 A certified email protocol is viable if there exists at least one possible protocol execution in which the exchange of an email (and the possibly corresponding evidence of origin) for an evidence of receipt of this email succeeds.

Finally, an important property, not always considered mandatory, is the dated receipt property (also known as temporal authentication [START_REF] Blundo | Certified email: Design and implementation of a new optimistic protocol[END_REF]). It allows Alice to prove that Bob received a certified email at a given moment in time, preventing therefore a dishonest Bob from claiming not to have received this email at that time.

Property 4 A certified email protocol provides the dated receipt property if and only if at the end of a protocol execution Alice obtains a time evidence allowing her to prove (with a bounded imprecision) the moment at which the receipt (or denial, cf. subsection 2.2) of m by Bob took place (or nothing if Bob did not have the possibility to receive m).

Evidence of denial and fairness

When we compare the certified mail service provided by the post to existing certified email protocols, we notice that the latter do not offer Alice any strong evidence if Bob refuses to receive an email. Some protocols deliver an evidence of submission [START_REF] Bahreman | Certified electronic mail[END_REF] issued by the TTP, proving that Alice has tried to send the email. Other protocols use evidences such as a report of delivery [START_REF] Zhou | Certified electronic mail[END_REF], which is only delivered if Bob accepts the email. In all cases, they are not intended to allow Alice to prove that the email has not been delivered because of Bob's unwillingness to receive this email. To the best of our knowledge, this important problem has never been considered before in the literature [START_REF] Bahreman | Certified electronic mail[END_REF][START_REF] Micali | Simultaneous electronic transactions[END_REF][START_REF] Robert | Practical protocols for certified electronic mail[END_REF][START_REF] Zhou | Certified electronic mail[END_REF][START_REF] Schneier | A certified e-mail protocol[END_REF][START_REF] Ateniese | TRICERT: A distributed certified e-mail scheme[END_REF][START_REF] Kremer | Selective receipt in certified e-mail[END_REF][START_REF] Blundo | Certified email: Design and implementation of a new optimistic protocol[END_REF][START_REF] Galdi | Certified email with temporal authentication: An improved optimistic protocol[END_REF].

Consider the scenario where a landlady Alice sends a certified email to a tenant Bob not paying the rent of his flat. Bob could refuse any email from Alice and, during a dispute where she claims to have reminded Bob to pay the rent, Bob could claim to not have received any notification from her, due, for example, to a network failure. Usually, contrary to the traditional certified mail service, Alice will not receive here an evidence that Bob refused the email and will not be able to prove Bob's misbehaviour during a dispute. We think that certified email protocols should offer such kind of evidences when Bob refuses to receive an email. This behaviour is not considered in the existing literature because certified email protocols are traditionally considered as being fair exchange protocols. Fair exchange protocols are often used to exchange a purchase against a payment or to exchange digital signatures on a contract. As all the participants are assumed to be willing to perform the exchange, it usually does not make sense in this context for a participant to refuse an item. Therefore, in addition to the evidence of receipt, we need another evidence that will allow a more precise understanding of how a protocol execution has ended.

We define thus an evidence of denial as a proof that Bob has refused to receive m. Consequently, the definition of fairness needs to be modified in order to take into account the need for this new evidence. Property 5 A certified email protocol is said to be fair if and only if at the end of a protocol execution either (1) Alice has received her expected evidence of receipt and Bob has received m (as well as the possibly corresponding evidence of origin), or (2) Alice has received an evidence of denial and Bob has not received any information about m (nor the possibly corresponding evidence of origin) because he did not want to take part in the protocol.

The no author-based selective receipt property defined by Kremer and Markowitch [START_REF] Kremer | Selective receipt in certified e-mail[END_REF] prevents Bob from deciding whether to accept or not an email from Alice on the basis of her identity. We point out that this property can be useful in a protocol respecting our new fairness definition, in order to increase the chance of obtaining an evidence of receipt instead of an evidence of denial.

Network quality

Some minimal hypothesis need to be made on the network quality to ensure the correct execution of any certified email protocol. The following communication channels are usually considered in the literature on fair exchange protocols: unreliable, for which no assumptions are made (the data sent through it may be lost); resilient, which correctly delivers the sent data after a finite, but unknown, amount of time (the sent data may be delayed, but will eventually arrive); and operational, in which the sent data correctly arrive before a known finite constant amount of time.

Our protocol assumes that the channels used between the TTP and Alice and between the TTP and Bob are operational. Indeed, if the message is sent using a channel that is not operational, then Bob can always argue, in case of a trial or a dispute resolution, that he has still not received the message that Alice sent him. Alice will not be able to prove that Bob has received her message, while a dishonest Bob has probably received it, thus resulting in an unfair situation. Although the Internet does not formally provide operational channels, we can assume, in the context of certified email protocols, that its bound on the messages' transmission delay is just much larger than what is usually considered to be an operational channel. In consequence, protocols may be based on an operational channel that does not require messages to reach their destination in less than a few seconds or a few minutes, but within hours or days. Therefore we propose in section 5 a new protocol that respects all the required properties, and that takes the day-based bound on the transmission time into account to satisfy the dated receipt property.

Protocols comparison

Several papers in the literature address specifically the certified email problem, either with an inline [START_REF] Bahreman | Certified electronic mail[END_REF][START_REF] Zhou | Certified electronic mail[END_REF], online [START_REF] Robert | Practical protocols for certified electronic mail[END_REF][START_REF] Schneier | A certified e-mail protocol[END_REF] or offline [START_REF] Micali | Simultaneous electronic transactions[END_REF][START_REF] Ateniese | TRICERT: A distributed certified e-mail scheme[END_REF][START_REF] Kremer | Selective receipt in certified e-mail[END_REF] trusted third party. We review in this section some relevant and well-known certified email protocols, by studying them in light of the properties defined in section 2. The choice has been made in order to focus on the most representative protocols out of the vast existing diversity.

A basic inline protocol with six message exchanges, and providing an evidence of submission to Alice, is presented by Bahreman and Tygar [START_REF] Bahreman | Certified electronic mail[END_REF]. Deng et al. [START_REF] Robert | Practical protocols for certified electronic mail[END_REF] use a protocol with an online TTP and four messages, where Bob has to obtain the expected email from a public directory managed by the TTP (instead of having the latter directly sending the email to him). Riordan and Schneier [START_REF] Schneier | A certified e-mail protocol[END_REF] use a public board, also on a four messages model. Zhou and Gollmann [START_REF] Zhou | Certified electronic mail[END_REF] propose a protocol with several trusted third parties, with the email going from one third party to the following in a chain. Micali [START_REF] Micali | Simultaneous electronic transactions[END_REF] is the first to propose an optimistic protocol, and this idea is modified by Ateniese et al. [START_REF] Ateniese | TRICERT: A distributed certified e-mail scheme[END_REF] to build a hybrid model, having some characteristics of the online model and some of the offline one. Kre-mer and Markowitch [START_REF] Kremer | Selective receipt in certified e-mail[END_REF] introduce the no author-based selective receipt property, preventing Bob from learning the sender's identity before sending the evidence of receipt, and propose an optimistic protocol respecting this property. Blundo et al. [START_REF] Blundo | Certified email: Design and implementation of a new optimistic protocol[END_REF] rely on an online time stamping server to provide the dated receipt property, and this protocol is improved by Galdi and Giordano [START_REF] Galdi | Certified email with temporal authentication: An improved optimistic protocol[END_REF].

As explained in section 2, most certified email protocols do not provide any evidence to Alice when Bob refuses the email. Only the Galdi and Giordano's protocol has been found to satisfy fairness (property 5). We are the first to define this property, but that protocol satisfies it as a side effect (to ensure timeliness). However, Galdi and Giordano use an online TTP (called a timestamping server, but that needs to be trusted), which is less efficient than the pure offline scheme that we propose in the next section.

The table presented below shows which properties these classical certified email protocols satisfy. As the authors do not always specify a sufficient network quality in order to provide fairness (or do not specify any network quality at all), we consider in this comparison that all the used communication channels are operational.

The properties considered in this table are timeliness (T), the delivery of an evidence of submission (EOS), the delivery of an evidence of origin (EOO), fairness in the sense of property 5 (F), dated receipt (DR), and the minimal number of messages needed for the exchange to succeed (Ex). indicates that the protocol satisfies the given property, × that the protocol does not satisfy it, and in, on and off denote respectively an inline, online and offline TTP. Every protocol considered in this table respects the viability property. [START_REF] Ateniese | TRICERT: A distributed certified e-mail scheme[END_REF] off / on b × × × × 5 KM [START_REF] Kremer | Selective receipt in certified e-mail[END_REF] off / on c × × × 4 BCDP [START_REF] Blundo | Certified email: Design and implementation of a new optimistic protocol[END_REF] off / on d × 6 GG [START_REF] Galdi | Certified email with temporal authentication: An improved optimistic protocol[END_REF] off / on d × 4 Ours off 3

Protocol TTP T EOS EOO F DR Ex

BT [5] in × × × 6 M [11] off × × × 3 DGLW [8] on × × × 4 ZG [7] in × × × 6 RS a [10] on × × × 4 AMG
a The non-optimistic version.

b This protocol is hard to classify because it uses two types of TTPs, one of them being offline and the other being inline or online.

c This protocol uses a structure ensuring anonymity that must be online. d This protocol uses two types of TTPs, one of them being offline and the other being online.

The protocol that we propose fulfils all the properties mentioned here and is efficient.

A certified email protocol

Before describing our protocol, let us first indicate the notations that we will use through this section. X → Y : i

Protocol 1 Main protocol 1. A → B : f EOO , A, B, TTP , label , h(m), h(k), t, E TTP (key), E k (m), EOO 2. B → A : f EOR , label , EOR 3. A → B : key Protocol 2 Recovery protocol for Bob 1. B o → TTP : f rB , A, B, TTP , label , h(m), h(k), t, E TTP (key), E k (m), EOO, EOR 2. TTP o → A : f EOR , label , EOR TTP o → B :
key denotes entity X sending information i to entity Y using an unreliable channel; X o → Y : i denotes X sending information i to Y using an operational channel; h(i) is the result of applying i to a one-way collision-resistant hash function h; E k (p) is the result of applying a symmetric encryption algorithm E to the plaintext p with the secret key k; E X (p) is the result of applying a (deterministic) asymmetric encryption algorithm E to the plaintext p with X's public key1 ; S X (i) denotes the digital signature (with appendix) of X on information i; and f x is a flag indicating the purpose of a message in a given protocol, where x identifies the corresponding message in that protocol.

Moreover, we assume that the correct public keys needed to verify the digital signatures produced during the protocol, and to asymmetrically encrypt sensitive information, have been obtained by the participants.

The protocol allows Alice and Bob to exchange the certified email for the corresponding evidence of receipt by themselves during a main protocol. If a problem occurs during this main protocol (due to a dishonest participant or a poor communication channel quality), the participants will be able to ask the help of the TTP in order to fairly end the protocol, by running their corresponding recovery protocol. We assume that the communication channel used between the TTP and Alice, as well as between the TTP and Bob, is operational, and we denote by delay o the maximal transmission delay on these channels.

When considering time bounds, we will use a particular value T MAX representing the time allowed to complete the main protocol. For example, a reasonable value for this constant could be five hours. We will also assume that there is a bound on the imprecision between a perfectly synchronised clock and the clock of each participant. Taking for example one hour as a bound ensures that it is possi-ble for the participants to synchronise their clocks without requiring any particular channel quality, e.g. listening to the radio is sufficient. For a better readability, we will not take into account in the protocol description these supplementary delays nor the different processing times, but it is easy to modify it accordingly.

Through all the three protocols a particular information, the label, is used to identify the protocol run. We define it [START_REF] Gürgens | On the security of fair non-repudiation protocols[END_REF] as label = h(A, B, TTP , h(m), h(k), t).

The main protocol (which is summarised by protocol 1) begins with Alice sending to Bob the email m ciphered with a session key k of her choice (at this step, Bob does not know yet this session key), the information key = (f key , label , k, S A (f key , A, B, label , k)) ciphered with the TTP's public key (needed in case of recovery), the hash values of the email and of the session key (needed to verify the label), the current date and time t, and her digital signature on these information, EOO = S A (f EOO , A, B, TTP , label , h(m), h(k), t, E TTP (key), E k (m)).

If the label is coherent with the information present in the message, if Alice's signature EOO is correct, and if t ≤ current time < t + T MAX, then Bob answers with his digital signature on the received information, EOR = S B (f EOR , A, B, TTP , label , h(m), h(k), t, E TTP (key), E k (m)). By doing so, he acknowledges having received the ciphered email from Alice.

Finally, if Bob's signature is correct, Alice sends him the session key k as well as her signature on it. Since Bob has the ciphered email and the corresponding session key, he is now able to derive the email m from E k (m).

If Bob does not receive the third message from Alice before time t+T MAX or receives a message not allowing him to reconstruct the label from the values of k and m, Bob has to invoke the following recovery protocol in order to obtain the expected session key k.

In his recovery protocol (protocol 2), Bob provides the TTP with all the information that should have been ex- If the label can be reconstructed from the received information, if EOO and EOR are correct with respect to the received information, and if t ≤ current time < t+T MAX+delay o , then the TTP deciphers E TTP (key), obtains the session key k, deciphers E k (m), and verifies whether m is coherent with h(m). If this last test succeeds, then the TTP provides the session key k and Alice's signature on this key (both information are contained in key) to Bob, and the evidence EOR to Alice. Otherwise, if one of these tests fails, the TTP replies to Bob with an error message.

On the other hand, if Bob does not (properly) perform the second step of the main protocol, Alice needs to execute, before time t + T MAX, the following recovery protocol with the TTP in order to obtain an evidence of receipt or an evidence of denial for the email that she is trying to send.

Alice initiates her recovery protocol (protocol 3) by sending to the TTP the first message of the main protocol 1 . Upon receipt of this message, the TTP verifies whether the label is coherent with the hash values of the message and of the key, and whether Alice's signature EOO is correct. Furthermore, it verifies that t ≤ current time < t + T MAX + delay o .

If all these tests succeed, the TTP forwards this first message to Bob. If Bob has still not replied at time t + T MAX + 3 • delay o , the TTP provides Alice with an evidence that Bob refused to receive her email. Otherwise, it performs the same actions as in the second step of the recovery protocol for Bob.

The evidence of origin that Bob may receive at the end of the protocol is composed of EOO, m, k, the timestamp t, and the signature S A (f key , A, B, label , k). Similarly, the evidence of receipt that Alice may receive at the end of the protocol is composed of EOR, m, k, t, and the signature S A (f key , A, B, label , k). The evidence of denial is composed of S TTP (f denial , A, B, label ), m, k and t.

If Alice wants to prove that she has received an evidence of receipt or an evidence of denial, she has to present the corresponding evidence, as well as the identities of A, B and TTP , to an adjudicator. The latter has first to reconstruct the label, and for an evidence of receipt, reconstruct also E TTP (key) and E k (m). The adjudicator verifies then respectively EOR or S TTP (f denial , A, B, label ). If the verification succeeds, it settles respectively that Bob has received the email m or that Bob refused m. Similarly, if Bob wants to prove that he has received a message from Alice, he has to present the evidence of origin that he has obtained during the protocol, as well as the identities of A, B and TTP , to an adjudicator. The latter has first to reconstruct the label, E TTP (key) and E k (m). The adjudicator verifies then the signature EOO. If this verification succeeds, it settles that Alice is the author of m.

The protocol is fair in the sense of property 5 since each execution ends with Alice obtaining either an evidence of receipt (if Bob received the message), or an evidence of denial (otherwise). The same reasoning shows that it is fair in the sense of property 1.

Concerning timeliness, we note that the main protocol should be finished at t + T MAX. If this is not the case, Alice and/or Bob have to run their recovery protocol. Their request has to reach the TTP no later than t + T MAX + delay o , otherwise the TTP will reject it. In the case of Bob's recovery protocol, the protocol ends no later than t + T MAX + 2 • delay o . For Alice, the second message reaches Bob no later than t+T MAX+2•delay o . The TTP will at most wait until t + T MAX + 3 • delay o . Its response will reach Alice and/or Bob no later than t + T MAX + 4 • delay o . As both Alice and Bob know this value from the beginning of the protocol, the timeliness property is respected. An important related remark is that Bob must, once he has replied to Alice in the main protocol, remain available until t + T MAX + 2 • delay o in case Alice would invoke her recovery protocol in order to obtain an evidence of denial after having already received a valid evidence of receipt.

The reasoning above shows that the protocol also satisfies the dated receipt property, as an adjudicator knows that Alice's email has been received by Bob after t, and before t + T MAX + 4 • delay o .

Conclusion

We have examined the main properties that have been considered in the literature on certified email protocols. In consequence, we have proposed that a certified email protocol should provide an evidence to the sender even when the recipient is reluctant to participate in the protocol, and, as a result, we have suggested a new definition of the fairness property. We have also presented a new protocol satisfying all the required properties, being more efficient than the few existing protocols indirectly satisfying our new fairness definition.

  TTP : f EOO , A, B, TTP , label , h(m), h(k), t, E TTP (key), E k (m), EOO EOO , A, B, TTP , label , h(m), h(k), t, E TTP (key), E k (m), EOO : f denial , label , S TTP (f denial , A, B, label ) changed during the first two steps of the main protocol.

	Protocol 3 Recovery protocol for Alice
	1.	A
	2.	TTP
	3.	if Bob replies
	a.	B	o → TTP : f EOR , label , EOR
	b.	TTP	o → A : f EOR , label , EOR
		TTP	o → B : key
	3'.	if Bob does not reply
		TTP

o → o → B : f o → A

The algorithms used to encrypt information are supposed to be deterministic. Although they are not formally provably secure, such algorithms are widely used in practice.

Note that fairness is still respected if the message is different, for example with another t, since any modification results in another protocol run.