Hélène Fargier
email: fargier@irit.fr

Gildas Jeantet
email: gildas.jeantet@gmail.com

Olivier Spanjaard
email: olivier.spanjaard@lip6.fr

Resolute Choice in Sequential Decision Problems with Multiple Priors

. In this setting, a set of probability measures (priors) is defined instead of a single one, and the decision maker selects a strategy that maximizes the minimum possible value of expected utility over this set of priors. We are interested here in the resolute choice approach, where one initially commits to a complete strategy and never deviates from it later. Given a decision tree representation with multiple priors, we study the problem of determining an optimal strategy from the root according to min expected utility. We prove the intractability of evaluating a strategy in the general case. We then identify different properties of a decision tree that enable to design dedicated resolution procedures. Finally, experimental results are presented that evaluate these procedures.

Introduction

In many sequential decision problems, agents must act under uncertainty. This issue arises in several applications of artificial intelligence (AI), e.g. medical diagnosis (sequence of medical treatments/tests), troubleshooting under uncertainty (sequence of observations/repairs), poker-playing program (sequence of raise/call/fold). Decision theory provides useful tools to deal with uncertainty in decision problems. A decision under uncertainty is classically viewed as a function that maps states of the word to consequences -denoting Θ the set of states, X the set of consequences, D = {f : Θ → X} is the set of potential acts. Following the theory of expected utility [START_REF] Von Neuman And Morgenstern | Theory of games and economic behaviour[END_REF], a probability P can model the uncertainty about the state of the world, and a utility function u : X → U ⊂ R will capture the utility of the consequences. Then each decision f can be evaluated by its expected utility EU P,u (f ) = Σ θ∈Θ u(f (θ)) . P (θ) and compared to other decision. The best decision should be the one that maximizes expected utility.

However, it has been shown that expected utility cannot always capture the behaviour of rational decision makers. Ellsberg's counter example [1961] is the following: let U be an urn containing 1 3 of red balls and 2 3 of black or yellow balls.

One ball will be drawn and guessing the right color leads to a gain of 1 (0 otherwise). The decision to bet on red (resp. black) is denoted by f R (resp. f B ). The decision to bet on "red or yellow" (resp. "black or yellow") is denoted by f RY (resp. f BY ).Most of people prefer f R to f B and f BY to f RY . But there exist no probability measure P and no utility function u such that EU P,u (f R ) > EU P,u (f B ) and EU P,u (f BY ) > EU P,u (f RY ). The point is that the knowledge about the world is ambiguous: the underlying probability measure could be any probability in the set P = {P : P ({red}) = 1 3 , P ({black, yellow}) = 2 3 }. [START_REF] Gilboa | Maxmin expected utility with non-unique prior[END_REF] have then shown that most decision makers do use the expected utility model, but on the basis of the whole set of priors: they maximize the min, over P, of the possible values of the expected utility. In Ellsberg's example, for instance, the probability of {black} belongs to [0, 2 3 ]: the minimum value of EU for act f B is thus 0; for act f R , P ({red}) = 1 3 , hence the expected utility is 1 3 in any case: f R is preferred to f B . The probability of P ({red, yellow}) varies between 1 3 and 1, hence the min expected utility of act f RY is 1 3 (it is possible that there is no yellow ball). Probability P ({black, yellow}) is equal to 2 3 , hence the expected utility of act f BY is 2 3 in any case: f BY is preferred to f RY . The topic of this paper is to study how to optimize min expected utility in problems of sequential decision making under uncertainty involving multiple priors. More precisely, we tackle the problem of optimizing this criterion in a tree endowed with multiple priors. The choice of decision trees as the basic way of representing sequential problems is motivated by its generality: no linearity assumption on utility under certainty is indeed made, and even the Markov property is not required. Note that the algorithms proposed here can nevertheless be used to "solve" an influence diagram by "unfolding" the decision diagram in a decision tree, and then selecting an optimal strategy in this tree. This approach is suitable for small or medium size decision problems.

The question of selecting a strategy in a decision tree endowed with imprecise probabilities has received little attention in the literature. It raises two types of issues: decisiontheoretic ones [START_REF] Jaffray | [END_REF]Jaffray, 1999], i.e. the suitability -from the normative point of view-of various decision criteria under imprecise probability in a sequential decision setting, and algorithmic ones [START_REF] Kikuti | [END_REF]Huntley and Troffaes, 2008], i.e. the effective computation of an optimal strategy. In this paper, we are more concerned with the algorithmic issues.

In a decision tree endowed with clear probabilities, it is well-known that an optimal strategy can be recovered in linear time by rolling back the decision tree, i.e. computing a strategy recursively in a dynamic programming manner. Nevertheless, this approach is not valid anymore when optimizing min expected utility in a decision tree with multiple priors, since Bellman's principle of optimality does not hold anymore. From this point, two research directions can be explored. The first one, followed by [START_REF] Kikuti | [END_REF] is to add an assumption of dynamic feasibility, which amounts at seeking the strategy returned by rolling back the decision tree. This strategy will be preferred by a consequentialist decision maker, i.e. a decision maker whose present decision does not depend on the past nor on what she plan to do when making her first decision. Though appealing from an algorithmic viewpoint, this approach does not necessarily prevent the decision maker from selecting a strategy that could be "dominated" in some sense [Hammond, 1988]. The alternative way, proposed by [McClennen, 1990], is the resolute choice approach, where the decision maker commits to an optimal strategy viewed from the root of the decision tree, and never deviates from it later. It raises a challenging algorithmic problem, provided the combinatorial number of potential strategies. Huntley and Troffaes [2008] have adressed this issue by proposing a very generic method to compute the set of non-dominated strategies (to be defined later), but without entering into computational considerations: they do not study the computational complexity of the problem, and the method they provide is not implementable as it stands.

The paper is organized as follows. After introducing the framework (Section 2), we show that evaluating a strategy according to min expected utility is NP-hard (Section 3) and we study how linear programming can be used to automatize this evaluation. We then provide operational algorithms to compute an optimal strategy (Section 4), and conclude by reporting the results of numerical tests (Section 5).

Decision Trees with Multiple Priors

In multistage decision making, one studies problems where one has to make a sequence of decisions conditionally to events. Decision trees provides a simple and explicit representation of a sequential decision problem under uncertainty. A decision tree T involves three kinds of nodes: a set N D of decision nodes (represented by squares), a set N C of chance nodes (represented by circles) and a set N U of utility nodes (leaves of the tree). A decision node can be seen as a decision variable, the domain of which corresponds to the labels of the branches starting from that node. A random variable X is assigned to each chance node, and there is one outgoing branch for each possible value x ∈ D(X), where D(X) is the domain of X. These branches are labelled by the probabilities of the corresponding events. The values indicated at the leaves correspond to the utilities of the consequences. For illustration, we now present an example of a decision tree representing a sequential problem involving an Ellsberg's urn. Example 1 Consider a game beginning with a toss coin, before a ball is drawn in an Ellsberg's urn (the same as in the introduction). Depending on whether the coin comes up heads or tails (random variable X 1 , with D(X 1 ) = {H, T } for heads and tails), the decision maker is asked to bet on red or black (decision D 1 ), or red or yellow (decision D 2 ). The color of the ball is a random variable X 2 , with D(X 2 ) = {R, B, Y } for red, black or yellow. If the decision maker bets on red (f R ) and a red ball is drawn, it yields a gain of 1 -ε (with ε > 0). If she bets on black or yellow (f B or f Y ) and the guess is correct, it yields a gain of 1. The overall game can be represented by the decision tree of Figure 1. Note that random variable X 2 appears several times in the decision tree since the draw can be made in several contexts (the coin comes up heads and the decision maker chooses red, the coin comes up heads and the decision maker chooses black, etc.).

When crisp probabilities are known, the joint probability measure over the random variables X i is not given in extenso, but through the labelling on the tree by conditional probabilities : each branch starting from a chance node X j i represent an event X i = x and is endowed with a number, that represents the probability P (X i = x|past(X j i )), where past(X j i ) denotes all the value assignments to random and decision variables on the path from the root to X j i . Furthermore, in this paper, we assume that P (X i = x|past(X j i )) only depends on the random variables in past(X j i ). In the case of multiple priors, the joint probability is imprecise and it is not possible to represent it by a labeling of the edges with numbers. In the present paper, we propose to label them by variables representing the (ill-known) possible values of the conditional probabilities. Each branch starting from a chance node X j i represents an event X i = x and is labelled by a variable p i,j,x (for P (X i = x|past(X j i ))). The joint imprecise probability should be expressed explicitly, by a set of joint probability measures, but it is not always feasible, e.g. when random variables have an infinite range of possible values. In this paper, we consider the case where the set of measures are represented by probability intervals P (X i ∈ E|past(X j i )) on events E, where E ⊆ D(X i ). Formally, we have sets of linear constraints C j i locally defined over subsets of variables p i,j,x at each chance node X j i . A

(D 1 = f B , D 2 = f Y ). constraint c ∈ C j i takes the form p - c ≤ x∈Dc p i,j,x ≤ p + c
, where D c = {x : p i,j,x is in the scope of c} ⊆ D(X i ) and p - c , p + c are reals (if p - c = p + c the interval is said degenerated). In Figure 1, these constraints are defined as follows:

C 1 1 = { 1 2 ≤ p 1,1,H ≤ 1 2 , 1 2 ≤ p 1,1,T ≤ 1 2 } C j 2 = { 1 3 ≤ p 2,j,R ≤ 1 3 , 2 3 ≤ p 2,j,B + p 2,j,Y ≤ 2
3 } for all j Obviously, if the probabilities are precisely known at node X j i , then C j i simply assigns a value to each p i,j,x . Furthermore, some independencies can be taken into account by explicitly adding a set C e of equality constraints over the p i,j,x . In the example, since X 1 and X 2 are independent, we have p 2,1,x =p 2,2,x =p 2,3,x =p 2,4,x for all x. We denote by P T the set of possible probability measures over decision tree T that are compatible with constraints C = ( i,j C j i ) ∪ C e . In a decision tree T , a strategy consists in setting a value to every decision node, i.e. to every decision variable conditionally to the past. The decision tree in Figure 1 includes 4 feasible strategies, among which for instance strategy s

