Leila Bahri

Barbara Carminati

Elena Ferrari

William Lucia

Mike Dima

LAMP -Label-based Access-control for More Privacy in Online Social Networks

Access control in Online Social Networks (OSNs) is generally approached with a relationship-based model. This limits the options in expressing privacy preferences to only the types of relationships users establish in the OSN. Moreover, current proposals do not address the privacy of dependent information types, such as comments or likes, at their atomic levels of ownership. Rather, the privacy of these data elements is holistically dependent on the aggregate object they belong to. To overcome this, we propose LAMP, a model that deploys fine grained labelbased access control for information sharing in OSNs. Users in LAMP assign customized labels to their friends and to all types of their information; whereas access requests are evaluated by security properties carefully designed to establish orders between requestor's and information's labels. We prove the correctness of the suggested model, and we perform performance experiments based on different access scenarios simulated on a real OSN graph. We also performed a preliminary usability study that compared LAMP to Facebook privacy settings.

Introduction

Online Social Networks (OSNs) enable users to have more freedom and proximity in keeping in touch with their friends and in expanding their social contacts. However, they also create serious privacy concerns given the personal nature of information users share over them on almost a daily basis [START_REF] Gao | Security issues in online social networks[END_REF] [START_REF] Caviglione | A taxonomy-based model of security and privacy in online social networks[END_REF]. Users publish their personal stories and updates, as they might also express their opinion by interacting on information shared by others, but, in most cases, they are not fully aware of the size of the audience that gets access to their information. 1Moreover, privacy settings currently available in OSNs remain both complicated to use, and not flexible enough to model all the privacy preferences that users may require [START_REF] Madejski | The failure of online social network privacy settings[END_REF].

This limitation seems to come, fundamentally, from relying solely on a relationship based model for access control (ReBAC), as mostly adopted by nowadays OSNs and research proposals. ReBAC is characterized by the explicit tracking of interpersonal relationships among users, and the expression of access control policies in terms of these relationships [START_REF] Ferrari | Access Control in Data Management Systems[END_REF]. These relationships could refer to explicit friendship links established by users [START_REF] Carminati | Enforcing access control in web-based social networks[END_REF] [START_REF] Fong | Relationship-based access control policies and their policy languages[END_REF], or they could be inferred from relationships created between users through the resources they share [START_REF] Cheng | Relationship-based access control for online social networks: Beyond user-to-user relationships[END_REF] (e.g., connecting users who are tagged in the same photo), or by linking other public information, such as considering attendance to the same school, or originating from the same country as a basis for relationships between users (e.g., the work in [START_REF] Pang | A new access control scheme for facebook-style social networks[END_REF]). However, this type of access control limits, by design, the options for privacy settings. For instance, defining privacy settings based only on the social relationships implicitly enforces that all the friends of a user who belong to the same relationship type are equal and, hence, will enjoy the same access and interaction rights. For example, referring to Figure 1.a, if Walt categorizes Mike and Dima as family, and Javier and Lina as colleagues, then all the information Walt shares with the family group will be accessible by both Mike and Dima and the same goes for information shared with the colleagues one. In case Walt needs to share an item only with Mike and Javier, he is required to create a new group or categorization under which he declares both of them.

Additionally, the information that users create in OSNs is subject to interactions from their friends, resulting in the creation of intermingled nets of objects with multiple co-owners. For example, Walt shares a photo, and one of his friends tags Dima in it, or Dima shares a status update and Walt comments on it. Such scenarios exemplify the creation of aggregate content that is co-owned by multiple users in the system, who might have conflictual privacy preferences over it. Thus far, this problem has been approached mostly from a multiple ownership perspective. That is, the aggregate co-created content is considered as one single object over which multiple access preferences could be specified by its stakeholders, but only one is selected as dominant using different strategies, such as game theory, and majority voting [START_REF] Hu | Multiparty access control for online social networks: model and mechanisms[END_REF][15] [START_REF] Masoumzadeh | Osnac: An ontology-based access control model for social networking systems[END_REF] [16][9]. This may limit the right of the coowners in guarantying the enforcement of their individual privacy preferences over the specific content they have contributed with.

In contrast, our idea is that of looking at this co-owned content in terms of the relationships between its components. Thus, allowing us to model it as separate pieces of data that are dependent on each other, but that are uniquely owned and for which unique privacy preferences could be specified by their owners. Taking this approach simplifies the co-ownership problem and empowers users to be in full control over data they create at a fine granularity level. For example, if Walt is allowed to comment on Dima's status update, he may have the right to limit the audience of his comment and not to have it subject to the one set by Dima for the corresponding status update. Unfortunately, privacy settings available in today's OSNs do not allow the granularity of managing privacy for pieces of data that are dependent on others, such as comments or likes. Moreover, the available related research provides complex solutions that mostly rely on managing multiownership at an object's aggregate level, as mentioned above.

To overcome these limitations, in this paper, we propose a new model, LAMP (Label-based Access-control for More Privacy in OSNs), that introduces a new and more flexible way for users to express finer granularity levels of privacy for all information types, respecting the relationships and connections between objects as well. LAMP achieves this by exploiting the security principles of Mandatory Access Control (MAC), according to which a data administrator assigns ordered security levels (that is, labels) to subjects, and ordered sensitivity levels to objects [START_REF] Ferrari | Access Control in Data Management Systems[END_REF]. However, differently from the centralized assignment of labels by a single data administrator as in MAC, LAMP operates based on a discretionary model wherein each user is considered as the ultimate owner of her data. 2 As such, users in LAMP express their privacy preferences by assigning sensitivity labels to their owned objects, and security labels to their friends.

Labels in LAMP are expressed in terms of security or sensitivity levels, types of relationships, and types of objects (see Figure 1.b). Access decisions are taken based on well defined axioms that consider the richness of interaction types and access privileges that OSNs allow. These axioms ensure that subjects can only gain specific privileges on objects, based on the relationship existing between the object sensitivity levels and their own security levels.

To the best of our knowledge, except from the work in [START_REF] Mehregan | Design patterns for multiple stakeholders in social computing[END_REF], which has discussed design principles for privacy settings by considering co-owned aggregate objects as collections of related annotations, LAMP is the first proposal that considers the relationships between aggregate data objects to decompose them to atomic unique levels of ownership, and that uses a labeling strategy to provide more control and richer privacy settings to data owners on all types of objects they create.

We formalize and prove the security and complexity properties of LAMP, and we discuss how it allows users to express a richer set of privacy settings, compared to existing proposals. We conduct performance experiments using different access scenarios simulated on a real OSN graph. We also deployed LAMP as a Facebook test app and performed a preliminary study on LAMP's usability by comparing LAMP to Facebook privacy settings. For space considerations, we report here the performance experiments and refer the reader to a technical report for the preliminary results of the usability experiments [START_REF] Bahri | Technical report: Lamp -labelbased access control for more privacy in online social networks[END_REF].

The remainder of this paper is organized as follows. Section 2 introduces a background on the interactions allowed in OSNs nowadays. Section 3 describes the proposed model; whereas Section 4 provides its correctness and complexity properties. Section 5 reports the results of the performed experiments. Finally, Section 6 concludes the paper.

Background

In this paper, we consider the scenario of general-purpose OSNs that allow users to establish friendship links with each other, and share different types of information. There are number of such OSNs in the online market nowadays, but it remains safe to say that the two worldwide biggest ones currently in the box are Facebook and Google+. Generally, OSN users are associated with an information space typically made of two main blocks: a profile and a wall or timeline. The profile contains personal information, like full name, gender, age, education etc; whereas the wall organizes, in a graphically timelined manner, the data objects the user shared with her friends or those that her friends have shared with her. Users can upload content of different types into their information space, or interact on their friends' shared information (like, comment, tag, etc.), creating by this aggregate co-owned objects. These aggregate objects are typically made of an information that stands as independent by itself, and a tree of objects that are dependent on it (see Figure 2 for an example). The privacy settings currently available in mainstream OSNs, such as Facebook or Google+, present limitations to the expression of users refined privacy needs, especially w.r.t dependent object types (e.g., no privacy settings for ob-jects of types like (L) and comment (C)). LAMP addresses these limitations and offers a more flexible and a richer privacy setting functionality to OSN users. We define and detail the underlying model in the following section.

The LAMP Model

