Jahid Khondker

Md Zahidul Reza

Vladimir Islam
email: zislam@csu.edu.auvladimir.estivill@upf.edu

Estivill-Castro

Khondker Jahid

Vladimir Estivill-Castro

3LP: Three Layers of Protection for Individual Privacy in Facebook

Keywords:

Introduction

Humans naturally keep themselves connected with friends, colleagues and families but due to geographical distances, people may not be able to meet their friends regularly. Hence, online social networks (OSNs) play a vital role to connect and share contents among people. Now, all over the world, citizens and organisations make extensive use of OSNs such as Facebook, Twitter, LinkedIn, and Google+. In recent years the usage of OSNs, particularly the usage of Facebook, has increased extensively [2,3].

Facebook is currently the third (after Google and Youtube) most viewed website [3] with 1.09 billion average active users every day [2]. Users typically store and share various personal data on Facebook resulting in the possibility of privacy breaches [START_REF] Ho | Privacy protection issues in social networking sites[END_REF]. Privacy is a crucial element of society. Social scientists have provided several definitions. Tavani defines privacy as our ability to restrict access to our personal information and to have control over the transfer of our information [START_REF] Herman | Ethics and Technology: Controversies, Questions, and Strategies for Ethical Computing[END_REF]. Rachel [START_REF] Rachels | Why privacy is important[END_REF] argues that privacy is the individuals' ability to disclose selectively personal information related to themselves. What is private for one may not be private for some others. For example, some may consider their political affiliation to be private while some others may not consider important to disclose their political alignment.

Data stored on Facebook about other users can be analysed for link prediction and attribute value prediction to learn sensitive and private information of victim users and hence compromise their privacy [START_REF] Heatherly | Preventing private information inference attacks on social networks[END_REF][START_REF] Ryu | curso: Protect yourself from curse of attribute inference: A social network privacy-analyzer[END_REF]. Sophisticated data mining techniques can breach individual privacy [START_REF] Al-Saggaf | Privacy in social network sites (SNS): The threats from data mining[END_REF] on Facebook.

It was empirically demonstrated [START_REF] Al-Saggaf | Privacy in social network sites (SNS): The threats from data mining[END_REF] that a data set built from other users' data that do reveal what one user U considers confidential can be used by an attacker M to build a classifier that predicts U 's private information with high confidence. The fundamental idea of the first techniques to guard against the attribute inference attack (NOYB [START_REF] Guha | NOYB: Privacy in online social networks[END_REF], TOTAL COUNT, and CUM SENSITIVITY [START_REF] Estivill-Castro | Empowering users of social networks to assess their privacy risks[END_REF]) is to identify a user's publicly available attribute values which are high predictors of a sensitive attribute value and recommend to the user to obfuscate the predictors. While NOYB [START_REF] Guha | NOYB: Privacy in online social networks[END_REF] randomly selects visible attribute values to obfuscate, TOTAL COUNT and CUM SENSITIVITY [START_REF] Estivill-Castro | Empowering users of social networks to assess their privacy risks[END_REF] heuristically identify which public data is highly informative and very likely to be influential in any classifier built by data mining techniques; therefore, recommending to the victim to modify or suppress the visible attribute values those are high predictors. The difference between TOTAL COUNT and CUM SENSITIVITY is in the ranking of the predictors, but both of them are very similar, so we encapsulate them into the global name of PrivAdv for short.

The protection technique PrivAdv does not consider friendship links among the users as information that M can use to infer the sensitive value of U . The information from on-line social networks can often be organised as a social attribute network (SAN ) [START_REF] Gong | Joint link prediction and attribute inference using a socialattribute network[END_REF]. The SAN model integrates both users' attribute information and their friendship network. Although PrivAdv has been extended to evaluate risks of the inference attack that derive from connections in the social network [START_REF] Estivill-Castro | Can on-line social network users trust that what they designated as confidential data remains so?[END_REF], the easiness of such an attack was not illustrated. Moreover, no concrete suggestions of what shall users do when their privacy is at risks because of social connections. That is, in such extensions [START_REF] Estivill-Castro | Can on-line social network users trust that what they designated as confidential data remains so?[END_REF], the algorithms recommend to unfriend or befriend a user from the victim's friend list randomly if such friend discloses any information which is sensitive to the victim. In those methods, the number of added or deleted friends may be large, and the victim may not be interested in this frequent addition and deletion of friends. We experimentally show that friendship links can be a useful piece of information for M . We also show that naively extending the existing technique [START_REF] Estivill-Castro | Empowering users of social networks to assess their privacy risks[END_REF] may not be effective to ensure privacy protection against M usage of this information. Here, we also propose a new technique (which we name 3LP) with three layers of protection in order to protect the sensitive value of U even if M uses the friendship links. We also experimentally demonstrate the effectiveness of 3LP. This paper is organised as follows. Section 2 discusses some limitations of existing techniques as evidenced by our initial experiments. Section 3 presents 3LP. Finally, Section 5 gives concluding remarks.

The Importance of Friendship Links

We now argue that any protection technique that does not take into consideration both, the attribute values of a user and links of a social network, is not able to ensure sufficient protection. We justify our argument since a real-life attacker can try to infer the sensitive information using whichever of the two aspects (attribute values and links) is ignored by the protection technique, dodging the single focused privacy mechanism. For example, we demonstrate that a previous work [START_REF] Estivill-Castro | Empowering users of social networks to assess their privacy risks[END_REF] that does not take the link information into consideration may not be able to secure sensitive data of users when an attacker uses the connection information of a social network.

We assume that attackers have access to a large data set which has the structure of an undirected social network (or graph) G having a N number of users, each with A attributes. Here, without loss of generality, each attribute value is considered as a distinct binary attribute. This standard data representation converts a categorical attribute like hometown (with possible values Sydney, Melbourne, and Brisbane) into a characteristic vector: the value is true if and only if the user's residential city correspond to that attribute-value pair. Under the SAN model, not only members of the OSN are vertices, but attribute-values are also vertices. For each user-vertex u with an attribute-value pair a = v, the SAN places an edge between u and the attribute-value pair a = v.

The SAN model also places an edge between two users if they are friends.

The SAN data model can be used by attackers to estimate the influence of a user on another user. The idea here is that linked users who have a small number of friends are strongly connected and have a high influence on each other. For example, if a user Tom White is linked to Rob Black and each of them has only two other friends then Tom and Rob have a high influence on each other meaning that if Rob supports the Labour party, then there is a greater chance that Tom will also support the Labour party. On the other hand, if a user is linked to another user who has a huge number of friends then the two users are relatively weakly connected and have low influence on each other. For example, if Tom is linked to Mel Gibson who has thousands of friends, then the fact that Tom supports the Liberal party does not give a strong clue on whether or not Mel Gibson also supports the Liberal party. Such influence of a user on another user u can be computed through a metric that represents the strength of the connection between u and an attribute-value pair a = v, where the strength of a connection is proportionate to the number of common users (who are friends of u and have the attribute-value pair a = v) and inversely proportionate to the numbers of friends of the common users.

We first need to introduce some notations before we formally present the metric function for a user and an attribute-value pair. We denote by Γ s+ (u) the set of all social users linked to a user u. Similarly, Γ s+ (a = v) is the set of all users having the attribute-value a = v. Also, Γ a+ (u) is the set of all attribute-value pairs linked to user u. Thus, the neighbourhood of u in the SAN is, Γ + (u) = Γ s+ (u) ∪ Γ a+ (u). On the other hand, w(u) is the weight of any social node (i.e. a user) u ∈ G. In this study, we assume the weight of each social node is constant and is set to 1. The equation [START_REF] Adamic | Friends and neighbors on the web[END_REF] for the metric m(u, a

= v) is m(u, a = v) = t∈Γs+(u)∩Γs+(a=v) w(t) log|Γ + (t)| . (1)
An interesting property of this metric is that, if friendship information is available, then m(u, a = v) can be calculated for any attribute-value pair a = v whether the user u has that value or not. A high m(u, a = v) suggests that u has a high chance of having value v for attribute a since, u is connected to many other users who have a = v. Since m(u, a = v) is computed by taking the network link information into account, we will add m(u, a = v) information for each user and each attribute in a data set (having a number of users and a number of attributes for the users) [START_REF] Estivill-Castro | Can on-line social network users trust that what they designated as confidential data remains so?[END_REF] to demonstrate that an existing technique [START_REF] Estivill-Castro | Empowering users of social networks to assess their privacy risks[END_REF] (that does not take the network link information into account) may not provide protection against an attack using the link information.

Data sets

