Julien Alexandre Dit Sandretto
email: julien.alexandreditsandretto@inria.fr

Gilles Trombettoni
email: gilles.trombettoni@inria.fr

David Daney
email: david.daney@inria.fr

Confirmation of Hypothesis on Cable Properties for Cable-driven Robots

Keywords:

In the cable-driven robot studies, the mass and the elasticity of cables are often neglected, particularly for small-sized robots. Indeed, this assumption allows one to simplify the robot model and is used in control, design or calibration. We propose in this paper a method using interval analysis to judge the validity of this hypothesis in a given workspace, whatever are the cable characteristics, i.e., the applied tensions and the robot configuration.

Introduction

Parallel cable-driven robots have several interesting properties such as a reduced mass of mobile parts (i.e., cables have a mass negligible compared to the load), and a potentially large workspace. They are used in several applications, including flying camera systems [START_REF] Skycam | [END_REF], heavy load transportation, contour crafting [START_REF] Bosscher | Cable-suspended robotic contour crafting system[END_REF].

These robots are structurally similar to classical parallel manipulators, but are driven by cables instead of rigid links. The past studies performed have shown the kinematics complexity of parallel robots [START_REF] Merlet | Parallel Robots[END_REF]. In addition, the unilateral driving property of cables leads to hardly solvable kinematics and dynamics behavior due to the flexibility, mass and elasticity of the cables.

Several studies have been achieved on cable-driven robot kinematics [START_REF] Ming | Study On Multiple Degree-Of-Freedom Positioning Mechanism Using Wires International[END_REF], workspace [START_REF] Gouttefarde | Determination of the wrench-closure workspace of 6-DOF parallel cable-driven mechanisms[END_REF] or calibration [START_REF] Varziri | Kinematic calibration of a wire-actuated parallel robot[END_REF]. However, most of the researches on cable-driven robots use a fundamental hypothesis: the cables driving the platform are mass-less and non-elastic. This hypothesis leads to a simplification which permits control, kinematics, calibration, design, as a classical redundant Gough platform for example. In this paper, we propose a way to verify the validity of this hypothesis in the whole workspace of a given robot.

In robotics, especially when the handled problem is complex, several pioneering researchers have used the capabilities of interval methods. For example, Jaulin et al. showed in their book how to identify parameters [START_REF] Jaulin | Applied Interval Analysis[END_REF]; Merlet solved the forward kinematics of a Gough platform [START_REF] Merlet | Solving the Forward Kinematics of a Gough-Type Parallel Manipulator with Interval Analysis[END_REF]; Chablat et al. designed 3 d.o.f parallel machines [START_REF] Chablat | An Interval Analysis Based Study for the Design and the Comparison of Three-Degrees-of-Freedom Parallel Kinematic Machines[END_REF], and Pott and Hiller performed an optimization process for parallel machines [START_REF] Andreas Pott | A Parallel Implementation for the Optimization of Parallel Kinematic Machines under Process Requirements[END_REF].

In these works, interval analysis is used because it can certify properties, which is sometimes crucial in robotics. Indeed, interval analysis [START_REF] Jaulin | Applied Interval Analysis[END_REF][START_REF] Moore | Interval Analysis[END_REF][START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF] can handle the whole continuous space, contrarily to approaches based on discretization that may fail in checking some points.

Cable-driven robots

The goal of our national project, named CoGiRo, is to build a giant parallel cabledriven robot. This raises numerous issues: design, mechanical conception, modeling, vision-based control, etc. We will focus on the kinematics. Static is only used for the cable model, but not for the robot equilibrium. Also, we do not deal with the dynamic model.

Robot description

A parallel cable-driven robot is made of a mobile platform (end-effector) connected to a fixed base by m cables. These cables can vary in length by the actuation of m pulleys linked to m rotary engines. The variation in length and tension of cables generates a movement with n degrees of freedom (position and/or orientation). In the sketch presented in Fig. 1, the mobile platform (mobile reference frame Ω C ) Fig. 1 A cable-driven robot sketch and a ReelAx8 picture is connected to the base (fixed reference frame Ω O ) by m = 8 cables (m > n to be fully controllable [START_REF] Ming | Study On Multiple Degree-Of-Freedom Positioning Mechanism Using Wires International[END_REF]). The i th cable connects the point A i of the base (coordinate a i in Ω O ) to the point B i on the mobile platform (coordinate b i in Ω C ). The pose of the mobile X = (P, R) (defined by the position P and the orientation matrix R of Ω C w.r.t. Ω O ) is directly controlled by the length and the tension in each cable. The workspace W X is the set of all possible pairs (P, R) for the robot.

The prototype, named ReelAx8 and shown in Fig. 1, was built by the TECNA-LIA company (www.tecnalia.com) in collaboration with the LIRMM laboratory (www.lirmm.fr). Eight cables, wound on winches, are attached by spherical joints to the eight corners of a cube shaped platform of about 40 centimeters large. Four pairs of winches are fixed on posts up to three meters high arranged at the four corners of a 3 meters by 4 meters rectangle. The prototype is given with a rectangular and centered workspace (see Fig. 3) of 2 by 1 meter on floor, 1 meter high and ± 5 degrees of rotation on each axis:

W X = {X = [P, R], P ∈ [1, 3] × [1, 2] × [1, 2], R ∈ [-5, 5] × [-5, 5] × [-5, 5]}.

Cable model

Cable-driven robots take advantage of the use of cables, providing a large workspace, light actuators in comparison to the possible load mass, and low cost. However, cable-driven robots suffer from the complex kinematics and dynamics of cables.

A well-known realistic model that is often used for the kinematics of cables is proposed by Irvine in [START_REF] Irvine | Cable Structures[END_REF]. In the Irvine model, the length of a cable depends on its tension. It is given for one cable and the equations are expressed in a plane made of the points A and B and the gravitational force. The Irvine model considers the geometric and static parameters of the configuration and the cable properties: attachment points A (on base) and B (on platform); linear mass m, tightness k and length L of the cable; applied tensions T b in B and T a in A . The system of three equations to be solved in order to obtain the actual length of cable and the tension distribution on point A = [0, 0] is:

               B x = T x a L k + |T x a | mg [sinh -1 ( T z a T x a ) -sinh -1 ( T z a -mgL T x a )] B z = mgL 2 k ( T z a mgL - 1 2 ) + 1 mg [ T x a 2 + T z a 2 -T x a 2 + (T z a -mgL) 2 ] T b = T x a 2 + (T z a -mgL) 2 (1)
The fact that a robot is controlled with cables having a complex kinematics leads to some problems in the classical fields of robotics:

• complex modeling, control and design;

• unworkable existing methods for the workspace determination;

• unfeasible self-calibration.
The hypothesis of non-elastic and mass-less cables is very useful to simplify the modeling. Moreover, this hypothesis is often realistic and generates a negligible error in robot accuracy. Most of the papers dealing with these subjects use this hypothesis and replace the real length of cables L (depending on tensions) by the distances D = AB. Under this assumption, the model is highly simplified.

Checking of non-elasticity and mass-less hypothesis

The hypothesis of non-elasticity and mass-less done on cables properties has to be checked on one cable before any static or dynamic modeling (currently not mastered by the community). Our problematics is therefore to verify this hypothesis in the whole workspace of the robot to bring the guarantee that the simplification is valid.

For this purpose, we compute the errors σ i = |L i -D i | made between the length L i given by Irvine's model -function of B i , T B i and the cable parameters-and the distance D i , only function of B i . B i itself is function of X ∈ W X . We then verify that these errors all lie under an acceptable threshold ε (which could be selected in function of the expected articular accuracy): σ i ≤ ε, i = 1..m. The coordinates of B i in Ω O are e i = P + R.b i , b i being the coordinates of B i expressed in the platform reference Ω C (defined by the platform geometry). The hypothesis is verified on a pose X ∈ W X , if for each of the m points e i : σ i ≤ ε.

Therefore, we can define the subset S X of acceptable poses as follows: S X = {X ∈ W X , ∀i ∈ 1..m : σ i ≤ ε}. The proposed verification consists in checking the hypothesis in all the poses of the workspace. A sufficient condition is based on the dual set S !X = {X ∈ W X , ∃i ∈ 1..m : σ i > ε}. Interval methods can determine if S !X = / 0, which implies the hypothesis holds on W X . Moreover, the m points B i depending on X all belong to the same parallelepiped, whatever can be X ∈ W X . Thus, it is sufficient to test the hypothesis for only one cable. In addition, the parallelepiped built with the e i is entirely covered by the diagonal plane with a simple rotation around the z axis. Overall, the study of the workspace W X can be reduced to the one of the diagonal plane W B , as shown in Fig. 3. The point B ∈ W B could be expressed in the plane reference frame like in

Interval methods for constraint satisfaction and optimization

This problematics demands a rigorous solver which could consider a whole space made of an infinity of points and give a reliable result. Interval analysis meets this requirement by using algorithmic principles exploiting constraints and sub-spaces containing an infinity of points, without risk of solution loss.

An interval [x i ] = [x i , x i ] defines the set of reals x i s.t.

x i ≤ x i ≤ x i . A box [x] is the Cartesian product of intervals [x 1 ] × ... × [x i ] × ... × [x n ].
Its width is defined by max i w([x i ]).

Interval methods for solving a constraint system

Interval methods can accurately approximate, by boxes, the set of solutions of a constraint system. The solving process starts from an initial box representing the search space and builds a search tree, following a Branch & Contract scheme:

• Branch: the current box is bisected on one dimension (variable), generating two sub-boxes. • Contract: filtering (also called contraction) algorithms reduce the bounds of the box with no loss of solution.

The process terminates with atomic boxes of size at most ε on every dimension. Contraction algorithms comprise interval Newton-like algorithms issued from the numerical interval analysis community [START_REF] Moore | Interval Analysis[END_REF] along with algorithms from constraint programming.

Constrained optimization

Interval methods can also deal with a more difficult problem, constrained optimization, in which a solution must be found that minimizes an objective function while satisfying a set of constraints. To do so, the strategy follows a branch and bound schema [START_REF] Horst | Global Optimization: Deterministic Approaches[END_REF]. At each iteration, the algorithm selects in the list a box [x]. It chooses a branching variable x i ∈ x heuristically, bisects [x i ] and applies the main Con-tract&Bound procedure on the two sub-boxes. In addition to the contraction phase mentioned above, the procedure Contract & Bound resorts to a lower bounding phase updating a cost lb (that the objective function will never reach for sure) and an upper bounding phase searching for a solution that improves the current best cost ub [START_REF] Horst | Global Optimization: Deterministic Approaches[END_REF]. The search terminates when ublb reaches a precision ε ob j .

Experimentation

The solving follows the principles briefly described in Section 4. It is implemented with an interval tool developed in the COPRIN team.

Case 1: existing prototype

The cables used have the following characteristics: k = 137kN/m , m = 0.007kg/m. With the workspace W X introduced in the description of the robot, the plane W B to be tested is the diagonal plane of the rectangular parallelepiped

