Marc Joye
email: marc.joye@nxp.com

Fariborz Salehi
email: fsalehi@caltech.edu

Private yet Efficient Decision Tree Evaluation

Keywords: Data mining, privacy, integer comparison, decision trees

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Machine learning techniques are currently widely used for many real-world applications. These applications range from spam detection [START_REF] Abu-Nimeh | A comparison of machine learning techniques for phishing detection[END_REF], face and pattern recognition [START_REF] Liu | Gabor feature based classification using the enhanced Fisher linear discriminant model for face recognition[END_REF][START_REF] Nasrabadi | Pattern recognition and machine learning[END_REF], to the analysis of genome sequencing and financial markets [START_REF] Libbrecht | Machine learning applications in genetics and genomics[END_REF][START_REF] Min | Bankruptcy prediction using support vector machine with optimal choice of kernel function parameters[END_REF]. Unfortunately, in many cases, data mining and privacy are perceived to be at odds since the data mining algorithm requires access to the user's information in the clear. Privacy is especially relevant to applications handling sensitive data. As an example, consider the case of a medical study to diagnose a certain disease. In this scenario, medical profiles of patients are considered as highly sensitive data and their usage has to be compliant with regulations [START_REF] Bost | Machine learning classification over encrypted data[END_REF] such as Health Insurance Portability and Accountability Act (HIPAA).

An important class of machine learning algorithms is known as classification where each datapoint belongs to a certain class. The goal is to generate a model that can predict the class of a new datapoint. These models are useful in applications that provide personalized services, such as recommender systems [START_REF] Resnick | Recommender systems[END_REF], credit scoring models [START_REF] Yap | Using data mining to improve assessment of credit worthiness via credit scoring models[END_REF], automatic medical assessments [START_REF] Azar | Decision tree classifiers for automated medical diagnosis[END_REF], etc.

In this paper, we address the problem of privacy-preserving classification. We focus on commonly used classifiers: decision trees. Decision trees are simple classifiers that consist of a collection of decision nodes in a tree structure. A classical example is the twenty-question game where one player has in mind some object and another player tries to guess the object with no more than 20 yes-or-no questions. Decision trees are non-linear models for classification, yet they are easy to interpret since their evaluation simply corresponds to a tree traversal.

The secure evaluation of decision trees involves two parties. A server possesses a decision-tree model and a client wishes to evaluate the model. This is a typical setting in a cloud-based query system, where the service provider has a model which was trained by integrating the data of thousands of users and the client wants to learn the output of the model for her input data. An evaluation protocol is said to be secure, when at the conclusion of the protocol execution, the server cannot learn anything about the client's data and the client cannot learn additional information about the server's model.

The output of a decision-tree model is computed by traversing the tree, level by level. At each level, an entry of the client's input is compared against a fixed threshold and the result indicates how to traverse to the next level. The comparison at each visited node has to be performed in a secure way, otherwise there would be information leakage about the client's input and/or the server's model. At the heart of our privacy-preserving decision-tree evaluation lies an efficient protocol for the secure comparison of private values. It is worth mentioning that comparison is an essential building block for developing many other secure machine learning algorithms. These include clustering [START_REF] Bunn | Secure two-party k-means clustering[END_REF], support vector machines (SVM) [START_REF] Vaidya | Privacy-preserving SVM classification[END_REF], matrix factorization [START_REF] Nikolaenko | Privacy-preserving matrix factorization[END_REF], regression [START_REF] Nikolaenko | Privacypreserving ridge regression on hundreds of millions of records[END_REF], and neural networks [START_REF] Mohassel | SecureML: A system for scalable privacy-preserving machine learning[END_REF]. Hence, the proposed comparison algorithms can improve the performance of a wide range of applications.

Related work. Privacy-preserving data mining was introduced in [START_REF] Agrawal | Privacy-preserving data mining[END_REF][START_REF] Lindell | Privacy preserving data mining[END_REF][START_REF] Du | Building decision tree classifier on private data[END_REF]. These works present different approaches to securely construct decision trees. Protocols for the private evaluation of decision trees were subsequently developed in [START_REF] Barni | Secure evaluation of private linear branching programs with medical applications[END_REF] and more recently in [START_REF] Bost | Machine learning classification over encrypted data[END_REF][START_REF] Wu | Privately evaluating decision trees and random forests[END_REF][START_REF] Tai | Privacy-preserving decision trees evaluation via linear functions[END_REF]. In [START_REF] Bost | Machine learning classification over encrypted data[END_REF], Bost et al. express the decision tree as a polynomial whose output is the result of the classification. Their representation requires a small number of multiplications and is evaluated using a fully homomorphic encryption scheme. Wu et al. [START_REF] Wu | Privately evaluating decision trees and random forests[END_REF] reduce the problem of decision-tree evaluation to the oblivious transfer of a leaf node. Assuming a complete decision tree, they hide its structure to the client by applying a random permutation. They so gain an order of magnitude reduction in client computation and bandwidth. Tai et al. [START_REF] Tai | Privacy-preserving decision trees evaluation via linear functions[END_REF] replace the evaluation step in [START_REF] Wu | Privately evaluating decision trees and random forests[END_REF] via linear functions. This leads to better performance for sparse decision trees. Finally, we note that [START_REF] Wu | Privately evaluating decision trees and random forests[END_REF] and [START_REF] Tai | Privacy-preserving decision trees evaluation via linear functions[END_REF] also introduce extended protocols that are made secure against malicious adversaries.

In [START_REF] Damgård | Efficient and secure comparison for on-line auctions[END_REF][START_REF] Damgård | Homomorphic encryption and secure comparison[END_REF][START_REF] Damgård | A correction to 'Efficient and secure comparison for on-line auctions[END_REF], Damgård, Geisler, and Krøigaard (DGK) present an elegant two-party protocol for comparing private values. It was later modified in [START_REF] Erkin | Privacypreserving face recognition[END_REF] and [START_REF] Veugen | Improving the DGK comparison protocol[END_REF], and adapted in [START_REF] Bost | Machine learning classification over encrypted data[END_REF][START_REF] Wu | Privately evaluating decision trees and random forests[END_REF]. It relies on additively homomorphic encryption. The DGK protocol and its variants are dominated by exponentiations in the group underlying the homomorphic encryption scheme. Those are costly operations. Another drawback in the DGK protocol is the communication cost. The former issue was addressed by Veugen in [START_REF] Veugen | Improving the DGK comparison protocol[END_REF]. The author was able to divide the computational workload by approximately a factor of two, on average. Unfortunately, the resulting implementation is subject to timing attacks [START_REF] Kocher | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF].

Our contributions. We devise privacy-preserving comparison protocols that reduce by roughly a factor of two both the computational complexity and the necessary bandwidth. Furthermore, unlike [START_REF] Veugen | Improving the DGK comparison protocol[END_REF], provided proper implementation the proposed protocols are made resistant against timing attacks.