= (D 1 = f B , D 2 = f Y ).
In our setting, a strategy can be associated to a compound lottery over the utilities, where the probabilities of the involved events are ambigous. For instance, strategy s corresponds to the compound lottery pictured in Figure 2. Comparing strategies amounts therefore to compare compound lotteries. The evaluation of a strategy (more precisely, of the corresponding compound lottery) according to min expected utility depends on the multi-prior set P T . In this setting, we denote by EU(s) = min P ∈P T EU (P, s) the min expected utility of strategy s, where EU (P, s) is the expected utility of s for probability measure P . A strategy s is preferred to s if EU(s) > EU(s ). We show in the next section that the evaluation of a strategy is a combinatorial problem in itself due to the combinatorial nature of P T .

Evaluating a Strategy

We now prove that evaluating a strategy according to its min expected utility is an NP-hard problem, where the size of an instance is the number of involved chance nodes.

Proposition 1 Evaluating a strategy according to its min expected utility is an NP-hard problem, even if all nondegenerated probability intervals are [0, 1].

Proof.

The proof relies on a polynomial reduction from problem 3-SAT, which can be stated as follows: given a set X of boolean variables and a collection C of clauses on X such that |c| = 3 for every clause c ∈ C, does there exist an assignment of truth values to the boolean variables of X that satisfies simultaneously all the clauses of C ? Let X = {x 1 , . . . , x n } and C = {c 1 , . . . , c m }. Note that evaluating a strategy amounts to evaluating a compound lottery. One associates a random variable X i to every booolean variable x i , with domain {true, f alse}. The polynomial generation of a compound lottery from an instance of 3-SAT is performed as follows. One generates a subtree T k for each clause c k ∈ C. The indices of the boolean variables appearing in clause c k are denoted u k , v k , w k . For instance, for clause c 2 = x 1 ∨ x 3 ∨ x 4 , u 2 = 1, v 2 = 3 and w 2 = 4. Subtree T k is a complete binary tree such that: -the root (depth 0) is a chance node labeled by X u k , -nodes of depth 1 are chance nodes labeled by X v k , -nodes of depth 2 are chance nodes labeled by X w k , -nodes of depth 3 are utility nodes. Each chance node X j i has two outgoing branches: -one corresponding to X i = true and labelled by p i ∈ [0, 1], -one corresponding to X i = f alse and labelled by 1 -p i . Finally, the value of a utility node is 1 if it is on the path making false all the literals of c k , otherwise its value is 0. Once all subtrees T k have been generated, a unique root node X 0 is generated, which is parent of all subtrees T k . A probability 1/m is assigned to each branch from X 0 . This concludes the reduction. Clearly, the generated tree can be computed in polynomial time. As an illustration, in Figure 3, we give the compound lottery generated from the following instance of 3-SAT:

(x 1 ∨ x 2 ∨ x 3 ) ∧ (x 1 ∨ x 3 ∨ x 4 ).
Let us show that the 3-SAT formula is satisfiable if and only if the min expected utility of the compound lottery is 0. If there is an instantiation {x 1 = a 1 , x 2 = a 2 , . . . , x n = a n } that satisfies the 3-SAT formula, then the min expected utility of the compound lottery L is 0. Indeed, setting each variable p i to 1 if a i is equal to "true", and 0 otherwise, yields a min expected utility equal to 0. This is related to the fact that each utility node of value 1 is the terminal node of the unique path in T k that makes false clause c k . As clause c k is made true by the instanciation, this utility node has probability 0 to be reached. Conversely, if the min expected utility of L is 0, then the 3-SAT formula is satisfiable. Indeed, given an instantiation of parameters p i making zero the min expected utility of the lottery, the probability to reach a nonzero utility node is necessarily 0. This implies that, for every path to a nonzero utility node, at least one probability p i is 0 (label p i ) or 1 (label 1 -p i ). By setting value "true" (resp. "false") to x i if p i = 1 (resp. 0), the 3-SAT formula is satisfied.

We now describe a procedure to evaluate a strategy, based on a mathematical programming formulation. Before providing the formal expression of min expected utility EU(s) of a strategy s, we need to introduce some notations. We denote by X 1 , . . . , X n the set of random variables appearing in a decision tree T , and by X = X 1 , . . . , X n the corresponding random vector. We denote by D(Y ) the domain of a random variable (or random vector) Y . Furthermore, given a subset I ⊆ {1, . . . , n} of indices, we denote by X I the random vector whose components are X i (i ∈ I). Besides, given a node N , we denote by π(N ) the set of indices of the random variables on the path from the root to N (random variable Figure 3: An example of reduction for the following instance of 3-SAT:

(x 1 ∨ x 2 ∨ x 3 ) ∧ (x 1 ∨ x 3 ∨ x 4 ). in N excluded if N ∈ N C ).
The complementary set is denoted by π(N ) = {1, . . . , n} \ π(N ). Finally, we denote by x(N ) the assignment vector of X π(N ) that leads to node N . For instance, consider the decision tree of Figure 1. We have π(X 1 2 ) = {1} since random variable X 1 (node X 1 1 ) appears on the path from X 1 1 to X 1 2 . Thus X π(X 1 2 ) = X 1 , and x(X 1 2 ) = H since X 1 = H on the considered path. In a decision tree T , a strategy s is characterized by the subset U s ⊂ N U of utility nodes it enables to reach. The min expected utility EU(s) of s can thus be written as follows: EU(s) = min

P ∈P T N ∈Us P (X π(N ) = x(N )) × u(N )
where P (X π(N ) = x(N )) represents (in accordance with our notations) the probability to reach node N when following strategy s. For instance, strategy 1 yields the following formula:

(D 1 = f B , D 2 = f Y ) in Figure
EU(s) = min P ∈P T P (X 1 = H, X 2 = B)+P (X 1 = T, X 2 = Y )
Given the combinatorial nature of P T , we formulate a mathematical program to evaluate a strategy s. The main difficulty consists in characterizing the set of measures P ∈ P T . The fact that the crisp probabilities satisfies constraints C is indeed not sufficient to ensure the global consistency of the probability measure over T [START_REF] Jeantet | [END_REF], due to the possibility of several instances of the same random variable in T . For instance, assume that the probabilities P (X 1 ), P (X 2 ) and P (X 2 |X 1 ) appear in the decision tree. Then, the total probability theorem should hold: P (X 2 ) = x∈D(X1) P (X 2 |X 1 = x)P (X 1 = x). In order to characterize set P T of "feasible" probability measures, we define constraints upon atomic probabilities P (X = x) instead of variables p i,j,x . Furthermore, we consider the probabilities P (X(N ) = x(N )) to reach each of the nodes N of the tree, provided the node is compatible with the followed strategy. The variables used in our formulation are thus not the p i,j,x , and their number is exponential in n (number of distinct random variables), but the interest is that they are sufficient to both properly characterize a probability measure and insure its compatibility with C. So that Kolmogorov's axioms hold, it is necessary to satisfy the following constraint:

x∈D(X) P (X = x) = 1
In Example 1, one has:

x 1 ∈D(X 1 ) x 2 ∈D(X 2 ) P (X 1 = x 1 , X 2 = x 2 ) = 1.
Besides, in order to link atomic probabilities P (X = x) to probabilities P (X π(N ) = x(N )), we introduce the following linear constraints for all N ∈ N (there are some redundancies, but we do not elaborate here to save space):

P (X π(N ) = x(N )) = y∈D(X π(N ) ) P (X = (x(N ), y))
where (x, y) denote the assignment of X such that X π(N ) = x and X π(N ) = y. In Example 1, for N = X 1 2 , it writes:

P (X1 = H) = x 2 ∈D(X 2 ) P (X1 = H, X2 = x2)
Then, to insure that constraints C j i are satisfied, we introduce the following constraints for each chance node X j i by using Bayes' rule: ∀c ∈ C j i ,

P (X π(X j i ) = x(X j i )) × p - c ≤ z∈Dc P (X π(X j i )∪{i} = (x(X j i ), z)) z∈Dc P (X π(X j i )∪{i} = (x(X j i ), z)) ≤ P (X π(X j i ) = x(X j i )) × p + c
where D c is the subdomain of X i involved in constraint c (see Section 2), and X π(X j i )∪{i} = (x, z) means that X π(X j i ) = x and X i = z. In Example 1, it writes for X 1 2 , :

1 3 P (X1 = H) ≤ P (X1 = H, X2 = R) ≤ 1 3 P (X1 = H) 2 3 P (X1 = H) ≤ P (X1 = H, X2 = B) + P (X1 = H, X2 = Y ) P (X1 = H, X2 = B) + P (X1 = H, X2 = Y ) ≤ 2 3 P (X1 = H)
Finally, to insure that constraints C e are satisfied, we need the following bilinear constraint, by using Bayes' rule:

P (Xi = x, X π(X j i ) = x(X j i )) × P (X π(X j i ) = x(X j i )) = P (X i = x, X π(X j i ) = x(X j i )) × P (X π(X j i ) = x(X j i ))
for each constraint p i,j,x = p i ,j ,x in C e . In Example 1, for constraint p 2,1,R = p 2,3,R , it writes:

P (X1 = T ) × P (X1 = H, X2 = R) = P (X1 = H) × P (X1 = T, X2 = R).
The characterization of P T thus requires O(|N |+|D(X)|) variables (representing the probabilities to reach each of the nodes, and the atomic probabilities) and O(|N | + |C|) constraints (the constraints to link the atomic probabilities to the probabilities to reach each of the nodes, and the constraints to insure compatibility with C). Clearly, |D(X)| (and hence n) appears to be a key parameter for the spatial (and time) efficiency of this formulation, and the numerical tests will confirm it. Now that P T is characterized, we are able to evaluate a strategy by using an off-the-shelf optimization software.

Selecting a Strategy

Due to their combinatorial number, the enumeration of all strategies is quickly cumbersome. Furthermore, when trying to maximize min expected utility in a decision tree, it is important to note that the optimality principle does not hold. For illustration, let us perform the rolling back procedure on the decision tree of Figure 1. In D 1 and D 2 , the decision maker prefers decision f R , since it provides a min expected utility of (1 -ε)/3, while it is 0 for the other decision. The strategy returned by rolling back the decision tree is therefore s

= (D 1 = f R , D 2 = f R ). The min expected utility of s is (1 -ε)/3, while strategy (D 1 = f B , D 2 = f Y ) yields 1/3.
Hence, to compute a strategy optimizing min expected utility one cannot resort to standard dynamic programming in the general case. Nevertheless, there exist cases authorizing it. We describe one such case in the next paragraph.

Separable Decision Trees. For each chance node X j i , we denote by P j i the set of conditional probability distributions over X i |past(X j i ) that satisfies constraints C j i . A decision tree T is called separable (or separately specified [START_REF] Kikuti | [END_REF]) if P T = X j i ∈N C P j i . In such a tree, it is valid to use a rolling back procedure for maximizing min expected utility. In this procedure, comparing strategies s and s in a subtree amounts to compare the induced (ambiguous) lotteries L s and L s . The validity of the rolling back procedure is related to the fulfillment of the following property:

EU(λL s + (1 -λ)L s ) = λEU(L s ) + (1 -λ)EU(L s )
where λ ∈ [0, 1] and λL s + (1 -λ)L s is the compound lottery that yields lottery L s (resp. L s ) with probability λ (resp. (1 -λ)). The fulfillment of this property directly follows from the separability assumption [START_REF] Jeantet | [END_REF]. The optimal min expected utility EU * (N ) at node N is computed recursively by using the following formulas: -At a decision node

D i : EU * (D i ) = max d∈D(Di) EU * (D i = d).
where D(D i ) is the domain of decision variable D i .

-At a chance node X j i : EU * (X j i ) = min

P ∈P j i x∈D(Xi) P (X i = x|past(X j i ))EU * (N x ).
where N x is the node reached if X i = x.

The computation of EU * (X j i ) according to the above formula requires the resolution of a linear program whose set of constraints is C j i (note that the separability assumption implies of course that C e = ∅). The number of such (small size) linear programs solved during the running of the procedure is clearly linear in the number of chance nodes.

Non-separable Decision Trees. In the general (nonseparable) case, the rolling back method does not work when directly operating with min expected utility. However, one can use the following simple property: if a strategy s is dominated by another strategy s , i.e. EU (P, s) ≤ EU (P, s ) for all P ∈ P T , then EU(s) ≤ EU(s ). The main idea is therefore to compute the set of all non-dominated strategies (w.r.t. the asymetric part of the previous relation) in a first phase, and then, in a second phase, to recover the optimal one in this set according to min expected utility. The evaluation procedure of Section 3 can be used to determine the best strategies in the second phase. It has been proved that the set of non-dominated strategies can be computed by rolling back the decision tree [Huntley and Troffaes, 2008]. We provide here an operational approach to perform this procedure in our setting. The set S * (N ) of non-dominated strategies at node N is computed recursively:

-At a decision node N : S * (N ) = N D( The key primitive in this procedure is function N D(•). To compute the non-dominated elements of a set S, one performs pairwise comparisons of strategies in S. Such comparisons are called dominance test hereafter. A strategy s dominates a strategy s if there does not exist P ∈ P T (i.e., satisfying the constraints presented in Section 3) such that:

N ∈Us P (X π(N ) =x(N ))×u(N ) < N ∈U s P (X π(N ) =x(N ))×u(N )
where U s is the subset of utility nodes that s reaches. The test thus amounts to solve a set of linear constraints.

Numerical Tests

The proposed algorithms have been implemented in C++, and the CPLEX solver has been used to solve the mathematical programs. The numerical tests have been performed on a Pentium IV 2.13GHz CPU computer with 3GB of RAM.

For the separable case, one considers decision trees of (even) depth h, where all chance (resp. decision) nodes have outdegree d (resp. 2). The utilities are real numbers randomly drawn in [0, 100]. To define the imprecise probability, or equivalently the constraints C j i , one generates d -1 constraints of arity d -1 (two constraints of arity 1 if d = 2). For each constraint c, one sets p + c -p - c = 0.1. The average execution times on 20 such random instances are reported in Table 1. Timeout was set to 100 sec., and symbol X appears as soon as the running time exceeded the timeout for at least one instance. Notice that our procedure was able to solve decision trees with up to 2m nodes and that, unsurprizingly, ambiguity degree d has a great impact on the resolution times.

For the non-separable case, one considers binary and complete decision trees of even depth h, with real utilities in [0, 100]. The binary assumption allows to consider a larger range of depths for the decision trees. To generate the constraints C j i on the imprecise probabilities, we first generate a crisp probability distribution P over n random variables. Then, for each chance node, a random variable is randomly Table 3: Average execution time (in sec.) of a positive dominance test according to number n of random variables. assigned. At each chance node, following Bayes' rule, we compute the crisp conditional probabilities according to P . Finally, each conditional probability p on a branch is replaced by an interval [p -, p + ] including p. The imprecision degree w = p + -p -ranges in {0.01, 0.05, 0.1, 0.5} (one value for the whole tree). Furthermore, and importantly, one sets C e = ∅ in all instances. This assumption prevents from the insertion of bilinear constraints, and the CPLEX solver can therefore safely be used for evaluating strategies and testing dominance. The average execution times over 20 random instances are reported in Table 2 (symbol "-" means that n is greater than the number of chance nodes). Line N D gives the average number of non-dominated strategies at the root. Timeout was set to 1000 seconds. The size of the tackled instances are of course smaller than in the separable case, since the procedure handles sets of non-dominated elements, which is computationally more demanding than simply rolling back single values. As the dominance test is an important primitive in the procedure, Table 3 gives the average execution times of such tests according to the number n of random variables. We report here only the cases when a dominance relation is actually detected (average over 50 positive cases), since it takes longer than when it does not exist. Consistently with our expectation, the times strongly increase with n, that appears to be a key parameter for the efficiency of the procedure.

Conclusion

The optimization of min expected utility in sequential decision problems with multiple priors is known to be difficult from the algorithmic point of view, since the usual principles of dynamic programming do not apply. We have shown in this paper that the problem is indeed intractable. Evaluating a given strategy is NP-hard, even in a simple variant where the distinct random variables are mutually independent. Facing this difficulty, we distinguished two cases: separable and nonseparable decision trees. For each case, we have proposed a dedicated procedure to tackle the problem. Our first experiments are promising, although classic improvements still have to be explored, e.g. column generation [START_REF] Kikuti | [END_REF], use of bounds to prune the search, etc.

The model proposed here is nevertheless quite simple from the viewpoint of expressivity. In a more general setting, one should provide the user with a richer way of expressing her knowledge about the random variables, e.g. by a credal network. Clearly, the more expressive the setting, the higher the risk of an increase in complexity. The challenge is to balance expressivity of the model and algorithmic efficiency.

Figure 1 :

 1 Figure 1: A decision tree involving an Ellsberg's urn.

Figure 2 :

 2 Figure 2: Lottery for strategy (D 1 = f B , D 2 = f Y ).

k i=1 S

 i=1 * (N i )) where N 1 , . . . , N k are the children of N and N D(S) returns the set of non-dominated strategies in S.-At a chance node N :S * (N ) = N D({s 1 ⊕ . . . ⊕ s k : s i ∈ S * (N i ) ∀i})where N 1 , . . . , N k are the children of N and ⊕ is the combination operation of substrategies.

Table 1 :

 1 Separable case: average execution time (in sec.) according to height h and outdegree d of chance nodes.

	h \ d	2		3		4
		# nodes	time	# nodes	time	# nodes	time
	8	511	< 1	2073	< 1	5851	< 1
	10	2047	< 1	12441	< 1	46811	< 1
	12	8191	< 1	74639	1.2	374491	5.7
	14	32767	< 1	447897	7.8	2995931	65.5
	16	131071	2.6	2687385	57.3	X
	18	524287	10.8	X		X
	20	2097151	43.2	X		X


Anna ‡ Guerra
email: anna.guerra3@unibo.it

Francesco ‡ Guidi
email: francesco.guidi@cea.fr

Antonio Clemente
email: antonio.clemente@cea.fr

Laurent ‡ Raffaele D'errico
email: raffaele.derrico@cea.fr

Davide ‡ Dussopt

Dardari

Dussopt

Millimeter-Wave Backscattering Measurements with Transmitarrays for Personal Radar Applications

Keywords: Millimeter-wave propagation measurements, massive antenna arrays, indoor mapping, personal radar

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Millimeter-wave Backscattering Measurements with