We use the same data set D FB that was used in some previous studies [START_REF] Estivill-Castro | Empowering users of social networks to assess their privacy risks[END_REF][START_REF] Al-Saggaf | Privacy in social network sites (SNS): The threats from data mining[END_REF]. The data set D FB has 616 records where each record contains information of a female Facebook user who is either feeling lonely or connected as it is explicitly mentioned in their recent posts. Out of 616 records, 308 users are lonely, and 308 users are connected . As in the previous studies [START_REF] Estivill-Castro | Empowering users of social networks to assess their privacy risks[END_REF][START_REF] Al-Saggaf | Privacy in social network sites (SNS): The threats from data mining[END_REF], we also assume that the emotional status is confidential. A malicious data miner will try to learn this information of a user who has not revealed this information. Hence, emotional status is the class attribute while building a classifier to learn the patterns for discovering the emotional status of members of the social network. Thus, the structure of the data set D FB consists of 23 non-class attributes and the class attribute emotional status. Table 1 provides details of these attributes. If the friendship information is not available, then the attribute has null .

However, D FB does not have any information relating the social network links (i.e. friendship information). Therefore, we first simulate the connections among users to construct a data set D FB that contains information relating social network links. We set the probability of a link between two users inversely proportional to the Hamming distance between the two users. We set the record-torecord distance (or R2RD ∈ [0, 1]) between two users as the Hamming distance divided by 23 (the number of non-class attributes).

Users having similar attribute values (i.e. low Hamming distance) are likely to have common interests and thus are likely to have friendship links (social links) between them [START_REF] Fond | Randomization tests for distinguishing social influence and homophily effects[END_REF]. A link between two users will be a Bernoulli trial with probability p where we set p as a high probability of a friendship link when the R2RD is low. In particular, when the value of R2RD between two users is within the range of 0.0 and 0.2, then we set the link probability p linearly between 0.9 and 0.7. When R2RD is between 0.2 and 0.3, then the link probability p is linear between 0.7 and 0.5. Thus, for example, if the R2RD between two users is 0.3, then we draw a link between them with probability 1/2; that is, it is equally likely there is no connection. Fig. 1(a) provides the plot that determines the link probability p as a function of R2RD. In this model, even if the R2RD is large, between 0.6 and 1, there is still some probability that the users are linked as friends. Fig. 1(a) shows that 1258 friendship links were created among users whose R2RD is between 0.1 and 0.2. Fig. 1(b) shows a social network drawn in the way, where the dots represent the users and the links represent the friendship between the users.

Once the friendship links are simulated we can compute the m(u, a = v) for every user u and attribute-value pair a = v. Recall that the data set D FB has 23 non-class attributes and a class attribute. A user u is represented by a record r ∈ D FB that has 24 attribute values. For each attribute value of u we compute m(u, a = v). Thus, for each attribute-value pair, we create a new attribute containing m(u, a = v) for each user u. Let us call these newly created attributes "link attributes" and the original 23 attributes "regular attributes". Therefore, when we consider the link information, the expanded data set D FB has now altogether 24+24 = 48 attributes. That is, in the expanded data set D FB , we have 47 non-class attributes and a class attribute containing two possible values: lonely and connected .

We also utilize a synthetic data set as per those synthetic OSN data sets [START_REF] Nettleton | Generating synthetic online social network graph data and topologies. 3rd Workshop on Graph-based Technologies and Applications[END_REF]. This data set consists of 11 non-class attributes which are given in Table 2. The data contains 1000 records (489 male users and 511 female users) and 50,397 friendship links. These are also synthetically generated friendship links [START_REF] Nettleton | Generating synthetic online social network graph data and topologies. 3rd Workshop on Graph-based Technologies and Applications[END_REF]. We shall consider two version of this data set. In the first, we take political orientation as the confidential attribute of the data set and it is denoted by D Political . In the second one, now D Sexor we consider sexual orientation as the confidential attribute. Both of this will have 10 non-class attributes (but they exchange sexual orientation and political orientation as the class attribute).

After preparing D Political and D Sexor , we calculate SAN metric values for each attribute as we did for D FB . This results in expanded data sets D Political and D Sexor respectively with 11+11=22 attributes one of which is the confidential class attribute.

Empirical Demonstration

We now empirically demonstrate the impact of considering social links on individual's privacy. For a data set D, in our experiments, we split the users in 10 disjoint groups: {D 1 , D 2 , D 3 , . . . , D 10 }. For example, for D FB |D i FB | = 61 for i = 1, . . . , 9 and |D 10 FB | = 67. For the i-th iteration the users in D i are considered those users who wish to keep their confidential attribute unpredictable from the adversary M , while the adversary has the data of the other users ∪ 10 j=1 D j \ D i who have revealed such confidential attribute.

For each user U in D i , we use PrivAdv repeatedly to identify the sensitive rules R u . In each iteration, the primary attribute obtained from R u is suppressed until R u = ∅. At this stage, PrivAdv considers U 's privacy protected. Different users in D i have different attribute-value pairs suppressed.

How, we complement the columns of ∪ 10 j=1 D j \ D i and D i with the link information, essentially considering D instead of D. We impersonate the adversary M who builds a forest from ∪ 10 j=1 D j \D i . That is, we assume the adversary uses the SAN metric and thus obtains a new set of sensitive rules R u for each user U in D i (the users in D i and D i are the same, D i has the SAN link information as the metric m(u, a = v) as per Equation ( 1)).

The assumed strategy of the adversary for each D i is a decision-tree forest SysFor [START_REF] Islam | Knowledge discovery through SysFor: A systematically developed forest of multiple decision trees[END_REF] with the aim of building a forest of 10 trees. Throughout the experiments, we use the standard set of parameters of SysFor. SysFor sometimes cannot build 10 trees as requested due to various reasons such as not having enough good attributes. Nevertheless, SysFor always builds at least 8 trees and 40 rules for D FB data set (refer to Table 3). The sensitive rules (SR) obtained by the adversary's strategy are of 3 types, SRR tests only regular attributes, SRRL tests both link attributes and regular attributes, SRL are sensitive rules made of only the link attributes.

Table 3 contrasts the types of sensitive rules that are obtained from the link attributes from D FB versus those that do not. Those users in D i FB who have at least one sensitive rule ∈ R u FB for which no regular attribute value is suppressed by PrivAdv are at risk, and we found that the adversary always found at least 20 of these rules. That is, there are plenty of sensitive rules for which all values tested in the antecedent are link attributes (i.e. the attributes that contain m(u, a = v) values). Note again that these values are not suppressed 3 that on an average there are 25.9 SRLs out of 38.9 SRs. This indicates that most of the sensitive rules obtained from D FB are not taken care of by PrivAdv. This should not be surprising, the vast majority of information derived in recommender systems and on-line social networks where information is represented as graph models like the SAN derives from the link information.

On the other hand, SysFor generates 9 trees in each component D i for both D Political and D Sexor data sets. The average number of SRRL is comparatively higher than SRL and SRR in each component of D Political . Out of 50 SR (i.e., sensitive rules), on average, the number of SRRL is 41.6 where SRL (i.e., sensitive rules with link attributes only) is approximately 0 in our experiments. In D Sexor data set, on average, 180 SR are generated in each part D i and among these 176.4 are SRRL. Only 3.7 (on average) sensitive rules are SRL (i.e., containing both regular and link attributes).

The limitation of PrivAdv is further defined by the confidential attributevalue pair is revealed by rules in SRL or SRRL. If a user in D i has a sensitive rule in SRL or SRRL (PrivAdv does not suppress any of the attributes in the antecedent of the rule), then the user's information is considered to be insecure, otherwise the user's information is considered to be secure.

In our experiments, we found that among 62 users in each cross fold of D FB data set, 35 of them (56.62%) have protected information. However, 27 (43.38%) out of 62 users having insecure information. In case of D Political and D Sexor data sets, out of all 10 parts D i , on an average 41.7% and 70.5% users, respectively, are having insecure information after PrivAdv has been applied. For these insecure users, the attributes suppressed by PrivAdv are insufficient to protect their privacy when an adversary uses a data set with link attributes.

Our Technique

Our technique 3LP secures the confidential attribute-value pairs of users even when link attributes (obtained from social links) are taken into consideration. Our technique suggests three layers of protection: Layer 1 suggests to suppress necessary attribute values (and is equivalent to PrivAdv: Step 1 and 2 in Algorithm 1), Layer 2 suggests to hide some friendship information and Layer 3 suggests to add new friends.

Step 1 Compute Sensitivity of Each Attribute for a User. In Step 1, we invoke the function GetSensitiveRules() to create the set of sensitive rules R s . The set R s is generic, but the function GetSensRulesForUser() uses the attribute values of a particular user U and returns the set R u of sensitive rules for U . The set A r/s u of sensitive attributes is the union of all regular attributes in the antecedents of the rules in R u . The TOTAL COUNT [START_REF] Estivill-Castro | Empowering users of social networks to assess their privacy risks[END_REF] counts how many times each regular attribute A i appears in the antecedents of set R u .