Another contribution of this work is a new protocol for evaluating a decision tree model. We borrow from [START_REF] Wu | Privately evaluating decision trees and random forests[END_REF] the astute idea of hiding the indexes of the comparison nodes using a random permutation at each level of the tree. However, we reduce the number of comparisons with a more interactive setting. Doing so, we also take advantage of the amortized complexity of efficient OT protocols. The works of [START_REF] Wu | Privately evaluating decision trees and random forests[END_REF] and [START_REF] Tai | Privacy-preserving decision trees evaluation via linear functions[END_REF] require a comparison for every internal node. In our setting, a single comparison per level is required. For a decision tree of depth d, this amounts to a total of d comparisons. This has to be compared with the m comparisons in [START_REF] Tai | Privacy-preserving decision trees evaluation via linear functions[END_REF][START_REF] Wu | Privately evaluating decision trees and random forests[END_REF], where m d is the number of internal nodes.

Paper outline. The rest of the paper is organized as follows. The next section introduces some cryptographic tools. Sections 3 and 4 are the core of the paper. They present a new design for evaluating decision trees in a privacy-preserving fashion, making use of an enhanced comparison protocol. The security and performance are discussed in Section 5. Finally, Section 6 concludes the paper.

2 Cryptographic Tools

Additively homomorphic encryption

An additively homomorphic encryption scheme [START_REF] Rivest | On data banks and privacy homomorphisms[END_REF] consists of a tuple of four algorithms (KeyGen, Enc, Dec, AddH). On input a security parameter κ, the key generation algorithm KeyGen returns a matching pair (pk , sk ) of public key and secret key. Let M denote the message space. The encryption algorithm Enc is a randomized algorithm that takes as input pk and a plaintext m ∈ M, and returns a ciphertext c. Given a valid ciphertext c, the decryption algorithm Dec, using sk , returns the corresponding plaintext m. For homomorphic encryption, the message space M is modeled as a finite ring. Additional public-key algorithm AddH operates on ciphertexts. It takes as input the encryption of two messages m, m ∈ M and returns an encryption of m + m . When the public key is clear from the context, it is customary to write an encryption of m as m in lieu of Enc pk (m). We then use the 'boxplus' operator ( ) to denote the addition of two ciphertexts. Hence, an encryption of m+m is obtained as m+m = m m . Likewise, for a known constant d, the encryption of d • m can be obtained from the encryption of m as d

• m = d • m ; i.e., as d i=1 m = m m • • • m (d times). Finally, we write m m for m -m = m -m .

Oblivious transfer

Oblivious transfer (OT) [START_REF] Rabin | How to exchange secrets by oblivious transfer[END_REF][START_REF] Even | A randomized protocol for signing contracts[END_REF] is a two-party protocol between a chooser and a sender. On a 1-out-of-N OT, the sender has a set of N t-bit strings {σ 0 , σ 1 , . . . , σ N -1 }. The chooser selects an index j ∈ {0, 1, . . . , N -1} and exactly obtains from the sender the string σ j in an oblivious way (i.e., the sender does not know the value of j). Oblivious transfer protocols can be constructed from many cryptographic assumptions. Efficient implementations are provided in [START_REF] Naor | Efficient oblivious transfer protocols[END_REF][START_REF] Asharov | More efficient oblivious transfer extensions[END_REF]; see also Appendix A.

Private Comparison of Integers

In this section, we introduce our enhanced design for the secure comparison of t-bit values based on additively homomorphic encryption. To make the presentation easier to follow, we describe it in stages. We start with a basic protocol which is not secure when some prior information is known. We then extend it to get full security regardless of the inputs.

Basic protocol

The setting is as follows. Each party possesses a private t-bit value: Party A (Alice) has x = t-1 i=0 x i 2 i while party B (Bob) has y = t-1 i=0 y i 2 i . The goal for parties A and B is to respectively obtain at the conclusion of the protocol bits δ A and δ B such that δ A ⊕ δ B = 1{x y}. Neither party can learn anything more about the other party's input.

We depict in Fig. 1 the protocol by describing the different steps performed by the two parties. Party B is equipped with an additively homomorphic public-key encryption scheme. We let m denote the encryption of a message m ∈ M under B's public key; see Sect. 2.1. The message space M is assumed to be a finite integral domain and to satisfy #M t + 1.

Remark 1. In Step 3 (Fig. 1), note that given y i , A can obtain x i ⊕ y i as y i if x i = 0, and as 1

y i if x i = 1.
To show the correctness of the protocol, it is useful to introduce some notation. For a t-bit integer a = t-1 i=0 a i 2 i with a i ∈ {0, 1}, we let a denote the complement of a; i.e., a = 2 t -a -1. In particular, for t = 1, a = a 0 and a = a 0 = 1 -a 0 . With this notation, we can reformulate an observation made in [9, Section 3].

Proposition 1. Let x = t-1 i=0 x i 2 i and y = t-1 i=0 y i 2 i , with x i , y i ∈ {0, 1}, be two t-bit integers. Define c -1 = t-1 j=0 (x j ⊕ y j ) , c i = x i + y i + t-1 j=i+1 (x j ⊕ y j ) for 0 i t -1 .
Then x < y if and only if there exists some unique index i with 0 i t -1 such that c i = 0. Moreover, x = y if and only if c -1 = 0 and c i = 1 for 0 i t -1.

Proof. As defined, c i is the sum of nonnegative terms. Therefore, for 0 i t -1, c i = 0 is equivalent to (i) x i = y i = 0 and (ii) for i + 1 j t -1, x j ⊕ y j = 0. 1. Party B encrypts the bits of y = t-1 i=0 yi 2 i under his public key and sends yi , 0 i t -1, to A.

Party

c * i = ri • 1 + (1 -2δA)xi (2δA -1) • yi t-1 j=i+1 xj ⊕ yj .
Finally, she computes This in turn is equivalent to (i) x i < y i and (ii) for i + 1 j t -1, x j = y j ; that is, x < y. To see that index i such that c i = 0 is unique, suppose that c i = 0 for some i = i. Without loss of generality, assume that i < i. This leads to

c * -1 = r-1 • δA t-1 j=0 xj ⊕ yj
c i = x i + y i + t-1 j=i +1 (x j ⊕ y j ) x i ⊕ y i = 1, a contradiction.
The second part of the proposition is clear. If t-1 j=0 x j 2 j = t-1 j=0 y j 2 j then c -1 = 0 and c i = 1 for i 0.

By reversing the roles of x and y in Proposition 1, we get as an immediate corollary the following proposition.

Proposition 2. Let x = t-1 i=0 x i 2 i and y = t-1 i=0 y i 2 i , with x i , y i ∈ {0, 1}, be two t-bit integers. For 0 i t -1, define c i = y i + x i + t-1 j=i+1 (y j ⊕ x j ) .
Then x y if and only if there exists no index i with 0 i t -1 such that c i = 0.

Proof. If there were such an index i, this would imply y < x by Proposition 1. The absence of such an index therefore implies y x.

We are now ready to show that the protocol must terminate with the correct result. Following [START_REF] Veugen | Improving the DGK comparison protocol[END_REF], depending on the value of h (see Step 2 in Fig. 1), we distinguish three cases.