We start by presenting basic definitions, then we define how privacy requirements of users can be expressed using labels. Finally, we introduce the mechanism governing access decisions.

Basic Definitions

We model an OSN as an undirected graph F G = (U, F R), where U is the set of users, and F R is the set of edges. We say that two users a, b ∈ U are friends in the OSN if and only if there exists one direct edge connecting them, that is, ∃e a,b ∈ F R.

OSN users create and share different types of information (see Table 1) leveraging on the relationships they establish with others. We define the set of information types in the OSN as OT S = {T X, P, V, L, C, T G, GL, F P }, and we refer to all pieces of information as an object, that we formally define as follows:

Definition 1 (OSN object) An OSN object o is a tuple (type, owner, parent, children, copyof ), where:3 (i) type ∈ OT S denotes the type of the object. (ii) owner ∈ U denotes the owner of the object. If o.type / ∈ {T G, F P }, the owner is the user who generated the object (dependent or independent). Otherwise, it is the user who is tagged or the user on whose wall the friend post is made. (iii) parent: if o is a dependent object, this refers to the object on which it depends. It is set to null, otherwise. (iv) children: is the set of objects that depend on o, as generated by interactions on it, if any. It is set to null, otherwise. (v) copyof: if o is a shared copy of another object o, this is equal to o, otherwise it is set to null.

In addition to the objects that users can create, we consider the existence of another special object type, that we refer to as the root object, and that models user walls. We consider that every OSN user owns exactly one root object that is created by default upon her subscription to the OSN. Root objects serve for controlling the function of writing on users' walls by their friends as we will detail later (see Algorithm 1). A root object associated with user a is modelled as root a = (root, a, null, null, null).

Example 1. Consider the OSN objects in Figure 2. By Definition 1, object o 1 is modeled as (TX, Javier, null, {o 3 , o 4 }, o 2 ), whereas the tag object o 5 is modeled as (TG, Bob, o 4 , null, null).

Besides creating and sharing objects, there are different types of actions that users can perform on them. We accordingly define the set of controllable privileges in LAMP as PS = {read, add-comment, add-like, add-tag, share, write}. 4As mentioned earlier, access requirements in LAMP are expressed by means of labels, formally defined in the next section.

Privacy Requirements Formulation

To express privacy requirements, users assign security labels to each of their owned objects and to each of their friends. By labeling friends, users express the limitations they want to put on them, whereas object labeling serves for expressing the sensitivity of the information and its accessibility criteria. We note that we assume a set of possible groups that users can organize their friends into. These groups are created by users depending on their preferences and can be viewed as similar to users' lists or users' circles as available on Facebook and Google+, respectively. A possible example of a set of user groups might be {friends, colleagues, teammates, schoolmates, family, acquaintances}. This set is created at user's side and is only used for the purpose of creating their friends and objects security labels. In addition, we also assume in the system a totally ordered set of levels LOS = {Unclassified (UC), Very Low (VL), Low (L), Medium (M), High (H), Very High (VH)}, with UC

< VL < L < M < H < VH.
We refer to a friend label as Friend Clearance Label (FCL) and we formally define it as follows: Example 2. Assume Walt uploads a photo (GP ) and assigns to it OSL GP =(L, P, {colleagues, family}). This means that GP has a low sensitivity and it concerns Walt's colleagues, or family. Assume Walt assigned to his friend Javier an F CL w,j =(H, {P, T, V}, {colleagues, university}). This implies that Walt grants to Javier a high clearance level, allows him to see his photos, texts, and videos, and he considers him a member of the colleagues and university groups.

Access Control Decisions

Access to objects in an OSN can be related to one of the privileges enclosed in the privileges set (PS). To reflect this broader range of privileges, compared to traditional scenarios formalizing only read and write privileges, we refer to access requests as interaction requests -(IR). An IR can be of two types: 1) performed on an object (e.g., read or comment on an object), or 2) made to create an object related to another user (i.e., tag a user or write on her wall). We define an interaction request as follows: Users can explicitly issue a read IR on independent objects only. If such a read IR is positively evaluated, the system issues, on behalf of the requesting user, read IRs on all the children's tree of the granted independent object. This ensures that the children objects are evaluated independently of their parent object and only based on their proper OSLs. We explain this later under Algorithm 1.

Like in standard MAC, the evaluation of an IR is performed based on properties that define orders between subject and object labels. In standard MAC, there are two properties that govern the system, related to the read and to the write requests, respectively. LAMP requires not only the redefinition of these two properties to account for all the features in the FCLs and the OSLs, but it also requires defining new axioms to take into account the other interactions possible in an OSN.

An order relation among labels must be defined to have the basis on which they can be compared. In LAMP, we refer to this relation as the dominance relationship, formally defined as follows:

CL a,b > SL o ∧ T Y o ∈ T S a,b ∧ GS o ∩ GS a,b = ∅ Example 3. Consider Example 2.
The FCL that Walt assigned to Javier dominates the OSL assigned to GP photo because: 1) the clearance level of Javier (High) is higher than the sensitivity level of the photo (Low); 2) object type photo is in the types set in Javier's label; and 3) the group sets in Javier's and the photo's labels have a group in common (colleague). Informally, the FSP dictates that to grant a read, share, add-like, or addcomment IR on an object, the FCL of the requestor must dominate the OSL of the object it targets. A requirement of the FSP is that the requestor and the object owner are friends in the OSN as otherwise the friend label to be compared would not exist. As a consequence, in LAMP, only friends of a user can have access to and interact on her information space. This is not fully aligned with the classical approach of OSNs where there is the possibility of making information available to friends-of-friends or public. Regarding the case of information desired to be made public (i.e., accessible to all users in the OSN), it can be easily enabled by making the object unclassified, and by letting the system assign a default label F CL def ault =(U C, GS, OT S) to all OSN users who are not direct friends with the object owner, where GS, and OT S are the sets of all groups and of all object types in the OSN, respectively. For other information that is not made publicly available, our approach is to provide users with an environment that facilitates the understanding and control of their objects audiences. This is ensured by the suggested labels assignment, as users can be fully aware of (and track) who might gain access to what, contrary to the approach of allowing the unlimited and uncontrollable friend-of-friend access. However, LAMP can still be extended to cover such a scenario by complementing it with a mechanism for automatic FCLs assignment to friends of friends. This issue is a research subject in itself, that we plan to address as future work.

The fundamental security property

The FSP is sufficient for all the IRs it targets, except from the share one. This is what we address in the following sub-section.

The share privilege and the share up property When a share IR is granted, it results in the creation of a copy of the original object, that is owned by the sharing user. The problem here is on what should be the label of this shared copy. The simplest design idea is to make the copy inherit the same label as the original object, ensuring by this that only the audience of the original object is allowed to view the shared copy. This will map to what is being the standard in current OSNs, such as Facebook. However, this design choice results in two limitations that could not be desirable: 1) the user who performs the share interaction would have no way to influence the privacy settings of the shared copy; and 2) this strategy limits the intended purpose of the share functionality, since it does not result in an enlargement of the intended audience. Indeed, when a user allows a friend to share an object, this logically means that the user wants to delegate to her/him the dissemination of that object in order to make it available to a wider audience from the friend's side. Otherwise, if the user wants to limit the visibility of an object strictly to her allowed audience, then what could be the purpose from allowing a share interaction on it? Therefore, an alternative design decision, that would offer more flexibility and give meaning to the power of a share operation, is to have the shared copy have its distinct object label. However, the copy's label should still respect the privacy of the original object in such a way that the copy might be available to a wider audience without violating the privacy of the original object. Herein, the focus is on two concerns: 1) the shared copy so of an object o should not be made available to the friends of o.owner who are initially not allowed to access o; 2) the delegation offered by o.owner to the friend who creates the shared copy so should respect the sensitivity of o, such that so is shared only with those friends of so.owner who are at least as trusted as the sensitivity of o. We present Example 4 for a better illustration of these two concerns.