Step 2 Suppress Attribute Values as Necessary (Layer 1). 3LP identifies the regular attribute A n with the highest number of appearances in the set R u and suggests user U shall suppress the value of attribute A n . As in TOTAL COUNT [START_REF] Estivill-Castro | Empowering users of social networks to assess their privacy risks[END_REF], our first layer only suggests the suppression and leaves the decision up to the user. Either way, the attribute A n is removed from the set A s u of sensitive attributes. If user U suppresses attribute A n , then all sensitive rules in R u that have A n in their antecedent are no longer applicable. In this case, those sensitive rules are no longer in R u . The treatment is repeated with the next regular attribute with the highest number of appearances in the set R u until R u is empty (in which case the algorithm terminates) or the set A r/s u of regular attributes in R u is empty (in which case the algorithm continues with Step 3. We remark here that in the experiments of this study we assume that a user follows all the suggestions.

Step 3 Hide Friendship Links as Necessary (Layer 2). If there are still some sensitive rules R u j ∈ R u , such rules must use only link attributes. We explore if there is any link attribute m(u, A n = v) whose value can be reduced by deleting or hiding some friendship links in order to reduce the number of sensitive rules in R u . Unlike the regular attributes, the link attributes cannot be suppressed easily. Moreover, as discussed when Equation (1) was introduced, in many cases m(u, A n = v) derives from the social links of the user and not the explicit links the user has control. However, we can offer to the user to carefully change the social links (by deleting/hiding some friendships) and thus alter the values of the link attributes m(u, A n = v). For example, if we hide the friendship link of the user U with a friend who also shares the same attribute-value pair A n = v, then we can decrease the link attribute value m(u, A n = v). Moreover, we can see from Equation (1) that if we hide the friendship link of the friend t who has the smallest Γ + (t) = Γ s+ (t) ∪ Γ a+ (t), then we can maximise the reduction of m(u, A n = v).

In Step 3, we first find the most sensitive link attribute m(u, A n = v) for the user U . We then check if the value of m(u, A n = v) is higher than the split point in a sensitive rule R u j , where one of the tests in the antecedent of R u j is A n ≥ split point. If it is, then we suggest user U shall hide the friendship link with a friend who has the smallest Γ + (t) = Γ s+ (t) ∪ Γ a+ (t) in order to reduce the m(u, A n = v) value the most. If the user accepts the recommendation, we recompute m(u, A n = v). The goal here is to reduce the value of m(u, A n = v) below the split point so rule R u j is no longer applicable to U . We continue the process of hiding friends until we get the a value of m(u, A n = v) lower than the split point in R u j . We then remove R u j and any other rules no longer applicable to user U from R u and repeat the process for another sensitive rule R u j that tests m(u, A n = v) ≥ some split point in it antecedent. At the end of Step 3, if we still have some rules R u j ∈ R u then we move to Step 4 (Layer 3).

Step 4 Add New Friends as Necessary (Layer 3). We again find the most sensitive link attribute m(u, A n = v) for the user. We check if there is any sensitive rule R u j ∈ R u that has an antecedent of the from m(u, A n = v) ≤ some split point. If there is such R u j , then we aim to add friends and thus increase the value of m(u, A n = v) so that it eventually becomes greater than the split point and thus R u j is no loner applicable to U . Our algorithm 3LP suggests the adding approach to the user U and the user shall make the decision whether to add the friend or not. Our 3LP retrieves the possible friend t with the smallest Γ + (t) = Γ s+ (t) ∪ Γ a+ (t), and recommends to add a friendship link to t. This maximises the increase of the value of m(u, A n = v) and minimises the number of friendship links to be added.

Experimental Results and Discussion

We now present experimental results that validate our algorithm 3LP. We apply 3LP on the expanded data sets named D FB , D Political and D Sexor separately. We again partition the data sets into 10 disjoint parts, using one part as the potential victims and 90% of the dataset as the data available for inferring confidential attributes. Table 4 shows experimental results for D FB .

Earlier we saw that PrivAdv [START_REF] Estivill-Castro | Empowering users of social networks to assess their privacy risks[END_REF] could secure the confidential attributes of only 56.62% users from the attribute inference attack that uses link information on the D FB dataset. However, using algorithm 3LP the remaining 43.38% users are protected. Later 1 is essentially PrivAdv, none of the information of the users at risk is secured further. Typically, for a group of 61 users, 27 users are still at risk after Layer 1. But, on average, 5 of them can prevent a breach of privacy by hiding friends. In percentage terms, users whose confidential attribute is secure increases to 64.52% after Layer 2, with a 7.9% increment with respect to Layer 1. Although hiding a particular friend from user profile is currently unavailable on Facebook these results suggest that the operators of OSN such as Facebook may consider adding this option to a user profile. That is, enable users to select the automatic masking of some friendships to any data analyst so their confidential attribute (already not present) can not be inferred.

Moreover, to secure the data of the remaining users, our experimental results show that on an average 22 users need to add more friends to prevent a breach of privacy. (i.e., Layer 3 of 3LP). Of the users who are not protected by previous approaches (Layer 1), equivalently 83.84% (22 out of 27) need to do it by adding friends. While choosing the friend during addition, lower degree friends carry more impact on the metric function values.

Although adding more friends may seem unrealistic in OSNs settings, and other risks may derive from linking with strangers, we believe the operators of OSNs would be able to perform this. Certainly ensuring the privacy of their users is in the operators' best interest, Thus, our results here suggest that operators can suggest to users the addition of some synthetic friends. Alternatively, they could use such technique to sanitise the data before releasing it to data analysts. We plan to focus on this in our future work. On the other hand, in Table 5 we present respectively the experimental results with D Political and D Sexor . The average results show that, for a group of 100 users, about 23 and 3 (after rounding) users are still insecure after applying the first layer of 3LP on D Political and D Sexor data sets respectively.

In order to secure these users we then apply Layer 2 of 3LP (i.e., obfuscate friends from friend lists) and we notice that no more users are at risk (after applying Layer 2 of 3LP) in both D Political and D Sexor data sets. Hence Layer 3 of 3LP is not required in our experiments for both of these data sets. The Column 2 of Table 6 shows the number of attributes needed suppression in Layer 1 of 3LP. Please note that these are the suppressions made in addition to the suppressions suggested by the regular PrivAdv. The average number of attribute suppression (Layer 1 of 3LP), on the other hand, is higher both in D Political and D Sexor compared to D FB . The reason may be the number of generated SRR (i.e., sensitive rules with regular attributes) is much lower for D FB .

Our results also show that the burden of additions and obfuscations of friends is not that large. For example, in D FB data set, we need to hide/add at most 1-2 friends, on average, in each partition D i to secure the confidential attribute (refer to Table 6). In case of the data sets D Political and D Sexor , we need to hide 3-4 friends, on average, in each partition whereas, Layer 3 is not required in our experiments (refer to Table 7).

Conclusion

We proposed 3LP, a privacy-preserving technique in order to protect the privacy of Facebook users from attribute inference risks. Previous works did not consider friendship network information which may create vulnerability to users' privacy. Our technique provides suggestions, to a user to suppress necessary attribute values and fabricate friendship links, in order to protect sensitive attribute values of the user. The technique can also enable a social network provider to query a user whether to fabricate such links to preserve his/her privacy. Our experimental results show that by hiding or adding a few friends in a user's profile can protect the user's sensitive information from being inferred. Though hiding a particular friend from the user's profile is currently unavailable on Facebook, the approach here suggests that such feature could be added in order to protect users' privacy.

Fig. 1 .

 1 Fig. 1. The friendship links simulation

Table 1 .

 1 Attributes of Facebook data set DFB .

	Attribute name	Attribute values
	Gender	female; all 616 users are female aged over 18 years
	Profile image	contains 12 categories represented by 1 to 12, as follows, image shows
		the user: 1-alone, 2-with one or more friends, 3-at a special occasion,
		4-with their special partner, 5-smiling, 6-in a unique location not in
		their hometown, 7-shows only face/head, 8-playing or watching sport,
		9-with family, 10-depicts an object with apparent meaning to the user,
		11-having a unique visual effect, 12-Reveals too much skin
	Relationship status	contains 11 categories: 1 to 10 and null, as follows. 1-single, 2-in a re-
		lationship, 3-engaged, 4-married, 5-it's complicated, 6-in an open rela-
		tionship, 7-widowed, 8-separated, 9-divorced, 10-in a civil union, null
	Interested in	null, men,women,both
	Family on FB	absent, present
	Hometown	absent, present
	Show sex	no, yes
	High school	absent, present
	Year-graduated from	absent, present
	high school
	University or college	absent, present
	Year graduated from	absent, present
	university or college
	Timeline	absent, present
	Work	absent, present
	Friend	high, medium, low, null
	Album	high, medium, low, null
	Photo	high, medium, low, null
	Language	english, english+, other, other+, null
	Religion	absent, present
	Activities	absent, present
	Email	absent, present
	Date of birth (DOB)	1-full dob is revealed, 2-only day and month are revealed, 3-dob is not
	Political view	revealed absent, present
	People who inspire	absent, present
	Class attribute	connected, lonely

Table 2 .

 2 Attributes of Synthetic Dataset.

	Attribute name Attribute values
	Age	contains 7 categories: 18-25, 26-35, 36-45, 46-55, 56-65, 66-75, 76-85
	Gender	male, female
	Residence	contains 5 categories: palo alto, santa barbara, san jose, boston, winthrop
	Religion	contains 7 categories: christian, hindu, jewish, muslim, sikh, other reli-
		gions, no religious affiliation
	Marital status	contains 4 categories: single, married, divorced, widowed
	Profession	contains 7 categories: image shows the user: manager, professional, ser-
		vice, sales and office, student, natural resources construction and main-
		tenance, production transportation and material moving
	Political orientation	contains 7 categories: absent sexual information, bisexual, heterosexual,
	Political orientation	homosexual contains 7 categories: far left, left, centre left,centre, centre right, right,
		far right
	Like 1	contains 5 categories: entertainment, music artist, drink brand, soccer
		club, tv show
	Like 2	contains 5 categories: entertainment, music artist, drink brand, soccer
		club, tv show
	Like 3	contains 5 categories: entertainment, music artist, drink brand, soccer
		club, tv show
	Class attribute	political orientation or sexual orientation (any one at a time)

Table 3 .

 3 Analysis of sensitive rules with and without social link information by PrivAdv since PrivAdv only uses regular attributes from D FB [1]. Users are not properly secured by PrivAdv with respect to the social link information. For instance, consider D 1 FB , any records satisfying any of the 23 SRLs for D 1 FB are not secured by PrivAdv. We can see from Table

	Run	Trees Rules SR SRR SRRL SRL
	1	9	40	31	1	7	23
	2	8	71	41	1	8	32
	3	8	50	33	0	9	24
	4	8	69	42	3	6	23
	5	8	83	43	3	20	20
	6	8	81	44	3	13	28
	7	9	60	41	3	8	30
	8	8	49	35	1	13	21
	9	8	61	42	3	13	26
	10	8	48	37	0	5	32
	Average 8.2 61.2 38.9 1.8 10.2 25.9

Table 4 .

 4 Number of insecure users after applying 3LP on expanded dataset D FB .

	Number of insecure users

Table 5 .

 5 Number of insecure users after applying 3LP on the expanded dataset D Political and D Sexor .

	D Political			Number of insecure users
	Run	Number of users in Di	After using PrivAdv	After using Layer 1 of 3LP	After Layer 1 Layer 2 of 3LP using and	After using Layer 1, Layer 2 and Layer 3 of 3LP
	1	100	17	0	X	X
	2	100	15	0	X	X
	3	100	12	0	X	X
	4	100	100	99	0	X
	5	100	20	0	X	X
	6	100	35	0	X	X
	7	100	29	0	X	X
	8	100	97	95	0	X
	9	100	53	39	0	X
	10	100	39	0	X	X
	Average	100	41.7	23.3	0	X
	D Sexor			Number of insecure users
	Run	Number of users in Di	After using PrivAdv	After using Layer 1 of 3LP	After Layer 1 Layer 2 of 3LP using and	After using Layer 1, Layer 2 and Layer 3 of 3LP
	1	100	69	1	0	X
	2	100	69	0	X	X
	3	100	67	0	X	X
	4	100	75	7	0	X
	5	100	86	15	0	X
	6	100	77	0	X	X
	7	100	60	0	X	X
	8	100	74	0	0	X
	9	100	63	5	0	X
	10	100	65	0	X	X
	Average	100	70.5	2.8	0	X

Table 6 .

 6 Required number of attribute Suppression, Friend Deletion or Addition for each insecure user suggested by 3LP in expanded data set D FB .

	Run	Average Num-ber of attribute suppression (per user) in Layer 1 of 3LP	Average ber of friends num-needed to be hidden (per user) in Layer 2 of 3LP	Average ber of friends num-needed to be added (per user) in Layer 3 of 3LP
	1	0	1	2
	2	0	1	1
	3	0	1	1
	4	0	0	1
	5	1	2	2
	6	0	1	2
	7	1	1	1
	8	0	0	1
	9	1	1	2
	10	0	1	2
	Average	0	1	2

Table 7 .

 7 Required number of attribute Suppression, Friend Deletion or Addition for each insecure user suggested by 3LP in expanded data sets D Political and D Sexor .

	D Political Run	Average Num-ber of attribute suppression (per user) in Layer 1 of 3LP	Average ber of friends num-needed to be hidden (per user) in Layer 2 of 3LP	Average ber of friends num-needed to be added (per user) in Layer 3 of 3LP
	1	1	X	X
	2	1	X	X
	3	1	X	X
	4	1	10	X
	5	1	X	X
	6	1	X	X
	7	1	X	X
	8	1	6	X
	9	1	11	X
	10	2	X	X
	Average	1.1	2.7	X
	D Sexor Run	Average Num-ber of attribute suppression (per user) in Layer 1 of 3LP	Average ber of friends num-needed to be hidden (per user) in Layer 2 of 3LP	Average ber of friends num-needed to be added (per user) in Layer 3 of 3LP
	1	2	11	X
	2	2	X	X
	3	2	X	X
	4	1	9	X
	5	2	7	X
	6	1	X	X
	7	1	X	X
	8	3	X	X
	9	1	14	X
	10	2	X	X
	Average	2	4.1	X

Algorithm 1 3LP()

Input

: User U , attribute C that U considers confidential is the class attribute, dataset D having N records, A is the set of non-class attributes where A r ⊂ A is the set of regular attributes and A l ⊂ A is the set of link attributes, C denotes the class attribute C and G the graph information.

Output

: Recommendations for U to act on some attributes in A. Variables : An=the n th attribute R s = set of sensitive rules

Step 1: Compute Sensitivity of Each Attribute for a User R s ← GetSensitiveRules(D, C) R u ← GetSensRulesForUser(R s , U ) Counteri ← 0; ∀Counteri ∈ Counter /*Counteri shall total the number of appearances of Ai ∈ A r in the set of sensitive rules*/;

Step 4: Add New Friends as Necessary for the User

In this paper, we have considered that only the user or few others in user's network are consumers of 3LP. If all friends in a user's friend list continuously use and adopt the recommendations of 3LP, then the calculation will be dynamic and different. We believe this is an exciting avenue for further research.


Md Morshedul Islam Somayeh Taheri

Reihaneh Safavi-Naini

Privacy-enhanced Profile-based Authentication using Sparse Random Projection

Keywords: Profile privacy, Random projection, Profile, Biometrics

In a profile-based authentication system, a user profile is stored at the verifier and later used to verify their authentication claim. A profile includes user-specific information that is privacy sensitive. In this paper we propose a non-cryptographic approach to providing privacy for user profile data in profile-based authentication systems, using an efficient construction of random projection: a linear dimension reducing transform that projects the profile and the verification data to a lower dimension space, while preserving relative distances of the vectors and so correctness of authentication. We define privacy measures for two types of profiles: a single vector profile and a multivector profile, derive theoretical bounds on the privacy and correctness of privacy enhanced systems, and verify the results experimentally on two profile-based authentication systems: a face-biometric system and a behavioural based authentication system. We discuss our results and propose directions for future research.

Introduction

Traditional entity authentication systems that rely on secrets (e.g. passwords, secret keys), or hardware tokens, are vulnerable to credential theft and credential sharing. This latter vulnerability not only allows users to share their credentials with others to bypass security of subscription services (e.g. online games), but also has been used for delegation (subcontracting) of work to others [START_REF]US employee 'outsourced job to china[END_REF] resulting in the breach of the company security policy. In a profile-based authentication system, a user's authentication claim is compared with their stored profile that is constructed during a trusted registration process. A profile is one or more vectors of feature values, each sampling a feature that captures some user-specific property. The profile data is stored at the verifier and is used to accept or reject an authentication claim of a user that presents their verification data. The verifier uses a matching algorithm that compares the verification data with the stored profile and decides to accept, or reject, the claim. A traditional biometric system [START_REF] Maltoni | Handbook of fingerprint recognition[END_REF][START_REF] Jain | Handbook of face recognition[END_REF] is a profile-based authentication system where the profile data and verification data are each a single vector, and matching is by measuring the distance between the two. A more recent type of profile-based authentication system, sometimes referred to as implicit authentication system (IA) [START_REF] Shi | Implicit authentication through learning user behavior[END_REF], uses a user profile that is a vector of random variables whose distribution is specific to the user. A feature is stored as a set of samples that represent the distribution of the feature, and the verification (matching) algorithm compares the distribution of the verification data (represented by a second sample set) with the profile data to determine if they are from the same distribution.

Privacy. Profile data carry sensitive personal information that must be protected from the verifier. Ideally the verifier should only be able to use the profile data for the verification decision. In practice however profiles can be used to learn about users' behaviour and interests for marketing and advertising, or track them across websites. Biometric profiles are uniquely identifying, and are of extreme sensitivity from privacy view point. Behavioural profiles also reveal user private information such as their health conditions, physical abilities or user skills and behaviour, as well as pattern of usage of applications and devices. Richer profiles (i.e. more behaviour data) lead to higher accuracy in authentication and this provides incentive to employ more user data, and "to keep it around for a longer period of time" [START_REF] Bonneau | Privacy concerns of implicit secondary factors for web authentication[END_REF].

An immediate solution to protecting privacy of profile data against the verifier is to store them in encrypted form and design the verification algorithm as a computation in encrypted domain, or use a secure two party computation protocol. These approaches in their general form [START_REF] Lindell | Secure multiparty computation for privacy-preserving data mining[END_REF] are computationally expensive and are primarily of theoretical interest. One can tailor more efficient secure computation systems for computationally simple verification algorithms, such as finding linear sums [START_REF] Safa | Privacy-preserving implicit authentication[END_REF], but this cannot be easily extended to more general matching algorithms such as KS-test used in this paper (See Section 2). In [START_REF] Wang | An analysis of random projection for changeable and privacy-preserving biometric verification[END_REF] random projection of profile data was proposed to provide profile privacy for biometric data. Authors showed that, using a random transformation matrix whose elements are generated using a Gaussian distribution, one can project profile vectors to a lower dimension space, such that the correctness of the verification algorithm is maintained. Authors also showed that the approach allows changeability of the profile, which is a desirable security property. Our work builds on this result and strengthens and extends in a number of ways.

Our Work. The setting. We consider a profile-based authentication system with an honest-but-curious verifier who follows the protocol but would like to glean information about users from their stored data. We define correctness and security of the authentications system using Success Rate (SR), False Acceptance Rate (FAR) and False Rejection Rate (FRR) (See Definition 1).

To provide profile privacy, a trusted registration authority (RA) performs user registration during which the following two things happen: (i) after checking the user's credentials, the RA generates a random matrix R [u] that will be stored on the user's device, and (ii) use the user's device (with the embedded transform) to generate their transformed profile R [u] X [u] , where X [u] is the original user profile. (Note that the user profile stays private to the RA also.) The user identifier and the transformed profile, (u, R [u] X [u] ), will be securely sent to the verifier. (The system can be designed such that the transform be generated by the device, and remain unknown to the RA.) In a user authentication session, verification data is generated by the device, transformed using the embedded transform, and sent to the verifier. For efficient computation we use discrete random matrices whose elements are generated according to equation (1) (Section 2).

Privacy model and theoretical results. We consider two cases: single-vector profiles, and multivector profiles. For single-vector profiles the adversary, denoted by A F V adversary, wants to find the original Feature Values. Our notion of privacy in this case is in terms of the expected mean and variance of the adversary' error in finding these values (See Definition 3, item (1)). For multivector profiles, the Feature Distribution adversary denoted by A F D adversary, wants to learn the distribution of the feature. Definition 3, item (2) introduces the notion of π-Distribution-Privacy, where π is the fraction of features (in the feature vector) that remain "close" to their original distributions, given the adversary's knowledge. We consider two types of adversary knowledge: (i) the adversary knows the distribution of random matrices, but does not know the random matrix R [u] that is assigned to the user, and (ii) the adversary knows R [u] . This latter case corresponds to the extreme case that the user device has been compromised and R [u] has been leaked. These two types of knowledge are shown by subscripts D and R, respectively. Thus we have A F V D , A F V R , A F D D , and A F D R adversaries, where the superscripts show the goal, and the subscripts show the knowledge type.

Single vector profiles. Proposition 1 gives the mean and variance of error for the best (least expected error) A F V adversary strategy for finding the profile vector. Theorem 2 uses this result to quantify the privacy level of the system against this adversary. When the projection matrix R [u] is known to the adversary, Proposition 1, item (ii), gives the expected mean and variance of error, and Theorem 2, item(ii), shows the privacy level against a A F V R adversary. Multivector profiles. Using the best estimation strategy on each profile vector we obtain an estimate of the multivector profile, that is compared with the original one, and closeness of each estimated feature with the original one is determined. To quantify closeness of an estimated feature distribution to its original distribution, we use KS-test [START_REF] Massey | The kolmogorov-smirnov test for goodness of fit[END_REF] for two one-dimensional probability distributions. Proposition 1, items (i) and (ii), show that the variance of the estimated values is high and so the original feature distribution cannot be recovered. In our experiments we will experimentally find the π values of the adversaries A F D D and A F D R .

We use the set of matrices that are generated using a discrete distribution. The correctness of authentication system in this case is shown in Section 3. Using a discrete distribution reduces the computation of profile transform to addition and subtraction only and so becomes very efficient (no multiplication).

Experimental results. To evaluate the above framework we considered the following profile-based authentication system. Our profile-based authentication systems. For single-vector profiles we designed a simple face recognition algorithm with a matching algorithm that for verification uses k-Nearest-Neighbors (kNN) algorithm [START_REF] Altman | An introduction to kernel and nearest-neighbor nonparametric regression[END_REF], with k=1 (verification uses the closest profile in the profile database to the presented verification vector). This profile-based authentication was evaluated using the face-biometric data that was downloaded from AT&T Laboratories [START_REF]An archive of AT&T laboratories cambridge[END_REF], and shown to have comparable performance to face-biometric system in [START_REF] Samaria | Parameterisation of a stochastic model for human face identification[END_REF].

For multivector system we used a profile-based behavioural biometric system called Draw a Circle (DAC) [START_REF] Islam | POSTER: A behavioural authentication system for mobile users[END_REF]. This is a challenge-response authentication system in which profile data and verification data consist of 30 and 20 profile vectors, respectively. The verification algorithm, for each feature, matches the distribution of the feature samples in the verification data against the corresponding distribution of feature samples in the profile data using Kolmogorov Smirnov-test (KS-test) [START_REF] Massey | The kolmogorov-smirnov test for goodness of fit[END_REF], and then combines the results, using the meta-data analyzer VoteP [START_REF] Cooper | The handbook of research synthesis and meta-analysis[END_REF], into a final accept, reject decision. More details about DAC is in Section 4. The success rate of the above systems, before using random projection, are 94.16% and 94.40%, respectively.

Profile projection. We assign a m × k random matrix R [u] that is generated using the distribution, described by equation (1), to each user. For correctness, our experimental results show that after projection, the FRR and FAR of both systems improve: in the case of face-biometric system, FRR and FAR both become close to 0.0, while for DAC, they are slightly lower than their original values. This is due to the combination of the distance preserving property of RP, and the fact that each user has an individual matrix. For privacy evaluation we use the same matrices and k values. For A F V D and A F V R adversaries in the facebiometric system, our results show that for higher k values, although the mean of estimated error becomes smaller, but as expected, because of large variance, the estimated value will be different from the original value. For DAC we used A F D D and A F D R adversaries that aim at feature distributions. We measured the similarity between the original and estimated profile and showed that feature distributions were not be preserved and this was even true for A F D R when the projection matrix is known. Details of experiments are given in Section 4.

Profile changeability. This property ensures that by changing user matrix, one can effectively refresh the stored (projected) profile. Although this is not the focus of this work, we report our experiment in Section 4.3. that shows perfect ability to refresh the profile. The rest of the paper is organized as follows. Section 2 provides the background. Section 3 describes our setting, privacy attacks and measures for quantifying privacy, and provides privacy analysis for different attack scenarios, and Section 4 gives the experimental results. Section 5 summarizes related works, and Section 6 concludes the paper.

Preliminaries

A metric space M m is a set of points equipped with a non-negative distance function d : M m × M m → R that satisfy, non-negativity, symmetry and triangular properties. We consider elements of M m to be vectors of length m with components in R, i.e. M m ⊂ R m . For two vectors X, Y ∈ M m , where

X = {X 1 , X 2 , ..., X m } and Y = {Y 1 , Y 2 , ..., Y m }, we consider the Euclidean distance d(X, Y) = m i=1 (X i -Y i ) 2 .
For two subsets A and B of M m , we consider each set as samples of an underlying distribution, and use the distance between the two underlying distributions using Kolmogorov-Smirnov (KS) test in [START_REF] Massey | The kolmogorov-smirnov test for goodness of fit[END_REF], as the distance D(A, B) between the two subsets . Two-sample Kolmogorov-Smirnov (KS) test [START_REF] Massey | The kolmogorov-smirnov test for goodness of fit[END_REF] is a non-parametric hypothesis testing method for equality of two distributions, each represented by a set of points. For two sample sets of size n and n , the test measures D, the maximum distance between two cumulative empirical distribution functions, and rejects the null hypothesis at level α if D > c(α) (n + n )/(nn ). The test outputs a P-value which is the confidence level of the test.

VoteP method [START_REF] Cooper | The handbook of research synthesis and meta-analysis[END_REF] is a method of combining the results of multiple KStests, and obtain the combined P-value. We use this method to combine the result of feature similarity tests to obtain the verification decision. The method finds the number of P-values that are above a given threshold, and accepts the hypothesis if the fraction of these P-values (over all P-values) is above some specific threshold. Performance Measures. Let fa, tr, fr and ta denote the number of false acceptance, true rejection, false rejection and true acceptance instances of an experiment (e.g. verification of claims). False Acceptance Rate (FAR), False Rejection Rate (FRR) and the Success Rate (SR) are defined as follows:

F AR = f a/(f a+tr), F RR = f r/(f r+ta), SR = (ta+tr)/(ta+f r+tr+f a).
Random projection(RP) is a dimension reduction transformation that uses random matrices to project a vector X ∈ R m , to a vector X = 1 √ kσr RX, X ∈ R k , using a random matrix R k×m , k < m, where σ r is the standard deviation of entries of R [u] . The important property of this transformation is that it preserves pair-wise Euclidean distances between the points in the metric space R m , up to an error that can be estimated for the dimension reduction parameter. Existence of distance-preserving dimension reduction transformations follows from the following Lemma. Johnson-Lindenstrauss(JL) Lemma [START_REF] Dasgupta | An elementary proof of a theorem of johnson and lindenstrauss[END_REF]. Let ∈ (0, 1) and M m ⊂ R m be a set of n vectors and k = 4ln(n) 2 /2-3 /3 . There exists a Lipshcitz mapping f : R m → R k such that for all u, v ∈ M m :

(1 -)d 2 (u, v) ≤ d 2 (f (u), f (v)) ≤ (1 + )d 2 (u, v)
For a given projected dimension k, to satisfy the above inequality for a small (i.e. to preserve distances up to ), one needs to have a sufficiently small n (sparse set). In profile-based authentication systems, sparseness of the profile vector space is a requirement for the correctness of the system (otherwise matching verification data against the profile will have high error) and so the required condition is satisfied.

The proof of JL Lemma constructs the RP transform using matrices whose entries are sampled from a Gaussian distribution [START_REF] Dasgupta | An elementary proof of a theorem of johnson and lindenstrauss[END_REF]. It has been shown ex-perimentally (e.g. in [START_REF] Bingham | Random projection in dimensionality reduction: applications to image and text data[END_REF]) that the result also holds if R is generated by a zero mean and unit variance distribution. In [START_REF] Achlioptas | Database-friendly random projections: Johnson-lindenstrauss with binary coins[END_REF], it is proved that the property will hold if the matrix entries are sampled individually and independently, from the following three-valued distribution,

Pr(x = +1) = 1 2s , Pr(x = 0) = 1 - 1 s , Pr(x = -1) = 1 2s , (1)
Theorem 1. ( [17]) Suppose M m ⊂ R m be a set of n vectors projected onto R k using the transform f : R m → R k defined as f (u) = 1 √ kσr Ru for u ∈ M m ,
where R is a k ×m matrix generated using the distribution given in equation ( 1) and σ r is the standard deviation of entries of R. Given , β > 0 let k 0 = 4+2β 2 /2-3 /3 log(n). If k ≥ k 0 then with probability at least 1 -n -β for all u, v ∈ M m we will have:

(1 -)d 2 (u, v) ≤ d 2 (f (u), f (v)) ≤ (1 + )d 2 (u, v)
We use s = 3 that results in many zeros in the matrix and speeds up the computation (only 1 3 of the data are actually processed) and called it sparse random projection.

Minimum-norm solution. Let X = RX, where X ∈ R m and R ∈ R k×m and k < m. This system of linear equations has m -k degrees of freedom. Among all solutions of the system, the solution X = R T (RR T ) -1 X , known as the minimum-norm solution, minimizes the Euclidean norm of the solution X = m t=1

X2

i [START_REF] Demmel | Improved error bounds for underdetermined system solvers[END_REF]. In [START_REF] Liu | Random projection-based multiplicative data perturbation for privacy preserving distributed data mining[END_REF] the following result is proven about this solution. For a fixed X ∈ R m , let pairs (X j , R j ), 1 ≤ j ≤ be given, where R j ∈ R k×m entries are generated using a Gaussian distribution with zero mean and X j = R j X. Let Xj denote the minimum-norm solution of the linear system X j = R j X. Then, the mean of the estimation error of X will be zero. This suggests that, given the projected value X of a vector X, the minimum-norm solution of the system of linear equation that can be written for the projected profile, provides a good estimation of X.

Privacy-preserving profile-based authentication systems

A profile-based authentication system consists of three types of entities: (i) a group of users U that must be authenticated; (ii) a trusted registration authority (RA) that interacts with a user u and generates a profile X [u] for them; and (iii) a verifier V that interacts with a user, and using the profile and the presented verification data decides if the user's claim is valid or not. The set of user profiles is stored in a profile database DB at the verifier. There are two types of profilebased systems, depending on the nature of profile data (and verification data).

(i) The profile of user u, X [u] , is a single vector X [u] ∈ M m , and can be represented as a 1 × m vector with elements from R. Biometric systems can generate such profiles (e.g. fingerprint data). In practice one may use multiple instances of the profile vector to achieve better accuracy in verification.

(ii) The profile of user u, X [u] , is a set of n profile vectors

X [u] j ∈ M m (for 1 ≤ j ≤ n) where each X [u] j consists of m feature values , i.e. X [u] j = {X [u] j1 , X [u] j2 , ..., X [u] jm }.
We refer to these vectors as feature vectors. A profile thus can be represented as an n × m matrix with elements from R. Behavioural authentication data (e.g. keystroke, mouse dynamics etc.) generate this kind of profile.

Note that in (i), the actual feature values provide information about the user, while in (ii), the distribution of a feature that is captured by a set of sample points, provide identifying information.

3.1 Correctness and Security. Correctness and security of profile-based authentication system is define by two parameters -FRR, and δ-FAR. Definition 1. ( , δ)-security: A profile-based authentication system provides ( , δ)-security if it satisfies the following: For the claimed identity u and the verification data Y [v] , the matching algorithm outputs M (X [u] , Y [v] ) = 0 (reject) with probability at most , if u = v, and outputs M (X [u] , Y [v] ) = 1 (accept) with probability at most δ, when

u = v. P r[M (X [u] , Y [v] ) = 0 | u = v] ≤ ; P r[M (X [u] , Y [v] ) = 1 | u = v] ≤ δ;
Changeability of a profile-based authentication captures the ability to refresh a user profile while maintaining correctness and security.

Definition 2. ζ-changeability:

A privacy-preserving profile-based authentication system provides ζ-changeability if it satisfies the following: For transformed profile X

[u] = R u X [u] and the verification data

Y [v] = R v X [u] ,
the matching algorithm outputs M (X [u] , Y

[v] ) = 1(accept) with probability at most ζ, if R u = R v . P r[M (R u X [u] , R v X [u] ) = 1 | R u = R v ] ≤ ζ.

Privacy Model.

Privacy transform must not be significantly adversely affect the correctness of authentication, and must protect the profile data. Correctness after applying privacy transform. Let a profile X [u] be mapped to X [u] , and the verification date Y [v] be mapped to Y [u] . To preserve correctness of authentication, ideally we must have, M (X

[u] , Y [u] ) = 1, if M (X [u] , Y [v] ) = 1, and M (X [u] , Y [u] ) = 0, if M (X [u] , Y [v]
) = 0 where M () and M () are the matching algorithm used before applying the transform and the one used in the projected space. Privacy Attacks. We define four types of adversaries A G K that are distinguished by their (i) attack goal (G), and their (ii) prior knowledge (K). The goal G∈ {F V, F D} where F V denotes Feature Value and F D denotes Feature Distribution. These goals are for single and multivector profiles, respectively. The prior knowledge of the adversary is denoted by K∈ {D, R}, where D denote the distribution that is used for the generation of the random matrices, and R denotes the actual user matrix. Thus we have A F V R , A F D R , A F V D and A F D D adversaries. Assume the adversary has the transformed profile of a user X [u] (or transformed verification data). Definition 3. Let f be a random transformation. Our privacy notions are: 1. (µ, λ)-Value-Privacy: Let f applied to a profile vector X of length m, result in X . Then f provides (µ, λ)-Value-Privacy for the ith feature in X(i.e. X i ), against an attacker A F V , if given X , the best strategy of

A F V for X i satisfies, E[X i -Xi ] ≤ µ and V ar[X i -Xi ] ≤ λ, where E[X i -Xi ] and V ar[X i -Xi ]
are the expected value and the variance of the attacker's normalized estimation error under the random transformation, respectively. 2. π-Distribution-Privacy: Let f be applied to a multivector profile X, resulting in X . Then f provides π-Distribution-Privacy against an attacker A F D if the best strategy of A F D results in an estimated profile in which at most π-percent of features pass a statistical closeness test with the corresponding features in the original profile.

Privacy Transform.

We use the privacy transformation given in equation [START_REF]US employee 'outsourced job to china[END_REF]. A user u is associated with a k × m matrix R [u] that is generated using this distribution (in our experiments we use s = 3). Correctness of the privacy enhanced authentication follows from Theorem 1, using M = M . 3.4 Privacy Analysis. We have the following results. Privacy adversaries A F V . The system of linear equations X

[u] = 1 √ kσr R [u] X [u]
is under-determined and has infinite number of solutions. For a fixed unknown X [u] and the set of random R [u] matrices, the minimum-norm solution of the above system is known to be the best estimate in the sense that the estimation error of X [u] will have a distribution with zero mean and small variance. We adopt this solution as the best estimate for A F V R attacker who knows R [u] and the projected profile. In the case of A F V D , they can generate an RP matrix R [u] according to the distribution, and estimate X [u] using minimum-norm solution, hoping that the estimated value is close to the real value. The following proposition gives the mean and variance of the best estimation for the cases, (i) attacker A F V R and (ii) attacker A F V D . The proof is given in Appendix A. Proposition 1 Let R [u] be a k × m RP matrix with entries sampled from equation 1 with parameter s. For the projected profile X

[u] = 1 √ kσr R [u] X [u] ,
we have, (i) If X [u] and distribution of R [u] entries are known and

X[u]
i is the best estimation for the ith component of X [u] obtained using minimum-norm solution, the mean and variance of the estimation error

X [u] i - X[u] i will be µ i = X [u]
i , and

σ i 2 = 1 k m t=1 X [u] t 2 . (ii) If X [u]
and R [u] are known and X[u] i is the estimation of the ith component of X [u] obtained using minimum-norm solution, the mean and variance of the estimation error

X [u] i - X[u]
i will be, µ i = 0, and

σ 2 i = 1 k ((s-1)X [u] i 2 + t =i X [u] t 2
), respectively.

The above propositions lead to the following theorem.

Theorem 2. (i) Random projection as defined in Proposition 1 provides (µ i , λ i )-Value-Privacy against A F V D for the ith component of X [u] , and we have

µ i = X [u]
i , and

λ i 2 = 1 k m t=1 X [u] t 2 .
(ii) Random projection as defined in Proposition 1 provides (µ i , λ i )-Value-Privacy against A F V R for the ith component of X [u] , and we have µ i = 0, and

λ 2 i = 1 k ((s -1)X [u] i 2 + t =i X [u] t 2
).

Note that in both above cases, due to the large variance of the estimation error, the attacker's best estimation will be highly unreliable.

Privacy adversaries A F D . Proposition 1 shows that for A F D D the expected error and variance of the ith feature, when s = 3, will be µ i = X

[u] i , and

λ i 2 = 1 k m t=1 X [u] t 2
, respectively. The high variance of error, results in the estimation values to vary significantly from the mean, and so the original feature distributions will not be recovered by the attacker. For A F D R , using Proposition 1 and s = 3, we have µ i = 0 and

λ i 2 = 1 k (2X [u] i 2 + t =i X [u] t 2
). Again due to the large variance of the error, the probability that an estimated value be close to the original feature values will be negligible.

Experiments

We will use our privacy transform on a single vector, and a multivector, profilebased authentication system, referred to as face-biometric system and DAC, respectively. We will measure the correctness and privacy of the transformed systems against A F V D , A F V R , A F D D , and A F D R adversaries. First we give a brief overview of the face-biometric system and DAC and their corresponding matching algorithms. A face-biometric user authentication system. We use the face database used in the paper [START_REF] Samaria | Parameterisation of a stochastic model for human face identification[END_REF] and published in [START_REF]An archive of AT&T laboratories cambridge[END_REF]. A face image is represented by a vector of length 10304 (each value [0,255]). The database has 40 users, each represented by 10 face images. We designed and implemented a simple matching algorithm that uses kNN algorithm with k = 1. Using multiple sample face for each user we obtained success rate of 98.0%, FRR of 2.0% and FAR of 0.0%, which are comparable with the original results reported in [START_REF] Samaria | Parameterisation of a stochastic model for human face identification[END_REF]. DAC (Draw A Circle). DAC is a behavioural authentication for mobile devices. DAC is a challenge-response system that is implemented as a two level game: In Level 1, the challenge is a random circle that must be drawn from a given starting point. In Level 2, the challenge is a circle with a given starting point, that disappears after 3 seconds. There are 55 features in Level 1, and 56 in Level 2 (Table 1 in [START_REF] Islam | POSTER: A behavioural authentication system for mobile users[END_REF]). Figure 1 shows the system interface of DAC. Verification algorithm, for each feature, measures closeness of presented verification Table 1: Comparison of correctness before and after projection. Random projection improve the system correctness a bit.

Fig. 1: A Challenge from server side and the user's response data with the corresponding profile feature data using KS-test, and combines the resulting P-values using VoteP method [START_REF] Cooper | The handbook of research synthesis and meta-analysis[END_REF]. 4.1 Correctness experiments. Face-biometric. We measured the correctness of face-biometric system before and after RP, using FAR, FRR and SR metrics. We used, k = {56, 66, 110, 355}. From the 10 available feature vectors for a user, one vector models their single vector profile and the remaining 9 vectors are used as verification claims. For this data-set kNN with K = 1, the results are given in Table 1, showing that the privacy transform with individual user RP matrices, has improved the correctness, for all k values, making it close to 1.0. As discussed earlier this is because of the combination of distance preserving property, and the use of individual matrices that increases the distinguishability of the data of different users in the space. DAC. For DAC we use a database of 39 users. Each profile consists of 30 feature vectors (collected during registration), and 20 other vectors for verification. We calculate FAR, FRR and SR of DAC, before and after projection, for k = {25, 35, 45}. By reducing k, we expect FAR and FRR of the system to increase because more information will be lost. Table 1 shows that FAR and FRR will remain below 6.0% for different values of k, even when k = 25. The success rate in all cases is higher than 94.0%, and again random projection improves the correctness results.

Privacy

Evaluation for the two systems are below. Face-biometric system. We transformed each profile in the face-biometric system using 10,000 random matrices of size k × m, where m is the length of the feature vector. Matrices are generated using the distribution in (1). For A F V R attacker, for each projected profile we found the minimum-norm solution, X[u] , as the best estimate of the original profile assuming the matrix was known. For A F V D we repeated the same process, using a random matrix that was generated according to the known distribution. We calculated the mean and the standard deviation of the estimation error for each feature i,

X [u] i - X[u]
i , for each profile, and compared the results with Theorem 2, for k = {56, 66, 110, 355}. Using Theorem 2, these choices of k correspond to = {1, 0.75, 0.50, 0.25} (accuracy . of distance preservation) and β = {2.66, 2.64, 2.58, 2.62}, where 1-n -β = 0.99 is the probability of successful distance preservation for n=50. The first sub-figure of Figure 2 gives the mean of estimation error for k = 355 for each feature, assuming A F V D . This conforms with our theoretical results showing that the mean of the estimated value is zero. The second sub-figure of Figure 2 gives the results for the variance of the estimation error for k = 355 and shows that the error has a very large variance of the order of 10 6 , hence very unreliable estimation for the attacker. The first sub-figure of Figure 3 shows the theoretical and experimental results for the mean of the error for A F V R , and the last sub-figure of Figure 3 show similar results for variances of the estimation error for feature. It can be seen that the variance is large (of the order of 10 6 ), indicating that even A F V R will obtain negligible information about feature values. For both cases, the results for other k values are given in the full version of the paper.

In both attack scenarios, decreasing k results in higher error variance and so further reducing the dimension of data will improve privacy but this will be at the cost of correctness. Note that dimension reduction must maintain sparseness of the space and so the optimum value of k must be found experimentally.

DAC. We transformed each profile using 10,000 random matrices generated using the distribution given by equation [START_REF]US employee 'outsourced job to china[END_REF]. For A F D R , we obtained the best estimate of the 30 transformed feature vectors by calculating the minimum-norm solutions, assuming the matrix is known. Then we used KS-test to measure the similarity between the distribution of features in the estimated set of vectors and the original ones, as the measure of the attacker's success. For A F D D we performed the same experiment, using random matrices that were generated from the known distribution. The first sub-figure of Figure 4 shows the portion of features that passed the KStest in game level 2, for 15 users, assuming A F D D . The experiments are done with k = {25, 35, 45} that according to Theorem 2 correspond to distance preserving parameters of = {0.31, 0.26, 0.22}, and β = 1.17 which indicates 1-n -β = 0.99 for n=10. The second sub-figure of Figure 4 shows similar results for same parameters, assuming A F D R . Our results show that for both attack scenarios only in a small fraction of features distributions could be correctly estimated. For k = {25, 35, 45}, in the case of A F D D this fraction is {3.78, 3.51, 3.24}%. For A F D R the values increase to {7.80, 9.10, 10.19}%. Thus, our approach achieves better than (4%)-Distribution-Privacy for A F D D and better than (11%)-Distribution-Privacy against the extreme attacker A F D R . Similar results were obtained for game level 1 and are not presented due to limited space.

Changeability Evaluation.

In [START_REF] Wang | An analysis of random projection for changeable and privacy-preserving biometric verification[END_REF] authors evaluated changeability property of RP for single vector profile. We extend this result to multivector profile. For a profile X [u] , for each k, we used 1,000 random matrices to transform X [u] into {X

[u] 1 , X [u] 2 , ...., X [u]
1000 }. We used our matching algorithm, to measure the similarity of every pair of profiles that are transformed using two different random matrices, to estimate the probability of M (X u] and R [u] itself is known : distribution of less than (4%) and (11%) of features estimated close to the original one in game Level 2, for 15 different users.

.

Related Works

RP has been used for private data mining [START_REF] Liu | Random projection-based multiplicative data perturbation for privacy preserving distributed data mining[END_REF], and RP for profile privacy and achieving changeability of biometric data is considered in [START_REF] Wang | An analysis of random projection for changeable and privacy-preserving biometric verification[END_REF]. In this work the projection matrix uses continuous Gaussian distribution and a single matrix is used to transform all user's biometric data. Authors analyse correctness and privacy and provide experimental results for an attack scenario where the attacker knows, or tries to recover, the random matrix. The paper does not consider the case that only the distribution of the matrix entries are known to the adversary. The paper focusses on biometric profiles (not behavioural) and does not consider distribution privacy attacks where the attacker's goal is to recover the distribution of features. The accuracy results in [START_REF] Wang | An analysis of random projection for changeable and privacy-preserving biometric verification[END_REF] are worse than ours. This is because the same RP is used for all profiles. Using Gaussian distribution results in higher storage and computational overhead compared to discrete distribution that we use. Other non-cryptographic approaches to privacy includes data perturbation [START_REF] Liew | A data distortion by probability distribution[END_REF], [START_REF] Lefons | An analytic approach to statistical databases[END_REF], or adding noise to the data [START_REF] Agrawal | Privacy-preserving data mining[END_REF]. These approaches cannot be directly used for profile privacy because they will affect the output of the matching algorithm. Behavioural authentication systems [START_REF] Revett | Behavioral biometrics: a remote access approach[END_REF] come in many forms such as keystroke, touch dynamics or game playing [START_REF] Frank | Touchalytics: On the applicability of touchscreen input as a behavioral biometric for continuous authentication[END_REF][START_REF] Alimomeni | How to Prevent to delegate authentication[END_REF]. DAC is an active challenge-responses behavioural-based authentication system. Privacy protection of profiles can use cryptographic approaches [START_REF] Safa | Privacy-preserving implicit authentication[END_REF], but this approach is limited to special matching algorithms.

Concluding remarks.

Profile-based authentication provides a powerful method of increasing confidence in authentication results, and protecting against a range of new attacks that defeat traditional authentication systems. Profile data is privacy sensitive and must be protected. We proposed a non-cryptographic approach, using RP, for privacy enhancement of profile-based authentication systems that rely on a single, or multivector, profiles. We provided a framework for analysing privacy enhancement of profile-based authentication systems, theoretically derived the privacy level that is offered by RP, and experimentally showed the effectiveness of RP as a privacy preserving transform. Our future work includes applying the transform to other profile-based authentication systems, and investigating optimal reduction of dimension such that the privacy is maximized while correctness results are maintained. Assuming σr = σr we will have:

1 k 2 σ 2 r σr 2 E[( m t=1 itX [u] t ) 2 ] -( σr σr X [u] i ) 2 = 1 k 2 σ 2 r σr 2 E[ m t=1 it 2 X [u] t 2 + m p,q=1 p =q ip X [u] p iq X [u] q ] -( σr σr X [u] i ) 2 = 1 k 2 σ 2 r σr 2 X [u] i 2 E[ ii 2 ] + E[ m t=1 t =i X [u] t 2 it 2 ] -( σr σr X[u] i ) 2 = 1 k 2 σ 2 r σr 2 X [u] i ) 2 E[( k t=1 rti 2 ) 2 ] + m t=1 t =i X [u] t 2 E[( k f =1 r f i r f t ) 2 ]) -( σr σr X [u] i ) 2 = 1 k 2 σ 2
E[ X[u] i -X [u] i ] ≈ 0 and V ar[X [u] i - X[u] i ] = s-1 k X [u] i 2 + 1 k t =i (X [u]
t ) 2 where s is the parameter of the distribution of R [u] .