1. Suppose first that the Hamming weight of x is greater than t/2 (and thus δ A = 0). This means that x has more ones than zeros in its binary representation. Specifically, among the t bits of x, at most t/2 bits are equal to 0. Furthermore, for 0 i t -1, Proposition 1 shows that c i needs only to be evaluated when x i = 0 since when x i = 1 we already know that the corresponding c i cannot be zero. The case x = y is taken into account using c -1 . 2. Now suppose that the Hamming weight of x is less than t/2 (and thus δ A = 1). In this case, among the t bits of x, at most t/2 bits are equal to 1. We can then make use of Proposition 2. With at most t/2 tests for c i = 0 (i.e., when x i = 1), we can decide whether x y. 3. The last case is when the Hamming weight of x is t/2 (and thus δ A is equiprobably equal to 0 or 1). This supposes t even. In this case, among the t bits of x, t/2 bits are equal to 0 and t/2 bits are equal to 1. Proposition 1 or Proposition 2 can be used indifferently to decide after at most t/2 = t/2 tests for c i = 0 whether x y.

The above analysis shows that (i) only the indexes i ∈ L need to be tested, and (ii) #L t/2 . If #L < t/2 then additional indexes are added to L to form L . This ensures that #L is always equal to t/2 and is aimed at preventing timing attacks. Now the correctness follows by noting that the c * i 's include the encryptions of r i • c i for all i ∈ L . It is also important to see that c * -1 is the encryption of a non-zero value when δ B = 1.

By construction, δ B = 1 if one of the c * i 's decrypts to 0. -When δ A = 0, Proposition 1 is used. A decryption to 0 means x y. We therefore have 1{x y} = 1 = δ A ⊕ δ B , as desired. -When δ A = 1, Proposition 2 is used and a decryption to 0 means x y. Then, 1{x y} = 0 = δ A ⊕ δ B , as desired.

If none of the c * i 's decrypts to 0 then δ B = 0. When δ A = 0, this means x y; when δ A = 1, this means x y. In both cases, we have 1{x y} = δ A ⊕ δ B , as desired.

Full protocol

The basic protocol needs special care. In particular, it requires that the Hamming weight of x a priori has the same probability to be greater than t/2 or less than t/2 . This guarantees that δ A is uniformly distributed over {0, 1}. Indeed, if party B knows for example that the Hamming weight of x is more likely less than t/2 (and thus δ A is more likely equal to 1), a value δ B = 0 tells party B that x is more likely less than or equal to y since δ A ⊕ δ B = 1{x y}.

We modify our basic protocol so that it remains secure when party B has some prior knowledge on the Hamming weight of x. The resulting distribution of δ A will always be uniform over {0, 1}, independently of the value of x. The full protocol is detailed in Fig. 2. It is worth remarking that x as defined in Step 1b (Fig. 2) is a random t-bit integer. There is therefore no way for party B to gain more information on its Hamming weight.

The correctness of the protocol is easily verified. By definition, we have y * = y + η -2 t Y * , z * = y * + x -x -2 t Z * , and y = z * -η -Y 2 t . This leads to

δ A ⊕ δ B = 1{x y} = y+2 t -x 2 t = y +2 t -x 2 t + Y * + Y + Z * = (δ A ⊕ δ B ) + Y * + Y + Z * .

Reducing the above relation modulo 2 yields δ

A + δ B ≡ δ A + δ B + Y * + Y + Z * (mod 2), a solution of which is δ A = δ A +Z * mod 2 and δ B = δ B +Y * +Y mod 2.

Further settings

Encrypted comparison bit. Let δ denote the comparison bit; i.e., δ = 1{x y}. In certain settings, a party wishes to produce an encryption of δ at the end of the protocol, rather than a share δ A of δ (the other share, δ B , being held by the other party). In this case, we can add the following step to our comparison protocols: 1) and ( 2

) become β = 1 x i ( ) k T ( ) k with k := k ( ) = (β 0 , . . . , β -1 ) 2 .
In particular, for = 1, we obtain

β 1 = 1 x i (1) k T (1) k with k = β 0 = b 0 if b 0 = 0 b 0 ⊕ 1 otherwise .
Specifically, if b 0 = 0, the server knows that the client possesses the correct result of the comparison; i.e., b 0 = β 0 . If b 0 = 1, the server knows that the client possesses the flipped result. To maintain the consistency, the server uses a copied version T * of the initial tree. If b 0 = 1, the server updates T * by switching the left subtree and the right subtree at level = 1. What is important to observe here is that k coincides with b 0 in T * . Hence, the client can obtain x i (1)

k -T (1)
k + µ 1 -and in turn x i (1)

k -T (1)
k + µ 1 after decryption-from the server, where µ 1 is a mask chosen by the server to hide the value of x i oracle. The sender selects at random K 1 , . . . , K N -1 ∈ G and computes y = g x for some random integer x ∈ Z q . The sender's public key is (g, y, K 1 , . . . , K N -1 ) and the secret key is x. The sender pre-computes S i = (K i ) x for 1 i N -1.

The sender's input is a set of N bit-strings σ 0 , . . . , σ N -1 ∈ {0, 1} t . Suppose a chooser (Carol) wishes to get string σ j for some j ∈ {0, . . . , N -1}. The amortized 1-out-of-N Naor-Pinkas OT protocol [24, § 3.1] proceeds as follows.

1. The chooser draws a random integer r ∈ Z q and computes pk j = g r . If j = 0, she sets pk 0 = K j /pk j . She sends pk 0 to the sender. 2. The sender computes (pk 0 ) x and then, for 1 i N -1, sets (pk i ) x as (pk i ) x = S i /(pk 0 ) x . Next, he chooses a nonce R and encrypts each string σ i as c i = H (pk i ) x , R, i ⊕ σ i , for 0 i N -1. He sends (c 0 , . . . , c N -1 , R) to the chooser. 3. The chooser recovers σ j as c j ⊕ H(y r , R, j).

Interestingly, the protocol can be re-used multiple times. After the one-time initialization phase, each transfer only costs a single exponentiation (in G) plus N -1 multiplications for the sender. The chooser essentially computes one exponentiation per transfer.

Fig. 1 .

 1 Fig. 1. Basic comparison protocol.

  for a random non-zero element r-1 ∈ M. Party A sends the t/2 + 1 ciphertexts c * i in a random order to B. 4. Using his private key, party B decrypts the received c * i 's. If one is decrypted to zero, B sets δB = 1. Otherwise, he sets δB = 0.

Fig. 2 .. 2 .

 22 Fig. 2. Full comparison protocol.

5 .

 5 Party B encrypts δ B using his public key and sends δ B to A. Upon receiving δ B , party A computes the encryption of δ as δ = δ B if δ A = 0, and δ = 1 δ B otherwise. client. The encryption scheme is supposed being additively homomorphic with message space M such that #M 2 t+κ for a certain security parameter κ. Using the techniques developed in the previous section, the client and server can now engage in a two-party protocol to secret-share the decision bit β 0 = b 0 ⊕ b 0 -where the server holds b 0 and the client holds b 0 . Details are provided in Step 2 of Fig. 6. -For = 1, . . . , d -1, Equations (

  , the client and server engage in a two-party protocol to secret-share the decision bit β 1 = b 1 ⊕ b 1 . To prevent the server to learn the index k , x i (1)

  A computes the Hamming weight of x (i.e., the number of nonzero bits of x). Let h denote the Hamming weight of x.

	There are three cases to
	consider:
	(a) if h > t/2 , A sets δA = 0;
	(b) if h < t/2 , A sets δA = 1;
	(c) if h = t/2 (this can only occur when t is even), A chooses a random value
	in {0, 1} for δA.
	3. Next, party A forms a set L of indexes i such that