Example 4. Consider Example 2, and assume that Walt and Javier have Mina as a common friend in the OSN. Let Walt's FCL for Mina be F CL w,m =(VL, {T}, {university}). Recall that the OSL of Walt's photo is OSL GP =(L, P, {colleagues, family, university}). Clearly, Mina does not have access to Walt's photo as F CL w,m does not dominate OSL GP . Assume now that Walt allows Javier to share the photo; hence delegates to him its broader dissemination. This delegation means that Walt entrusts Javier to disseminate the picture to those of his friends that he trusts at least as high as the sensitivity of the photo (i.e., Walt's picture has a Low sensitivity, therefore it should be disseminated to those friends of Javier whom he trusts with at least a Low value). Furthermore, the shared photo by Javier should not be made available to Mina, no matter how Javier trust's in Mina could be different from Walt's.

To address these two concerns, we first introduce an additional axiom, called the Share Higher Property. Before formally defining it, we introduce a new required concept that governs the relationship between the label of an object and that of its copies made from a granted share IR. We refer to this as the Notdeclassify relationship: The Not-declassify relationship requires that the sensitivity level of an object's copy is at least equal to that of the original object. This would ensure that a share action does not declassify the shared information, with the assumption of a delegated trust from the original object's owner to the sharing friend. It is also to be noted that no restriction is made on the groups set parameter of the label. This is because the organization of friends into groups is dependent on each user without necessarily mapping to the groupings adopted by their friends. For example, those who might be family to a user, might be colleagues to another. However, it is worth mentioning that the purpose of the share action is to disseminate objects to wider and different audiences, as long as this does not result in explicitly making the information available to a non-desired friend.

Based on the Not-declassify relationship, the second axiom of LAMP, the Share Higher Property, is defined as follows: Informally, the SHP enforces that users can share their friends' objects only if they assign to the shared copy an OSL that does not declassify the one of the original object. We recall that a share IR should first satisfy the FSP. Therefore, only those friends who have a clearance level at least equal to the sensitivity level of the object can perform a share IR. This ensures respecting the delegation of objects dissemination to only those friends who are at least as trusted as the sensitivity of the object they are entrusted to share.

The SHP addresses the delegation of dissemination concern, however it does not solve the first concern we discussed earlier related to when an object owner and the sharing friend have a friend in common who is not initially allowed to access the object by the owner (the case of Mina in Example 4). To prevent such horizontal disclosures, we enforce the preferences of objects' owners by considering their labels and not the copy's when the requestor, the sharer, and the owner are mutual friends. For the scenario in Example 4, for instance, if Mina issues a read IR on the shared copy of Walt's picture from the common friend Javier, the labels assigned by Walt for the original picture and for Mina are used to evaluate the IR, and not the ones assigned by Javier to the shared copy and to Mina. This is enforced by Algorithm 1 as it will be presented later.

The add-tag & write privileges and the write higher property Both the add-tag and the write interactions, if granted, result in the creation of new objects, and therefore they bring to the problem of what the labels for these resulting objects should be. For instance, assume Bob has a very high level of trust in Alice and allows her to post on his wall. Alice might hold sensitive information about Bob and, as such, her posts on his wall might reflect some of it. Thus, Bob would want that Alice's posts on his wall be managed with a label that reflects their expected sensitivity; that is, a label that is at least as high as the one he assigned to Alice. On the other hand, if Bob's trust on another user, say Aliah, is low, then he might need to impose more control on her posts on his wall as it could be that she holds some sensitive information about him that she might post to embarrass him, for example. The same applies to the add-tag interaction as well. To cope with this, we suggest enforcing two conditions on the labels that requestors of granted write or add-tag IRs can assign to the resulting objects. The first condition imposes a sensitivity level for the created object that is at least as high as the clearance level that the affected user assigned to the requestor, if this latter is higher than the medium level. For example, if Bob assigns a high clearance level to Alice, Alice's posts on his wall will have at least a high sensitivity level. However, if the clearance level assigned by the affected user to the requestor is lower than the medium level, its inverse is set as the least requirement for the sensitivity level of the resulting object. For instance, if Bob assigns to Aliah a low clearance level, Aliah's posts on his wall will have a sensitivity level at least equal to the inverse of Aliah's clearance level (i.e., a high sensitivity level).

The second condition imposes that the group set of the resulting object's label is exactly the group set that the affected user specified in her label for the requestor. For example, if Bob assigned the group "colleagues" to Alice, then it is likely that Alice's posts about him will also concern the "colleagues" group. To formalize these conditions, we introduce the third axiom of LAMP, referred to as the Write Higher Property -(WHT): Definition 9 (Write Higher Property -WHT) Let a, b ∈ U be two friends in the OSN (i.e., ∃e a,b ∈ F R) and let F CL a,b =(CL a,b , T S a,b , GS a,b ) be the label a assigned to b. Let ir b,x = (x, p, b) be an IR such that p ∈ {write, add-tag} and x = a, if p = write, x = (a, ob), if p = add-tag, with ob the object to be tagged. Let o be the object resulting from granting ir b,x and OSL o be its assigned label by b. ir b,x satisfies WHT if and only if:

o.owner = a ∧ OSL o = (SL o , T Y o , GS o ) s.t., GS o = GS a,b , T Y o = T G if p=add-tag. F P if p=write. and SL o ≥ CL a,b if CL a,b ≥ M. f -1 (CL a,b ) otherwise.
With f -1 (y), y ∈ LOS being the inverse function for security levels. For example

f -1 (V H) = V L, f -1 (L) = H, etc.
Example 5. Consider Example 2, and assume Javier has the right to post on Walt's wall and that he posts on it a video of Walt's graduation ceremony. We recall that Walt assigned to Javier (H, {P, T, V}, {colleagues, university}). By the WHT property, the video's owner is Walt, and a possible granted label that Javier can assign to it is: (H, FP, {colleagues, university}). This means that the video will be available only to the friends of Walt to whom he assigned a high or a very high clearance level, who belong to the colleagues or to the university groups, and who are allowed to see Walt's friends' posts.

Access control enforcement Putting it up all together, Algorithm 1 defines how access control is enforced in the system based on the privacy preferences of users, as expressed through FCLs and OSLs and on the properties defined above.

Algorithm 1 takes as input an IR and produces as output a granted or denied message, based on the corresponding properties to the requested privilege. For a read IR, the algorithm first checks if the target object is a copy. If it is, the NoHorDisclosure function is called (lines 3,4) to rewrite the IR as targeting the original object, as long as the involved parties are mutual friends (lines 34,39). It is then checked if the retrieved IR satisfies the FSP. If it does, a similar IR is propagated through the children of the target object (i.e., calling the propagate procedure in line 6). The procedure traverses the object's tree in a depth first manner, evaluating each child against the FSP. If satisfied, granted is returned and the depth traversal continues. Otherwise, denied is returned (lines 39-46) and the traversal moves to the next breadth child. In case the input IR does not satisfy the FSP, denied is returned (line 8).

For a write IR, it is first checked if the requestor has a write privilege on the targeted user's wall, by evaluating a read IR on the root object of the targeted user (lines [START_REF] Madejski | The failure of online social network privacy settings[END_REF][START_REF] Masoumzadeh | Osnac: An ontology-based access control model for social networking systems[END_REF]. If this IR satisfies the FSP and the input write IR satisfies the WHP, this latter is granted, otherwis denied is returned (lines [START_REF] Mehregan | Design patterns for multiple stakeholders in social computing[END_REF][START_REF]Label security administrator's guide[END_REF][START_REF] Pang | A new access control scheme for facebook-style social networks[END_REF][START_REF] Squicciarini | Cope: Enabling collaborative privacy management in online social networks[END_REF].

In case the input IR is a share one (line 16), it is checked if it satisfies both the FSP and the SHP sending granted if it does, or denied in the failing case.

As for add-tag IRs, a read IR on the object to be tagged is formulated by the system (line 22). Then it is checked if this system IR satisfies the FSP and if the input add-tag IR satisfies the WHP. If the two conditions are satisfied, the input IR is granted, otherwise it is denied.

Finally, for add-like and add-comment IRs, they are granted only if they satisfy the FSP and if a system issued read IR on the object they target (line 29) is granted (i.e., it satisfies the FSP too) (lines 30-33).

Correctness Property

To formalize the correctness property of the system, we define the concept of its state as the set, SIR = {ir 1 , ir 2 , ..ir n }, of interaction requests currently granted in the system. We say that the state of the system is correct, and we refer to it as the correct state, if and only if ∀ir i ∈ SIR, ir i satisfies all the model's properties. The system changes its state only when a new IR processed by Algorithm 1 returns a granted message. Given a correct state, the following holds: 5Theorem 1. Let SIR be the current state of the system. Let ir new be a new interaction request issued to the system. Algorithm 1 issues a granted message if and only if SIR new = SIR ∪ {ir new } is a correct state.