Transmitarrays for Personal Radar Applications Anna Guerra * , Francesco Guidi † ‡ , Antonio Clemente † ‡ , Raffaele D'Errico † ‡ , Laurent Dussopt † ‡ , and Davide Dardari * I. INTRODUCTION In the new era of device-to-device (D2D) communications, claimed by the fifth generation (5G) wireless mobile networks, people and objects will share their information in real time, as data transfer could be enabled at an unprecedented scale. At the moment, 5G is still at its infancy, as its practical adoption is expected in the next decade [1], with a consequent explosion of research studies and projects for its assessment. To put forth on the need to achieve high data rates and D2D communication, massive arrays and millimeter-wave (mmW) technology have become a matter of investigation [START_REF] Rusek | Scaling up MIMO: Opportunities and challenges with very large arrays[END_REF], [START_REF] Rappaport | Millimeter wave wireless communications[END_REF]. It is expected that their joint adoption will play a key role in future 5G communications scenarios [START_REF] Boccardi | Five disruptive technology directions for 5G[END_REF]. Indeed, the reduced wavelength at mmW paves the way for packing a large number of antenna elements into a small area and for adopting massive arrays systems at base station (BS) or access points (APs) as well as at mobile end [START_REF] Rusek | Scaling up MIMO: Opportunities and challenges with very large arrays[END_REF], [START_REF] Hong | Study and prototyping of practically large-scale mmwave antenna systems for 5G cellular devices[END_REF].

In this context, transmitarrays (TAs) are a recent cuttingedge antenna array technology. Thanks to their spatial feeding techniques, TAs are extremely attractive compared to traditional phased arrays that suffer from large insertion losses due to their beamforming network and do not experience any feed blockage effects if compared to reflector and reflectarray antennas [START_REF] Kaouach | Wideband low-loss linear and circular polarization transmit-arrays in V-band[END_REF]- [START_REF] Palma | Circularly polarized transmit-array with sequentially rotated elements in Ka band[END_REF]. Studies concerning the adoption of mmW TAs can be found in [START_REF] Kaouach | Wideband low-loss linear and circular polarization transmit-arrays in V-band[END_REF]. Note that such reduced dimensions open new interesting scenarios for the integration of arrays on smartphones and for the development of new applications.

In this perspective, the concept of a smart personal radar has been recently proposed in [START_REF] Guidi | Personal mobile radars with millimeter-wave massive arrays for indoor mapping[END_REF]- [START_REF] Guerra | Millimeter-wave personal radars for 3D environment mapping[END_REF] as well as the adoption of TAs for this kind of application [START_REF] Guerra | Application of transmitarray antennas for indoor mapping at millimeter-waves[END_REF]. The personal radar is based on the idea of a massive array operating at mmW frequencies able to electronically scan the surrounding environment and to reconstruct a map of it (see Fig. 1). As a consequence, a high-definition distance estimate (ranging) and very narrow steering beams (angle resolution) are essential requirements to achieve a high level of mapping reconstruction. Differently from previous works in the field of mapping and localization [START_REF] Jose | An augmented state SLAM formulation for multiple line-of-sight features with millimetre wave radar[END_REF], such needs are met by the combination of the mmW technology and massive arrays.

Moreover, the possibility to share data within the incoming crowd-sensing technology [START_REF] Wu | Smartphones based crowdsourcing for indoor localization[END_REF] opens unprecedented scenarios where continuously up-to-date maps could be obtained with zero-efforts exploiting not participatory users. In fact, to avoid invasive and costly ad-hoc systems to support people (e.g., visually impaired people) and perform self-localization, the adoption of personal radars in next generation smartphones represents an appealing idea [START_REF] Dardari | A combined GP-state space method for efficient crowd mapping[END_REF].

In this paper we aim at characterizing real mapping performance by exploiting, for the first time, measurements collected in the V-band in a typical office environment. Stimulated by the preliminary simulation results presented in [START_REF] Guidi | Personal mobile radars with millimeter-wave massive arrays for indoor mapping[END_REF], [START_REF] Guerra | Application of transmitarray antennas for indoor mapping at millimeter-waves[END_REF], we have conducted a mmW measurements campaign with the purpose of assessing the actual system performance and the feasibility of the personal radar idea. We first describe the measurements campaign and then we include the collected data in the mapping algorithm in order to reconstruct the environment and to test the feasibility of the proposed ap- proach. Measurement mapping results are finally compared with simulation ones.

The rest of the paper is organized as follows. Sec. II describes the measurement set-up and the considered TAs. Sec. III presents the mapping algorithm and finally, Sec. IV describes the case study and discuss the obtained measurement and simulations results. Sec. V concludes the work.

II. MILLIMETER-WAVE INDOOR MEASUREMENT CAMPAIGN

A. Measurements Set-Up

In order to validate the personal radar concept, a measurements campaign has been conducted at CEA-Grenoble indoor premises (the map of the building floor is reported in Fig. 2

-(top-left)).

In particular, we exploited the measurement set-up represented in Fig. 2

-(right) which consists of:

• A 4-ports Vector Network Analyzer (VNA) operating in the frequency range 10 MHz-24 GHz;

• 2 mmW converters operating in the frequency range 50 GHz-75 GHz;

• 2 Linearly polarized TAs (size 20×20, 1 bit, F/D = 0.5) [START_REF] Kaouach | Wideband low-loss linear and circular polarization transmit-arrays in v-band[END_REF];

• X-Y-Azimuth positioner.

A bistatic configuration has been considered with the TAs spaced apart of 0.16 m in order to mitigate the antenna coupling and to separate the transmitting and receiving channels. As the objective application is to facilitate the navigation inside buildings (as for example blind-aid applications), the corridor has appeared as a natural choice. Specifically, as we can see from Fig. 2-(top-left) where the office plan is reported, measurements have been collected in 12 different positions spaced of 0.405 m1 in the frequency range between 55 -70 GHz with a step of 5 MHz. For each measurement position, the X-Y-Azimuth positioner rotates the radar in the semi-plane from -90 • to 90 • with a step of 5 • in accordance to the TA half power beamwidth (HPBW) to emulate the beamforming operation. Such mechanical steering reproduces an electronical steering since the adopted TAs are not reconfigurable. Technological solutions to perform electronically beamsteering at V-band can be found in [START_REF] Luna | A V-band switched-beam transmitarray antenna[END_REF] where a multiplesource system is proposed. Fig. 3 shows two photos taken during the measurements campaign.

B. Transmitarray antenna

The TAs used for measurements are fully described in [START_REF] Kaouach | Wideband low-loss linear and circular polarization transmit-arrays in v-band[END_REF] and here we report the most important information useful for the reader to appreciate how TAs radiation properties impact the mapping performance. As can be seen in Fig. 4, the TA is composed of a focal source illuminating a planar array whose building blocks are called unit-cells. In the considered TA structure, 20 × 20 unit-cells are adopted each with size of 2.5 × 2.5 mm 2 (i.e. the spacing between antennas is set to λ 0 /2 = 2.5 mm where λ 0 is the wavelength at f 0 = 60 GHz). Each unit-cell is composed of two patch antennas (receiver and transmission one) printed on two identical substrates separated by a ground plane and connected by a metallized via hole. The transmission phase can be controlled by rotating the patch on the transmission side. As previously introduced, this TA is non-reconfigurable because the patches rotation is fixed once the array is realized. The considered TA presents 1-bit of phase compensation corresponding to two possible phase values (0 • and 180 • ). Finally, the focal source is a linearlypolarized pyramidal horn antenna with a gain equal to 10.2 dBi at 60 GHz and a full HPBW of 72 • × 57 • .

Given this array structure, in [START_REF] Kaouach | Wideband low-loss linear and circular polarization transmit-arrays in v-band[END_REF] simulations and measurements results report a maximum gain of 23.3 dBi, a directivity, spill-over loss and power efficiency equal to 26 dBi, 2.24 dB, and 53.6%, respectively.

In realized gain for f L , f H and for the frequency f c = 60 GHz at which the TA has been optimized.

C. Measurement Results

For each position and each TA steering direction, the Smatrix was measured in the frequency domain from 55 to 70 GHz. In particular, the measured S 21 (f ) has been translated in time-domain through the inverse Fourier transform, and time gating was performed in order to suppress the coupling between the two arrays.

Successively, the round-trip channel impulse response (CIR), representative of the two-hop backscattering link, has been convoluted with a root raised cosine (RRC) pulse, with the effective radiated isotropic power (EIRP) compliant with the Federal Communications Commission (FCC).

In Figs. 6, 7 the CIR s 21 (τ ), the received signal and the energy profile collected from position p for two different steering angles (θ b = 0 • and θ b = -45 • , respectively) are shown. The energy profile has been obtained by considering N bin time bins of duration T ED . A signal bandwidth of W = 2 GHz (T ED = 0.5 ns), a time frame T f = 100 ns (N bin = 200) and N p = 100 transmitted pulses have been taken into account. As we can see, when the steering angle is fixed to θ b = 0 • , the received signal presents a peak in correspondence to 13 ns approximately. This refers to the time-of-arrival (TOA) related to the reflection of the wall in front of the radar at the end of the corridor. Thanks to the high directivity and gain of the adopted TAs, all the other reflections are filtered out or strongly mitigated. Contrarily, when θ b = -45 • , a first peak in the received signal can be detected at 5 ns related to the left-hand wall side while the highest peak is at approximately 18 ns probably corresponding to the wall in the direction of the main beam.

III. MAPPING ALGORITHM

As previously anticipated, the goal of this paper is to provide the feasibility of the mapping approach by exploiting measurement data, and compare them with simulations. Thus, the grid-based state-space model for probabilistic mapping we proposed in [START_REF] Guerra | Millimeter-wave personal radars for 3D environment mapping[END_REF] has been considered, by including alternatively both simulated and real measured data. Since we suppose that the personal radar trajectory and orientation are obtained using a dedicated positioning infrastructure, here we focus only on mapping and not on simultaneous localization and mapping (SLAM).

As reported in Fig. 1, the personal radar explores an unknown environment by performing a beamsteering operation during which its main beam is oriented in different spatial directions. For each position and each steering direction, the radar emits a train of N p pulses and then it collects the respective backscattered response. Energies are evaluated by subdividing the time frame into N bin = ⌊T f /T ED ⌋ time slots (bins) of duration T ED ≈ 1/W , which are successively accumulated for N p times [START_REF] Guerra | Millimeter-wave personal radars for 3D environment mapping[END_REF].