(a) L ⊇ L where L = 0 i t -1 | xi = δA ; and (b) #L = t/2 .

For each i ∈ L , A draws at random a non-zero element ri ∈ M and computes

We use triple brackets rather than double brackets to indicate that the encryption scheme may be different from the one used for the comparisons.

Encrypted inputs. There exists another practical setting for the comparison of private inputs. Suppose that one party possesses x and y , the encryption of two t-bit values x = t-1 i=0 x i 2 i and y = t-1 i=0 y i 2 i . The other party possesses the corresponding decryption key. Our protocols easily generalize to cover this setting as well. An example is given in Sect. 4.2.

Other frameworks. The technique we employed is fairly generic and can be adapted to increase the efficiency of other bit-wise comparison protocols, including the protocol in [START_REF] Lin | An efficient solution to the millionaires' problem based on homomorphic encryption[END_REF].

Application: Private Evaluation of Decision Trees

Secure comparison protocols find numerous practical applications. We apply the results of the previous section to the private evaluation of decision trees. As the values being compared will be random, our basic protocol (Fig. 1) suffices.

Problem setup

There are two parties involved: a client and a server. The client has a private feature vector x = (x 1 , x 2 , . . . , x n ) ∈ Z n and the server possesses a decision tree model T : Z n → Z. At the end of protocol, the client obtains the value z r := T(x) and learns nothing else; the server learns nothing.

In a binary tree, each internal node ν ( ) k (with 0 k ) at level in the tree is associated with a Boolean function

where i

k is an index in the feature vector x ∈ Z n , and T ( ) k is a threshold. The depth of the tree (i.e., the longest path from the root to a leaf) is denoted by d. The number of internal nodes is denoted by m. Without loss of generality, we assume that T is a complete binary decision tree; that is, a binary decision tree with exactly 2 nodes at each level . We note that it is easy to derive a complete binary decision tree by introducing dummy internal nodes and assigning an arbitrary value in {0, 1} for the corresponding Boolean function f ( ) k (x) . This is illustrated in the figure below on a decision tree of depth d = 2.

Fig. 3. Transforming a binary decision tree into a complete binary decision tree.

From public to private evaluation

On input x, the evaluation of a decision tree starts at the root node. At each level , depending on the result of f ( ) k (x), either the left branch (for 0) or the right branch (for 1) is taken. The process is repeated until a leaf node is reached. The output of T(x) is z r , the value of the so-obtained leaf node.

Public evaluation. When the feature vector x and the decision tree T are available in the clear, the decision tree can be evaluated by performing d comparisons. Let β ∈ {0, 1} denote the result of the decision (0 or 1) at level , for = 0, 1, . . . , d-1. It turns out that

Consequently, the index r of the corresponding leaf node can be expressed as

, where (β 0 , β 1 , . . . , β d-1 ) 2 represents the binary expansion of r.

Example 1. Figure 4 depicts an example of a binary decision tree with 4 levels. In this example, the index r of the output, z r , is given by r = (β 0 , β 1 , β 2 , β 3 ) 2 = (0, 1, 0, 1) 2 = 5. Private evaluation. In the private setting, the server knows the model T (including i

-For = 0, we have

. However, the private comparison protocols of Sect. 3 do not directly apply because the value of i (0) 0 is unknown to the client. This issue is resolved by providing the server with x i , for 1 i n. Here, x i denotes an encryption 3 of x i under the public-key of the k -T Our decision-tree evaluation protocol is given in Figure 6. The permuted tree T * is represented at level 1 by the string σ ( ) = (b 0 , . . . , b -1 ) 2 ; T * = T for = 0. Step 2d in Fig. 6 outputs shares of the decision at level . It is worth noting that a single execution of the comparison protocol is run per level.

Fig. 5. Public vs. private evaluation of a decision tree.

Proof. From m = M -M /2 t 2 t and m = µ -µ /2 t 2 t , we can write

. Furthermore, defining s = σ ( ) ⊕ j, we have

Putting the two relations together, modulo 2, yields

This concludes the proof by noting that s = k , b = δ + µ /2 t (mod 2), and b ≡ δ + M /2 t (mod 2).

As a result, the client learns the classification result T(x) at the end of the protocol in Fig. 6.

Discussion

Security considerations

The decision tree evaluation protocol presented in Fig. 6 is secure in the semihonest model, a.k.a. honest-but-curious model. It assumes two semantically secure additively homomorphic encryption schemes, • and • , and a semi-honest secure 1-out-of-N OT protocol. Informally, if the parties interact according to the protocol specification, the semi-honest model guarantees that (i) the client only learns the classification result and a bound d on the depth of the decision tree, and (ii) the server learns nothing. The security is defined via the ideal-world/real-world simulation paradigm; see e.g. the excellent tutorial provided in [START_REF]Tutorials on the Foundations of Cryptography[END_REF]Chapter 6]. The security proof of our main construction is standard. We refer the reader to [START_REF] Wu | Privately evaluating decision trees and random forests[END_REF]Sect. 2.3] for precise security definitions and to [START_REF] Wu | Privately evaluating decision trees and random forests[END_REF]Theorem 3.2] for the proof technique.

Selecting parameter κ.

Step 2a in Fig. 6 requires a random mask µ to blind the value of

for k = 0, . . . , 2 -1. In Step 2c, as the output of the 1-out-2 OT, the client obtains M = M ( ) j

for a single value j ∈ [0, . . . , 2 -1]. This justifies that the same mask µ can be re-used at level , for each successive value of k.

Moreover, when the message space M for • is much larger than the set {0, 1} t , since x i ( ) k⊕σ ( ) and T ( ) k⊕σ ( ) are t-bit values, there is no need to draw the mask µ in the whole range of M. Any (t + κ)-bit value for a relatively short security length κ will generate a mask that statistically hides x i ( ) k⊕σ ( ) -T ( ) k⊕σ ( ) . When the message space M = Z 2 t (like in [START_REF] Benhamouda | Efficient cryptosystems from 2 k -th power residue symbols[END_REF]), µ and M are defined modulo 2 t as elements in Z 2 t (and thus µ /2 t = M /2 t = 0). Parameter κ will be in this case set to 0.

Performance analysis

We compare the proposed evaluation protocol with the two most recent protocols, Let T be a binary decision tree of depth d with m [non-dummy] internal nodes (i.e., decision nodes). Let also n be the number of entries in the feature vector; each entry being represented as a t-bit integer. Both the computation and bandwidth are analyzed. For the computation complexity, we count the number of public-key operations performed by each of the parties. For the bandwidth, we count the number of ciphertexts sent by one party to the other. In our protocol, the client first encrypts the feature vector. This requires O(n) public-key operations and produces n ciphertexts. Next, in the main loop, at each level (for 0 d -1), the client mainly performs two steps with the server: (1) one 1-out-of-2 OT where the client is the chooser and (2) one comparison of two t-bit integers. We assume that the OT is implemented with the Naor-Pinkas protocol (see Appendix A) and that the comparison makes use of our comparison protocol (Fig. 1). So, on the client's side, the OT requires in total for the main loop O(d) public-key operations and d -1 ciphertexts; the comparison requires in total O(dt) public-key operations and d( t/2 + 1) ciphertexts. The last step is a 1-out-of-2 d OT, which requires O(1) public-key operation and one ciphertext. Summing up, the total complexity for the client amounts to O(n + dt) with n + d -1 + d( t/2 + 1) + 1 = d( t/2 + 2) + n ciphertexts. On the server's side, the server processes in addition m encryptions (Step 2a in Fig. 6) to form M ( ) k for the non-dummy nodes. This corresponds to a complexity of O(m). The OT in the main loop requires in total O(d) public-key operations and 2 d -1 ciphertexts. The comparison requires O(dt) public-key operations and dt ciphertexts (we suppose here that the server plays the role of Party B; cf. Fig. 1). The last step for the final OT incurs for the server O(1) public-key operation and 2 d ciphertexts. Consequently, the total complexity for the server is of O(m + dt) and the needed bandwidth is of 2 d -1 + dt + 2 d = dt + 2 d+1 -1 ciphertexts.