We note that changes to labels, either FCLs or OSLs, by a user does not affect the stability of the system, as they concern how the user's data flows to her friends only. That is, if Alice changes the OSL of her photo, this will only result in making it available to a larger audience from her friends, as will be imposed by Algorithm 1. Likewise, changing the FCL of her friend Bob, will result in changing the set of her available objects to Bob, for which the access will always be controlled by Algorithm 1.

Algorithm 1 Access control enforcement

Performance Experiments

In our experiments, we study the performance of LAMP under access scenarios simulated on a real OSN graph. We have implemented a prototype of LAMP as a web application that we interfaced with Facebook graph API. The prototype has been implemented using PHP and the MySQL DBMS. We have been running a usability study, for which preliminary satisfactory results have been obtained.

For space limitations, we report these in a technical report [START_REF] Bahri | Technical report: Lamp -labelbased access control for more privacy in online social networks[END_REF]. Our experiments have been conducted on a standard PC with a dual core processor of 2.99 GHZ each and 8 GB of RAM.

For performance testing, we exploited the public dataset available for the Slovakian OSN, Pokec. 6 The dataset represents a friendship graph of 1.63 million nodes and 30.6 million edges with a diameter equal to 11; however, it does not contain any data object. As we discuss in [START_REF] Bahri | Technical report: Lamp -labelbased access control for more privacy in online social networks[END_REF], the performance is regulated by the number of children in an object dependency tree (i.e., d), and by the number of chained shares an object is subject to (i.e., m). For this, we performed two experiments, by varying both m and d independently. As such, we first simulated share operations along friendship paths of different lengths, and we computed the time required to evaluate an access request on each of the shared copies. Figure 3.a reports the achieved results. The x-axis refers to the number of chained shares an object has been subject to, whereas the y-axis refers to the average time in milliseconds required to evaluate an access request on the last shared copy. All the reported numbers are the result of averaging 40 individual instances. As we can see on the figure, the time required to evaluate an access request on a shared copy is directly proportional to the distance between the target shared copy and the original object it refers to (i.e., the number of chained shares). However, the case of a chained share of length 50 requires no more than 80 ms. We can also see that the evaluation time does not follow a perfect linear increase with the number of chained shares. This is because the friendship sub-graph surrounding the sharing path also affects the convergence of the evaluation, as the NoHorDisclosure function in Algorithm 1 makes recursive calls as long as a common friendship is found to be between the requestor and the owner of the copied object.

We have also simulated object dependency trees of different sizes (d) varying both their breadth and depth. We considered the worst case scenario whereby the access evaluation on all children of a tree is positive. Figure 3.b reports the achieved results by plotting the time in milliseconds (the y-axis) for tree sizes varying from 100 to 10K children. 7 For each reported tree size, the evaluation time has been averaged across 10 different trees by varying their breadth and depth sizes. For all considered trees, the breadth made at least 80% of the tree's size. This is because on Facebook for instance, and according to the same study mentioned above, most of the interactions are one level likes or one level comments. As it can be seen on the figure, the amount of time required to evaluate access requests on all the children in an objects dependency tree increases, as expected, almost linearly with the size of the tree. We can see that the evaluation time still remains below 8k ms for trees of 10k children in size.

Conclusion and Future Work

In this paper, we presented a label-based access control model for OSNs. The proposed LAMP model considers relationships between objects in an OSN and allows their control at an atomic ownership level, simplifying as such the complexity of addressing data co-ownership of integral elements over which conflictual access policies may be specified. LAMP ensures a flexible and rich set of privacy settings, and empowers data owners to have control over the objects they create at finer granularity levels (e.g., comment, like, etc.). Our method achieves practical performance results and it is also designed to fit within different types of OSNs. Indeed, although we assume an undirected graph model for OSNs, our proposed solution can naturally fit the directed graph model as well, as the FCLs are directional (i.e., F CL A,B and F CL B,A are independently governing the data flow from A to B and from B to A, respectively.)

We are aware of the importance of ensuring usability and friendliness to average OSN users. Our preliminary usability experiments results are satisfactory [START_REF] Bahri | Technical report: Lamp -labelbased access control for more privacy in online social networks[END_REF]; however, they remain limited in terms of the number of participants and their representation of average users, but most importantly in terms of the amount of time these participants have been using our app. However, we believe that our model provides a simpler solution compared to other proposals for the management of co-owned data. As such, the first planned extension of this work is on usability experiments that need to be enriched in terms of the representativeness of participants, the statistical relevance of usage time, and the completeness of the interactions available on the app. Moreover, we plan to design accompanying

Fig. 1 :

 1 Fig. 1: Privacy management with ReBAC vs. LAMP

Fig. 2 :

 2 Fig. 2: Typical objects' structure in OSNs.

Definition 2 (

 2 Friend Clearance Label -FCL) Let a, b ∈ U be two friends in the OSN (i.e., ∃e a,b ∈ F R). The label F CL a,b , assigned by user a to user b, is denoted by the tuple (CL a,b , T S a,b , GS a,b ), where: (i) CL a,b ∈ LOS is the clearance level that a grants to b; (ii) T S a,b ⊆ OT S is the set of object types that a wants b to get access to; (iii) GS a,b is the set of groups that a assigns to b.We refer to object labels as Object Sensitivity Labels (OSL), and we formally define them as follows: Definition 3 (Object Sensitivity Label -OSL) Let a ∈ U be a user in the OSN and let o be an OSN object such that o.owner = a. The label OSL o of object o is denoted by the tuple (SL o , T Y o , GS o ), where: (i) SL o ∈ LOS is the sensitivity level of o; (ii) T Y o = o.type is the type of o; (iii) GS o is the set of groups for which object o should be available.

Definition 4 (

 4 Interaction Request -IR) Let a, b ∈ U be two friends in the OSN (i.e., ∃e a,b ∈ F R). An IR by user b on user a is denoted by the tuple ir b,x = (x, p, b), where p ∈ P S is the requested privilege, and x has one of the following forms: x = o, where o is an object s.t. o.owner = a; if p ∈ {read, add-like, add-comment}, or x = o, where o is an object s.t. o.owner = a and o.parent = null; if p = share, or x = a, where a is the target user; if p = write, or x = (a, o), where a is the target user and o is an object; if p =add-tag.

Definition 5 (

 5 Dominance relationship) Let a, b ∈ U be two friends in the OSN (i.e., ∃e a,b ∈ F R) and let F CL a,b =(CL a,b , T S a,b , GS a,b ) be the label a assigned to b. Let o be an object s.t. o.owner = a, and let OSL o = (SL o , T Y o , GS o ) be its OSL. F CL a,b dominates OSL o , denoted as F CL a,b OSL o , if an only if,

  We are now ready to introduce the first property in LAMP, referred to as the Fundamental Security Property (FSP): Definition 6 (Fundamental Security Property) Let a, b ∈ U be two friends in the OSN (i.e., ∃e a,b ∈ F R) and let F CL a,b be the label a assigned to b. Let o be an object s.t. o.owner = a, and let OSL o be its label. Let ir b,o = (o, p, b) be an IR made by b on o s.t p ∈ {read, share, add-like, add-comment}. ir b,o satisfies FSP, iff: F CL a,b OSL o .

Definition 7 (

 7 Not-declassify relationship) Let OSL o = (SL o , T Y o , GS o ) be the label of an object o. Let OSL o = (SL o , T Y o , GS o ) be the label assigned to a copy o of o (i.e., o.copyof = o). Label OSL o does not declassify label OSL o , and we write OSL o OSL o , if and only if: SL o ≥ SL o .

Definition 8 (

 8 Share Higher Property -SHP) Let a, b ∈ U be two friends in the OSN (i.e., ∃e a,b ∈ F R), and let o be an object s.t. o.owner = a. Let OSL o be the label a assigned to o. Let ir b,o = (o, share, b) be a share IR made by b on o, and let OSL o be the object label that b intends to assign to the copy of o. We say that ir b,o satisfies SHP, if and only if: OSL o OSL o .

Fig. 3 :

 3 Fig. 3: Performance results on LAMP