Proof of Proposition 1(ii).

Proof. The attacker can generate a k × m matrix R[u] using the known distribution (as an estimate for R [u] ) and use it to estimate X [u] similar to the case of known R [u] , as follows.

X[u] = 1 √ kσr R[u] T X [u] = 1 kσr 2 R[u] T R [u] X [u]
Let ˆ ij be the ijth entry of R[u] T R [u] . That is ˆ ij = t ] = 0 and

V ar[ X[u] i ] = E[ X[u] i 2 ] -E 2 [ X[u] i ] = 1 k 2 σr 4 E[ m t=1 ˆ itX [u] t 2 ] = 1 k 2 σr 4 E[ m t=1 ˆ 2 it X [u] t 2 + m p,q=1 p =q ˆ ip X [u] p ˆ iq X [u] q ] = 1 k m t=1 X [u] t 2
Therefore we will have:

E[X [u] i - X[u] i ] = X [u] i and V ar[X [u] i - X[u] i ] = 1 k m t=1 X [u] t

Fig. 2 :

 2 Fig. 2: Comparison of theoretical and experimental mean of error X [u] i -X[u]i for k=355 where distribution of R[u] is known to the attacker. The experimental mean and variance of the estimation error is large for all k.

Fig. 3 :

 3 Fig. 3: Comparison of theoretical and practical mean of error X [u] i -X[u] i for k=355 where R [u] is known. The experimental mean and variance of the estimation error is large for all k.

  i ), 1 ≤ i, j ≤ 1, 000 (i = j) return accept. From 999 × 1, 000 claims for each k = {25, 35, 45}, none of the (X[u] j , X [u]i ) pairs was accepted. The average % of features that pass the KS-test (α=0.05) for different k is as 15.26%,14.70% and 14.46%, respectively.