A typical value for the precision is t = 64. As shown in Table 1, since d m, the proposed protocol greatly reduces the workload on both the client's and server's sides. The bandwidth usage is also improved on the client's side with our protocol. On the server's side, the savings depend on the tree sparsity. Denser decision trees give rise to more savings; for a complete binary tree (i.e., m = 2 d -1), our protocol saves (2 d -d)t ciphertexts on the server's side.

Random forests

As in [START_REF] Wu | Privately evaluating decision trees and random forests[END_REF], our main construction extend to the evaluation of random forests. Introduced by Ho [START_REF] Ho | The random subspace method for constructing decision forests[END_REF], the random forest improves the quality of the classification task by combining the results of a multitude of decision trees. A random forest F can be defined as an ensemble of decision trees, F = {T i } i . Its output is computed by taking the majority vote; i.e., F(x) = maj{T i (x)} i .

Conclusion and Future Work

In this work, we introduced an enhanced comparison protocol and several extensions thereof. As an application, combined with a novel design strategy and a number of optimizations, we developed an efficient protocol for the private evaluation of decision trees. Future work. An interesting direction for future work is to design a privacypreserving evaluation protocol in the multi-user setting, wherein the feature vector and/or the model are shared among multiple entities. Another interesting direction is to extend the protocol to make it secure against malicious adversaries.


Vishwas T Patil
email: ivishwas@gmail.com

Nivia Jatain
email: jatain.nivia@gmail.com

R K Shyamasundar
email: shyamasundar@gmail.com

Role of Apps in Undoing of Privacy Policies on Facebook

Keywords: Social network, Privacy, Linkability

Facebook allows its users to specify privacy settings for the information they share with other users and Apps. Apps seek a set of permissions from the user at the time of installation. There is no check that is performed to evaluate any possible adverse implications of App's permissions on the in-force privacy settings of an user. In this paper, we have investigated FB's platform for access to users' data by Apps and Advertisers. By signing up with FB, users implicitly trust the platform, which they believe can be held accountable in case of a breach. However, similar expectation of accountability from Apps is hard to imagine and difficult to ensure. At times, Apps have as much access to user data as FB and such a common access to user data undermines provenance of data leakage. Recently, though FB has reduced the extent of data access for Apps by deprecating certain APIs, a systematic design approach is missing for platform-wide access policy specification and conformance. We have presented several scenarios where App permissions are violating user privacy policies. Our findings have been presented with the help of experiments using Facebook Developer Platform.

Introduction

Facebook is the largest social network. Maintaining 1.5 billion daily active users, their connections and updates in real-time is a tremendous engineering feat. However, it appears that the guiding principles in the evolution of Facebook's data platform have been: real-time response [START_REF] Bronson | TAO: Facebook's Distributed Data Store for the Social Graph[END_REF] and features to users, app developers, and advertisers. The recent revelations [START_REF] Cadwalladr | I made Steve Bannon's psychological warfare tool': meet the data war whistleblower[END_REF] have forced Facebook to acknowledge that data privacy is an important feature! The platform's design choices, for speed and features, will hinder it from coherently enforcing privacy policies anytime soon in the near future.

Facebook's platform allows users to establish and organize their relationships with other users using social relationship categories like "Friends", "Close Friends", "Family", etc. An update in user's personal life is more relevant to members of "Family" than "Friends" and the platform does such a prioritization intelligently. Similarly, among the categories of relationships further prioritization of updates is done based on the interests of the users that are at the other end of the connection. That is, a friend from school falls in sub-category school and likewise a friend from university. Furthermore, friends from school who have interest in history are distinguished from the friends who have interest in finance. Such a segmentation of categories helps the platform to build relevant audiences for a user's updates. Users are given a control to decide which segment should see what updates. Facebook (FB) organizes all these information about its users and their interactions as a graph -called social graph. Users (nodes) are free to form new relationship (edge) and update the old ones. Social graph is a continuously evolving graph and this type of organization of users and their data helps FB in segmenting users with similar interests so that they can be introduced to a new post or an advertisement.

FB platform allows developers to write Apps, which users can install. An App serves a specific function to its users. When a user installs an App (represented by an edge between the App and the user on social graph), it signifies that user's interest in the functionality provided by that App. Thus, users get a functional convenience and FB automatically gets contextual insights about users. Both, the App and the platform will have an access to users' interactions within the administrative sphere of the App. FB can build an accurate context about an user than an App because it has other insights about the user. Thus an App, through its functional category, helps the platform to segment users in a specific category so that it can be used in profiling the users. For example, a flower delivery App can help identify users who are single, male, within a specific geographical area, and who have purchased flowers last year on Valentine's day. In order to build audiences of such type, FB needs to build, maintain a detailed profile for each of its users. Higher the interactions of a user, richer the profile. Connectivity and interactions are important objectives of the platform, and FB does it very well in its ecosystem of users, Apps, content and interactions among them. This ecosystem of interacting nodes is depicted as a pyramid, in Fig. 2), to highlight their access privileges (either explicit or implicit) on the platform. Each layer (user layer, app layer, advertisement layer) serves a different purpose and has a different access control mechanism to control access to users' information. In [START_REF] Patil | Undoing of privacy policies on facebook[END_REF], we have analyzed privacy claims of the platform at the user level alone. In this paper, we analyze conformance of user privacy settings in the presence of Apps. We will show that there is no coherence in policy enforcement across the layers, which undermines the privacy of its users. We have validated our observations through experiments on Facebook's developer platform v2.12 and Facebook Audience Network. While FB does profiling of users for varieties of reasons, one of the trusting factors of FB is that it shall not divulge intentionally or for price the data that violates its committed privacy setting with its users. However, this cannot be said about the app developers or the advertisers on the app. Thus, our findings show the challenges to plug the leaks, due to apps/advertisers, FB should undertake.

In the following section, we present the somewhat hybrid, ad-hoc nature of access control mechanisms employed by FB. In Section 3, we analyze the platform and trace the flow of user information beyond the layers of its policy sphere. In Section 4, we present a few scenarios where defined privacy settings of a user are violated due to Apps. Section 5 discusses related work followed by conclusion in Section 6.

Access Control in Facebook