Table 1

 1

	lists the different

Table 1 :

 1 Types of information shared in OSNs.

	o1=Javier shares o2 of Bob:"Fresh air!"
	o3 = Bob Likes	o4 = Aliah comments "poetic!"
	o5 = James Tags Bob o6 = Javier Likes

http://www.americanbar.org/publications/blt/2014/01/03a_claypoole.html

Using the labeling strategy of MAC under a decentralized approach has been adopted in other systems, such as Oracle Label Security where labels are used in conjunction with DAC functionalities to provide access policy refinement at a table level[START_REF]Label security administrator's guide[END_REF].

We use the dot notation to refer to the parameters in an object tuple.

We recall that the write privilege refers to posting on friends' walls.

Related proofs are reported in[START_REF] Bahri | Technical report: Lamp -labelbased access control for more privacy in online social networks[END_REF].

http://snap.stanford.edu/data/soc-pokec.html

Based on a 2015 study on Facebook, the average likes for personal content is below 100. It is about 100K for business and fans pages: http://www.adweek.com/socialtimes/infographic-quintly-average-like-totals-pagesfebruary-2015/617303

mechanisms for the automatic assignment of friend and object labels based on general policies that the users can set, or based on automated learning strategies.


Frank Morgner

Paul Bastian

Marc Fischlin

Securing Transactions with the eIDAS Protocols

The proposed European system for electronic identities, authentication, and trust services (eIDAS) enables remote authentication of an identity card (and selected data of the card) to an eID service. The core system has already been running on the German identity card since 2010. We analyze an extension proposed by Bundesdruckerei that enables the protocol to authenticate further transaction data such as phone numbers or PGP keys. In particular we prove cryptographically that the extension provides strong authenticity guarantees. We also discuss privacy aspects of the solution, preventing the card and the service provider of the eIDAS system to learn the actual transaction data.

Introduction

With Regulation EU No 910/2014 about electronic identification, authentication, and trust services for electronic transactions (eIDAS) in 2014, the European parliament has paved the way for a common electronic identity system for Europe. Driven by German and French IT security offices, namely BSI and ANSSI, the first technical proposal for such eIDAS tokens has been put forward in [START_REF]Federal Office for Information Security): Technical Guideline TR-03110-2: Advanced Security Mechanisms for Machine Readable Travel Documents and eIDAS Token, Part 2, Protocols for electronic IDentification, Authentication and trust Services (eIDAS)[END_REF] in February 2015. The proposal extends a previous specification for the new German identity cards [START_REF]Federal Office for Information Security): Advanced Security Mechanism for Machine Readable Travel Documents -Extended Access Control (EAC), Password Authenticated Connection Establishment (PACE), and Restricted Identification (RI)[END_REF], and as the cards have been issued since November 2010, this means that the basic eIDAS system proposal is already effectively running at this point.

The Basic eIDAS System

The system of the German identity card adopted early the idea to use the identity card securely for internet services. The basic steps of the protocol are outlined in Figure 1. The identity card is securely connected to a local card reader at the user's computer via the password-authenticated connection establishment (PACE) protocol. The reader itself is equipped with a small tamper-proof display and is connected (through an application interface on the user's computer) with a service running the eID server. The connection from the computer to the server may be secured through TLS.

The ID card and the eID server then execute the extended access control (EAC) protocol which consists of a terminal authentication (TA) and a chip authentication (CA). In the TA step the eID server authenticates and transmits the credentials for accessing some fields on the ID card, such as for age verification or the address. The human user confirms access to the fields via the reader, by verifying the request on the reader's display. Then the card authenticates itself and the requested data through the CA step.

Securing Transactions through the eID System

Based on a proposal by Bundesdruckerei [START_REF] Morgner | Transaktionsabsicherung mit der Online-Ausweisfunktion. Kryptographische Bindung von Transaktionsdaten an den Personalausweis. Presentation[END_REF], we discuss how to use the German identity card system (and consequently, the anticipated European eIDAS system) to secure further transaction data. As an example assume that the eID system is used in an online banking service, and that the bank would also like to authenticate the mobile phone number of the user (e.g., for establishing a reliable communication channel for authentication of bank transactions). This phone number is not present on the identity card and thus cannot, per se, be authenticated through the eID system.

The idea of building a transaction system on top of the eID system is to use the auxiliary-data field, originally provisioned for refinements in the data authentication (e.g., the eID server has to commit to the current date for age verification). In order to show that one can securely use this entry for authenticating data like the phone number one needs to show that (a) the solution really validates the transaction, and that (b) it is indeed possible to smoothly extend the existing system to incorporate such checks. The feasibility has already been reported in [START_REF] Morgner | Transaktionsabsicherung mit der Online-Ausweisfunktion. Kryptographische Bindung von Transaktionsdaten an den Personalausweis. Presentation[END_REF], and we briefly revisit the details at the end of the work, such that it remains to show that the scheme is indeed secure.

We therefore first present a cryptographic description of the transaction system of Bundesdruckerei, called eIDAS transaction system here. The idea is depicted in Figure 2 and consists of the following steps. [START_REF]Federal Office for Information Security): Advanced Security Mechanism for Machine Readable Travel Documents -Extended Access Control (EAC), Password Authenticated Connection Establishment (PACE), and Restricted Identification (RI)[END_REF] The card holder and the service provider first agree upon the transaction T. (2) Then the service provider initiates the eID server for a hash value H(T) of the transaction. [START_REF] Morgner | Transaktionsabsicherung mit der Online-Ausweisfunktion. Kryptographische Bindung von Transaktionsdaten an den Personalausweis. Presentation[END_REF] The card holder also forwards the transaction in clear to the reader. (4) The original eID components run the TA step, including H(T) as auxiliary data. [START_REF] Bender | The PACE|AA Protocol for Machine Readable Travel Documents, and Its Security[END_REF] The reader verifies T against H(T), and the user verifies the transaction via the reader's display. [START_REF] Bender | Domain-Specific Pseudonymous Signatures for the German Identity Card[END_REF] To approve the transaction the user initiates chip authentication. [START_REF] Bender | Security Analysis of the PACE Key-Agreement Protocol Information Security Conference[END_REF] The eID server reports back approval of the transaction if chip authentication terminates successfully.

Fig. 2. The eIDAS transaction system

Our contribution is to put the security of the eIDAS transaction system on formal grounds. To this end we first discuss a security model which ensures that a transaction system satisfying the requirements in the model provides strong authenticity properties of transactions. The model basically guarantees that both parties, card holder and service provider, can have confidence that they agree on the same transaction with the intended partner in a certain session. By this the security model captures for example replay attacks or cloning of transactions across executions, such that the secure transaction system remains immune against such attacks.

An extra feature of the eIDAS transaction system is that the transaction data can be hidden from the underlying eID service. That is, instead of passing the transaction in clear to the service, one can forward a hashed (or committed) version to the service. Our other contribution is to analyze, too, the privacy guarantees given through such a step formally.

We note again that [START_REF] Morgner | Transaktionsabsicherung mit der Online-Ausweisfunktion. Kryptographische Bindung von Transaktionsdaten an den Personalausweis. Presentation[END_REF] presents an implementation of the above protocol which requires only minor modifications on the reader's side, but is otherwise based on the existing software and hardware for the German identity card. We report on this briefly in Section 5.

Related Work

Since we model transactions as digital data, the authenticity problem of transaction systems at the core resembles the authenticity problem in secure channels. Therefore, it is no surprise that previous approaches for modeling secure channels such as [START_REF] Bellare | Breaking and provably repairing the SSH authenticated encryption scheme: A case study of the encode-then-encryptand-MAC paradigm[END_REF][START_REF] Canetti | Analysis of key-exchange protocols and their use for building secure channels[END_REF][START_REF] Namprempre | Secure channels based on authenticated encryption schemes: a simple characterization[END_REF][START_REF] Maurer | On the soundness of authenticate-then-encrypt: formalizing the malleability of symmetric encryption[END_REF] can serve as a starting point to model security for the transaction system. There are, nonetheless, significant differences.

On one hand, we face a simpler problem in the sense that transactions are atomic and we do not have to deal for example with the order of channel transmissions. On the other hand, a transaction in our sense should be authenticated mutually: both parties should be ensured that the transaction is authentic. In contrast, most channel protocols and models consider unidirectional message transfers, where the message is sent and authenticated by one party only. This in principle allows for mutual authentication by "mirroring" the message back.