The environment has been discretized in N L = X grid Y grid cells, where each cell is associated with a radar cross section (RCS) value to be inferred by the estimation process. The cell size is set in accordance to the minimum footprint area, as detailed in Sec. IV.

The state vector of the system here considered is given by

x(k) = m(k) = [m 1 (k), . . . , m i (k), . . . , m NL (k)] T ( 1
)
where k is the discrete time instant and m i (k) indicates the root radar cross section (RRCS) (with sign) of the ith cell of the grid, where the frequency dependency has been Contrarily to conventional radar approaches where environment mapping is preceded by a detection phase [START_REF] Jose | An augmented state SLAM formulation for multiple line-of-sight features with millimetre wave radar[END_REF], in our model all the available energy measurements are included in the observation model. Specifically, we define e(k) the vector containing the accumulated measured energy at the output of the receiver at time k, T the set of points inside the room which belongs to the radar trajectory and we indicate with z(k) the corresponding Gaussian observation model fully described in [START_REF] Guidi | Personal mobile radars with millimeter-wave massive arrays for indoor mapping[END_REF].

The map estimation is performed by adopting the EKF method to efficiently evaluate the posterior distribution p(x(k)|e(1 : k)) of x(k) given the set of measurements e(1 : k) = {e(1), e(2), . . . , e(k)} collected by the TA-radar until time instant k, from which a maximum a posteriori estimate of the state x(k) is derived.

More details on how the mapping algorithm is performed are reported in Algorithm 1 and in [START_REF] Guidi | Personal mobile radars with millimeter-wave massive arrays for indoor mapping[END_REF], [START_REF] Guerra | Position and orientation error bound for wideband massive antenna arrays[END_REF].

IV. CASE STUDY

We now describe the mapping results obtained with the proposed model by including both simulated and measured data.

A. Scenario and System Parameters

The case study here described refers to the corridor environment described in Sec. II-A whose layout is juxtaposed to the estimated RCS maps in the results. As previously mentioned, we adopt a grid-based approach where the environment is discretized in cells having area 0.1 × 0.1 m 2 each according to the TA radiation patterns. We consider the radar equipped with the TA described in Sec. II-B, exploring the surrounding area and collecting energy measurements by performing a scanning process over an angular range of (-90 • , 90 • ) with a step of 5 • as described in previous sections. The TA-radar moves along a determined and known path, denoted by the red circles in Fig. 4, with a spatial step of 0.405 m. The orientation of the radar is always in the sense of the movement. In this scenario the TA-radar position and orientation are known; however, in a more realistic scenario errors in the position/orientation estimation have to be accounted for. In [START_REF] Guidi | Personal mobile radars with millimeter-wave massive arrays for indoor mapping[END_REF] the effects of such errors have been considered in the simulation results to analyse how they could impact in the map reconstruction.

We compare the TA mapping capabilities in terms of the signal bandwidth and by taking into account the quantization effect introduced by the 1-bit phase shift. A noise figure of N F = 4 dB, T 0 = 290 K and a signal bandwidth of W = 1 -2 -3 GHz (with T ED = 1/W ) are considered. RRC pulses centered at frequency f c = 60 GHz, roll-off factor α = 0.6, and pulse width parameter t p = (1+α)/W have been adopted. The time frame has been set to 100 ns and the number of transmitted pulses to N p = 100.

Results are obtained considering an EIRP of 30 dBm in accordance to Federal Communications Commission (FCC) mask at 60 GHz [START_REF]Revision of Part 15 of the Commissions Rules Regarding Operation in the 57-64 GHz Band[END_REF].

B. Mapping Results with Measured Energy Vectors

In this case, the measurement vector e(k) is given by data collected in Sec. II, where the energy profiles are directly included.

In Fig. 8 the mapping results exploiting the accumulated energy measurements are reported as a function of the signal bandwidth. Specifically, from the left to the right the RCS estimated map obtained with W = 1 GHz (i.e. T ED = 1 ns), W = 2 GHz (i.e. T ED = 0.5 ns) and W = 3 GHz (i.e. T ED = 0.34 ns) are shown. As expected, when increasing the bandwidth the mapping performance improves due to the increased temporal resolution.

Results obtained with W = 3 GHz are quite satisfactory as there is a nice match between the real maps and those estimated.

C. Mapping Results with Simulated Energy Vectors

We then simulate the measurements step taking into account the RCS scattering model described in [START_REF] Correia | Estimation of materials characteristics from power measurements at 60 GHz[END_REF] with a wall made of aerate concrete (i.e. relative permittivity equal to ǫ r = 2.26 and its loss tangent to 0.0491) and by exploiting the mapping model proposed in [START_REF] Guerra | Position and orientation error bound for wideband massive antenna arrays[END_REF]. In this scenario, we have considered the radar moving with a speed of 1 m/s and taking measurements every 0.4 s. The radiation characteristics of the 1-bit 20 × 20 TAs used for measurements have been included in the simulator. As before, in Fig. 9 the simulation results are reported as a function of the signal bandwidth. Discrepancies between the previous results are due to different phenomena. First of all in the simulations a simple scattering model has been assumed. As a consequence, when considering collected measurements as an input for the mapping simulator a mismatch between the model and the real scattering behaviour can cause a performance degradation. Secondly, in simulations we have assumed a free space propagation condition for each interrogated cell supposing that the multipath effects is implicitly taken into account when including all the array pattern information in the grid-based approach. Obviously a more realistic channel model might help to fill the gap between simulations and measurements. Finally, in the simulation results the far-field assumption has been made. Thanks to this hypothesis, it is possible to exploit the far-field TA radiation pattern both in the prediction and the measurement phases when evaluating the mapping performance. Contrarily, in the real scenario where the measurements have been collected in a corridor (1.6 m width) the far-field condition is not always satisfied due to the high TA directivity with the consequence that the expected TA main beam could be not perfectly formed. This fact could cause a mismatch between the prediction and the measurement step of the mapping algorithm. Future works will be addressed in improving the mapping algorithm by properly accounting for such phenomena.

V. CONCLUSIONS

In this paper we present an indoor backscattering measurement campaign at millimeter-wave for personal radar mapping applications. Two 1-bit 20 × 20 linearly polarized TAs have been used in a bistatic radar configuration to scan a real office environment. The data collected have been exploited for map reconstruction using a grid-based Bayesian statespace approach. Results have demonstrated the feasibility of the mmW personal radar, previously proved only through simulations, and that a good quality of map reconstruction can be achieved even when a limited set of phase values, i.e. only two in our case, are available.

Fig. 1 .

 1 Fig. 1. Smartphone centric solution for next crowd-sensing applications (left) and personal radar concept (right).

pFig. 2 .

 2 Fig. 2. Plan of the indoor corridor environment (top-left) and measurement set-up (right).

Fig. 3 .

 3 Fig. 3. Photos of measurements campaign in the corridor.

Fig. 5 -Fig. 4 .

 54 Fig. 4. TA structure: (a) TA configuration and (b) unit-cell.

Fig. 5 .

 5 Fig.5. Computed maximum gain of the TA used for measurements for θ b = 0 • as a function of frequencies (top), phase distribution and realized gain for f L , f H and fc (bottom)[START_REF] Kaouach | Wideband low-loss linear and circular polarization transmit-arrays in V-band[END_REF].

Fig. 6 .

 6 Fig. 6. Example of CIR (top), received signal (middle) and of the correspondent accumulated energy profile (bottom) taken from position p 6 in the corridor, for a steering direction of θ b = 0 • , W = 2 GHz and Np = 100.

Fig. 7 .

 7 Fig. 7. Example of CIR (top), received signal (middle) and of the correspondent accumulated energy profile (bottom) taken from position p 6 in the corridor, for a steering direction of θ b = -45 • , W = 2 GHz and Np = 100.

Fig. 8 .

 8 Fig. 8. Mapping results using 1-bit 20 × 20 transmitarrays, W = 1 -2 -3 GHz (top-left, top-right and bottom, respectively), Np = 100 and exploiting real measured data.

Fig. 9 .

 9 Fig. 9. Mapping results using 1-bit 20 × 20 transmitarrays, W = 1 -2 -3 GHz (top-left, top-right and bottom, respectively), Np = 100 and exploiting simulated data.

  Algorithm 1: Mapping algorithm.Input: N p , T , p = p 1 with p 1 ∈ T being the initial radar position, TA size and HPBW.

	1 Initialize the state vector and the covariance matrix
	2 while p ∈ T do
	• Collect or simulate a new radar energy measurement ;
	• Time Update (Prediction);
	1) Estimate the mean of the state to the next
	trajectory point;
	2) Estimate the covariance matrix to the next
	trajectory point.
	• Measurement Update (Correction);
	1) Compute the innovation by comparing the
	measurement with the prediction related to the
	previous trajectory point;
	2) Compute the extended Kalman-Filter (EKF)
	update;
	3) Update the estimate of the state;
	4) Update the covariance matrix.
	Go to the next radar position
	3 return RCS value for each grid point
	neglected. Moreover, since we assume stationary environment,
	the transition model is not introduced.

This step has been chosen in accordance to the value of the fully automated movement along the y-axis achievable with the positioner.

ACKNOWLEDGMENT

This work has been supported by the Italian Ministerial PRIN project GRETA (Grant 2010WHY5PR), H2020 project XCycle and in part by the H2020-EU.1.3.2 IF-EF Marie-Curie project MAPS (Grant 659067).


Jan Vossaert

Pieter Verhaeghe

Bart De Decker

Vincent Naessens

A smart card based solution for user-centric identity management

Keywords: user-centric identity management, privacy, security