At the different layers of the platform, FB employs different types of access control mechanisms. At the user layer, user content and user attributes are protected by a discretionary access control. At the App layer, user content and user attributes are protected by capability lists. The other entities of the platform are not governed by any policy that user can influence. Also, the metadata the platform collects about user is not controlled by the user in any way. The platform organizes all of its entities and content in a graph, which has a sub-graph that can be traversed by users/Apps according to their respective permissions. The platform owner can traverse the whole graph without any restriction and acts as a proxy to its collaborators (the advertisers). Social graph -Reachability as the condition for access: Social graph in Facebook is a representation of user information on Facebook. Two user nodes have an edge between them if the users are friends with each other. Having an edge between two nodes establishes connectivity between them and in turn extends their reachability: that is, a user can access posts of her friend because there is a path present on the graph between the user and her friend's post via the friend node. Now, if the user likes her friend's post, this will be reflected in the social graph by putting an edge of type like between the user and her friend's post. Thus, each and every action or event created by Facebook's users is consumed by the social graph. The graph continuously changes its state reflecting its users' actions and interactions. Updates to social graph happen by adding/deleting nodes (or updating fields of nodes), and adding/deleting/updating the labelled edges -all such updates are due to a user's and app's interactions with their reachable nodes. Passive nodes like posts, photos, et al, do not interact on their own. Social graph also allows its nodes to be queried [START_REF] Patil | Undoing of privacy policies on facebook[END_REF]. A user is allowed to compose a query by specifying a particular node (of type root [START_REF]Facebook: Graph API overview[END_REF]) about which the requester needs information. It is very likely that different sets of information about a node are presented based on who the requester is. Lists as access policies for users: Each user is provided with pre-defined relationship categories, called lists, along which users organize their relationships with others. Then there is a category of lists that FB creates for a user based on her social affiliations. And a user is also allowed to create and manage her own private lists. Given below is a typical set of labels provided to express access control policies:

-Only Me: is a label/list in which user herself is the only member -Public: is a label, when used, the associated object is accessible publicly -Friends: is the primary list under which all friendship relations are enlisted -Restricted: is a list of friends to whom only Public labelled information is allowed -Family: is a list of friends who are assigned as family members -Close Friends: is a list of friends who are assigned as close friends -Acquaintances: is a list of friends who are assigned as acquaintances -Friends of friends: list of users who have friendship relation with "Friends" -University: is a social list of friends who are also members of Smart List University -School: is a social list of friends who are also members of Smart List School -Cycling: is a Private List to which user has assigned a set of friends -Custom: is a custom policy constructed using the label types described above.

Access control of objects in FB is a simple check on associated list's membership. If a requester of an object is a member of the list with which the object is protected, the requester gets access. Tagging is a positive exception to the membership check. There are two negative exceptions to the membership check: "Restricted" list and "Blocked" list. If a requester of an object is member of one of these lists, access is denied even when the requester is member of the list with which the object is protected. Post2 cannot be accessed by User1 because the custom policy allows access to all friends of User2 except User1. The Event created by User1 cannot be accessed by anyone except User1 because the access policy is only me. Thus, labels or lists are used to control access to the content owned/posted by Facebook users. Capabilities as access policies for Apps: FB Apps too are represented by nodes on social graph. However, Apps' traverse-ability on the social graph is limited to the immediate neighborhood of the user node consisting only the object nodes. In other words, the App can neither reach the friends of the user nor the other Apps installed by that user. What interactions the App can do in the user's neighborhood is determined by the set of permissions the user has allowed at the time of establishing the installed relationship with the user. There are 48 such permissions an App can obtain from its user. This is similar to capability lists in access control paradigm [START_REF] Levy | Capability-Based Computer Systems[END_REF]. In later sections we shall discuss which of these permissions to an App undermines user's privacy.

The utility of social graph is not limited to representation of subjects, objects and their relationship but to also provide real-time updates about the changes in the neighborhood of the subject. Prioritization of updates according to their relevancy to a user based on users' past interactions on social graph is handled by NewsFeed algorithm; a core function of FB platform. How the App ecosystem helps it in achieving precision is explained below along with the other important components of platform.

3 Architecture of Facebook Platform Fig. 3 gives a schematic architecture of Facebook platform depicting the relationships between the major entities of this platform. In the following we describe the entities and their functionalities. The platform is logically divided into two: public space & private space. The entities in public space are the users and applications. They are said to be in public space because, having an account on FB, these types of nodes can query and interact among each other based on the access policies. Though the entities from private space can influence and have a richer view of the graph topology, they cannot perform any of the operations available to nodes in public space without being a node in the public space. Fig. 2 depicts the access-hierarchy in the social graph of Facebook. The primary objective of the platform is to build accurate user profiles (behavioral, psychometric, etc.) so that advertisers can be accurately matched to their audience.

The platform has been quite successful in micro-targeting users in real-time so that it artificially puts limits on advertisers while building their target audiences. An advertiser cannot compose a target audience whose size is less than 100. Similarly, an advertiser cannot request audience-tracking for audience size less than 100. To understand the design of this platform let us describe the role and functionality of its individual entities. NewsFeed: Facebook has an intelligent algorithm to prioritize the updates to a user, which is called NewsFeed. If we assume that each object/content on the social graph has a category type associated with it, like: education, finance, food, sarcasm, celebrity, etc., then a subject's interaction with these objects determine the probability of interest the subject may have in such categories. Each interaction of a subject with its neighborhood node improves the confidence level of subject-category mapping. The objective of NewsFeed algorithm is to increase subjects' interaction with varying categories [START_REF][END_REF] of content so that a rich user profile can be built. Such a user profile is necessary to determine relevancy of updates to the user and also to match the user with an advertiser interested in particular category [START_REF]ProPublica Data Store: Facebook ad categories[END_REF]. If we assume the nodes in the graph are labelled with categories and edges are weighted proportional to the confidence level of the category, then we can think of an influence function over two nodes. A node with higher confidence value influences the confidence value of its peer. Thus the utility of NewsFeed function is incite the user to interact with content from its neighborhood and also from other influential nodes with whom the user does not have relationship (either friend or follow) yet. Higher the engagement of the user, more are the interaction, and thus higher the confidence value to categorize the user. Users: Users are the largest part of the platform. Their interactions within their reachable neighborhood and with the nodes introduced by the NewsFeed builds their individual user profiles. Users interactions with content outside the platform also helps in building the profile. Apps: The platform gives a general purpose connectivity and interaction mechanism to the users, whereas the Apps give a context to user profile. Apps serves a specific functionality (e.g., finance, education, dating, et al.) to its users and that functionality is a stronger measure to categorize users. Apps can opt for monetization of their functionality by serving advertisements to the users via the App. Apps obtain analytics over their users interactions. The analytics information contains attributes (like mobile advertisement ID, Facebook UID, email, phone, Device info, location, etc.) that can uniquely measure interactions of App users. To advertise itself, or to persuade its existing users the App may share its analytics with advertisers to target the existing and new users. Advertisers: Advertisers are the paid interfaces to the platform's ability to find precise audiences for a specific category/issue. Advertisers build advertisement campaigns by requesting specific audience type from the platform against a fee. To build the audience request, advertisers upload data fields that are compared against the user profiles that are built by the platform. Upon evaluating the scope of campaign targeting based on the uploaded data by the advertiser, the platform either accepts or rejects the request. Advertisers are allowed to micro-target a specific audience that is already engaged with it. Advertisers do so by defining events inside the Apps and trigger actions via Pixel for those events' realization. For example, list of users who have browsed a product but did not checkout. Pixel: It is a micro-targeting framework https://fb.com/business/learn/facebook-ads-pixel that uniquely identifies users of the platform and also the users off-the-platform. This is a script that generates a unique tracking number each time a defined event occurs. The events could be as simple as loading a website or a user selecting a product in her cart. The unique number concatenated with cookie at user side tracks the user event by event. These user behavior analytics are shared by the platform with the advertisers so that advertisers can measure the impact of their advertising campaigns. FBAN: Facebook Audience Network (https://fb.com/audiencenetwork) is the core component of the platform and has access to users profiles generated by the platform. It has its own data-set that is built from user tracking (analytics) and other associated plat-forms' meta-data information (like WhatsApp, Messenger, Instagram). It accepts audience requests from advertisers and based on the corroboration with its data-sets and user profiles, it identifies the target audience for a campaign. There exist public dataexchanges for user information, which can help enriching the profile attributes of users that come in contact with the platform. Profiles: All individual user profiles are further enriched and attributed by the insights obtained from platform analytics and plausibly external public/private data-sets [START_REF]Facebook: Data policy[END_REF] (For Indian users, Facebook tried to link their Aadhaar numbers with their profiles. Aadhaar numbers are not secret but are used in various financial and public services delivery).