In fact, a secure transaction system could be implemented straightforwardly in principle via signatures: have both parties exchange nonces and then have each party sign the transaction and the nonces under its certified key. The nonces would prevent replay attacks. The point of the solution in [START_REF] Morgner | Transaktionsabsicherung mit der Online-Ausweisfunktion. Kryptographische Bindung von Transaktionsdaten an den Personalausweis. Presentation[END_REF], however, is to build upon an existing system with reliable hardware components such as the identity card and the card reader, without or with minimal interference with the underlying system.

The protocols of the German identity card and (some of) the eIDAS extensions have been analyzed in a series of works [START_REF] Bender | Security Analysis of the PACE Key-Agreement Protocol Information Security Conference[END_REF][START_REF] Dagdelen | Security Analysis of the Extended Access Control Protocol for Machine Readable Travel Documents[END_REF][START_REF] Kutylowski | Restricted Identification Scheme and Diffie-Hellman Linking Problem[END_REF][START_REF] Coron | Pascal Paillier: Supplemental Access Control (PACE v2): Security Analysis of PACE Integrated Mapping[END_REF][START_REF] Bender | The PACE|AA Protocol for Machine Readable Travel Documents, and Its Security[END_REF][START_REF] Bender | Domain-Specific Pseudonymous Signatures for the German Identity Card[END_REF][START_REF] Hanzlik | Simplified PACE-AA Protocol[END_REF][START_REF] Bender | The PACE|CA Protocol for Machine Readable Travel Documents INTRUST[END_REF][START_REF] Hanzlik | Restricted Identification Secure in the Extended Canetti-Krawczyk Model[END_REF]. In fact, supporting the protocols by security arguments in form of cryptographic proofs has been a key point in the marketing strategy. We do not directly rely on these results, but we draw on the EAC analysis in [START_REF] Dagdelen | Security Analysis of the Extended Access Control Protocol for Machine Readable Travel Documents[END_REF] for showing that the CA ensures transaction authenticity for the service provider.

The eIDAS transaction system

We first define transaction systems abstractly, and then present the eIDAS transaction system of Bundesdruckerei in our notation.

Transaction Systems

A transaction system T S is given by an interactive protocol between one type of parties, called card holders (or clients) and another type of parties, denoted as service providers (or servers). This is formally specified through a pair of (stateful) algorithms Π C , Π S which describe the next message the corresponding party sends upon receiving a message from the other partner. In addition to the interactive protocol the system also comprises key generation algorithms KG C and KG S for both types of parties. The key generation algorithms generate key pairs (sk, pk) for the corresponding party, together with a certificate cert.

We assume uniqueness of the certificates and it is convenient to view some unique identifier in a certificate, such as the serial number, as the party's (administrative) identity id. We often use cert interchangeably as the identifier id.

The certification process is prepared by a general Setup algorithm which creates public parameters such as the root key pk CVCA for verification of certificate chains, as well as secret parameters for certificate generation, typically signing keys.

The interactive protocol execution between a card holder and service provider starts with both parties receiving their keys and certificate as input. Both parties also get the public data of the Setup algorithm as additional input. Each party usually also receives a transaction T as input which it tries to authenticate. A party may abort the execution at any time; it may also accept and terminate. We assume the usual completeness requirement that, if running on genuine parameters and the same transaction, both parties accept.

A preportioned transaction system does not hand over the transaction T to the parties in clear. Instead, it uses another algorithm H (as a mnemonic for a hash function) to first compute H(T) before handing the value to the party. The parameters of this algorithm can be specified through the Setup algorithm, and it may be even be a probabilistic algorithm: H(T; r) for random string r. 3We nonetheless often simply refer to H(T) instead of H(T; r), as the difference becomes relevant only for the privacy setting. Note that the actual transaction system can then only ensure validity of H(T) and that this extends to T must be checked by some other mean, e.g., as in the eIDAS transaction system providing the card reader also with T, r and having it check these values against the hash value used in the underlying transaction system.

The eIDAS transaction system

The eIDAS transaction system basically consists of the EAC system where we use the auxiliary data field A T to transport the (hidden) transaction H(T). Since our goal is to build upon the existing scheme, we do not argue about the specific choices of the EAC system here but instead refer to [START_REF]Federal Office for Information Security): Advanced Security Mechanism for Machine Readable Travel Documents -Extended Access Control (EAC), Password Authenticated Connection Establishment (PACE), and Restricted Identification (RI)[END_REF][START_REF]Federal Office for Information Security): Technical Guideline TR-03110-2: Advanced Security Mechanisms for Machine Readable Travel Documents and eIDAS Token, Part 2, Protocols for electronic IDentification, Authentication and trust Services (eIDAS)[END_REF] for information about the design ratio. In more detail, both parties first execute the so-called Terminal Authentication (TA) steps of the extended access control. 4 In this step, the terminal picks a fresh ephemeral key pair (esk T , epk T ) for the domain parameters D C describing the elliptic curve, sends over its certificate for the long-term key pk T (which is also included in cert T ) and a compressed version Compr(epk T ) of the ephemeral public key. The compression function can be for example the projection onto the x-coordinate of the elliptic curve point. For our analysis we merely assume that Compr is R-regular, meaning that each image has exactly R pre-images.

The chip replies with a random nonce r C and the terminal then signs this nonce, together with Compr(epk T ). In this step, the eID server of the service provider augments the signature step by the hash value H(T) it has received from the web server. This assumes that the forwarding of H(T) to the eID server is carried out securely; else it is easy to replace the otherwise unprotected transaction T in the communication with the card holder. Note that in the TA protocol both parties also use some chip identifier id C , not to be confused with our administrative identifier id, for signature generation and verification. Since this value is irrelevant for our security analysis we do not comment further on this value. The chip finally verifies the signature.

Upon successful completion of the TA step, the reader verifies that the given transaction T matches the augmented data H(T) from the TA step and then displays the transaction to the user. Upon confirmation of the user, the reader initiates the Chip Authentication (CA) step between the card and the eID server. In this step the chip sends its certificate cert C and public key pk C , and the terminal replies with its ephemeral public key epk T (in clear).

Finally, both parties compute the Diffie-Hellman key of pk C and epk T with the corresponding secret key they hold, and derive an encryption key K enc (which is irrelevant here) and the MAC key K mac with the help of the corresponding key derivation functions KDF Enc and KDF M . This step again involves a random nonce r C of the chip. The chip computes the MAC over epk T and sends it to the terminal. If this phase is completed successfully then the eID server reports to the web server that the transaction has been confirmed. This, again, must be done in a secure way.

The protocol details of the TA and CA phase are depicted in Figure 3. For administrative purposes in light of the security model it is convenient to also specify a point in time in the execution in which a session identifier sid is set. This session identifier can be thought of as a quasi unique, purely administrative value, although the parties can determine the identifier easily themselves. Note that both parties output the identifier sid at different points of the execution, due to the sequential order of the authentication steps.

Analogously, we let the protocol specify a partner identifier, pid, which should represent the identity of the intended partner. Since we assume a one-to-one correspondence between certificates and administrative identities, we extract the correct identity out of the certificate. Completeness requires that both session identifier and partner identifier are set upon acceptance, that session identifiers are identical for both parties in genuine executions, and that the partner identifiers correctly point to the corresponding parties.

Unforgeability of Transactions

In this section we provide our security analysis of the eIDAS transaction system. For this we first introduce a demanding security model for unforgeability, then we discuss that the eIDAS transaction system achieves this property.