Fig. 4 :

 4 Fig.4: The distribution of R[u] and R[u] itself is known : distribution of less than (4%) and (11%) of features estimated close to the original one in game Level 2, for 15 different users.

  have E[ˆ ij ] = E[ k t=1 rtirtj ] = 0 and E[ˆ 2 ij ] = E[( k t=1 rtirtj ) 2 ] = E[

  r σr 2 X

		[u] i )	2 E[	k t=1	rti	4 +	k p =q	rpi	2 rqi	2 ] +	m t=1	X [u] t	2	E[	k f =1	r f i	2 r f t	2 +	k p,q=1	rpirptrqirqt]) -(	σr σr	X [u] i ) 2
														t =i							p =q
	=	1 k 2 σ 2 r σr 2 (X [u] i	2	(ksσr	4 + k(k -1)σr	4 ) + kσr	4	m t=1	X	[u] t	2	) -(	σr σr	X	[u] i ) 2
															t =i

Acknowledgement. This research is in part supported by TELUS Communications, Canada.

Appendix A: Proof of Proposition 1

Proof of Proposition 1(i).

Proof. Suppose σr be the variance of the distribution used to generate entries of R [u] . Let ij be the ijth entry of R [u] T R [u] . We have ij = k t=1 rtirtj , and

We know, the minimum-norm solution of the linear system of equations

, which due to

Knowing the matrix R [u] , the attacker can estimate the variance of the entries of R [u] , σr and use it to calculate the minimum-norm solution as ≈

i , and