Filters: These determine the general access policy of the platform. For example, Facebook recently decided not to allow querying of its users (nodes) by their email/phone. This is also responsible for guiding the behavior of the platform in general. For example, to suppress a specific category of nodes appearing in the NewsFeed. Facebook had made an understanding with a large government (Project Colorful Balloons) to ensure a specific category of nodes is identified, tracked and controlled.

Having understood the roles various entities play in the FB ecosystem and keeping in mind those entities' access hierarchy, the question we ask is the following: Assuming users explicitly trust Facebook to handle their private data against the free services, and assuming that Facebook desensitizes user data before making use of it for advertisement: what privacy & leakage assurances can we expect from the platform?

As Apps are only loosely coupled with the ecosystem as compared to the other entities in the ecosystem, it is difficult to assume that (smaller) Apps will strive for achieving the same level of trust with users as Facebook may have. In the following we present a few scenarios in which Apps violate users' privacy settings. In [START_REF] Patil | Undoing of privacy policies on facebook[END_REF], we have presented whether Facebook users really preserve their privacy as they understand it or certain of their innocuous actions leak information contrary to their privacy settings. We would like to list those findings (at user-object layer of the platform) here:

1. Nonrestrictive change in policy of an object risks privacy of others, 2. Restrictive change in policy of an object suspends other's privileges, 3. "Share" operation is privacy-preserving, 4. Policy composition using intensional labels is not privacy-preserving, 5. "Like", "Comment" operations are not privacy-preserving.

In this paper, we extended the scope of our investigation to higher layers in the platform: that is, App layer and advertiser layer.

Experimental Scenarios of Access by Apps

In this section we list out our experiments using apps and advertisement facility of Facebook and highlight their potential in undermining user's privacy and security. The experiments are carried out using Facebook APIs (v2.12) and our findings are reproducible as of April 13, 2018. This sort of gap analysis in privacy policy conformance across platform is ignored [START_REF]Facebook: Cracking down on platform abuse[END_REF], and precisely due to the lack of a platform-wide, coherent, privacy policy enforcement, rouge apps are tracking and siphoning off user data. Facebook has deprecated Apps to access its user's friend list. Consider a scenario as shown in Fig. 4, in which Alice has set her list of friends to private in her privacy settings. This setting sets an expectation that Alice's friend list will not be available to others. Alice installs App1 with permission user posts. This permission allows App1 to reach all of Alice's posts and their fields (comments, reactions, post privacy settings). Fig. 5 is the list of posts retrieved by App1 from Alice's timeline. Fig. 6 shows the retrieval of comment & reaction on the first post in the list shown in Fig. 5. FB's NewsFeed function presents updates from Alice's timeline to her friends (Bob). When a friend interacts with the post, App1 can observe it and deduce with high probability that Bob is Alice's friend. The probability of such an inference is 1 when Alice has given App1 permission to post with post's access policy as "Friends". Similarly, depending on post's permission policy setting, App1 can reason about Family et al.

App Finds out User's Friends

data:Array(7) 0:{message: "Test post for comment", created_time: "2018-04-12T10:34:40+0000", id: "113415586159959_152355935599257"} 1:{message: "Post by TestApp", created_time: "2018-04-12T06:47:07+0000", id: "113415586159959_152253442276173"} 2:{message: "Vtp", created_time: "2018-04-10T08:29:11+0000", id: "113415586159959_150842215750629"} 3:{message: "Modified Post", created_time: "2018-04-07T07:14:44+0000", id: "113415586159959_148447715990079"} 4:{message: "test post", created_time: "2018-04-03T08:21:11+0000", id: "113415586159959_145280909640093"} 5:{message: "Test post for Comments", created_time: "2018-03-20T04:16:11+0000", id: "113415586159959_133157927519058"} 6:{message: "Test post for Alice", created_time: "2018-03-20T04:15:24+0000", id: "113415586159959_133157680852416"} length:7 Fig. 5. List of posts retrieved by App1 from Alice's timeline data:Array(1) 0: created_time:"2018-04-12T10:36:14+0000" from: id:"104812420348221" name:"Bob Greenewitz" __proto__:Object id:"152355935599257_152356518932532" message:"Test comment by Bob" __proto__:Object length:1 data:Array(1) 0: id:"104812420348221" name:"Bob Greenewitz" type:"WOW" __proto__:Object length:1 Fig. 6. retrieval of comment & reaction on the first post in the list shown in Fig. 5 4.2 App Can Access User Objects Despite "Only Me" Policy Consider in Fig. 4, Alice changes the access policy of her post P1 to "Only Me". This implies that only she can access this post. However, App1 can still access the post P1 even when Alice sets the policy to "Only Me", see Fig. 7.

created_time:"2018-04-07T07:14:44+0000" id:"113415586159959_148447715990079" message:"Modified Post" privacy: allow:"" deny:"" description:"Only me" friends:"" value:"SELF" Consider the scenario shown in Fig. 8. Both the apps have permission user posts. App2 (i.e., anshx.ananx as its real name in our experiments) has one additional permission publish actions as shown in the figure. Let us assume that App2 publishes a post on Alice's timeline. App1 can observe this event and can obtain the post ID. Fig. 9 shows the query composed by App1 and its result, through which App1 deduces that Alice has also installed App2. Such a knowledge is useful is various ways.

App & Advertiser Can Identify Users: Linkability

Fig. 11 is the analytics report for a campaign we designed for a Page under our control. The analytics is available in real-time. The campaign was to invite users to follow our page on "Online Privacy". We could correlate the Likes (by Facebook users) on our page with the feed sequence report and find out which user has accessed the advertisement from what type of device and device OS version. This information greatly narrows down the types of attack payloads one can design to compromise a device. We could also access App user's Device Information. 4. Linkability: App and advertiser can identify their audience from the analytics data.

Analysis

Given that the trust level of FB and the app are not comparable, the question is how can FB control such data leaks? Some of the broad ways to contain these data leaks are:

1. By increasing the user's privacy policy specification scope from current user-object layers (refer Fig. 2) to all the layers of the platform, except the owner's layer. The current approach is fragmented and incoherent -that is, impact of changes at app layer on in-force settings at user layer is not communicated to users. The use of naturally understandable labels like "Friends", "Family" should be devised to categorize apps and advertisers, using which user can define her access policies. 2. By encrypting the analytics available to apps and advertisers such that per campaign a distinct but ciphered string is generated for each measurable event that cannot be used to track users across campaigns. Only the platform owner should link the events across campaigns. Thus, only one entity takes the accountability. 3. It appears that FB is trying to address this issue of linkability through the concept of scope id. A user is assigned a unique local ID, whose scope is limited to the context (App, Page) for which it is generated. For example, App1 will generate a scope id, which is different from the scope id generated by App2. Thus App1 and App2 or their parent cannot link users. However, we observed that, as of now, these scope IDs are resolving to the real user ID for whom the scope IDs were generated. For example, https://fb.com/100007460080360, https://fb.com/2051781625080487, and https://fb.com/1708004396124880 reveal the actual user.

Related Work & Discussion

Social networks like Facebook, Twitter, Snapchat have come to prominence in last decade because of their ability to engage users online such that users can carry out their social discourse 24x7, around the world. As the users get convenience and realtime engagement with their connections for free, the platform gets user insights. The platform recovers its operational costs by sharing the insights in plausibly privacypreserving fashion with advertisers https://fb.com/ads/about/. The rich data-sets generated by such social networks have ushered: advertising into a real-time persuasion industry [START_REF] Matz | Psychological targeting as an effective approach to digital mass persuasion[END_REF][START_REF] Youyou | Computer-based personality judgments are more accurate than those made by humans[END_REF][START_REF] Biddle | Facebook uses artificial intelligence to predict your future actions for advertisers[END_REF], communication into a precision tracking system [START_REF] Acar | Facebook Tracking Through Social Plug-ins[END_REF][START_REF]Facebook: About facebook pixel[END_REF], and social network platform into a rich user/content/relation labelling platform. All of these transformations have brought in tremendous challenges [START_REF] Michal | Facebook as a research tool for the social sciences: Opportunities, challenges, ethical considerations, and practical guidelines[END_REF] in terms of privacy of users. Privacy in social networks has been studied for quite some time and the research community had been highlighting privacy implication of connectivity [START_REF] Juels | Targeted advertising ... and privacy too[END_REF] even before the Cambridge Analytica fiasco. In [START_REF] Joshi | Security and privacy in online social networks: A survey[END_REF], a survey on security and privacy in social networks is presented that touches upon properties like: anonymization, de-anonymization, link predictability [START_REF] Gilbert | Predicting tie strength with social media[END_REF][START_REF] Kahanda | Using transactional information to predict link strength in online social networks[END_REF], information leakage, trust [START_REF] Patil | Privacy as a currency: Un-regulated?[END_REF], and link privacy [START_REF] Mittal | Preserving link privacy in social network based systems[END_REF]. In [START_REF] Fong | A privacy preservation model for facebook-style social network systems[END_REF], a privacy-preservation model for Facebook-style social network is proposed. Concepts for privacy-preservation in an app ecosystem, presented in [START_REF] Lee | Box: A platform for privacypreserving apps[END_REF] for mobile platforms, can be borrowed in FB's platform. FB's infrastructure [START_REF] Bronson | TAO: Facebook's Distributed Data Store for the Social Graph[END_REF] is a unique and not much is available in public. It remains interesting to see how Facebook adopts to the forthcoming European GDPR [START_REF]European Union: Data Protection -Rules for the protection of personal data inside and outside the EU[END_REF] regulation. The data generated across layers of Facebook platform is interlinked and once a data-tuple is associated with personal data, it becomes tainted and the tainted attributes propagate user's identity further. Under GDPR, when a Facebook user invokes her right to be forgotten/erased, it will be interesting to see how far the data deletion chain goes; since the data is linked across the ecosystem. We believe that Facebook will have to define context and scope of user information and the deletion of user data will happen within that pre-defined scope.

Conclusion

We presented the role Apps play in tracking and profiling users on Facebook platform. We have shown a few instances of App configurations that violated the underlying primary privacy settings of the user. Apps may use such shortcomings in policy enforcement for various reasons that can seriously undermine not only the privacy of users but also their security. From the study of ecosystem on FB's platform we showed that Apps potentially have as much visibility of its users' objects, connections, and interactions as FF itself. If a coherent access control model across layers of FB ecosystem is not deployed, then FB with its ad-hoc approach will remain a sophisticated surveillance system available to any user. People, including lawmakers, around the world are asking FB should it really be expanding into influencing people based on what it has captured as their profile? This conundrum is multiplied in the presence of millions of Apps on its platform. App permission management need to be made understandable and available as extensional/intensional labels similar to permission management at users layer. It is not hard to see why our recommendations based on our analysis demands expansion of the scope of user privacy policies across user layer, app layer, and beyond.

Fig. 1 .

 1 Fig. 1. Reachability and access in social graph of FacebookIn Fig.1, User2 can reach & access Post1 because there is a path and the access policy for Post1 is set as friends by its owner User1. Therefore, User2 could interact with Post1 by like action. User1 & User2 can access Post3 because User1 is a friend of friend of User3 and User2 is friend of User3. Post2 cannot be accessed by User1 because the custom policy allows access to all friends of User2 except User1. The Event created by User1 cannot be accessed by anyone except User1 because the access policy is only me. Thus, labels or lists are used to control access to the content owned/posted by Facebook users. Capabilities as access policies for Apps: FB Apps too are represented by nodes on social graph. However, Apps' traverse-ability on the social graph is limited to the immediate neighborhood of the user node consisting only the object nodes. In other words, the App can neither reach the friends of the user nor the other Apps installed by that user. What interactions the App can do in the user's neighborhood is determined by the set of permissions the user has allowed at the time of establishing the installed relationship with the user. There are 48 such permissions an App can obtain from its user. This is similar to capability lists in access control paradigm[START_REF] Levy | Capability-Based Computer Systems[END_REF]. In later sections we shall discuss which of these permissions to an App undermines user's privacy.The utility of social graph is not limited to representation of subjects, objects and their relationship but to also provide real-time updates about the changes in the neighborhood of the subject. Prioritization of updates according to their relevancy to a user based on users' past interactions on social graph is handled by NewsFeed algorithm; a core function of FB platform. How the App ecosystem helps it in achieving precision is explained below along with the other important components of platform.

Fig. 2 .

 2 Fig. 2. Access-hierarchy in the social graph

Fig. 4 .

 4 Fig. 4. Scenario: Alice has installed App1. Bob is Alice's friend

Fig. 7 .Fig. 8 .

 78 Fig. 7. Results of App1's query to Post1

Fig. 11 .

 11 Fig. 11. Campaign measurement report

Acknowledgments: This work is carried out as part of research at ISRDC (Information Security Research and Development Center), supported by Ministry of Electronics and Information Technology, Govt. of India (15DEITY00-004). The authors would like to thank Anshu S. Anand, Abhishek Behra, Ankush Dubey for their participation in discussions and experiments.