certT ←-------------- check certT with pk CVCA abort if certT invalid extract pk T from certT generate (eskT , epk T ) for domain DC Compr(epk T ) ←-------------- pick rC ← {0, 1} n rC --------------→ sT ← Sig(skT , idC ||rC ||Compr(epk T ) [|| AT ] ) sT [, AT ] ←-------------- abort if SVf(pk T , sT , idC ||rC ||Compr(epk T ) [||AT ] ) = 0 sid = (Compr(epk T ), rC [, AT ] ) Chip Authentication (CA) pk C , certC , DC --------------→ check pk C , certC with pk CVCA abort if invalid epk T ←-------------- check epk T against Compr(epk T ) abort if invalid pick r C ← {0, 1} n K = DHD C (skC , epk T ) Kenc = KDFEnc(K, r C ) Kmac = KDFM(K, r C ) τ = M(Kmac, epk T ) τ, r C --------------→ K = DHD C (pk C , eskT ) Kenc = KDFEnc(K, r C ) Kmac = KDFM(K, r C ) abort if MVf(Kmac, τ, epk T ) = 0 sid = (Compr(epk T ), rC [, AT ] ) pid = id in certT pid = id in certC accept accept
Fig. 3. EAC protocol, consisting of Terminal Authentication (TA) and Chip Authentication (CA). All operations are modulo q resp. over the elliptic curve. The gray part shows the (in EAC optional) auxiliary data field, which we deploy here for securing the transaction.

Defining Unforgeability

Attack Model. We assume that all parties, divided exclusively into card holders from set C and service providers from a set S, receive their (certified) key pairs as initial input at the outset of the attack. We furthermore presume security of the certification in the sense that parties will only accept certified keys. This follows from the unforgeability of the underlying signature scheme used to create certificate, or even certificate chains, but we omit this here for sake of simplicity.

In the attack model the network is fully controlled by the adversary, implying that the adversary decides when to deliver messages to sessions and if to modify transmissions or even to inject new messages. We even assume that the adversary decides when to start new sessions at either party, possibly as a pair of synchronized sessions for the same transaction. Formally, this is captures by giving the adversary access to the following oracles:

-Init: The adversary can initiate new card holder or service provider sessions by calling Init(id, T) for some identity id ∈ C ∪ S and some chosen transaction T. Upon such a call we spawn a new session of the party for transaction T (and possibly a freshly chosen random string r in case of probabilistic hash functions) and assign it a unique label for administrative purposes. The label is returned to the adversary and we write ← Init(id, T).

In the case of a probabilistic hash function we need to give the adversary the ability to initiate sessions with the same random value r. Hence, slightly overloading the notation we allow the adversary to also pass triples (id, id , T) to the Init oracle for id ∈ C and id ∈ S, upon which the oracle initializes a new session for card holder id as well as a new session for service provider id . This time, however, each protocol party receives the same random string r as additional input. The adversary receives both labels ( , ) of the two sessions.

-Send: The adversary can send any protocol message m to a session with label via the Send( , m) command. If the session has not been initialized before, then oracle immediately returns ⊥. Else, it makes the corresponding party compute the next protocol message and this message is returned to the adversary (potentially also returning ⊥ to express rejection). In case the execution is successfully completed, the adversary is informed that the party has accepted. From then on, we assume that the adversary no longer sends commands to that session. -Corrupt: The adversary can corrupt a party with identity id via the command Corrupt(id). It receives the party's secret key in return, as well as all internal states of running sessions, and we put id in the (initially empty) set Corrupt of corrupt parties. From now on, we assume that the adversary does not send further commands to that session.

It is often convenient to augment the session identifier sid, output by the execution of some honest party, by the transaction T it has been initialized with. In this case we write tsid = (T, sid) for the augmented identifier (but omitting the random string r potentially used for computing the probabilistic hash value).

We also use the following self-explanatory notation. We write TSID( ) for the value tsid of the session with label , where potentially TSID( ) = ⊥ if the session identifier has not been set by the session yet. Analogously, we write ACC( ) for the acceptance status of the session (true or false), ID( ) for the identity id of the session owner, and PID( ) for the intended partner pid, possibly pid = ⊥ at this point.

Session-definite unforgeability. We define a very strong notion of unforgeability: if some (honest) card holder accepts a transaction in some execution, then there must be an execution in which a service provider has issued that transaction. Furthermore, this execution of the service provider points to a single card-holder session only. Note that this straightforwardly implies other desirable notions of unforgeability, such as plain unforgeability-if a card holder accepts some transaction then it must have been issued by some service provider-or replay resistance-that no card holder accepts a transaction twice. The latter follows from the fact that there is a one-to-one correspondence between serviceprovider sessions and card-holder sessions. We call our notion session-definite unforgeability.

More formally, we say that the adversary A wins the session-definite unforgeability game in Figure 4 if during the execution an honest card-holder party id ∈ C \ Corrupt accepts a transaction T under some session identifier tsid but such that there the partner id pid is not pointing to a corrupt provider and that provider has not set their local identifier to sid at that point. The latter corresponds to the fact that the service provider has issued the transaction. By symmetry, we demand the same for accepting sessions of honest service providers, i.e., that there must be a corresponding card-holder session. In addition, we assume that session identifiers only appear in matching pairs on the sides. This implies that there cannot be session-identifier collisions on the card-holder side, nor on the service-provider side. This also means that it suffices to demand for the first property above that every accepting session has a matching partner; together with collision-freeness of session identifiers on one side the matching session must be on the other party's side. The formal predicate capturing these requirements is depicted in Figure 5 and called as a subroutine in the attack game.