This paper presents a prototype of a previously proposed user-centric identity management system using trusted modules. The trusted module, implemented using a smart card, can retrieve user attributes from identity providers and offer them to service providers, after authentication. This paper allows an evaluation of the practical feasibility of the identity management architecture and provides insight in several design decisions made during the prototype implementation. Also, the cryptographic protocols implemented in the prototype are discussed.

Introduction

Many service providers want to control access to their services and critical resources. To address accountability and support personalized services, many services require the user to disclose personal information during a registration phase. Existing federated identity management systems (FIMs) offer a straightforward solution, in which a trusted party manages and releases attributes of an individual. Unfortunately, the privacy of a user is often neglected or not dealt with appropriately. Growing concerns about the privacy of individuals require new solutions that give an answer to these requirements. On the other hand, electronic identity solutions are rolled out in many countries. Many approaches are based on smart cards. An electronic identity card typically stores a set of immutable attributes that can be released during authentication. However, electronic identity cards are combined with FIMs if mutable attributes are requested. Moreover, the user has no or limited control over the attributes that are released. This paper presents an implementation of a user-centric identity management system based on trusted modules, presented in [START_REF] Vossaert | User-centric identity management using trusted modules[END_REF]. The prototype is implemented using a TOP IM GX4 smart card as trusted module. The contribution of this paper is threefold. First the paper allows for a evaluation of the practical feasibility of the proposed architecture. Second, this paper presents concrete protocols that realize the security and privacy requirements stated in [START_REF] Vossaert | User-centric identity management using trusted modules[END_REF]. Third, this paper provides insight in the important design decisions made during the prototype implementation.

The rest of this paper is structured as follows. Section 2 discusses related work. Section 3 recapitulates the general approach presented in [START_REF] Vossaert | User-centric identity management using trusted modules[END_REF]. Section 4 presents the roles, key infrastructure, requirements and notations. The major protocols are discussed in section 5. Section 6 focuses on implementation details. A prototype evaluation is done in section 7. This paper ends with general conclusions and points to future research.

Related Work

In the federated identity management model [START_REF] Chadwick | Federated identity management[END_REF][START_REF] Ahn | User-centric privacy management for federated identity management[END_REF], of which Shibboleth [START_REF] Morgan | Federated security : The shibboleth approach[END_REF], CardSpace [START_REF] Bertocci | Understanding windows cardspace: an introduction to the concepts and challenges of digital identities[END_REF] and OpenID [START_REF] Recordon | OpenID 2.0: a platform for user-centric identity management[END_REF] are common examples, a user is known to at least one organization (i.e., the identity provider) in the federation (i.e., a group of organizations with mutual trust agreements). If a user contacts a service provider, authentication is delegated to the identity provider of the user. The identity provider releases the personal data that are requested by the service provider. Therefore, user impersonization by identity providers is inherent to the FIM model. Moreover, attribute aggregation [START_REF] Chadwick | A conceptual model for attribute aggregation[END_REF] is often not supported. Further, many identity providers still use password based authentication since often no infrastructure for strong authentication is available.

Several European countries are issuing governmental eID cards [START_REF] Naumann | Privacy features of european eid card specifications[END_REF] to tackle these shortcomings. However, many designs are not flexible as service providers can only request attributes that are stored in the card itself. Attributes are typically stored in the card during the whole card's lifetime. This implies that only immutable attributes can be stored in the card. Our approach aims at eliminating the drawbacks of existing federated identity management systems and current eID initiatives Strong authentication is also realized by Jøsang and Pope [START_REF] Jøsang | User centric identity management[END_REF] who present a user-centric identity management model using a personal authentication device (PAD). Each service provider can store an authentication token on the PAD of the user. Our work generalizes the PAD concept to a personal identification device with extended functionality (e.g., support for multiple identity providers, deanonymization) and a concrete implementation is presented. A similar approach is taken in PorKI [START_REF] Pala | Portable credentials via proxy certificates in web environments[END_REF] where users can delegate temporary proxy credentials to workstations using their mobile devices.

Suriadi et al. [START_REF] Suriadi | A user-centric federated single sign-on system[END_REF] propose a user-centric federated single sign-on system based on the private credential system proposed in Bangerter et al [START_REF] Bangerter | A cryptographic framework for the controlled release of certified data[END_REF]. However, the computationally expensive nature of the credential scheme limits the feasibility in mobile solutions. Similar concerns apply to the identity management system [START_REF] Camenisch | Privacy and identity management for everyone[END_REF] proposed in the PRIME project. Moreover, this system is less flexible since attributes are embedded in immutable credentials. Multiple credentials need to be used if not all the requested attributes are contained in a single credential. This paper proposes an implementation of a privacy friendly user-centric federated identity management approach based on a trusted smart card. The smart card is the mediator between identity providers and service providers. More precisely, an identity provider can store some of the user's personal attributes (or properties thereof) in her smart card. Information that is endorsed by the identity provider can then be disclosed to service providers. The latter use the information to provide fine-grained access control and offer personalized services.

The smart card controls access to identity information. Before the user is authenticated, the service provider first has to authenticate to the smart card and prove that it is authorized to access certain personal attributes. The smart card verifies the acceptability of the service provider's information request. This verification ensures that only information from identity providers is queried, for which the identity providers (or their representative) gave their consent. The authorization info is included in the certificate (or credential) of the service provider. Additionally, the user may further restrict access to personal information through a policy or an explicit consent. If the query is acceptable, the smart card forwards this request to the identity provider(s) that can provide the information.

Roles, Key Infrastructure, Requirements and Notation

Roles Nine different roles are distinguished in our solution. The user (U) is the owner of a smart card (SC). The card is considered a trusted computing platform by the different actors in the system. It means -amongst others -that the user trusts that the card will never release more than the requested attributes (for which the service provider has been authorized) and that the service provider trusts the card to release genuine attributes. Further, the card also provides a safe environment for storing private information such as keys (i.e., no data can be directly extracted from the cards memory). A service provider (SP) can implement attributed-based access control and/or offer customized services by requiring user authentication with a valid smart card. An identity provider (IP) manages user attributes that can be retrieved by identity cards during authentication with service providers. Deanonymization providers (DP) are responsible for deanonymizing users in case of abuse. A provider (P) can either be an identity, service or deanonymization provider. Certification authorities (CA) issue card and server certificates. These certificates are used during mutual authentication between card and provider. The card issuer (CI) issues identity cards to users. The revalidation center (R)(re)validates or blocks cards at regular times. The middleware (M) is a software layer that enables communication between card and provider(s). The middleware also allows the user to monitor and influence the authentication process (e.g., view the service provider authentication certificate, view and modify the attribute query, enter PIN). The card also stores an internal private variable lastValTime which represents the time R last verified the revocation status of the card (see section 5). This variable serves two goals. First, it is used by the card during authentication with a provider for verifying that the revocation status of the card was verified by R at a time after the last accepted validation time posed by the provider. Second, since smart cards do not have an embedded real-time clock, the lastValTime is used to verify the validity period of certificates.

Key Infrastructure Each card holds a unique master secret, K U , that is used to generate service specific pseudonyms. K U can either be user-specific or cardspecific. The former strategy allows individuals to reuse K U in multiple smart cards (e.g., when the previous card is defect or lost). If K U is card-specific, it would be useful to have a mechanism that allows proving a link between (old and new) pseudonyms generated by two different cards of the same user. A revalidation key pair (SK R , PK R ) is used to set up a secure authenticated communication channel between a smart card and the card revalidation authority. PK R is stored in each smart card during initialization, the corresponding private key is only known by the revalidation center. A common key pair (SK Co , PK Co ) is used by a large set of smart cards. PK Co is embedded in a certificate Cert Co . SK Co and Cert Co are stored on the card during initialization. This allows the identity, service and revalidation providers to verify that a genuine smart card is used (without revealing unique identifiers). Each service provider, identity and deanonymization provider has an asymmetric key pair (SK P , PK P ). SK P and Cert P are used to authenticate to smart cards. SK P is certified by a CA, resulting in Cert P . Section 6 elaborates on additional data that is kept in Cert P . The public keys of (root) certification authorities in the system are placed on the card during initialization. This allows smart cards to verify the validity of certificates. A newly generated session key K s is used to securely transmit data between a card and providers.

Requirements The requirements to which the prototype system must satisfy are listed below:

-Functional requirements:

• F 1 : Service providers can retrieve personal attributes either stored in the identity card and/or managed by an identity provider. • F 2 : Cards can be personalized (e.g., through privacy policies and preferences). • F 3 : Adding new providers is straightforward.

• F 4 : Cards can be used online and offline.

-Security and privacy requirements:

• S 1 : Strong mutual authentication and secure communication between users and providers (including revalidation authorities). • S 2 : Controlled access to user attributes (i.e., based on rights/privileges and personal preferences). • P 1 : Service specific pseudonyms of a user are unlinkable (even by the card issuer). These pseudonyms also encompass pseudonyms of users towards deanonymization and identity providers. One service provider can offer multiple services for which different pseudonyms are generated. • P 2 : Support for conditional anonymity during authentication.

• P 3 : Support for anonymous subscriptions.

-Performance and scalability:

• O 1 : The prototype system should have straightforward and easy management functions. • O 2 : Economic use of computationally expensive operations should result in acceptable performance of the prototype system.

Notation During the protocol listings, authenticated encryption is assumed. Authenticated encryption can be realized using several block cipher modes [START_REF]Block cipher modes[END_REF] or by explicitly adding a MAC to the message [START_REF] Bellare | Authenticated encryption: Relations among notions andanalysis of the generic composition paradigm[END_REF] (requiring an extra integrity key).

If message integrity verification fails, an exception is thrown and retransmission of the previous message is requested. Arrows (→ or ← ) represent the direction of communication. We assume that during a protocol run, the same connection is used. Dashed arrows ( or ) represent communication over an anonymous channel. Variables of the card are shown in teletype font; if the variable is underlined, it is stored in temporary memory.

Card Operations