[1, 3] × [1, 2] × [1, 2] and W B = [1, 3.7] × [1, 2]
. We fix ε = 0.005m expected accuracy of robot. The sensors give, during our tests, a minimal tension of 20N and a maximal one of 120N. So 20 ≤ T b ≤ 120.

Case 2: robot under construction

We consider the same architecture robot but with heavier cables and a larger workspace. The cables are made of the same steel, with a tightness k = 137kN/m and a lineic mass m = 0.092kg/m. The workspace W B is [1, 8] * [1, 10] (in meters) and we also expect an accuracy of 1 cm. The tension should fall between 40N (without load) and 1000N (at maximal load).

Hypothesis confirmation

We use the constraint system (1) extended with the additional constraint σ > ε. Due to interval methods, we compute an overestimate of the subset S !B , noted S !B . If no solution is found in S !B , no solution exists in S !B , and the hypothesis is valid in the considered workspace. Case 1: No solution is found by our tool, therefore the hypothesis is acceptable for the studied robot. The model using the simplification is thus sufficiently accurate. The solving process achieved in the whole workspace takes about 2 hours. For a reduced workspace, for example one by one meter, the resolution is performed in about 10 minutes.

Case 2: A solution for S !B is immediately found (≈ 1 second). The hypothesis seems therefore too strong, which suggests that a more complex model must be developed for the giant robot under construction. Otherwise, the robot model accuracy could be highly deteriorated.

Quantifying the error

In addition to the yes/no results obtained about the hypothesis validation, global optimization gives the opportunity to enrich the knowledge about the robot. Indeed, we could expect additional quantified information, such as:

• the minimal tension satisfying the hypothesis, defined by S T b = Min T b , ∀B ∈ S B ,

• the maximal error committed in the workspace, defined by

S σ = Max σ , ∀B ∈ W B , ∀T b ∈ [T min , T max ].
Case 1: The analysis of the prototype model (for which the hypothesis has been proven acceptable by our verification method) provides useful information gathered in Table 1: The values found confirm the hypothesis validation.

• minimal T b to keep |σ | < ε,
Case 2: The same model analysis protocol is followed for the cable-driven robot under construction and the results are presented in Table 1:

• maximal |σ | for T b = 40N, see

Conclusion

In our research, we have done the hypothesis of mass-less and non-elasticity of cables for self-calibrating the robot presented in Section 2. Indeed, to self-calibrate a cable-driven robot, we must consider it as a redundantly actuated manipulator.

This redundancy is obtained with the simplified model under non-elasticity and mass-less assumption. If this hypothesis is validated using our method, the simplification is thus acceptable and the robot is self-calibratable. Concerning the robot under construction, the hypothesis is rejected. To self-calibrate this giant crane, we must define a slightly smaller sub-workspace where the hypothesis is acceptable or use a more complex model.

To conclude, we have designed an operational tool for analyzing the difference between a real cable model and a strong simplification of it. The method described in this paper has provided interesting and useful information for our study of cabledriven robots. Its implementation represents a first software version of a dedicated design tool which could be incorporated in an "Appropriate design" approach.

Finally, this dedicated tool can be useful for modeling, designing and optimizing in a reliable way robots, but also other mechanisms that make use of cables.

Fig. 2 A

 2 Fig. 2 A cable in a plane {A ,B, -→ P }

Fig. 3

 3 Fig. 3 Robot space frame in dashed lines, workspace W X and diagonal plane W B

Table 1

 1 The values found confirm the hypothesis rejection, even if the lower tension bound is close to the minimal tension for which the hypothesis is valid.

		1	2	3	4	5	6	7	8
	Error σ (m)	0.005 0.0006 -0.0037 -0.005 0.01009 0.01	-0.01	-0.093
	Tension T b (N) 1.4	20	120	171.5	40	40.1	121	1000
	Solv. time (s)	200	3	5	30	72	3	6000	5

, column 5; • minimal T b to keep |σ | < ε, see Table 1, column 6; • maximal T b to keep |σ | < ε, see Table 1, column 7; • maximal |σ | for T b = 1000N, see Table 1, column 8.

Table 1

 1 Results (in bold) obtained by optimization processes

Acknowledgment

This work was supported in part by the French National Research Agency (ANR) under grant 2009-SEGI-018 (CoGiRo ANR project) and in part by the Région Languedoc-Roussillon under grant 115217.


Claude Castelluccia

Daniel Le Métayer

NOTE D'ANALYSE

Contexte

Le décret du 28 octobre 2016 autorisant la création d'un fichier centralisé de « titres électroniques sécurisés » (TES) a suscité un certain nombre d'interrogations et d'inquiétudes. L'objectif principal mis en avant par le gouvernement est la lutte contre la fraude aux titres d'identité. Cependant, le texte du décret autorise aussi certains accès à la base de données par les agents de la police nationale, de la gendarmerie nationale et des renseignements. De nombreuses voix se sont élevées pour pointer les risques qu'un tel fichier centralisé pourrait représenter en matière de libertés individuelles, et notamment d'atteintes à la vie privée des citoyens. De son côté, le gouvernement avance que ce décret ne fait qu'étendre aux cartes d'identité les dispositions déjà en vigueur pour les passeports et que la solution technique retenue ne permettra pas l'utilisation de la base de données à des fins d'identification 1 .

Le présent rapport a été réalisé en parallèle et indépendamment de l'audit conduit par l'ANSSI et la DINSIC 2 . Contrairement à ce dernier, il ne vise pas à analyser la sécurité du système mis en oeuvre (auquel les auteurs n'ont pas accès) mais à élargir le débat par l'analyse d'architectures et de solutions alternatives. Son objectif est également d'apporter un éclairage complémentaire sur la protection des données personnelles.

Pour pouvoir se prononcer sur les avantages et inconvénients d'un système de gestion de titres électroniques, il nous paraît nécessaire de :

1 Cette affirmation est contredite par l'ANSSI et la DINSIC qui constatent dans leur rapport d'audit 2 que « le système TES peut techniquement être détourné à des fins d'identification ». Nous expliquons dans la partie 5 pourquoi l'identification est toujours possible dans les systèmes d'authentification reposant sur des liens unidirectionnels.

1. Définir clairement les fonctionnalités souhaitées et les avantages qu'on peut en attendre, notamment par rapport à la situation actuelle et à d'autres solutions. 2. Décrire la solution technique retenue de manière suffisamment précise pour permettre son analyse. 3. Analyser rigoureusement les risques d'atteinte à la vie privée au regard des bénéfices attendus.

Il va de soi qu'un tel document n'a aucune vocation à l'exhaustivité ni à proposer des analyses ou solutions définitives, notre intention étant essentiellement de fournir un cadre pour aborder ces questions de manière rigoureuse. Le jugement que chacun pourra ensuite former sur le bien-fondé de la constitution d'une telle base de données ne repose évidemment pas exclusivement sur ces éléments techniques.

Nous revenons dans la partie 2 sur les incertitudes entourant le projet TES avant d'analyser dans les parties suivantes différentes hypothèses concernant les trois éléments évoqués plus haut: la partie 3 est consacrée aux fonctionnalités du système, la partie 4 décrit différentes solutions techniques et la partie 5 fournit un aperçu de la méthode qui peut être adoptée pour analyser les risques d'atteinte à la vie privée. En conclusion, nous soulignons l'importance des procédures de contrôle (« accountability ») en la matière. Nous insistons également sur le fait que le renforcement des moyens de lutte contre la fraude (et la criminalité de manière plus générale) et l'exigence de protection de la vie privée ne sont pas forcément antinomiques.

Les incertitudes entourant le nouveau fichier TES

La première source d'inquiétude concernant le nouveau fichier TES est liée à la constitution d'une base de données centralisée regroupant des données sur des dizaines de millions de français 3 , qui a pu rappeler d'autres projets contestés comme le « fichier des gens honnêtes » abandonné en 2012 ou encore SAFARI 4 qui a conduit à la création de la CNIL en 1978. D'autres facteurs, de natures variées, ont aggravé la suspicion, comme l'adoption du projet par décret, donc sans débat préalable, alors qu'un pays proche comme la Grande-Bretagne, par exemple, a fini par abandonner un tel projet en 2010 suite à une vague de protestation. Par ailleurs, le texte du décret n'est pas dépourvu d'ambiguïtés et il a suscité des déclarations parfois contradictoires qui ont contribué à alimenter les doutes. Les incertitudes portent aussi bien sur les fonctionnalités attendues que sur la solution technique envisagée.

Objectifs et solutions à préciser

Pour ce qui concerne les fonctionnalités, l'objectif affiché par le gouvernement est de « simplifier les démarches des usagers et de fiabiliser les titres d'identité en luttant plus efficacement contre la fraude » 5 . Par ailleurs, le garde des Sceaux précise que le fichier 3 Tous les détenteurs de carte d'identité ou de passeport. Pour être précis, le ministère de l'Intérieur a décidé, « afin de répondre aux interrogations qui se sont fait jour », de « conditionner le versement dans TES des empreintes digitales des usagers au consentement de ces derniers » (http://www.interieur.gouv.fr/Actualites/Lefichier-des-titres-electroniques-securises). L'effet réel de cet assouplissement reste toutefois à vérifier en pratique. En effet, les limites du consentement en matière de protection de la vie privée ont déjà été mises en évidence par différentes études (voir par exemple : « Le consentement au traitement des données personnelles. Le rapport d'audit de l'ANSSI et de la DINSIC décrit quant à lui un système répartissant les dossiers en deux compartiments : un compartiment alphanumérique et un compartiment de données biométriques dans lequel les « différentes catégories de données biométriques sont gérées de manière indépendante dans l'optique d'assurer leur cloisonnement. »

Protection contre l'identification

Le ministère affirme que, s'il est « possible de remonter au deuxième compartiment, biométrique, à partir des données propres à la demande du titre, l'inverse est impossible. On ne peut accéder à l'identité à partir des données biométriques. » Cette impossibilité serait non seulement juridique (le décret l'interdit), mais aussi technique. Le fichier TES offrirait donc des fonctions d'authentification (« vérification que la personne qui demande un titre est bien celle qu'elle prétend être au vu du contrôle de conformité des données biométriques que permet la base ») mais serait mis en oeuvre de manière à empêcher toute fonctionnalité d'identification (découverte de l'identité d'une personne à partir de données biométriques). Les explications sur cette mise en oeuvre fournies par le ministère, notamment dans sa réponse au Conseil national du numérique 10 , évoquent une conservation des données biométriques dans une base distincte et séparée de celle des demandes de titres, un lien « asymétrique » entre ces bases, et un blocage technique « garanti par une cryptographie spécifique et un lien unidirectionnel ». Le rapport d'audit de l'ANSSI et la DINSIC affirme cependant que « le système TES peut techniquement être détourné à des fins d'identification » et recommande la prise en compte des « préconisations du Référentiel Général de Sécurité concernant les mécanismes cryptographiques mis en oeuvre pour construire les liens unidirectionnels. » Les éléments disponibles publiquement sont trop vagues pour permettre une véritable analyse technique. Cependant, certains scientifiques sont sceptiques 11 sur la possibilité même de l'existence d'une solution technique offrant la fonctionnalité d'authentification tout en interdisant celle d'identification. Cette question importante est discutée dans la partie 5 de ce document. Même si les mesures évoquées paraissent de bon sens, un examen plus approfondi serait nécessaire pour apporter des assurances plus solides 13 . L'audit réalisé par l'ANSSI et la DINSIC avait pour objet de répondre à ce besoin mais ses conclusions ne sont pas entièrement rassurantes puisque le rapport comprend onze recommandations portant sur des aspects critiques du système comme la robustesse du lien unidirectionnel, le cloisonnement, le traçage des requêtes, la sécurité des serveurs (« non conformes à l'état de l'art ») et la gouvernance du système. Par ailleurs, il serait nécessaire également d'analyser l'équilibre entre les risques inhérents à toute solution centralisée et les bénéfices qu'elle peut apporter par rapport à des architectures distribuées.