Experiment SessUnf T S A (n) 1 : foreach i ∈ C ∪ S do 2 : if i ∈ C then (ski, pk i , certi) ← KGC(1 n ) fi 3 : if i ∈ S then (ski, pk i , certi) ← KGS (1 n ) fi 4 : endforeach 5 : pks ← {(pk i , certi) | i ∈ C ∪ S } 6 : A Init(•,•),Send(•,•),Corrupt(•) (1 n , pks

Definition 1 (Session-definite unforgeability). A transaction system T S is session-definite unforgeable if for any efficient adversary A we have that

Prob SessUnf T S A (n) = 1 ≈ 0 is negligible.
Note that we let the adversary A decide when to stop the execution and to start evaluating the predicate. Hence, if it is advantageous and the adversary already detects a winning situation, it may end the execution immediately (instead of messing up the winning state by, say, corrupting another party). In our case this is easy to spot since all the data required to evaluate the predicate are known to the adversary.

Predicate SessUnfPred on execution state 1 : p ← true 2 : / / any accepting party must have honest partner with same tsid (or corrupt partner)

3 : foreach ∈ { | ACC( ) = true ∧ ID( ) / ∈ Corrupt } do 4 : p ← p ∧ [PID( ) ∈ Corrupt 5 : ∨ ∃ = : (TSID( ) = TSID( ) = ⊥ ∧ PID( ) = ID( ))]

Security of the eIDAS transaction system

Before proving the eIDAS transaction system unforgeable we need to make some assumptions about the underlying cryptographic primitives. As in [START_REF] Dagdelen | Security Analysis of the Extended Access Control Protocol for Machine Readable Travel Documents[END_REF] we model the key derivation function KDF M as a random oracle. We furthermore assume that the H function used to hide the actual transaction is collision-resistance in the sense that the probability Adv coll B,H (n) of B outputting such a collision is negligible for every efficient adversary B.

We also assume that forging signatures is infeasible, i.e., for any efficient adversary B the probability Adv unf B,SIG (n) of breaking the terminal's signature scheme given through SIG = (KG S , Sig, SVf) in an adaptive chosen-message attack (see [START_REF] Jatz | Introduction to Modern Cryptography[END_REF] for a formal definition) is negligible. We analogously demand that forging MACs for the scheme given through MAC = (KDF M , MAC, MVf) is infeasible, i.e., Adv unf B,MAC (n) is negligible for any efficient adversary B against the MAC scheme.

Finally, as in [START_REF] Dagdelen | Security Analysis of the Extended Access Control Protocol for Machine Readable Travel Documents[END_REF] we assume that the Gap-Diffie-Hellman problem in the group specified by D C is hard. That is, consider an efficient adversary B which receives (in multiplicative notation) g a , g b for generator g and hidden random a, b and which gets access to an oracle which for adversarially chosen group elements Y, Z verifies for the adversary whether Y a = Z or not. The adversary's task it to output DH(g a , g b ) = g ab . We now require that for no efficient adversary the probability Adv GapDH B,D C (n) of computing that DH value is negligible. Theorem 1 (Session-definite Unforgeability). The eIDAS transaction system in Section 2 is session-definite unforgeable in the random oracle model, assuming collision resistance of H, unforgeability of the signature and MAC scheme, and the GapDH assumption. More precisely, for any efficient adversary A there exists efficient adversaries

B 1 , B 2 , B 3 , B 4 such that Prob SessUnf T S A (n) = 1 ≤ s 2 • 2 -n + R q + Adv coll B1,H (n) + S • Adv unf B2,SIG (n) +S • Adv unf B3,MAC (n) + C • S • Adv GapDH B4,D C (n)
where we assume that Compr is a R-regular function, q is the group size specified by D C , the adversary initiates at most s sessions, and there are at most C cards and S service providers.

Moreover, adversaries B 1 , . . . , B 4 have roughly the same running time A plus the time to carry out the other steps in the experiment.

Proof (Sketch). We given the proof only for the case of a deterministic hash H(T) and single initializations through Init; for probabilistic hashes and synchronous initializations the proof can be adapted easily.

Assume that an adversary A mounts an attack against session-definite unforgeability. In order to win the adversary must either create a collision in two honest card-holder sessions, or in two honest service-provider sessions, or make one of the two types of parties accept such that there is no matching session (with a party of the other type, either corrupt or not having the same tsid).

The idea of ruling out the above attack possibility is that: sessions among honest card holders or among honest service providers do not collide because each session identifier sid contains fresh random values r C resp. epk T of both sides. The other property follows since the adversary, unless it forges signatures, cannot make a card holder accept without having an honest provider sign and output the session identifier sid. Since the session identifier includes the collisionresistant hash of transaction T this argument extends to the fully augmented identifiers tsid, as required by the security definition.

The final step is to note that, analogously to the signature case, an adversary making an honest provider accept without having an honest card-holder partner also requires the adversary to forge MACs. The latter argument is a bit more involved, but can be seen to follow from the proof that TA together CA is a secure key exchange protocol [START_REF] Dagdelen | Security Analysis of the Extended Access Control Protocol for Machine Readable Travel Documents[END_REF]. This is the step where we also use the Gap-Diffie-Hellman assumption. The full proof is omitted for space reasons.

Transaction Privacy

Analogous to the case of unforgeability we first describe the general security requirements and then discuss that the eIDAS transaction system meets these requirements.

Defining Privacy

Transaction privacy refers to the inability for the eID service to determine the transaction, even though it operates on the hash value. We use an indistinguishability-based approach here in which a privacy-adversary can initiate (multiple) executions on a random choice of one of two adversarially-chosen transactions T 0 , T 1 . This of course assumes that transactions are augmented by sufficient entropy, or else the adversary can easily determine the choice of the transaction used in the hash value.

The attack model is as in case of unforgeability. The only difference is now that the adversary now also gets a challenge oracle Chall, which is initialized with a secret bit b ← {0, 1}. If called about identities id ∈ C, id ∈ S, as well as two transactions T 0 , T 1 , then the challenge oracle executes ← Init(id, id , T b ) to initialize both parties, and it returns the session lables ( , ) to the adversary. From then on the adversary can communicate with the card-holder and service provider sessions via the Send oracle for the corresponding label (and in particular learn the hashed transaction). The adversary eventually should predict the bit b.

We next define privacy with the experiment in Figure 6.

Definition 2 (Transaction Privacy). A transaction system T S is transaction private if for any efficient adversary A we have that

Prob TPriv T S A (n) = 1 ≤ 1 2 + negl(n)
is negligibly close to 1 2 . Conceivably, any transaction-private system needs to be preportioned.

Privacy of the eIDAS transaction system

The privacy of the eIDAS transaction system now relies on the hiding property of the hash function, namely, that the probability of being able to distinguish H(T 0 , r 0 ) from H(T 1 , r 1 ) for chosen T 0 , T 1 and random r 0 , r 1 is infeasible for any efficient adversary B. We note that this is straightforward to formalize in terms of the hiding property of commitment schemes (see again [START_REF] Jatz | Introduction to Modern Cryptography[END_REF]), such that for the advantage Adv hide B,H (n) distinguishing the two cases it holds: Theorem 2 (Transaction Privacy of the eIDAS transaction system). The eIDAS transaction system provides transaction privacy. More precisely, for any efficient adversary A making at most Q challenge queries there exists an efficient adversary B such that

Experiment TPriv T S A (n) 1 : b ← {0, 1} 2 : foreach i ∈ C ∪ S do 3 : if i ∈ C then (ski, pk i , certi) ← KGC(1 n ) fi 4 : if i ∈ S then (ski, pk i , certi) ← KGS (1 n ) fi 5 : endforeach 6 : pks ← {(pk i , certi) | i ∈ C ∪ S } 7 : a ← A Init(•,•),Send(•,•),Corrupt(•),Chall(b,••• ) (1 n , pks) 8 : return a = b
Prob TPriv T S A (n) = 1 ≤ 1 2 + Q • Adv hide B,H (n).
Moreover, the running time of B is essentially the one of A, plus the time to execute the other steps of the privacy experiment.

Proof. Each call of A to the Chall oracle creates another fresh "commitment" of either the left or the right transaction. Then all parties work on the hashed value only. It follows that A's success probability is bounded by the probability of distinguishing at most Q left commitments from Q right commitments. Since a standard hybrid argument for commitments shows that such Q commitments (for adaptively chosen pairs) can only increase the distinguishing advantage compared to a single commitment by a factor Q, the claim now follows.

Implementation

As mentioned before, the eIDAS transaction system has been successfully integrated in a test bed for the German identity card, involving the Reiner SCT cyberJack reader. Recall that the user places the card in (or near) the reader and initiates a service through the software on its computer. The software application then requests the user to verify the transaction data (see Figure 7). The transaction data is encoded into an admissible format for the auxiliary data of the eID service under an unused object identifier such that the card, upon receiving the data, authenticates them through the protocol but ignores its semantics. In contrast, the reader has been modified to interpret these data accordingly.

From the user's perspective the steps to authenticate transaction data integrate smoothly with the other eID steps (see Figure 8). In the first step, where Fig. 7. Prototype implementation on a card reader. In this example the identity card has already been connected to the card reader, and the user is now asked via the (mockup) software on the computer to authenticate the e-mail address and PGP fingerprint on the reader. the regular eID system and the transaction system differ slightly, the user now checks the transaction data on the card reader, e.g., the mobile phone number in Figure 8. Then the user proceeds as for the regular eID service, confirming the card data the eID service can access (step 2 in Figure 8), and finally entering the card's PIN (step 3).

Overall, implementing the eIDAS transaction system requires minimal changes to the underlying system -only the reader's software needs to be adapted slightly-and to provide corresponding software applications.

Conclusion

The eIDAS transaction system is an easy and practical method to authenticate transactions via the eIDAS infrastructure. The work here demonstrates that, cryptographically, it also provides strong unforgeability guarantees, thwarting for example replay attacks. Furthermore, it also allows to hide the actual transaction data from the underyling infrastructure, again in a very strong sense.

Fig. 1 .

 1 Fig. 1. Extended Access Control (EAC) for online services, consisting of the terminal authentication (TA) step and the chip authentication (CA) step.

) 7 :Fig. 4 .

 74 Fig. 4. Session-definite unforgeabilty of transaction system.

6 : endforeach 7 : 9 :Fig. 5 .

 6795 Fig. 5. Security predicate SessUnfPred for session-definite unforgeability

Fig. 6 .

 6 Fig. 6. Transaction privacy experiment

Fig. 8 .

 8 Fig. 8. Immigration of transaction verification (left) into data access confirmation (middle) and PIN entering (right) of eID service.

  Terminal : key pair skC , pk C key pair skT , pk T certificate certC for pk C certificate certT for pk T card identifier idC card identifier idC auxiliary data [AT ] Setup: domain parameters DC , certification key pk CVCA Terminal Authentication (TA)

	Chip :

In combination with the yet-to-be-specified security properties this makes the algorithm rather a commitment algorithm but which, in turn, can be implemented via a hash function.

[START_REF] Bellare | Breaking and provably repairing the SSH authenticated encryption scheme: A case study of the encode-then-encryptand-MAC paradigm[END_REF] We skip the card holder's internal execution of the PACE protocol and assume a trustworthy reader and a secure connection between ID card and reader. This is justified by the fact that PACE has been shown to be a secure password-authenticated key exchange protocol[START_REF] Bender | Security Analysis of the PACE Key-Agreement Protocol Information Security Conference[END_REF] and that we anyhow require a trustworthy display for the user to check the transaction in clear.

Acknowledgements. We thank the anonymous reviewers of WISTP 2016 for valuable comments.