This section discusses the most important operations performed by the card and gives the cryptographic protocols implemented in the prototype to achieve the security and privacy requirements. 1), the lastValTime is updated with the current time. Prior to updating, the revocation status of the card is checked. This requires unique identification of the card. This is realized by setting up an secure authenticated channel between the card revalidation center and the card using Cert R and Cert Co . Over this channel, the card releases its (unique) serial number which allows the revalidation authority to block the card (if it has been reported lost or stolen) or update its lastValTime. The lastValTime will be used during authentication with providers allowing them to trust the card's current revocation status without the card releasing any uniquely identifying information. A location hiding communication channel can be setup between the middleware and R in order to hide the whereabouts of the card holder. Mutual Authentication between Card and Providers During mutual authentication (Table 2), the provider first authenticates to the card. This is done using Cert P and the public key of the CA stored on the card. Next, the card authenticates to the provider using the common certificate Cert Co and the lastValTime. Cert Co enables the verification of genuine smart cards (i.e., no uniquely identifying information is released) and the card checks its revocation status using lastValTime and a reference time from the service provider. During authentication, a session key is generated. This phase results in a secure revalidateCard(): 1. The card is periodically revalidated by the revalidation center.

Card Validation During card validation (Table

(1) M R : "RevalidationRequest" (2) SC ← M R : c := genRandom() (3) SC : sig := sign(c , SK Co ) (4) SC : Ks := genRandom() (5) SC : E key := asymEncrypt(Ks, PK R ) (6) SC : Emsg := symEncrypt([Cert Co , sig, chip number], Ks) (7) SC → M R : Emsg, E key (8) R : Ks := asymDecrypt(E key , SK R ) (9) R : [Cert Co , sig, chip number] := symDecrypt(Emsg, Ks) (10) R : if (verifyCert(Cert Co ) == false) abort() (11) R : if (verifySig(sig, c, PK Co ) == false) abort() (12) R : time := getCurrentTime() (13) R : if (isValid(chip number) == false) time := -1 (14) SC ← M R : E time := symEncrypt(time, Ks) (15) SC : lastValTime := symDecrypt(E time , Ks) Table
anonymous mutually authenticated communication channel 3 . Authentication of the provider is realized by generating and encrypting a session key with PK P on the card and sending it to the provider. All communication between card and provider is now encrypted with the session key. Hereby, a cryptographic link between the authentication of the provider and card is established. The authentication of the card is then executed by signing a challenge from the provider on the card using SK Co . Release of User Attributes After mutual authentication, the card can disclose the user's attributes over the previously established secure channel. Attributes that are not stored on the card can be retrieved by the card from identity providers. This also requires authentication between card and identity provider. The certificates of the service and identity provider restrict the attributes that can be queried and provided respectively (see section 6). These restrictions are enforced by the card. Attributes can also be a service specific pseudonym or a deanonymization item (i.e., an encryption of an identifier of the user). The first allows users to have persistent identifiers with a service without revealing identifiers that can be linked to other services. This identifier is generated by taking a cryptographic hash of K U with the identifier of the service provider (obtained from the certificate). The deanonymization entry is realized by probabilistically encrypting the concatenation of the service specific pseudonym of the user towards the selected deanonymization provider, the lastValTime and the conditions required for deanonymization with the key of the deanonymization authority (i.e., {hash(K U || ID DP ) || lastValTime || Cert SP .deanonCond} P KDP ). A list of trusted deanonymization providers is contained in the service providers' certificate.

Before users can use the services of a deanonymization provider, registration is required. During registration the deanonymization authority requires users to release some attributes and stores these in a database linked to the service specific pseudonym of the user. The card stores the public key of the authority together with the name and identifier. Once the deanonymization authority receives a deanonymization item, it can decrypt it and, consequently, link it to the unique identifiers stored in the database. Before revealing the identity of the user, the conditions contained in the deanonymization item are verified.

Although the card itself does not foresee a secure interaction mechanism with its holder, the query from the service provider can be displayed to the card holder using the middleware. The attributes are only released after the user's consent (e.g., after entering a PIN code). The user can also choose not to release some attributes requested by the service provider by removing them from the query.

Implementation Details

This section zooms in on several design decisions. The prototype is developed using the Java Card 2.2.1 framework and is deployed on a TOP IM GX4 smart card.

Certificates A hybrid certificate solution is used in the prototype. The card uses standard X.509 certificates to authenticate towards providers; a provider uses card verifiable certificates (CVCs) to authenticate towards a smart card. This strategy ensures interoperability (i.e., providers do not need to install a custom certificate verification module) while avoiding parsing complex certificate structures on the card. Each CVC contains standard information (issuer, subject, role, validity interval etc.). Moreover, each CVC that is issued to an identity provider contains an attributeList that lists the identifiers of attributes it may supply, together with a level of assurance (LOA). Authoritative identity providers typically guarantee a high level of assurance for many attributes. The CVC used by the deanonymization and service providers also contains an at-tributeList, which indicates the attributes that can be requested, together with the minimal level of assurance. Moreover, a trustedIDPList restricts the set of acceptable identity providers (or IDP groups) for the service. The card will only release attribute values to that particular service provider that were fetched from identity providers of the list (with an appropriate LOA). Note further that CVCs have a short lifetime. This is necessary to ensure a short window of vulnerability as revocation checks are not performed on the card. Each provider also has a X.509 certificate with a long lifetime. The latter is used to authenticate towards CAs that issue the CVCs.

Discovery of Identity Providers

Each attribute in the system is represented by an Attribute object. Each of them has a unique identifier. Some attribute values are cached on the card. Other attribute values need to be fetched from identity providers. Therefore, each card keeps a list of IdentityProvider objects. They define the set of identity providers in which the owner has enrolled. Each IdentityProvider object maintains references to a set of attribute objects. They refer to the Attribute objects that can be retrieved from the respective provider.

When an attribute query is received, the query handler first looks for the attribute value in the cache. The cached attributes that meet the prerequisites (e.g., LOA, trusted identity provider) are selected. The remaining attributes are fetched from identity providers. The handler selects a minimal set of acceptable identity providers that can supply the remaining attributes, hence, ensuring that only a minimal set of connections to identity providers is required.

Memory Management Smart cards have limited memory. The card used for the prototype has around 70K bytes of available EEPROM. Moreover, the Java Card virtual machine does not implement a garbage collector, nor is it possible in Java to explicitly release memory. Therefore, all required memory should be allocated at the beginning of the program and continously reused.

Caching attributes. A fixed set of byte arrays of variable length is allocated to cache attribute values. These arrays are embedded in AttributeValue objects that also keep context information such as retention time, LOA, time of last usage, etc. For an optimal implementation, the distribution of the average length of each type of attribute should be calculated. This caching strategy is straightfor-ward while limiting fragmentation. When an attribute value is fetched from an identity provider, it might be necessary to remove another attribute from the cache. The following selection strategy is applied. First, a predefined number of AttributeValue objects with the smallest memory footprint still large enough to keep the new attribute value are selected. Consequently, the least recently used attribute value is replaced. Persistent attributes (see section 6) are not considered by the cache update policy.

Static memory configuration. Since all memory allocations occur when the applet is deployed on the card, the attribute query length, the maximum number of supported identity providers and cached attributes . . . are fixed. Dynamically assigning memory increases flexibility. However, replacement strategies become more complex. Therefore, in the prototype, memory is configured statically. Hereby, the initializer can define the amount of memory assigned to the different parts of the program when installing the applet. For instance, the initializer can opt for allocating only a limited amount of memory for identity providers while increasing the attribute cache.

Personalized Policies

The policy engine on the card enforces the policies of the service and identity providers. The policies are specified in the CVCs (cfr. ...List). The user can further restrict the access policy (i.e., he can update his policy using his PIN code). First, the user can select the attributes that will be cached on the card until their retention time has expired. Those attributes are marked as persistent. Moreover, the user can assign a trust level to service providers: untrusted, default and trusted. Requests from untrusted service providers are blocked. In the default policy, user confirmation is required before the attributes are released. If a service provider is trusted, the user is no longer involved in the attribute(s) disclosure. The query, however, is still verified using the privileges listed in the CVC. Moreover, the user can also mark an Attribute as sensitive. If so, user consent (i.e., PIN code) is always required if that attribute needs to be released. The card issuer determines a set of trusted CAs of which the public key is stored in the card during initialization. However, users can further restrict the list of trusted CAs by deactivating keys of untrusted CAs. Although the user cannot further expand this list of trusted CAs, previously deactivated keys can be reactivated. Analogously, keys from deanonymization providers can be deactivated (or even removed which allows registration with a new deanonymization organization if no empty slots were available) and reactivated.

Anonymous Subscriptions For some applications, e.g., news sites, entrance control in buildings,. . . , it is not necessary for a user to disclose a persistent identifier. For instance, news sites only need to verify whether the user has a subscription that allows him to view the requested content. To support this, a Subscription object is initialized during enrollment of the user with the service provider. The Subscription object contains the id of the service provider, a validity period and a type. The type allows the service provider to verify whether the requested service (or content) is included in the subscription of the user. The validity period allows the service provider to specify subscriptions that expire after a specified time. Note that the actual validity period does not have to be released but can be verified by the card using a time provided by the service provider. The type field constraint can also be verified by the card but is less critical if released since typically only a limited number of subscription types are available. A pseudonym that allows the user to retain his subscription when re-enrolling with a new card (e.g., when the previous card was lost or expired) could be released during enrollment.

Cryptographic Parameters To realize the cryptographic functions defined in section 4 the cryptographic capabilities of the smart card are used. Since RSA is the only asymmetric cryptosystem available on the card, RSA keys are used for all the asymmetric keys in the system. Key lengths of 1024 bit were chosen to achieve good performance, section 7 discusses the performance impact of other key lengths and the potential use of other ciphers. For signing, a SHA-1 digest is encrypted using PKCS #1 padding. Asymmetric encryption uses OAEP padding and can, hence, also be used to realize the probabilistic encryption required for deanonymization.

For authenticated encryption, 128 bit AES keys are used to achieve confidentiality and a MAC is generated by encryption a SHA-1 digest with a 128 bit AES integrity key. The 256 bit session key K s is divided in two parts to obtain the integrity and confidentiality key.

Random number generation is realized using the on-board random number generator of the chip.

Evaluation

Functionality Analysis The proposed solution combines the benefits of smart cards and federated identity management systems. The card is a trusted module to all players in the system. Common secrets allow providers to establish authenticated sessions with the card. Over these channels, service providers can send attribute queries which are fulfilled by the card. Possibly, the requested attributes are retrieved from identity providers that are trusted by the service providers (cfr. F 1 ).

Although certificates of service providers already restrict the type of attributes that can be queried, the user can be even more restrictive by restricting the attribute query. Further, users can mark attributes as sensitive, assign trust levels to providers, influence caching policy, etc. Hence, extensive personalization functions are available (cfr. F 2 ).

Adding new providers only requires them to retrieve an authentication certificate from a CA. This requires them to have an audit done that determines what attributes they can request or supply. Service providers also require permissions from identity providers (or groups of) for requesting attributes they provide. Hence, adding new providers introduces some overhead for the respective in-stance and the certification authority. However, it is a clearly defined procedure transparent for the users and the majority of providers (cfr. F 3 ).

The caching policy maintains a set of attributes stored on the card. These cached attributes can also be used in offline settings. Hence, apart from authentication and identification also attributes queries are supported in offline environments if the required attributes are cached on the card (cfr. F 4 ).

Security and Privacy Analysis Reference protocols for realizing secure authenticated sessions between card and providers using the proposed key infrastructure are given in the section above. Providers are assured that the card was not revoked before a certain date/time (i.e., accValTime< lastValTime). If required, the card will execute the card revalidation protocol before proceeding with the authentication. Revocation of the CVCs of providers is not supported, however, as they are short-lived potential abuse is limited. Hence, S 1 is satisfied.

When a common key is compromised, the set of cards on which the keys are stored should be revoked. This can be done using certificate revocation lists or OCSP responders. The CRL will typically contain little entries since smart cards are designed with countermeasures against attempts to extract secret information. When a card is lost or stolen, this should be reported with the revalidation center, who will block the respective card. Hence, these cards should not be added to the CRL. However, stolen cards can be misused during a service specific time interval (i.e., accValTime< lastValTime) if the PIN is compromised.

A potential misuse of the revocation strategy is that providers require realtime revocation checks of the card (i.e., accValTime= currentTime) while this might not be necessary for the requested service. This decreases performance of the card as revalidation is required for each authentication. The CRLs, currently used for revocation checks, are also typically only periodically updated. This may also lead to timing attacks (i.e., linking a profile of a provider to the card number released to the revalidation center) if revalidation center and provider collude.

The public key of the revalidation center stored on the card can be updated by the revalidation center itself. After establishing a secure session with the card, the new certificate can be sent to the card. It will verify that the certificate was issued to the revalidation authority, that the old validity interval precedes the new and the validity of the signature (using the CA public key stored on the card). The revalidation authority can also deactivate keys of CAs that are no longer trusted over the secure channel. Other keys stored on the card cannot be updated or deactivated by the revalidation center.

Access to user attributes is controlled on three levels. First, an audit organization determines the set of user attributes relevant for the offered services. Second, identity providers control the set of service providers that can acquire attributes they provide. These restrictions are embedded in the service provider certificate and, hence, can be verified by the card. Third, users can implement policies or determine at runtime which attributes are released. Hence, extensive control over the release of attributes is enforced (cfr. S 2 ). The card is the policy enforcement point and should, hence, be trusted by both the user and providers.

After authentication, users can release service specific pseudonyms which are unique pseudonyms which providers nor card issuer can link (cfr. P 1 ).

Certain services may allow users to remain anonymous but require support for deanonymisation when abuse is detected. As mentioned in section 5, providers can request a probabilistic encryption of an identifier of the user using the attribute query. Hence, these providers can cooperate with the deanonymization service to identify users in case of abuse (cfr. P 2 ). The user can select supported (and hence trusted) deanonymization authorities by registering with the respective authorities. Further, the certification authorities should employ rigorous security requirements for the deanonymization authorities. This provides suitable security for the users and limits the number of deanonymization authorities. Further, different authorities could provide different levels of deanonymization, depending on the attributes that were released during registration.

During authentication, no unique identifiers are released. Hence, users can use the subscription functionality of the card to request access to content which does not necessarily requires identification (cfr. P 3 ).

Although a user can theoretically remain anonymous, note that the anonymity set for a user largely depends on the size of the set of identity cards with an identical private key and the frequency with which these cards are used. For instance in the case of subscriptions, if the anonymity set is too small and only one user with common certificate x has a certain subscription he is linkable. Hence, when determining the size of the set of identity cards with identical keys one has to consider both the impact of key revocation and potential linkable profiles.

Performance and Scalability Analysis Each party in the system has one or more clearly defined responsibilities. Further, the revocation strategy allows offline services without requiring manual updates of CRL on these devices. Card validation can be triggered by users, but if required, can be executed transparently. Hence O 1 is satisfied.

The rest of this section focuses on performance results. For the prototype implementation mutual authentication between card and provider takes, on average, 1040 ms. The influence of the communication delays between card, workstation and server are minimized by running the test applications locally. Processing the attribute queries takes around 180 ms for attribute sets of around 100 bytes. Hence, when all necessary attributes are cached on the card, the total required authentication time is around 1220 ms. For each identity provider that needs to be contacted, another 1220 ms is added to the required time. The card revalidation operation requires around 900 ms.

Table 3 lists the number of cryptographic operations required during each step. In Table 4 reference performance numbers for cryptographic operations on the prototype smart card are given. These tables illustrate that the asymmetric cryptographic operations are the major performance bottleneck. During authentication, the card performs one private and two public key operations. These operations alone, require around 615 ms, which is more than half of the total authentication time. However, the caching policy and the identity provider selector minimize the number of identity providers required for satisfying the query (cfr. O 2 ). Further, replacing RSA with a more efficient algorithm provides an opportunity for significantly improving the performance of the entire system. For instance, elliptic curve cryptography (ECC) could be used to replace the private key operation on the card which could significantly increase performance, especially for increasing key lengths. The smart card used for the prototype, however, does not yet support ECC, hence, no concrete results can be given. Moreover, during a normal authentication procedure the card and service provider first mutually authenticate. Then user interaction is required (entering PIN, modifying -if necessary -the attribute query), after which the card retrieves the attributes from the identity providers and sends them to the service provider. The user interaction divides the waiting time in two smaller pieces and, hence, improves the perceived experience.

The instantiated applet on the card requires around 17000 bytes of memory. This includes temporary memory to store session data but excludes memory required for storing setting dependant information (e.g., cached attributes, registered identity providers, deanonymization authorities). However, as around 70k bytes of memory are available on the prototype smart card, sufficient memory is left to support large numbers of identity providers, cached attributes. . .

Table 2 .

 2 Mutual authentication between provider and card.

		authenticate():
	(1) SC ← M	P : Cert P
	(2) SC	: if (verifyCert(Cert P )==false) abort()
	(3) SC	: if (Cert P .validEndTime < lastValTime) abort()
	(4) SC	: sesId := startNewSession();
	(5) SC	: session[sesId].maxRights := Cert P .maxRights
	(6) SC	: session[sesId].Subject := Cert P .Subject
	(7) SC	: Ks := genRandom()
	(8) SC	: session[sesId].Ks := Ks
	(9) SC	: c1 := genRandom()
	(10) SC	: session[sesId].chal := c1
	(11) SC	: E key := asymEncrypt(Ks, Cert P .PK)
	(12) SC	: Emsg := symEncrypt(c1, Ks)
	(13) SC → M	P : E Key , Emsg, sesId
	(14)	P : Ks := asymDecrypt(E key , SK P )
	(15)	P : c1 := symDecrypt(Emsg, Ks)
	(16)	P : c2 := genRandom()
	(17)

P : Eresp := symEncrypt([c1 +1, accValTime, c2 ], Ks) (18) SC ← M P : sesId, Eresp (19) SC : [resp, accValTime, c2 ] := symDecrypt(Eresp, session[sesId].Ks) (20) SC : if (resp != session[sesId].chal+1) abort() (21) SC : if (lastValTime < accValTime) abort() (22) SC : session[sesId].auth = true (23) SC : sig := sign(c2, SK Co ) (24) SC → M P : Emsg := symEncrypt([Cert Co , sig], session[sesId].Ks) (25) P : [Cert Co , sig] := symDecrypt(Emsg, Ks) (26) P : if (verifyCert(Cert Co ) == false) abort() (27) P : if (verifySig(sig, c2, Cert Co .PK) == false) abort()

We assume that several other requirements are met e.g., the identity set is sufficiently large, an anonymous communication channel is used.

Conclusion

This paper presents an implementation and evaluation of a smart card based solution for user-centric identity management [START_REF] Vossaert | User-centric identity management using trusted modules[END_REF]. Several implementation details are given and an evaluation is performed, illustrating the practical feasibility of the system. Further research is currently being conducted in two directions. First, the security of the system could be improved by using group signature for authenticating cards to providers. If the secret keys in one smart card are stolen, it suffices to revoke only that card. Also, support for signed attributes could give a stronger level of assurance which might be required for some services. Second, the usability could be improved by replacing RSA with a more efficient algorithm. The architecture is also being ported to mobile phones with secure elements. To validate the choices made during implementation (e.g., caching policy, selection of identity providers) several realistic use-cases are being implemented.