Sécurisation de la base de données

La question du consentement

Pour tenter de répondre aux inquiétudes soulevées par le projet, le gouvernement a indiqué que « dans le cadre d '

une demande ou d'un renouvellement d'une carte nationale d'identité, le versement des empreintes digitales du demandeur du titre seront soumis à son consentement express et éclairé. Ainsi, le recueil des empreintes reste obligatoire. Mais le refus du versement des empreintes dans la base centralisée TES n'empêchera pas la délivrance du titre. En revanche, ce versement simplifie et facilite l'émission d'un nouveau titre et permet de lutter efficacement contre l'usurpation d'identité : les Français qui y renoncent renonceront également aux services associés. »

11 Dont les auteurs de ce rapport. Voir aussi : http://www.lsv.ens-cachan.fr 12 http://www.interieur.gouv.fr/Actualites/Le-fichier-des-titres-electroniques-securises 13 La question n'est pas de savoir si la sécurité du système n'a jamais été compromise mais de fournir des garanties que les risques ont bien été étudiés et que des mesures satisfaisantes ont été prises pour y remédier. On sait que les risques de fuites de données ne sont jamais nuls et qu'ils peuvent devenir massifs quand les bases de données sont centralisées. A titre de rappel, l'Office of Personnel Management (OPM) a révélé en 2015 la fuite de 5,6 millions d'empreintes digitales de fonctionnaires américains : http://www.lemondeinformatique.fr/actualites/lire-5-6m-d-empreintes-digitales-de-fonctionnaires-americainsderobees-62451.html Cependant, on connaît de manière générale les limites du consentement en matière de collecte des données personnelles14 et on peut se demander si, dans un tel contexte et face aux arguments sécuritaires des agents chargés de l'émission des titres, un grand nombre de citoyens seront suffisamment informés ou auront suffisamment de détermination pour refuser ce consentement.

Contrôle des accès aux données personnelles

Pour ce qui concerne le contrôle des accès aux données personnelles, le site du ministère de l'Intérieur met en avant un avantage du nouveau système par rapport à la situation existante : « A cet égard, on soulignera que les données biométriques propres à la CNI existent déjà, sont déjà relevées par les agents de

mairie et consultées par les agents de préfecture (photo et empreintes). Simplement, elles sont conservées sous format papier. L'inconvénient majeur du format papier, c'est qu'il rend complexe la traçabilité des consultations auxquelles il donne lieu. Alors qu'en versant dès aujourd'hui les CNI dans l'application TES, nous sommes désormais en mesure de garantir aux Français la traçabilité parfaite des consultations de leurs données biométriques, notamment avec un système d'horodatage. »

Cependant, le traçage ne représente qu'une condition nécessaire du contrôle : il serait utile, pour rendre l'argument convaincant, de préciser les modes effectifs de contrôle, son organisation, les entités impliquées et les garanties qui peuvent être fournies aux citoyens quant à l'existence d'audits véritablement indépendants. Cette question importante, de ce qu'on appelle en anglais l'« accountability » (responsabilité, au sens d'obligation de « rendre compte »), est discutée en conclusion.

Définition des fonctionnalités

Le décret du 28 octobre 2016 s'inscrit dans le cadre du plan PPNG (« Plan Préfectures Nouvelles Générations »). L'objectif affiché par le gouvernement est double15 : « Il s'agit à la fois de simplifier les démarches des usagers et de fiabiliser les titres d'identité en luttant plus efficacement contre la fraude ». Nous nous focalisons dans ce document sur la finalité de lutte contre la fraude qui est généralement mise en avant pour justifier la constitution d'une base centralisée de données biométriques.

Nous pouvons distinguer trois phases principales dans la gestion des titres d'identité 16 VI (fort) : vérification de l'identité possible en comparant empreinte de l'utilisateur avec l'empreinte stockée dans la carte à puce.

Définition des architectures

Tableau 2 : protection contre la fraude 21 Si le demandeur a perdu sa carte, identique à la phase « premier titre ». 22 Ibid. 23 Ibid. 24 Ibid.

Analyse des risques d'atteinte à la vie privée

La mise en place d'un système de gestion des titres sécurisés pouvant présenter des risques d'atteinte à la vie privée, il nous paraît nécessaire de procéder au préalable à une étude d'impact (« Privacy Impact Assessment » ou « PIA » en anglais).

Etude d'impact

Une telle étude doit prendre en compte une multitude de facteurs qui peuvent avoir une incidence sur les risques. Il convient de considérer notamment les types de données personnelles traitées, les différents intervenants, les sources de risques 25 S'agissant d'un système de gestion de titres d'identité électroniques, une étude d'impact en matière de vie privée devrait permettre d'évaluer au moins les deux types de risques majeurs associés aux traitements biométriques, que sont :

1. Les risques liés à l'usage des données personnelles en mode identification par le gouvernement. 2. Les risques résultant de fuites ou de vols de données personnelles commis par des sources externes (cybercriminels, gouvernements étrangers, etc.) ou internes (employés ou sous-traitants mal intentionnés, etc.).

On considère généralement deux composantes essentielles pour évaluer les risques : la gravité de leurs impacts sur les personnes et leur vraisemblance 28 . La gravité des impacts des deux risques évoqués ci-dessus est majeure. Ces impacts peuvent être d'ordre physique (suicide suite à un vol d'identité ou à la publication de données personnelles), matériel (pillage d'un compte bancaire suite à une usurpation d'identité) ou psychologique (sensation de surveillance, de harcèlement, etc.). La vraisemblance d'un risque dépend directement de l'architecture envisagée et des contre-mesures mises en place. Dans le reste de cette partie, nous analysons de manière succincte la vraisemblance des deux risques cités plus haut pour les cinq architectures décrites dans la partie précédente.

Risques d'identification

Risques liés aux fuites de données

Les données stockées sur une plateforme de gestion des identités sont très sensibles et doivent être protégées avec la plus grande attention. On sait de longue date en sécurité informatique que la centralisation représente un facteur de risque majeur car elle désigne à un attaquant une cible très tentante. Une fuite de données peut résulter d'une attaque externe (intrusion), d'une attaque interne (employé malveillant) ou encore d'une négligence (mauvais choix de configuration, sauvegardes non sécurisées, etc.). Par ailleurs, même dans les cas où la probabilité d'une telle fuite pourrait être considéré comme très faible, il convient de considérer l'impact majeur qu'elle pourrait avoir en matière de vie privée 32 . En effet de telle données pourraient, par exemple, être utilisées par des fraudeurs (cybercriminels) pour réaliser des usurpations d'identité à grande échelle 33 En conclusion, il convient aussi d'insister sur la nécessité de mettre en place des mesures de responsabilisation (« accountability ») et des contrôles rigoureux pour minimiser les risques d'usages détournés des données personnelles, notamment de dévoiement de la base de données à des fins de surveillance. Des mesures techniques (système auditable, avec des logs sécurisés permettant de tracer toutes les opérations) doivent rendre possible ces contrôles44 mais elles sont insuffisantes si elles ne sont pas accompagnées de mesures organisationnelles tout aussi fiables : il est primordial notamment d'assurer que les audits pourront être conduits par des experts indépendants. Cet ensemble de garanties techniques, organisationnelles et juridiques est une condition sine qua non du rétablissement d'une certaine confiance des citoyens envers ce type de systèmes et ceux qui les mettent en place.

Figure 1 :

 1 Figure 1 : risques vs fonctionnalités

  la question de l'apport du nouveau traitement par rapport à la situation actuelle, le principal objectif mis en avant est l'amélioration de l'efficacité de la lutte contre la fraude aux titres d'identité. Par ailleurs, le ministère de l'Intérieur 7 évoque l'offre de « nouveaux télé-services, comparables à ceux qui existent aujourd'hui pour les passeports : prédemande en ligne, paiement du timbre dématérialisé en ligne, renouvellement des titres plus rapide, amélioration de la sécurité des CNI, et donc sécurisation de l'identité. ».Cependant, la nécessité de constituer une base de données biométriques centralisée pour offrir ces nouveaux services ne paraît pas manifeste. Par ailleurs, la pertinence d'une telle solution en matière de lutte contre la fraude mérite aussi d'être analysée de plus près en regard des modes opératoires utilisés par les fraudeurs 8 (falsification de documents, usage frauduleux d'un document authentique, obtention indue à partir de faux justificatifs, etc.).

Perspective comparative sur l'autonomie du sujet », C. Lazaro, D. Le Métayer, Revue Juridique Themis, vol. 48, n° 3, 2015, pp. 765-815). 4 http://section-ldh-toulon.net/a-l-origine-de-la-Cnil-Safari-ou.html 5 Site du ministère de l'Intérieur : http://www.interieur.gouv.fr/Actualites/Le-fichier-des-titres-electroniquessecurises TES « n'a pas vocation à être utilisé à des fins judiciaires » en ajoutant néanmoins « sauf dans le cas où les données feraient l'objet de réquisitions » 6 . A S'agissant de la solution technique envisagée, à notre connaissance aucune information précise n'est disponible publiquement. Le site du le ministère de l'Intérieur 9 fait état d'un fichier comportant trois « compartiments » relatifs respectivement à :

 « des données alphanumériques (l'adresse, le numéro de la demande, le nom du demandeur…) qui figurent sur le formulaire de demande de titre ou CERFA, qui est strictement inchangé » ;  « la photo et aux deux empreintes digitales numérisées » ;  « aux pièces justificatives ».

  La phase de renouvellement d'un titre durant laquelle une personne demande le renouvellement de son titre d'identité, son premier titre n'étant plus valide ou ayant été perdu ou volé. L'identification du demandeur peut être effectuée en utilisant l'ancien titre et des justificatifs sous forme de documents « papier » (seule possibilité en cas de non présentation du premier titre), tels que des actes de naissance. On pourra comparer les empreintes et photos du demandeur avec celles qui sont stockées dans la base de données et/ou sur la carte à puce, selon les options d'architectures retenues.

	3. La phase d'utilisation du titre durant laquelle une personne doit décliner son
	identité. L'identification de la personne est souvent effectuée par la présentation
	d'une carte nationale d'identité ou d'un passeport (sous forme papier ou
	électronique).
	Les deux fonctionnalités suivantes sont particulièrement utiles pour lutter contre la
	fraude :
	1. La vérification de l'identité (VI) : vérification qu'une identité est valide (elle n'est
	pas fausse) et qu'elle correspond à la personne qui se présente (elle n'est pas
	usurpée).

: 1. La phase d'émission du premier titre durant laquelle une personne demande son premier titre d'identité. L'identification de la personne est généralement effectuée en utilisant des certificats administratifs, tels que des actes de naissance. Durant cette phase, des empreintes et des photos du demandeur sont collectées et enregistrées. L'enregistrement peut être effectué (de manière non exclusive) dans une base de données ou sur un support physique individuel sécurisé (carte à puce). 2. 2. La détection de doublons (DD) : détection des doublons d'identité (tentative d'usurpation d'identité), c'est à dire qu'une empreinte, ou un trait biométrique, a été enregistré avec différents noms. Même si la fonctionnalité DD peut être utilisée pendant la phase d'utilisation d'un titre, elle est surtout importante pendant les phases d'émission et de renouvellement des titres. Par ailleurs, elle s'applique de la même manière dans ces deux phases. Par conséquent, et par souci de simplification, nous ne la considérons que pour la phase d'émission du premier titre dans la suite du document.

  Architecture A1 : cette architecture repose sur la mise en place de deux fichiers centralisés, constitués et gérés par l'administration. Le premier fichier contient, pour chaque citoyen enregistré 17 : les données d'état civil (nom, prénoms, date et lieu de naissance, sexe et données relatives à la filiation), certaines données personnelles additionnelles (couleur des yeux, taille, adresse) et une image de la signature du demandeur. Le deuxième fichier contient les données biométriques de chaque citoyen, c'est à dire des représentations numérisées du visage et des empreintes digitales. Les données biométriques sont chiffrées et liées aux données d'état civil par des liens unidirectionnels (ou asymétriques). Il est ainsi possible de retrouver simplement les données biométriques à partir des données d'état civil d'une personne (authentification), par exemple en suivant un simple lien (ou pointeur) mais il est plus difficile 18 de retrouver les données d'état civil à partir des données biométriques car le lien (ou pointeur) inverse n'existe pas. Cette architecture semble correspondre à la solution préconisée par le gouvernement pour le nouveau système TES.Architecture A2 : dans cette architecture, les titres électroniques (cartes d'identité, passeports) sont équipés d'une carte à puce qui contient les données personnelles et les données biométriques de leur détenteur. Le fichier centralisé ne contient que les données d'état civil (nom, prénoms, date et lieu de naissance, sexe et données relatives à la filiation) et certaines données personnelles additionnelles (couleur des yeux, taille, adresse). Les données biométriques sont donc stockées uniquement sur une carte à puce contrôlée par le détenteur du titre.  Architecture A3 : la troisième option peut être vue comme une combinaison des architectures A1 et A2 précédentes. Elle comporte un fichier biométrique centralisé et des titres électroniques équipés d'une carte à puce stockant les données d'état civil et biométriques du détenteur. Cette solution semble correspondre à l'architecture adoptée pour la gestion des passeports électroniques français (système TES existant).  L'un des maillons faibles des quatre architectures présentées est la phase de vérification de l'identité (VI) lors de l'émission du premier titre. Cette phase est très importante car l'authenticité des données versées dans la base, et par conséquent la sécurité des phases suivantes, en dépend directement. Dans toutes les architectures, la sécurité de cette phase est faible car elle repose essentiellement sur des justificatifs qui doivent être fournis par le demandeur et qui sont falsifiables. Il conviendrait de renforcer la sécurité de cette phase en replaçant, par exemple, les justificatifs « papier » par des justificatifs électroniques signés par les entités émettrices ou en généralisant l'usage de la solution 2D-Doc de sécurisation des justificatifs développée par l'ANTS Un titre d'identité sans carte à puce ne permet une vérification forte de l'identité lors de son utilisation que dans les scénarios permettant l'accès à une base de données centrale. Or, l'accès à cette base de données devra être strictement limité et contrôlé pour des raisons évidentes de sécurité 20 . Dans les autres cas, cette vérification restera essentiellement visuelle à partir d'un titre papier, facilement falsifiable, et fournira donc un niveau de protection faible. Les solutions qui font appel à une carte à puce ont l'avantage considérable de fournir une vérification d'un niveau de sécurité très élevé (les cartes à puce étant très difficilement falsifiables).

	Nous calculons également, pour chaque architecture considérée, à titre d'illustration, un caractéristique de l'architecture A4 permet, comme nous le montrons dans la
	« score de fonctionnalité ». Ce score est calculé en additionnant les trois sous-scores section 5, de réduire les risques d'atteinte à la vie privée tout en préservant un
	des trois phases de la gestion des titres d'identité (émission, renouvellement, utilisation). niveau de fonctionnalité équivalent.
	La valeur 2 correspond à une fonctionnalité garantie « fortement », la valeur 1 à une
	fonctionnalité garantie « faiblement » et la valeur 0 à fonctionnalité n'est pas fournie Premier Titre Renouvellement Titre Utilisation Titre
	(« impossible »). Le score final est donc une valeur entre 0 et 6, où 0 indique qu'aucune VI (faible) : vérification VI (faible) : vérification VI (faible) : vérification
	fonctionnalité souhaitée n'est fournie alors qu'un score de 6 indique que toutes les A0 réalisée sur les réalisée en comparant réalisée en comparant
	fonctionnalités sont garanties « fortement ». Ces scores sont présentés dans le tableau 2 justificatifs « papier ». l'empreinte du l'empreinte ou la photo
	(sous le nom de l'architecture considéré). Score demandeur avec celle qui	du demandeur avec
	:2.5/6	DD (impossible) :		apparaît sur l'ancien		celle qui apparaît sur le
	L'analyse du tableau 2 montre que : vérification impossible car	titre 21 (et vérification de		titre.
		aucune base centralisée.	justificatifs « papier »).
	A1	VI (faible) : vérification		VI (fort) : vérification		VI (faible ou fort) :
		réalisée sur les		réalisée en comparant		vérification automatique
		justificatifs « papier ».		l'empreinte du		impossible localement,
	Score			demandeur avec celle qui	car le titre ne possède
	:5/6	DD (fort) : vérification		correspond à son identité		aucune puce, mais
		réalisée en vérifiant		dans la base (et		possible en interrogeant
		si l'empreinte du		vérification de justificatifs		la base (si le vérifieur
		demandeur existe déjà		« papier »).		peut y accéder).
		dans la base biométrique.
		VI (faible) : vérification		VI (fort) : vérification		VI (fort) : vérification de
	A2	réalisée sur les		réalisée en comparant le		l'identité possible en
		justificatifs « papier ».		nom et l'empreinte du		comparant l'empreinte
				demandeur aux		de l'utilisateur avec
	Score	DD (impossible) :		empreintes dans la carte		l'empreinte stockée
	:	vérification impossible car	à puce 22 (et vérification		dans la carte à puce.
	4.5/6	aucune base de données	de justificatifs « papier »).
		centralisée
		VI (faible) : vérification		VI (fort) : vérification		VI (fort) : vérification de
	A3	réalisée sur les		réalisée en comparant le		l'identité possible en
		justificatifs « papier ».	Architecture avec fichiers nom et l'empreinte du		Architecture sans comparant empreinte de
			biométriques centralisés demandeur aux		fichier biométrique l'utilisateur avec
	DD (fort) : vérification Titre avec carte à puce Score réalisée en vérifiant	empreintes dans la carte A3 (solution TES passeport) à puce 23 (et vérification	l'empreinte stockée centralisé A2 dans la carte à puce.
	: 5.5/6	si l'empreinte du	A4	de justificatifs « papier »).	Vérification également
	Titre sans carte à puce demandeur existe déjà dans la base biométrique. A1 (solution TES cartes d'identité)	possible en interrogeant A0 (solution actuelle) la base (si le vérifieur peut y accéder).
	A4	VI (faible) : vérification Tableau 1 : architectures considérées VI (fort) : vérification réalisée sur les réalisée en comparant le
	justificatifs « papier ». La première question qui se pose à propos des architectures ci-dessus est celle de leurs nom et l'empreinte du demandeur aux capacités à assurer les fonctionnalités décrites dans la partie précédente. Le tableau 2 Score DD (fort) : vérification empreintes dans la carte compare, pour les quatre architectures considérées, le niveau de protection (en matière :5.5/6 réalisée en vérifiant à puce 24 (et vérification de lutte contre la fraude) apporté pour chacune de ces fonctionnalités. Nous distinguons des données biométriques et le fichier des données d'état civil. Cette apportée. A3 tout en garantissant l'indépendance totale (absence de liens) entre le fichier uniquement par des moyens visuels et « impossible » quand elle ne peut pas être  L'architecture A4 permet d'assurer les mêmes fonctionnalités que l'architecture dans la base biométrique. exemple à partir des données biométriques), « faible » quand elle est apportée demandeur existe déjà les niveaux « fort » quand la protection repose sur des moyens de sécurisation forts (par si l'empreinte du de justificatifs « papier »).

Différents choix d'architecture et de techniques sont possibles pour mettre en oeuvre un système de gestion de titres d'identité. Chaque solution peut permettre d'atteindre de manière plus ou moins satisfaisante les fonctionnalités attendues (ou un sous-ensemble de ces fonctionnalités) et présenter des risques plus ou moins importants en matière de vie privée. Nous décrivons dans cette partie quelques options architecturales avant d'analyser la manière dont elles permettent d'atteindre les fonctionnalités de vérification d'identité et de détection de doublons. Les risques qu'elles peuvent présenter en matière de vie privée sont étudiés dans la partie suivante. L'objectif de ce document est de fournir un aperçu de la diversité des options possibles et de montrer la nécessité de procéder de manière méthodique pour les comparer. Il n'est donc pas question, ici, d'analyser ou de citer toutes les architectures possibles. Nous nous focalisons sur les options suivantes :   Architecture A4 : la quatrième option est similaire à A3 à la différence près que le fichier centralisé des données d'état civil ne comporte aucun lien vers les données biométriques. Les deux fichiers sont donc complètement séparés et il est impossible d'associer (dans un sens ou dans l'autre) une donnée biométrique à des données d'état civil. Le tableau 1 ci-dessous résume les architectures considérées dans ce document ainsi que la solution actuelle (A0) qui ne comporte ni fichier biométrique centralisé ni carte à puce. 19 . Cependant, la sécurisation de justificatifs comme les certificats de naissance n'est pas un problème simple à résoudre, car il ne suffit pas d'authentifier l'émetteur de certificat (ce qui peut être fait, par exemple, via une signature électronique) : il faut aussi s'assurer que le certificat appartient bien au demandeur du titre. Cette question est délicate et mériterait une étude plus détaillée.  Une solution reposant sur les cartes à puce, sans faire appel à une base de données centralisée (A2), ne permet pas de détecter les doublons d'identité lors d'une demande de renouvellement d'un titre. Cependant, les protections apportées lors de la phase de renouvellement dépendent directement de la fiabilité de la phase d'émission du premier titre. En effet, si la phase d'émission du premier titre est sûre, et les titres d'identité eux-mêmes peuvent être considérés comme infalsifiables (les cartes à puce étant des dispositifs sécurisés), l'usurpation d'identité est alors très difficile et la phase de détection des doublons devient accessoire, voire inutile. 

  , les évènements redoutés 26 , les attaques 27 possibles, et enfin leurs impacts potentiels sur les personnes. L'analyse des risques est d'autant plus complexe qu'il est généralement nécessaire d'envisager un très grand nombre de scenarios correspondant à des combinaisons de paramètres variés. La réalisation d'une véritable étude d'impact sort clairement du cadre de ce document et notre objectif dans cette partie est essentiellement d'esquisser la démarche à suivre.

  Une protection contre l'identification est introduite dans A1 et A3 par l'utilisation de liens unidirectionnels, rendant plus difficile le passage d'une empreinte aux données d'état civil correspondantes. Cependant, cette protection demeure très faible car il suffirait d'interroger la base de données avec les noms des personnes susceptibles d'en faire partie (par exemple tous les citoyens français) pour reconstituer la base complète avec les liens bidirectionnels 29 . Il paraît difficile, voire impossible, de se protéger techniquement contre un tel risque à partir du moment où toutes les données sont contrôlées par une seule entité. L'introduction de liens unidirectionnels complique l'identification, mais ne l'empêche pas de façon absolue. De même, le fait de ne stocker qu'un gabarit ou un condensat des empreintes ou des photos, comme il est parfois proposé 30 , ne constitue qu'une faible protection contre ce risque, car il suffirait de comparer les condensats au lieu des empreintes afin de retrouver l'identité de la personne en question31 . Par ailleurs, même sans reconstituer la base, il est possible de l'interroger pour vérifier certaines identités. Il est aisé, par exemple lors d'une manifestation, d'effectuer une recherche à partir d'une liste de noms de « suspects » potentiels (opposants, syndicalistes, etc.). A2 protège contre ce type de risque car elle ne stocke aucune information biométrique dans la base centralisée. Pour ce qui est de A4, bien que cette architecture comporte un fichier biométrique, elle ne permet pas l'identification car ce fichier ne comporte aucun lien (ni dans un sens ni dans l'autre) avec le fichier de données d'état civil. Il est donc impossible d'identifier les données biométriques.

	 A1 et A3 :
	L'utilisation du système à des fins d'identification par le gouvernement consisterait à
	retrouver l'identité d'une personne à partir d'une empreinte ou d'une photo. Il est
	intéressant de noter que seules les solutions A2 et A4 offrent une protection
	satisfaisante à cet égard :

Etude préliminaire de la vraisemblance des risques en matière de vie privée 34

  ou pour identifier des personnes à partir de leurs photos ou empreintes. De toutes les architectures considérées précédemment, seules les architectures A2 et A4 protègent véritablement contre ce type de risques : A2 parce qu'elle ne comporte pas de base centralisée et A4 parce qu'elle ne permet pas d'établir de lien entre données biométriques et données d'état civil. également pour chaque architecture un « score de risque ». Ce score est calculé en additionnant les sous-scores de chaque source de risques (Etat français, sources internes, source externes). Le score final est donc une valeur entre 0 et 6, 0 indiquant que les risques sont négligeables et 6 que les risques sont très élevés. Même s'il ne fournit évidemment qu'une appréciation très grossière du niveau de risque, un score global de ce genre permet de faire ressortir des éléments de comparaison utiles pour l'aide à la décision. La nature des risques de l'architecture A0 est différente de celle des autres architectures. En effet, A0 n'utilise pas de fichier centralisé, les risques existent, mais sont « locaux » et d'ampleur moins importante.35 Même si les données biométriques sont chiffrées, des sources de risques internes (administrateur système malveillant ou soudoyé, sous-traitant indélicat, etc.) peuvent avoir accès aux clefs de chiffrement et donc aux données chiffrées. Ce risque peut être limité par des mesures de dissuasion (fichiers logs sécurisés, permettant de garder une trace des accès, et contrôlés par des auditeurs indépendants).

		Etat français	Sources internes	Sources externes
	Risques	(surveillance)	(employés, sous-	(cybercriminels, états tiers,
			traitants, etc.)	etc.)
	Archi-
	tectures
	A0 34	Identification :	Accès non-légitime aux	Fuite de données d'état civil :
		impossible	données d'état civil et	difficile
	Score :		biométriques : difficile	Fuite de données biométriques :
	2.5/6			difficile
				Identification des données
				biométriques : difficile
	A1	Identification : possible	Accès non-légitime aux données d'état civil et	Fuite de données d'état civil : difficile 36
	Score :		biométriques :	Fuite de données biométriques :
	5/6		possible 35	difficile
				Identification des données
				biométriques : difficile
	A2	Identification :	Accès non-légitime aux	Fuite de données d'état civil :
		impossible	données d'état civil :	difficile
	Score :		possible	Fuite de données biométriques :
	1.3/6		Accès non-légitime aux	impossible
			données biométriques :	Identification des données
			impossible	biométriques : impossible
	A3	Identification :	Accès non-légitime aux	Fuite de données d'état civil :
		possible	données d'état civil et	difficile
	Score :		biométriques :	Fuite de données biométriques :
	5/6		possible	difficile
				Identification des données
				biométriques : difficile
	A4	Identification :	Accès non-légitime aux	Fuite de données d'état civil :
		impossible	données d'état civil :	difficile
	Score :		possible	Fuite de données d'état civil et
	1.66/6		Accès non-légitime aux	biométriques : difficile
	données biométriques : Le tableau 3 ci-dessous résume les éléments de discussion concernant la Identification des données impossible biométriques : impossible vraisemblance des risques considérés ici. Nous avons utilisé la gradation suivante pour quantifier ces risques : possible (2), difficile (1) et impossible (0). Nous Tableau 3 :
	29 Ce qu'on appelle parfois une attaque de « force brute ». 30 Voir par exemple : Symmetric Hash Functions for Fingerprint Minutiae, S. Tulyakov, F. Farooq, V. Govindaraju,
	Third International Conference on Advances in Pattern Recognition, ICAPR 2005, Springer

31

Lire http://www.pellegrini.cc/2016/11/la-biometrie-des-honnetes-gens-reloaded/ 32 Le risque est parfois quantifié en multipliant la probabilité d'un l'évènement redouté par ses impacts potentiels.

33

Même si le nombre d'usurpations d'identité est limité, chaque fraude peut avoir un impact potentiellement très grand pour les victimes. L'introduction d'un fichier biométrique centralisé peut donc conduire à remplacer des évènements (fraudes) peu probables et ayant une incidence sur un nombre limité de personnes en évènements très peu probables mais faisant un très grand nombre de victimes (attaques à grande échelle).

présentons

36

Les bases de données d'état civil et biométriques étant chiffrées, il est difficile d'accéder aux données en cas de fuite.

Déclaration de Jean-Jacques Urvoas sur son compte Facebook : https://fr-fr.facebook.com/JJ.Urvoas/

Site du ministère de l'Intérieur : http://www.interieur.gouv.fr/Actualites/Le-fichier-des-titres-electroniquessecurises

"Le consentement au traitement des données personnelles. Perspective comparative sur l'autonomie du sujet", C. Lazaro, D. Le Métayer, Revue Juridique Themis, vol. 48, n° 3, 2015, pp. 765-815, http://www.academia.edu/12524523/_Le_consentement_au_traitement_des_données_personnelles._Perspective _comparative_sur_lautonomie_du_sujet

Site du ministère de l'Intérieur : http://www.interieur.gouv.fr/Actualites/Le-fichier-des-titres-electroniquessecurises

 16 https://www.service-public.fr/particuliers/vosdroits/F21089

http://www.interieur.gouv.fr/Actualites/Le-fichier-des-titres-electroniques-securises

Nous préférons utiliser l'expression « plus difficile » plutôt que « impossible » qui nous paraît un objectif inatteignable. Cette question est discutée dans la partie 5.

Voir le site de l'ANTS (Agence Nationale des Titres Sécurisés) : https://ants.gouv.fr/Les-solutions/2D-Doc

La réponse du ministre de l'Intérieur au président du CNNum suggère le déploiement d'un réseau dédié et d'une application « conservée à distance solide des réseaux publics ».

Cybercriminels, gouvernement, états étrangers, activistes, employés indélicats, fraudeurs, etc.

Identification, surveillance, usurpation d'identité, spams, phishing, etc.

Intrusion, vol, complicité, falsification de documents, etc.

https://www.cnil.fr/sites/default/files/typo/document/CNIL-PIA-1-Methode.pdf

Cette démarche mériterait d'ailleurs d'être également adoptée pour les systèmes déjà déployés, notamment pour le système TES des passeports qui comporte plusieurs dizaines de millions d'entrées.

Journal officiel de l'Union européenne, 4 mai 2016, Règlement général sur la protection des données (article 35), http://eur-lex.europa.eu/legal-content/FR/TXT/?uri=OJ%3AL%3A2016%3A119%3ATOC

Voir notamment : S. J. De, D. Le Métayer, Privacy Risk Analysis, Morgan & Claypool Publishers, septembre 2016, S. J. De, D. Le Métayer, A Risk-Based Approach to Privacy by Design (extended version), Rapport de Recherche Inria 9001, décembre 2016.

Voir notamment l'annexe de l'avis du CNNum sur le fichier TES, https://cnnumerique.fr

L'ANSSI et la DINSIC insistent également sur cette exigence de traçabilité dans leur rapport d'audit.

Remerciements

Les auteurs tiennent à remercier Hervé Chabanne, Mathieu Cunche, Antoine Petit et Vincent Roca pour leurs remarques constructives sur des versions antérieures de ce document.

.interieur.gouv.fr/Actualites/Le-systeme-des-titres-electroniques-securises/Systeme-TES-publication-du-rapport-de-l-ANSSI-

A propos d'Inria

Inria, institut national de recherche dédié au numérique, promeut « l'excellence scientifique au service du transfert technologique et de la société ». Inria emploie 2600 collaborateurs issus des meilleures universités mondiales, qui relèvent les défis des sciences informatiques et mathématiques. Son modèle ouvert et agile lui permet d'explorer des voies originales avec ses partenaires industriels et académiques. Inria répond ainsi efficacement aux enjeux pluridisciplinaires et applicatifs de la transition numérique. Inria est à l'origine de nombreuses innovations créatrices de valeur et d'emplois


The distribution of prime numbers: overview of n.ln(n)

is effectively reduced compared to the empirical formula. We discuss about the results and hypothesize that p(n) can be approximated with a constant defined in this work.

As prime numbers are important to cryptography and other fields, a better knowledge of the distribution of prime numbers would be very useful. Further investigations are needed to understand the behavior of this constant and therefore to determine the nth prime number with a basic formula that could be used in both theoretical and practical research.

Preliminaries

We define the difference ∆ as below:

∆ = N -(n.ln(n)) n ∈ N * (1)
1 if N is the real nth prime number and n.ln(n) the approximated nth prime number (see abstract).

We define ζ as below:

ζ = (n.ln(n)) -∆ n ∈ N * (2)
We define as below:

= ζ ∆ ∆ = 0 (3)
The aim is to know ∆ to find the real nth prime number. In fact ∆ is the difference between the real nth prime number and the number given by the empirical formula. According to

(2) we have:

ζ = (n.ln(n)) -∆ n ∈ N * ζ = (n.ln(n)) -ζ = 0 ζ = (n.ln(n))-ζ = 0 ζ + ζ = (n.ln(n)) ζ( + 1) = (n.ln(n)) ζ = (n.ln(n))

+1

According to (3) we have:

= ζ ∆ ∆ = 0 ∆ = ζ = 0 = 0 (4)
Finally the real nth prime number is given by the following formula:

N = (n.ln(n)) + ∆ n ∈ N * N = (n.ln(n)) 2+ 1+ = -1 (5)
Consequently, we must to know to find ∆ and the real nth prime number. In this work we discuss about the value of that is associated with four intervals and two values for n (see Methods and results). Although there are variations for we define it as a constant because seems to show small variations (its value is -0.14092488 for n=2 and 7.271015283 for n = 10 6 ).

Methods and results

Methods

In this work we use four intervals and two values for n as described below:

n ∈ [2, 200] n ∈ [1000, 1195] n ∈ [1800, 1999] n ∈ [2600, 2799] n = 100000 n = 10 6
Note that the gap between each interval is about 600 (except for the first).

By using Microsoft Excel 2016 and a list of known prime numbers we define, for each n of each interval, the corresponding prime number. For example the prime number N corresponding to n=2 is 3. If n=5, the prime number N that is associated is 11.

Then, for each nth prime number, we calculate n.ln(n) that is the approximated nth prime number, ∆, ζ and . Finally, for each interval, we determine the average value for . We define as the average value for . Our results suggest that shows small variations even if n is comprised between 2 and 10 6 .

Finally, we calculate for each n of each interval, the corresponding nth prime number given by our method with the formula (5). We define this number as N and we determine the difference between N and the real nth prime number as ∆ . Our results show that the average value for ∆ is significantly smaller than the average value for ∆.

Results

Note the corresponding values for for each interval:

Discussion

We have established a relationship between the real nth prime number and a constant . The use of our method shows results much more effective compared to the empirical formula. For certain values of n, we found the real nth prime number (i.e ∆ = 0). For example, if n=100000 the real nth prime number that is associated is 1299709. The best value for for n=100000 is 6.757176176. With this value, we find the real prime number (∆ = 0).

Unfortunately the best value for is found only if we know the real nth prime number. If the real nth prime number is unknown, the best value for remains to be elucidated and the best value is required to find the real nth prime number. If we know it is possible to determine the precise nth prime number (∆ = 0 since there is a link between ∆ and (see (4)).

Interestingly seems to show very small variations whereas n is comprised between 2 and 10 6 . For this reason, we hypothesize that could be a very good constant in order to find a formula establishing a more precise link with the nth prime number. Nevertheless small variations for are responsible for greater variations for ∆ .

seems to exhibit very small variations while n allows high values. However shows high variations between the first and the second interval (5.81488845-5.1504379 = 0.66445055 for a difference of n=800 between the two intervals). shows smaller variations between the last interval and 100000 (6.757176176-6.19761627=0.559559906) and between 100000 and 10 6 (7.271015283-6.757176176=0.513839107). These results suggest that is not defined by the length of the gap between two intervals because in this case would be much more greater than 7.271015283 for n=10 6 . Furthermore, these results suggest that

-→ n→+∞ k if k ∈ R and k > 7.271015283
If this is the case, is a constant when n → +∞ and it will be easier to find a formula to determine nth prime numbers when n tends to infinity. But the most likely hypothesis is that doesn't converge when n tends to infinity and it will be more difficult to find a formula to determine nth prime numbers.

Interestingly we notice that if we consider a specific nth prime number (in the third interval of this study for example), the value of of the next or the previous prime number is very close to the value of for the specific nth prime number considered. This is very useful because we could imagine a formula giving the next prime number if the previous is known.

However this is an observation with exceptions and there is no evidence when n → +∞.

Moreover, even if the value of of a next prime number seems to be close to the value of of a previous prime number, there are unpredictable variations and a little mistake for the value of results in a big error in the determination of the nth prime number. Note that the value of a specific can be smaller than the value of of a previous prime number.

Moreover, for certain values of n we observe exceptions, for example for n=30 (the real nth prime number corresponding is 113) we found = 8.30638366, a value that is greater than the value of that is associated with n=10 6 (7.271015283). These observations suggest there are several exceptions for the value of . However the average value for ( ) seems to be greater than the value for that is associated with smaller values for n. Therefore the exact relationship between n and is unknown and may not exist. Thus, the behavior of remains to be elucidated (see below).

Figure 7: The behavior of remains to be elucidated when n > 10 6 . may converge to k when n → +∞ or not.

Conjecture

For n > 2 seems to be comprised between 0 and +∞ (if doesn't converge when n → +∞).

So we hypothesize that:

N = (n.ln(n)) 2+ 1+ N = (n.ln(n))p with 1 < p < 2, p = 2+ 1+ and n > 2
In fact -1 (for n=1) and -0.14092488 (for n=2) seem to be the only negative values for .

When n → +∞ and if doesn't converge we have p → 1 because:

lim →+∞ 2+ 1+ = 1
But p is not exactly 1 and a small variation of p (for example 1.00000005 instead of 1.00000004) is responsible for a big error in the determination of big nth prime numbers. 10 Now, when n is smaller is also smaller and we have:

lim →0 2+ 1+ = 2
This is the reason for which we hypothesized that 1 < p < 2. However this is a conjecture because it is not sure if -1 and -0.14092488 are the only negative values for , even if it is very likely.

Conclusion

We established a model in which we were able to find the real nth prime number by using a new constant called . When this constant is known precisely, the nth prime number is known precisely. If this constant is imprecise, the nth prime number will be imprecise. Surprinsingly we found that would be comprised between -0.14092488 (for n=2) and 7.271015283 (for n=10 6 ), even if n undergoes high variations (from 2 to 10 6 ). But small variations in result in an imprecise formula and there are several exceptions with values of that are greater than 7.271015283. For this reason, further investigations are needed to understand the behavior of and to establish a potential relationship between n and . For example a new work is necessary to study all prime numbers between 3 and 10 6 (not shown in this study because we worked with only four intervals and two values for n).

In all cases, even if isn't known precisely, our formula seems to be more precise than the empirical formula n.ln(n).

Tools

Statistics. Statistics were performed using Microsoft Excel 2016.

The list of prime numbers used in this study. http://compoasso.free.fr/primelistweb/page/prime/ liste online.php

n ∈ [ 2

 2

Figure 1 :

 1 Figure 1: ∆ (4.87377461) is significantly smaller than ∆ (75.819752) (average value). Resultsfor the interval[START_REF] Rosser | The n th prime is greater than n.log(n)[END_REF] 200]

Figure 2 :

 2 Figure 2: ∆ (15.0668754) is significantly smaller than ∆ (1127.19363) (average value). Results for the interval [1000, 1195]

Figure 3 :

 3 Figure 3: ∆ (19.3845647) is significantly smaller than ∆ (2022.39968) (average value).Results for the interval[1800, 1999]

Figure 4 :

 4 Figure 4: ∆ (29.0238221) is significantly smaller than ∆ (2963.99395) (average value). Results for the interval [2600, 2799]


Robert E Alvarez

Non-Invertibility of spectral x-ray photon counting data with pileup

Keywords: photon counting, pileup, spectral x-ray, dual energy, spectral x-ray, energy selective, Cramèr-Rao lower bound

the attenuation coefficient is approximated as a linear combination of functions of energy multiplied by coefficients that depend on the material composition at points within the object. The method then computes the line integrals of the basis set coefficient from measurements with different x-ray spectra. This paper shows that the transformation from photon counting detector data with pileup to the line integrals can become ill-conditioned under some circumstances leading to highly increased noise.

Methods: An idealized model that includes pileup and quantum noise is used. The noise variance of the line integral estimates is computed using the Cramèr-Rao lower bound (CRLB). The CRLB is computed as a function of object thickness for photon counting detector data with three and four bin pulse height analysis (PHA) and low and high pileup.

Results: With four bin PHA data the transformation is well conditioned with either high or low pileup. With three bin PHA and high pileup, the transformation becomes illconditioned for specific values of object attenuation. At these values the CRLB variance increases by approximately 10 5 compared with the four bin PHA or low pileup results. The condition number of the forward transformation matrix also shows a spike at those attenuation values. Conclusion: Designers of systems using counting detectors should study the stability of the line integral estimator output with their data.

I. INTRODUCTION

This paper studies the stability of the Alvarez-Macovski method [START_REF] Alvarez | Energy-selective reconstructions in X-ray computerized tomography[END_REF] with x-ray photon counting data with pileup. The method uses an expansion of the x-ray attenuation coefficient as a linear combination of functions of energy multiplied by constants that depend only on the material composition at points in the object. Transmission measurements with multiple x-ray spectra are then used to estimate the line integrals of the basis set coefficients. With a photon counting detector, the transmitted photons are analyzed with pulse height analysis [START_REF] Knoll | Radiation Detection and Measurement[END_REF](PHA) so that each bin provides a separate measurement spectrum.

In order to focus on fundamental effects, the noise in the line integral estimates is computed using an idealized model that only includes pileup and quantum noise. In the computation, the transmitted spectra are first computed using realistic models of the x-ray tube source spectrum [START_REF] Boone | An accurate method for computer-generating tungsten anode x-ray spectra from 30 to 140 kV[END_REF] and tabulated attenuation coefficients [START_REF] Hubbell | Review of photon interaction cross section data in the medical and biological context[END_REF]. The Aprendtech.com, ralvarez@aprendtech.com recorded photon counts with pileup are then computed using a non-paralyzable model of the recorded photon counts with pileup [START_REF] Knoll | Radiation Detection and Measurement[END_REF]. In the model, the recorded energies are assumed to be the sum of the energies of the photons incident during the dead time period. The recorded energy data are measured using pulse height analysis with ideal rectangular energy bins. The PHA bin counts are the input data to the A-vector estimator.

The probability distribution of the PHA bin counts with pileup is modeled as multivariate normal with parameters that depend on the spectrum of the photons incident on the detector and the pileup parameter [START_REF] Alvarez | Signal to noise ratio of energy selective x-ray photon counting systems with pileup[END_REF]. A universal limit on the A-vector estimate noise variance is computed using the Cramèr-Rao lower bound (CRLB), which is the minimum covariance for any unbiased estimator [START_REF] Kay | Fundamentals of Statistical Signal Processing[END_REF]. The CRLB is computed from the multivariate normal parameters [START_REF] Kay | Fundamentals of Statistical Signal Processing[END_REF] as a function of object thickness for photon counting detector data with three or four bin PHA with low and high pileup.

The results show that with high pileup three bin PHA data the noise variance exhibits a sharp peak at specific object thicknesses. The peak does not appear with four bin PHA data or three bin data with low pileup. The peak variance is approximately 10 5 times the values for the same thicknesses in the cases without the instability.

II. METHODS

A. The Alvarez-Macovski method

For biological materials and an externally administered high atomic number contrast agent, we can approximate the x-ray attenuation coefficient µ(r, E) accurately with a three function basis set [START_REF] Alvarez | Dimensionality and noise in energy selective x-ray imaging[END_REF]

µ(r, E) = a 1 (r)f 1 (E) + a 2 (r)f 2 (E) + a 3 (r)f 3 (E). (1)
In this equation, a i (r) are the basis set coefficients and f i (E) are the basis functions, i = 1 . . . 3. As implied by the notation, the coefficients a i (r) are functions only of the position r within the object and the functions f i (E) depend only on the x-ray energy E. If there is more than one high atomic number material present, we can extend the basis set to higher dimensions.

Neglecting scatter, the expected value of the number of transmitted photons λ k with an effective measurement spectrum S k (E) is

λ k = ˆSk (E)e -´µ(r,E)dr dE (2)
where the line integral in the exponent is on a line from the x-ray source to the detector. For idealized PHA data, the effective spectrum for each energy bin is

S k (E) = S incident (E) Π k (E) (3)
where S incident (E) is the x-ray spectrum incident on the detector and Π k (E) is a rectangle function equal to one inside the energy bin and zero outside. Using the decomposition, Eq. 1, the line integral in Eq. 2 is ˆµ (r, E) dr

= A 1 f 1 (E) + A 2 f 2 (E) + A 3 f 3 (E). (4)
where A i = ´ai (r) dr, i = 1 . . . 3 are the line integrals of the basis set coefficients. The A i are summarized as the components of the A-vector, A, and the measurements by a vector, N, whose components are the photon counts with each effective spectrum. Since the body transmission is exponential in A, we can approximately linearize the measurements by taking logarithms. The results is the log measurement vector L = -log(N/N 0 ), where N 0 is the expected value of the measurements with no object in the beam and the division means that corresponding members of the vectors are divided. Equations 2 define a relationship between A and the expected value of the measurement vector, L(A). For xray measurements with noise, we can use a statistical estimator to invert the relationship and to compute the best estimate of  from the measurements L taking into account the probability distribution of the noise.

B. The CRLB for A-vector noise

In general, the estimator noise depends on its implementation but we can derive fundamental limits on xray system performance by using the Cramèr-Rao lower bound (CRLB) [START_REF] Alvarez | Energy-selective reconstructions in X-ray computerized tomography[END_REF], [START_REF] Alvarez | Signal to noise ratio of energy selective x-ray photon counting systems with pileup[END_REF]. The CRLB is the minimum covariance for any unbiased estimator and is a fundamental limit from statistical estimator theory [START_REF] Kay | Fundamentals of Statistical Signal Processing[END_REF]. It is the inverse of the Fisher information matrix F whose elements are

F ij = - ∂ 2 L ∂A i ∂A j ( 5
)
where L is the logarithm of the likelihood and the symbol denotes the expected value.

A large number of detected photons are required for material selective x-ray imaging and therefore we can model the measurements as having a multivariate normal distribution [START_REF] Alvarez | Signal to noise ratio of energy selective x-ray photon counting systems with pileup[END_REF]. Kay [START_REF] Kay | Fundamentals of Statistical Signal Processing[END_REF] shows that the Fisher matrix for multivariate normal measurements with expected value L(A) and covariance C L has elements

F ij = ∂ L(A) ∂Ai T C -1 L ∂ L(A) ∂Aj + 1 2 tr C -1 L ∂C L ∂Ai C -1 L ∂C L ∂Aj (6)
where the tr [] is the trace of a matrix.

For x-ray data, the first term in the Fisher matrix is much larger than the second [START_REF] Alvarez | Signal to noise ratio of energy selective x-ray photon counting systems with pileup[END_REF]. Ignoring the second term, the Fisher matrix is

F const.cov. = M T C -1 L M (7)
where M is the gradient matrix

M = ∂ L(A) ∂A (8)
with elements M ij = ∂Li /∂Aj. Notice that M is also the system matrix of a linearized first order model of the measurements about an operating point Ā

L(A) = L(A) + ∂L ∂A (A -A) + • • • (9)
so that δL with noise = MδA + w where δL = L(A + δA) -L(A) , δA = A -A, and w is multivariate normally distributed measurement noise. If M is not invertible then we cannot estimate the A vector from the spectral measurements. In general, M is invertible in a mathematical sense but, as will be shown in later sections, with pileup it can become ill-conditioned leading to large increases in the noise variance.

C. Physical model of photon counting detector data with pileup

The idealized model for photon counting data with pileup is described in detail in a previous paper [START_REF] Alvarez | Signal to noise ratio of energy selective x-ray photon counting systems with pileup[END_REF] and is summarized here. The detector output with pileup is modeled with the dead time parameter, τ [START_REF] Knoll | Radiation Detection and Measurement[END_REF], which is the minimum time between two photons that are recorded as separate events. Two models of pileup are commonly used. In both of the models, the detector is assumed to start in a "live" state. With the arrival of a photon, the detector enters a separate state where it does not count additional photons. In the first model, called nonparalyzable, the time in the separate state is assumed to be fixed and independent of the arrival of any other photons during the dead time. In the second model, called paralyzable, the arrival of photons extends the time in the non-counting state. Both models give similar recorded counts at low rates but give different results at high rates where the probability of multiple interactions during the dead time becomes significant. The non-paralyzable model will be used here. Measurements by Taguchi et al. [START_REF] Taguchi | Modeling the performance of a photon counting x-ray detector for CT: energy response and pulse pileup effects[END_REF] indicate it is more accurate at higher count rates with their detectors. It also leads to simpler analytical results [START_REF] Yu | Mean and variance of single photon counting with deadtime[END_REF].

A model is also needed for the recorded energies with pileup. One approach is to assume that the recorded energy is proportional to the integral of the sensor charge pulses during the dead time [START_REF] Taguchi | Modeling the performance of a photon counting x-ray detector for CT: energy response and pulse pileup effects[END_REF]. An idealization of this model is to assume that the recorded energy is the sum of the energies of the photons that arrive during the dead time regardless of how close the arrival of a photon to the end of the period [START_REF] Wang | Pulse pileup statistics for energy discriminating photon counting x-ray detectors[END_REF]. The idealized model assumes that the photon energy is converted completely into charge carriers so there are no losses due to Compton or Rayleigh scattering and all K-fluorescence radiation is re-absorbed within the sensor. All of the carriers are assumed to be collected so there is no charge trapping or charge sharing with nearby detectors.

D. Probability distribution of PHA data with pileup

The probability distribution of the PHA bin counts is modeled as multivariate normal with the expected value and covariance in Table I. This model can be shown to be accurate for the number of x-ray photons required for material selective imaging [START_REF] Alvarez | Signal to noise ratio of energy selective x-ray photon counting systems with pileup[END_REF].

The parameters in the Table are defined as follows: the expected value of the total number of photons incident on the detector during the measurement time is

λ = ˆSincident (E)dE (10)
where S incident (E) is the spectrum of the x-ray photons incident on the detector. This spectrum can be computed for an object with A-vector A using Equations 2 and 4.

The average rate of photons incident on the detector is ρ and the pileup parameter, η = ρτ , is the expected number of photons arriving during a dead time period, τ . The total number of photons recorded by the detector in all PHA bins with pileup is N rec and the number recorded in PHA bin k is N rec,k . Notice that with non-zero η, the non-Poisson factor D is not zero so the recorded counts are not Poisson distributed. These formulas were validated using a Monte Carlo simulation [START_REF] Alvarez | Signal to noise ratio of energy selective x-ray photon counting systems with pileup[END_REF].

If the probability of a zero recorded photon count value is negligible, which is the case with the large expected values of counts required for material selective imaging, the logarithm of the data is also normally distributed with parameters [START_REF] Papoulis | Probability, Random Variables, and Stochastic Processes[END_REF]

L = log( N /N 0 ) var (L) = var (N) N 2 (11) cov (log(N 1 ), log(N 2 )) = cov(N 1 , N 2 ) N 1 N 2 .

E. Matrix condition number

As discussed in Sec. II-B, M is the system matrix at an operating point for the computation of the A vector from the measurements, L. The condition of this matrix measures the size of the perturbation of the solution δA for a small perturbation of the measurement δL. If the matrix is ill-conditioned then there are large δA perturbations for small δL and the noise in the A-vector estimates will be large.

The condition of a matrix is discussed in chapter 12 of Trefethen and Bau [START_REF] Trefethen | Numerical Linear Algebra[END_REF]. It is typically quantified by the condition number, κ, that is equal to one for a well conditioned matrix and is large for an ill-conditioned matrix. If the matrix M is square and invertible, its condition number is

κ = M M -1 . ( 12
)
If M is not square, then the pseudo-inverse is used for the second factor in Eq. 12.

Using the 2-norm, the condition number is equal to the ratio of the largest and smallest singular values for either a square or rectangular matrix.

F. Optimal PHA energy bins

The PHA bins used in the simulation were computed with an algorithm that maximized the A-vector SNR with the CRLB as the covariance

SN R 2 = (δA) T C -1 A,CRLB (δA)
The algorithm used as a signal δA = [0, 0, -1] T . That is, the imaging task was to detect changes in the third Avector components with other components fixed. The results were not changed for signals resulting from changes to the other components. The SNR was optimized by exhaustively searching all possible bin widths summing to the maximum energy in the spectrum with an increment of 3 keV. The transmitted spectrum for an A-vector in the center of the test object region described in Sec. II-G was used.

G. The test object

The performance of the spectral x-ray system was computed for objects with A-vectors on three lines through the A-vector space as shown in Fig. 1. These correspond to a set of thicknesses of objects with three compositions. The x-ray attenuation coefficient of the material of each object is approximated using Eq. 1. Summarizing the coefficients as the components of the a vector, the line integrals are A = aW , where W is the thickness with units corresponding to attenuation coefficient, for example g/cm 2 . The A-vectors for each material therefore fall on a straight line through the origin in A-vector space. The end points of the lines used in the simulations, which also specify the ratios of the a vector coefficients, were [16, 1.2, 0.1], [5, 0.9, 0.1125], and [16, 0.375, 0.1] g/cm 2 . Fig. 1 shows a three dimension plot of the lines.

The test object attenuates the x-ray beam before it is incident on the detector so the rate of photon arrivals on the detector and therefore the pileup parameter, η, decreases as the object thickness increases along the lines in A-vector space. Each line is the A-vectors of different thicknesses of a material with a specific a vector of coefficients in its attenuation coefficient expansion.

= ´Sincident (E)dE {0 < E 1 < . . . < E nbins } photon number spectrum S(E) Srec(E) = λprec(E) normalized spectrum p(E) = S(E)/λ prec(E) = ∞ k=0 η k k! e -η p (k) * p bin probabilities P k = ´Ek E k-1 p(E)dE P rec,k = ´Ek E k-1 prec(E)dE

H. Compute CRLB for test object

A 120 kilovolt x-ray tube spectrum was computed using the TASMIP algorithm of Boone and Seibert [START_REF] Boone | An accurate method for computer-generating tungsten anode x-ray spectra from 30 to 140 kV[END_REF]. The number of photons incident on the object for each detector element or pixel was set to 10 6 . The measurement time was assumed to be 10 milliseconds so the rate of photons incident on the detector with no object in the beam was 10 8 photons per second. With detector deadtimes of 10 and 1 nanoseconds the zero object thickness pileup parameter, η 0 , had values of 1 or 0.1.

The attenuation coefficients of the calibration phantom materials described in Sec. II-G were used as the basis functions of energy in Eq. 1. With this choice, the Avectors were the thicknesses of each of the materials in the calibration phantom [START_REF] Alvarez | A comparison of noise and dose in conventional and energy selective computed tomography[END_REF]. The attenuation coefficients of the materials were computed as the fraction by weight of each element in the chemical formula multiplied by the attenuation coefficient of that element. The elements' attenuation coefficients were computed by piece-wise continuous Hermite polynomial interpolation of the standard Hubbell-Seltzer tables [START_REF] Hubbell | Review of photon interaction cross section data in the medical and biological context[END_REF].

For a single A-vector on one of the lines in Fig. 1, the TASMIP x-ray tube spectrum and the basis material attenuation coefficients were used with Eq. 10 to compute the spectrum and the expected value of the total number of transmitted photons incident on the detector sensor during the measurement time. The sensor was assumed to be perfectly absorbing so the charge signal of each photon was proportional to the photon energy. Pulse height analysis was performed for the total energy of the photons incident on the sensor during the measurement time. As described in Sec. II-F, the PHA energy response functions were computed with an algorithm that maximized the SNR with no pileup and were assumed to be perfect rectangles. The CRLB was computed for three and four bin PHA.

The CRLB was computed numerically by approximating the derivatives in Eq. 7 from the first central difference. For example, to compute ∆L we first compute the spectra through the object with attenuation A and then with A+∆A. The transmitted spectra are not affected by pileup since they occur before the measurement. These transmitted spectra are then used to compute the expected values of the measurements with pileup using the formulas in Sec. II-D.

I. M condition number for test object

As discussed in Sec. II-E, we would expect the estimator noise variance to be large if the M matrix is illconditioned, that is, it has a large condition number. This was verified by simultaneously plotting the normalized A 1 variance and the M condition number along the three lines in A-vector space.

J. M condition in 3D A-vector space

The CRLB and condition numbers showed sharp peaks in plots along the lines in A-vector space. To better characterize the behavior, the M matrix condition number was computed in three dimensional A-vector space. This was done by computing the L values with pileup on a 3D grid of points. The M matrices at each of the points were computed using the Matlab gradient function, which approximates the gradient using the first central difference of the L vector data on the neighboring points. The condition number of the M at each point was then computed with the Matlab cond function.

Two dimension data of the condition numbers in the (A 1 , A 2 ) planes were extracted for each of the A 3 values. The local maxima in the 2D condition number data were found using the Matlab imregionalmax function and their three dimension coordinates were saved. A three dimension plot of the positions of the peak values in the three dimension A-vector space was then created.

The pileup parameters η on the A-vector space plane of peak condition numbers were computed.

K. PHA data for large pileup case

To gain some insight into the cause of the noninvertibility, the relationship between the peaks in condition number and the count data in each of the PHA bins were computed as a function of object thickness by plotting the expected bin count values along the A-vector line for material 3 (see Fig. 1) in separate graphs.

III. RESULTS

A. CRLB for three and four bin PHA Figures 3 and3 show the CRLB noise variance as a function of position along the three lines in A-vector space in Fig. 1. In both figures, the zero object thickness pileup parameter, η 0 , is 1 count per dead time, a relatively large value. Fig. 2 is for four bin PHA and Fig. 3 is for three bin.

Fig. 4 shows the estimates' CRLB variance for three bin PHA with a relatively small zero thickness pileup parameter, η 0 = 0.1.

B. M condition number and CRLB variance peaks

Fig. 5 shows plots of the M matrix condition number and the CRLB as a function of position on line 1. Note that the peaks in variance coincide with a large condition number i.e. ill-conditioned matrix.

C. Three dimension plot of A-vectors of M condition number peaks

Fig. 6 shows the M matrix condition numbers on three planes in A-vector space displayed as gray scale images. The images show the (A 1 , A 2 ) planes for A 3 values of .02, .04, and .06 g/cm 2 . Fig. 7 shows a 3D plot of the A-vectors of the peaks detected in the M matrix condition numbers images shown in Fig. 6. There are two views of the best fit plane. The side view in the bottom panel shows that the peaks are very close to the plane. Fig. 2. Four bin PHA CRLB noise variance as a function of object thickness along the three lines in A-vector space in Fig. 1. There was a large, zero thickness pileup parameter, η 0 = 1.

D. PHA bin counts and estimator variance vs. object thickness

Fig. 9 shows the L vector components and the A 3 estimate variance as a function of the object thickness for line 3 in Fig. 1.

IV. DISCUSSION Fig. 3 shows that with large pileup the three bin PHA data the CRLB variance exhibits a sharp peak that does not occur with the four bin PHA data results in Fig. 2. The peak is approximately 10 5 times larger than four bin PHA variance at comparable object thickness. It is due to large pileup since the variance with three bin PHA data but with a small pileup parameter in Fig. 4 does not exhibit the peak.

Fig. 5 shows that the peak in variance coincides with a peak in the condition number of the M matrix. The reason for this is clear from the constant covariance approximation to the Fisher matrix in Eq. 7,

M T C -1 L M -1 .
If M is ill-conditioned then the CRLB variance, which is its inverse, will be large. Fig. 4 shows that, even though there are no peaks in variance with low pileup, the variance first decreases and then goes through a minimum as the object thickness increases. This is particularly evident in the A plastic component. This is contrary to the behavior with zero pileup where the variance increases monotonically with object thickness. With pileup, the pileup parameter η decreases as object thickness increases because the rate of photon arrivals on the detector decreases. The decrease in pileup parameter causes the condition number of the M matrix to improve so even though the photon counts are decreasing the condition number improvement compensates and the A-vector variance decreases for small object thicknesses. As the object thickness increases above the initial range, the condition number does not decrease rapidly enough to compensate for the lower photon count and the noise variance increases.

The figures in Sec. III-C show that the M condition number peaks occur on a plane in 3D A-vector space. This implies that the inverse L(A) transformation becomes ill-conditioned for a specific attenuation. The histogram of the pileup parameter η values on the plane in Fig. 8 shows that the values are approximately the same, 0.73 ± 0.04.

The PHA bin count data for the three bin PHA, high pileup case in Fig. 9 show that the second bin data are not invertible since the curve has a zero derivative with respect to the A-vector magnitude plotted on the x-axis. The shape of the bin counts curve is due to the fact that, as the object thickness increases, the count rate and therefore the amount of pileup decreases rapidly. With less pileup there are fewer cases where the recorded energy is due to two or more photons. This tends to decrease the relative number of counts in the third high energy bin and to increase the relative number of counts in the first and second lower energy bins.

Notice however that the peak in variance and therefore M condition number, shown in the bottom panel of Fig. 9 does not occur at the zero derivative A-vector magnitude value but somewhat below that value. High pileup severely distorts the recorded data and reduces its information content compared with the nonpileup case. The other defects of photon counting detec- tors noted in the Introduction also reduce the information content and it is reasonable that they may also lead to increased estimator noise variance. Therefore, designers of systems using these detectors should study the statistical properties of their data and conduct studies of the implication for the stability of the estimator output.

V. CONCLUSION

Photon counting data with pileup can lead to sharply increased noise variance in the estimates of the line integrals of the basis set coefficients in the Alvarez-Macovski method. The increased noise occurs with high pileup three bin data but does not occur with four bin data or either three or four bin PHA data with low pileup. The peaks in noise variance occur for specific object attenuation. State of the art detectors have pileup as well as other defects so they may also exhibit the spikes in noise variance found in this study.

3 AFig. 1 .

 31 Fig.1. Three lines in A-vector space used in the Monte Carlo simulation. Each line is the A-vectors of different thicknesses of a material with a specific a vector of coefficients in its attenuation coefficient expansion.

  Fig.6shows the M matrix condition numbers on three planes in A-vector space displayed as gray scale images. The images show the (A 1 , A 2 ) planes for A 3 values of .02, .04, and .06 g/cm2 . Fig.7shows a 3D plot of the A-vectors of the peaks detected in the M matrix condition numbers images shown in Fig.6. There are two views of the best fit plane. The side view in the bottom panel shows that the peaks are very close to the plane. Fig. shows the histogram of the pileup parameter η on the plane of the peak variance in Fig. 7.

Fig. 3 .

 3 Fig.3. Three bin PHA CRLB noise variance with η 0 = 1 as a function of object thickness. Note the peaks. They have variance values more than 10 5 times larger than the 4-bin PHA variance in Fig.2for comparable thickness. A logarithmic y-axis scale is used.

Fig. 4 . 3 Fig. 5 .

 435 Fig. 4. Three bin PHA CRLB noise variance with low pileup, η 0 = 0.1. Compare with the high pileup case in Fig. Notice that with low pileup there are no peaks in the variance. [5].

Fig. 6 .Fig. 7 .

 67 Fig. 6. Gray scale images of M matrix condition numbers on three planes in A-space. The images show the (A 1 , A 2 ) planes for A 3 values of .02, .04, and .06 g/cm 2 .

Fig. 8 .

 8 Fig. 8. Histogram of the pileup parameter η on the plane of the peak variance in Fig. 7.

Fig. 9 . 1 .

 91 Fig. 9. The recorded photon counts for each PHA bin and the estimator variance as a function of the object thickness for line 3 in Fig. 1. The number of PHA bins is 3 and the zero thickness pileup parameter, η 0 = 1. The y-axis scale is linear.

Table I PHA WITH PILEUP PROBABILITY DISTRIBUTION PARAMETERS.

 I THE DISTRIBUTION IS MULTIVARIATE NORMAL WITH THE EXPECTED VALUE AND COVARIANCE SHOWN. IN THE TABLE, λ IS THE EXPECTED NUMBER OF PHOTONS INCIDENT ON THE DETECTOR DURING THE MEASUREMENT TIME, η IS THE EXPECTED NUMBER OF PHOTONS ARRIVING DURING A DEAD TIME PERIOD, Nrec IS THE TOTAL NUMBER OF PHOTONS RECORDED BY THE DETECTOR IN ALL PHA BINS AND N rec,k IS THE NUMBER RECORDED IN PHA BIN k.

	no pileup	with pileup
	λ