Dang Vinh Pham

Dogan Kesdogan

Towards Relations between the Hitting-Set Attack and the Statistical Disclosure Attack

The Minimal-Hitting-Set attack (HS-attack) is a well-known, provably optimal exact attack against the anonymity provided by Chaumian Mixes (Threshold-Mixes). This attack allows an attacker to identify the fixed set of communication partners of a given user by observing all messages sent and received by a Chaum Mix. In contrast to this, the Statistical Disclosure attack (SDA) provides a guess of that user's contacts, based on statistical analyses of the observed message exchanges. We contribute the first closed formula that shows the influence of traffic distributions on the least number of observations of the Mix to complete the HS-attack. This measures when the Mix fails to hide a user's partners, such that the user cannot plausibly deny the identified contacts. It reveals that the HS-attack requires asymptotically less observations to identify a user's partners than the SDA, which guesses them with a given bias. This number of observations is O( 1 p ) for the HSattack and O( 1 p 2 ) for the SDA, where p the probability that the attacked user contacts his least frequent partner.

Introduction

Anonymity in communication networks is an essential part of privacy. According to the definition of Pfitzmann et al. [START_REF] Pfitzmann | Anonymity, Unobservability, Pseudonymity, and Identity Management -A Proposal for Terminology[END_REF]: "Anonymity is the state of being not identifiable within a set of subjects, the anonymity set". Anonymity systems commonly seek to establish anonymity sets. The most influential work in this area is the Chaumian Mix (also known as Threshold-Mix) [START_REF] Chaum | Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms[END_REF] that forms the basis of many popular services offering anonymity in open and shared networks [START_REF] Raymond | Traffic Analysis: Protocols, Attacks, Design Issues, and Open Problems[END_REF], e.g. the Internet. A Threshold-Mix collects in every round a batch of b encrypted messages from distinct senders, who all contribute the same number of messages1 of identical size. It changes the appearance and time characteristics of the messages in the output batch to provide unlinkability between its input and output messages. Therefore, the senders and recipients that use the Mix in a round form the sender-and recipient-anonymity set in that round. This work investigates the fundamental limit of anonymity provided by the anonymity sets established by the Threshold-Mix with respect to a global passive attacker 2 . Analogous to the fundamental work of Shannon's unicity distance [START_REF] Shannon | Communication Theory of Secrecy Systems[END_REF], we focus on determining the number of observations of Mix rounds required to disclose a profile of an arbitrary user (say Alice) and thus to break the anonymity system. We consider the case that Alice's profile determines a static set of friends that are repeatedly contacted by Alice. It is motivated by the observation that human relationships tend to be persistent and by the fact that anonymity should also be provided in this case.

The immanent information leaked by the Mix to a global passive attacker is the observed set of senders and recipients using the Mix in a round. Traffic analysis attacks can learn Alice's profile by accumulating this information, although the Mix provides unlinkability between the input and output messages in a single round. We distinguish between two categories: combinatorial attacks [START_REF] Berthold | Dummy Traffic against Long Term Intersection Attacks[END_REF][START_REF] Agrawal | Probabilistic Treatment of MIXes to Hamper Traffic Analysis[END_REF][START_REF] Kesdogan | The Hitting Set Attack on Anonymity Protocols[END_REF][START_REF] Kesdogan | Fundamental Limits on the Anonymity Provided by the Mix Technique[END_REF][START_REF] Pham | A Combinatorial Approach for an Anonymity Metric[END_REF][START_REF] Pham | A Practical Complexity-Theoretic Analysis of Mix Systems[END_REF] and statistical attacks [START_REF] Danezis | Statistical Disclosure Attacks: Traffic Confirmation in Open Environments[END_REF][START_REF] Danezis | Better Anonymous Communications[END_REF][START_REF] Mathewson | Practical Traffic Analysis: Extending and Resisting Statistical Disclosure[END_REF][START_REF] Danezis | Statistical Disclosure or Intersection Attacks on Anonymity Systems[END_REF][START_REF] Danezis | Two-sided Statistical Disclosure Attack[END_REF][START_REF] Troncoso | Perfect Matching Disclosure Attacks[END_REF][START_REF] Pérez-González | Understanding Statistical Disclosure: A Least Squares Approach[END_REF][START_REF] Perez-Gonzalez | A Least Squares Approach to the Static Traffic Analysis of High-Latency Anonymous Communication Systems[END_REF]. Combinatorial attacks are basically concerned with the disclosure of exact information about Alice's profile that is consistent to the observations of the anonymity system. In contrast to that, statistical attacks are concerned with classifying whether a recipient is likely Alice's friend, or not. Their main advantage is the computational efficiency. However, combinatorial attacks (e.g., the HS-attack) can also be computational efficient [START_REF] Pham | A Practical Complexity-Theoretic Analysis of Mix Systems[END_REF] for non-trivial cases. The classification of recipients by statistical attacks can lead to a profile that deviates from Alice's profile, e.g., due to false-positive errors, which classify recipients as friends that are not Alice's friends, or due to omitting friends.

We consider in this work the Minimal-Hitting-Set attack (HS-attack) [START_REF] Kesdogan | The Hitting Set Attack on Anonymity Protocols[END_REF][START_REF] Pham | A Practical Complexity-Theoretic Analysis of Mix Systems[END_REF], a combinatorial attack that provably requires the least number of rounds to uniquely identify Alice's set of friends [START_REF] Kesdogan | Fundamental Limits on the Anonymity Provided by the Mix Technique[END_REF]. Therefore it determines the fundamental limit of anonymity provided by the Threshold-Mix. This number of rounds is dependent on the traffic distribution of the users and on the parameters of the anonymity system. We contribute a closed formula that estimates the mean of this number with respect to arbitrary distributions of Alice's communication and the parameters of the Threshold-Mix. This complements past works that could only model uniform traffic distributions [START_REF] Kesdogan | The Lower Bound of Attacks on Anonymity Systems -A Unicity Distance Approach[END_REF][START_REF] Kesdogan | Fundamental Limits on the Anonymity Provided by the Mix Technique[END_REF][START_REF] Pham | A Combinatorial Approach for an Anonymity Metric[END_REF], which are less realistic. Therefore, we are to the best of our knowledge the first to provide such an analytical estimate. Our estimate proves that the number of rounds to uniquely identify Alice's set of friends by the HS-attack is O( 1 p ), while it is O( 1 p 2 ) to classify all friends with some error rate by the SDA. The probability 0 < p < 1 denotes the least probability in the distribution of Alice's traffic to her friends.

Although this work mainly addresses the anonymity of the Threshold-Mix, it might be generalisable to analyse the anonymity of other Mix variants like the Pool-Mix [START_REF] Raymond | Traffic Analysis: Protocols, Attacks, Design Issues, and Open Problems[END_REF] that models Mixmaster. There are initial works towards this direction [START_REF] Pham | Towards Practical and Fundamental Limits of Anonymity Protection[END_REF]Chap. 5.2] that extends the HS-attack for the Pool-Mix and identifies some conditions for the disclosure of Alice's set of friends in that Mix.

Our analyses refer to high-latency Mix systems, as they seek to protect against global passive attackers. In contrast to these, low-latency systems like Tor [START_REF] Dingledine | Tor: The Second-Generation Onion Router[END_REF] and JAP [START_REF] Berthold | Web Mixes: A System for Anonymous and Unobservable Internet Access[END_REF][START_REF] Köpsell | Entwicklung und Betrieb eines Anonymisierungsdienstes für das WWW[END_REF] (as applied in practice) do not try to withstand a global attacker in their design.

Related Works

Our work is concerned with passive traffic analysis attacks [START_REF] Raymond | Traffic Analysis: Protocols, Attacks, Design Issues, and Open Problems[END_REF]. These rely solely on external traffic observations of an anonymity system.

The idea of combinatorial traffic analyses was first discussed by Raymond [START_REF] Raymond | Traffic Analysis: Protocols, Attacks, Design Issues, and Open Problems[END_REF] who also sketched the "intersection attack". Later two implementations of combinatorial approaches have been suggested in parallel, the Intersection attack [START_REF] Berthold | Dummy Traffic against Long Term Intersection Attacks[END_REF] and the Disclosure attack [START_REF] Agrawal | Probabilistic Treatment of MIXes to Hamper Traffic Analysis[END_REF]. The first approach identifies the recipient of a targeted sender for the case that this sender repeatedly contacts a recipient from a singleton [START_REF] Berthold | Dummy Traffic against Long Term Intersection Attacks[END_REF]. In contrast to this, the Disclosure attack uncovers an arbitrary large set of repeated contacts of the targeted sender, which is thus more general than the Intersection attack. These were followed by the HS-attack [START_REF] Kesdogan | The Hitting Set Attack on Anonymity Protocols[END_REF], that unambiguously identifies a user's communication partner set with a provably minimal number of observations [START_REF] Kesdogan | Fundamental Limits on the Anonymity Provided by the Mix Technique[END_REF]. 3 The limitation to all these attacks are that they require the solution of an NP-complete problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] to succeed, placing a high computational burden on the attacker. However, the most recent HS-attack that uses the ExactHS algorithm [START_REF] Pham | Analysis of the Anonymity Set of Chaumian Mixes[END_REF][START_REF] Pham | A Practical Complexity-Theoretic Analysis of Mix Systems[END_REF] achieves a mean polynomial computational complexity for many non-trivial Mix configurations as proved in [START_REF] Pham | A Practical Complexity-Theoretic Analysis of Mix Systems[END_REF]. Due to the optimal nature of the HS-attacks, the observations required to conduct them provide a measurement for the anonymity provided by Mix system. Estimates of this number were suggested in [START_REF] Kesdogan | The Lower Bound of Attacks on Anonymity Systems -A Unicity Distance Approach[END_REF][START_REF] Kesdogan | Fundamental Limits on the Anonymity Provided by the Mix Technique[END_REF][START_REF] Pham | A Combinatorial Approach for an Anonymity Metric[END_REF][START_REF] O'connor | Entropy Bounds for Traffic Confirmation[END_REF] for a simple model of uniformly distributed communication traffic.

Statistical attacks identify users through statistical patterns in traffic data. These attacks, introduced by the Statistical disclosure attack (SDA) [START_REF] Danezis | Statistical Disclosure Attacks: Traffic Confirmation in Open Environments[END_REF][START_REF] Danezis | Better Anonymous Communications[END_REF][START_REF] Mathewson | Practical Traffic Analysis: Extending and Resisting Statistical Disclosure[END_REF][START_REF] Danezis | Statistical Disclosure or Intersection Attacks on Anonymity Systems[END_REF][START_REF] Danezis | Two-sided Statistical Disclosure Attack[END_REF], and subsequently improved by the Perfect-matching disclosure attack (PMDA) [START_REF] Troncoso | Perfect Matching Disclosure Attacks[END_REF] and the Bayesian-interference [START_REF] Danezis | Vida: How to Use Bayesian Inference to De-anonymize Persistent Communications[END_REF], achieve significant increases in computational efficiency by relaxing the requirement for absolute correctness and allowing misclassification or omission of actors. The Least square approach [START_REF] Pérez-González | Understanding Statistical Disclosure: A Least Squares Approach[END_REF] attempts to analytically analyse the deviation between a user's profile and the classification provided by it for the Threshold-Mix. Provided the same Threshold-Mix model as in SDA [START_REF] Danezis | Statistical Disclosure Attacks: Traffic Confirmation in Open Environments[END_REF] (that is often used in combinatorial analyses, as well as in this work in Section 2) this approach is identical to the SDA. A succeeding extension [START_REF] Perez-Gonzalez | A Least Squares Approach to the Static Traffic Analysis of High-Latency Anonymous Communication Systems[END_REF] of this approach considers analogous analyses for the Pool-Mix model.

Structure

We introduce a simple model for the Threshold-Mix and the attacker, as well as the scheme of the HS-attack in Section 2. Section 3 estimates the mean least number of rounds to uniquely identify Alice's set of friends by a closed formula, based on this model. It compares this estimate with the number of rounds required by the SDA mathematically which shows that the SDA requires asymptotically more observations. Our analyses are confirmed and illustrated by simulations and mathematical evaluations in Section 4. Section 5 finally concludes the work and suggests future works. The proofs of all claims are provided in Appendixes A.

We consider the Mix system as a black box that outputs information that is visible to the attacker (i.e. the sender-anonymity sets and recipient sets), as illustrated in Fig. 1. It represents a generalised and simplified model of practical real-world Threshold-Mixes.

The Mix is abstractly described as follow:

-A communication system consists of a set of senders, S, a set of all recipients, R, and a Mix node as shown in Fig. 1. S and R represent all users with the ability to send or receive messages in the system 4 . If a sender s ∈ S communicates with a recipient r ∈ R, then we say that r is a recipient of s. -In each communication round, a subset S ⊆ S of all senders each send precisely one message to their recipients. Let R ⊆ R be the set of intended recipients. -We call S the sender-anonymity set, which is the set of all senders that may have sent a given message in a round. The recipient set R is the set of all recipients that have received a message in a round. -We label the size of the sender-anonymity set, |S |, as b which is also called the batch size. -The size of the recipient set, |R |, is less than or equal to b, as each sender sends exactly one message per round, but several senders may communicate with the same recipient. The size of the set of all recipients is |R| = u.

Attacker Model

We consider a global passive attacker that observes the traffic on all links between the user and the Mix in the network. Therefore, he can observe all sending and receiving events in the Mix system, so that the pairs of sender anonymity set and recipient set (S , R ) of every round is known to the attacker. The goal of the attacker is to compute, from a set of traffic observations, all possible sets of friends of a target sender Alice ∈ S. These possibilities form hypotheses for the true set of Alice's set of friends, H

A , which is assumed to be a fixed set of size

m = | H A |. We call a recipient r ∈ H A a friend; a recipient that does not communicate with Alice, r ∈ R \ H
A , is called a non-friend and r is simply called a recipient if no distinction is required. To clarify that a variable r ∈ R refers to a friend, it is also denoted by a, whereas it is denoted by n, if it refers to a non-friend.

The attacker focuses on revealing Alice's set of friends by observing only those pairs (S , R ), where Alice participates as a sender. Under this condition we refer to the corresponding recipient set R as an observation, O. The set of all observations collected during t communication rounds is referred to as the observation set OS = {O 1 , . . . , O t }.

Hitting-Set Attack

Alice's possible set of friends can be specified by computing all hitting-sets of size m with respect to the observation set OS collected by the attacker. A hitting-set is a set that intersects with all observations 5 in OS. A hitting-set is a minimal-hitting-set if no proper subset of it is a hitting-set. We call a hitting-set H a unique minimum-hitting-set 6 , if all hitting-sets H = H in OS fulfil the condition |H| < |H |.

By collecting sufficiently many observations, until OS contains a unique minimumhitting-set, the attacker can unambiguously identify Alice's set of friends H

A . The intuition behind this attack is that at least one of Alice's friends in H A appears in each observation (due to the definition of observations), while this does not hold for any set H ⊇ H

A . Therefore, if there are sufficiently many observations, then H A becomes a unique minimum-hitting-set. This attack is known as the Minimal-Hitting-Set attack (HS-attack) [START_REF] Kesdogan | The Hitting Set Attack on Anonymity Protocols[END_REF]. We refer in the remaining paper to its most recent version that uses the ExactHS algorithm to compute the minimal-hitting-sets [START_REF] Pham | A Practical Complexity-Theoretic Analysis of Mix Systems[END_REF]. The HS-attack repeats aggregating new observations and computing all minimal-hitting-sets of a given size m in the aggregated observation set OS. It is successively applied for m = 1, . . . , m. If m underestimates m, then there will be no hitting-set of size m after a sufficient number of observation. This can be detected by the HS-attack to consider a larger value of m in the HS-attack, until m = m and H A becomes a unique minimum-hitting-set. As proved in [START_REF] Kesdogan | Fundamental Limits on the Anonymity Provided by the Mix Technique[END_REF], the HS-attack requires the least number of observations to uniquely identify Alice's set of friends with respect to the Threshold-Mix.

Attack Scheme In our Mix and attacker model, the effort of identifying Alice's set of friends is dependent on the Mix parameters (u, b, m) and the distribution of the cover traffic and of Alice's traffic. The cover traffic is induced by the communication of senders other than Alice to the recipients in the observations. We use the term Mix configuration to refer to a combination of Mix parameters and these traffic distributions. The basic scheme underlying the analysis of the HS-attack is illustrated in Fig. 2.

Alice's traffic distribution is modelled by the probability mass function P A (a) for a ∈ H A , where a∈

H A P A (a) = 1.
The cover traffic distribution is indirectly modelled by the probability function P N (r), which is the probability that any b -1 senders (other than Alice) of a batch contact the recipient r ∈ R in an observation.

Mean Number of Observations for Unique Identification

It was proved in [START_REF] Kesdogan | Fundamental Limits on the Anonymity Provided by the Mix Technique[END_REF] that the 2×-exclusivity of Alice's set of friends is a necessary condition for the unique identification of Alice's set of friends. The number of observa- tions aggregated by the attacker, until the 2×-exclusivity condition is fulfilled provides a close estimate of the least number of observations to uniquely identify Alice's set of friends, as evaluated in [START_REF] Kesdogan | Fundamental Limits on the Anonymity Provided by the Mix Technique[END_REF].

We contribute a closed formula that estimates the expected least number of observations to fulfil k×-exclusivity, which is for the general case of k ∈ N. As defined in [START_REF] Kesdogan | Fundamental Limits on the Anonymity Provided by the Mix Technique[END_REF], a friend a ∈ H A is exclusive, if there is an observation O that contains only a as an Alice's friend. This means O ∩ H A = {a} and we call O the observations that contains a exclusively. A friend a ∈ H A is k×-exclusive, if it appears at least k times exclusively in observations, or at least one time alone in an observation (i.e. there is an observation O = {a}). The k×-exclusivity is fulfilled, if all Alice's friends are k×-exclusive.

Mean Number of Observations for k×-Exclusivity

We estimate the mean of the least number of observations E(T k×e ) for k×-exclusivity by decomposing this mean in two sub means and estimating those sub means. These are the estimates of the following means 7 :

-The mean least number of observations E(T k× ), until Alice contacts all her friends at least k times. This is regardless whether the observations are exclusive, or not. -The maximum of the mean least number of times E(T e,a ) Alice has to contact a given friend a ∈ H A , until it is exclusive, with respect to all Alice's friends a ∈ H A . For each given friend a ∈ H A , this mean only accounts those observations, where Alice contacts a , and the maximum of that mean is max a ∈ H A E(T e,a ).

The variables T k×e , T k× and T e,a are random variables for: the least number of observations to fulfil k×-exclusivity, the least number of observations until Alice contacts all friends at least k times and the least number of times Alice has to contact a friend a, until it is exclusive. We define E(T e ) = max a ∈ H A E(T e,a ) and set for a = argmax a ∈ H A E(T e,a ), the equality T e = T e,a . Note that the value of T k× is dependent on Alice's traffic to her friends, but is independent of the traffic of other senders. In contrast to that, the value of T e,a depends on whether any sender other than Alice contacts any friend in H A \ {a} in observations where Alice contacts a. This is dependent on the cover-traffic, but is independent of Alice's traffic. Therefore, T k× and T e are statistically independent.

Claim 1 Let E(T e,a ) be the mean least number of times Alice has to contact a friend a ∈ H

A ,8 until a is exclusive and E(T e ) = max a∈ H A E(T e,a ). Let E(T k× ) be the mean least number of observations until Alice contacts all her friends at least k times9 , for k ∈ N. The mean least number of observations until all Alice's friends are k×exclusive is estimated by:

E(T k×e ) ≤ E(T k× )E(T e ) ≈ 1 p (ln m + γ) + (k -1) 1 p ln ln m u -(m -1) u 1-b , (1)
where p = min a∈ H A P A (a) and γ ≈ 0, 57721 is the Euler-Mascheroni constant.

We conclude by ( 1) that the 2×-exclusivity of all Alice's friends requires on average

1 p (ln m + γ) + 1 p ln ln m u-(m-1) u 1-b
observations. The proof of this claim can be found in Appendix A.

Relation to Statistical Disclosure Attack

While the HS-attack aims at exact identification of friends; statistical attacks, as introduced by the SDA, cf. [START_REF] Danezis | Better Anonymous Communications[END_REF], aim at correct classification of friends with some probabilities. Although these two approaches are orthogonal, we can now analytically compare the number of observations required by these attacks by [START_REF] Adamic | Zipf's Law and the Internet[END_REF].

The SDA [START_REF] Danezis | Better Anonymous Communications[END_REF] considers the classification of each friend as a signal to noise problem.

It virtually interprets Alice's traffic volume to a friend a ∈ H

A as a signal and the cumulative traffic volume of other senders to any recipient r ∈ R as a noise. Let t be the number of observations and p be the probability that Alice contacts a in an observation, then the mean signal to a is pt with the variance p(1 -p)t. To simplify the maths it is assumed that every non Alice sender contacts a recipient uniformly distributed, so that 1 u is the probability that r is contacted by a single non Alice sender. As there are b -1 non Alice senders in a batch, the mean noise to a recipient r after t observations is P N (r) = 1 u (b -1)t, with the variance 1 u (1 -1 u )(b -1)t. The SDA classifies a friend a better than a random guess, if the mean signal to a is higher than the sum of the standard deviation of the signal and of the noise to a [START_REF] Danezis | Better Anonymous Communications[END_REF]. This is a necessary condition to distinguish the signal from the noise to the same recipient. The least number of observations, such that this condition is fulfilled with a probability determined by a confidence parameter l is, cf. [START_REF] Danezis | Better Anonymous Communications[END_REF],

1 p 2 l 2 u -1 u 2 (b -1) + u -1 u 2 (b -1) + p 2 ( 1 p -1) 2 . ( 2
)
Setting l = 2, l = 3 in (2) leads to a classification with a true-positive rate of 95%, respectively 99%. Let us set p = min a∈ H A P A (a), as the recipient which is least frequently contacted by Alice dominates the number of observations to classify all friends. In the case that Alice's traffic is uniformly distributed, p = 1 m as assumed in [START_REF] Danezis | Better Anonymous Communications[END_REF].

We can now compare ( 2) with (1) (for k = 2 ) with respect to the probability p by fixing all other parameters u, b, m, l; they are identical in both equations. This reveals that the SDA requires O( 1 p 2 ) observations to classify all Alice's friends while the HS-attack only requires O( 1p ) observations to uniquely identify all Alice's friends. This relation between the HS-attack and the SDA is visualised for some examples in Section 4.

Evaluation

This section illustrates the closeness of the estimate of the least number of observations to identify Alice's friends and compares this with the number of observations required by the SDA.

The first task applies the 2×-exclusivity evaluation an the HS-attack on simulated random observations of a Threshold-Mix. These empirically measure the least number of observations for the 2×-exclusivity and the identification of all friends. We use them to illustrate the closeness of the corresponding mathematical estimate by [START_REF] Adamic | Zipf's Law and the Internet[END_REF].

The second task compares the estimated mean number of observations required by the HS-attack and the SDA for some Mix configurations considered in the simulations. This illustrates that SDA requires asymptotically more observations than the HS-attack.

The traffic distributions that we use to model Alice's traffic and the cover traffic in all simulative and mathematical evaluations are described next.

-Alice contacts in each observation a friend that is randomly drawn from a Zipf(m, α)

distribution of H A . The probability that she contacts her i-th most frequent contact is P A (a i ) = P Alice's traffic is modelled by a Zipf distribution, as it is known to closely model e-mail and internet traffic [START_REF] Adamic | Zipf's Law and the Internet[END_REF][START_REF] Breslau | Web Caching and Zipf-like Distributions: Evidence and Implications[END_REF][START_REF] Glassman | A Caching Relay for the World Wide Web[END_REF]. An example of this distribution is illustrated in Fig. 3 for distinct values of α, provide that Alice has m = 23 friends. The cover-traffic is for simplicity modelled by a uniform distribution that represents a bound of the real distribution. Note that an observation contains the recipients of senders who randomly communicate in the same round as Alice and is therefore a random variable. The distribution of this random variable and thus the number of observations to identify Alice's friends is dependent on the overall distribution of the cover-traffic and of Alice's traffic, regardless of differences in the communication distribution of the individual senders of the cover-traffic.

Therefore we assume that all non-Alice senders behave the same to simplify the maths and the simulation.

The HS-attack is successful (or succeeds) if it uniquely identifies Alice's set of friends H

A . For a given Mix configuration, the simulation generates new random observations until the HS-attack is successful and we call this an experiment. The average number of observations required by an attack is therefore the mean of the number of observations of all successful attacks (i.e. of all experiments with the same Mix configuration). Note that the results of these experiments, i.e., the number of observations to succeed the HS-attacks, are identically distributed independent random variables with unknown positive mean µ and standard deviation σ. By the law of large numbers, the empirical mean of the experiments' results approaches µ, while its standard deviation approaches 0, for large number of experiments 10 . To ensure that our results are statistically significant, experiments with the same Mix configuration are repeated until 95% of the results fall within an interval of 5% around the empirically observed mean. Every experiment is repeated at least 300 times and no experiment is dropped. We observed that most of our experiments require no more than 300 repeats to fulfil the statistical significance condition and therefore chose this number as a lower threshold. It is necessary to force a sufficiently large least number of repetitions to avoid cases like, e.g., after running two experiments, both results are within 5% around the empirical mean, which would be too few to represent a reliable measure. The plots provide these comparisons for distinct Mix configurations that are modelled by the parameters u, b, m, α. The y-axis always shows the mean number of observations, while the x-axis vary one of the parameters u, b, m, α. We can observe that the estimate (1) provides reasonable approximations, even for the cases that Alice's traffic is non-uniformly distributed (i.e. α > 0). According to [START_REF] Adamic | Zipf's Law and the Internet[END_REF][START_REF] Breslau | Web Caching and Zipf-like Distributions: Evidence and Implications[END_REF][START_REF] Glassman | A Caching Relay for the World Wide Web[END_REF], the value of α ≈ 1 typically models a user's Zipf(m, α) distributed traffic in the Internet. Due to a lack of experiences with running high-latency anonymity systems in a large user base, we have no authentic empirical values for the parameters u, b. Therefore, we choose parameter ranges that would be reasonable for JAP. JAP was designed to be close to the Chaum Mix, so that it contains batch mixing capabilities [START_REF] Köpsell | Entwicklung und Betrieb eines Anonymisierungsdienstes für das WWW[END_REF]. However, collecting messages for a batch increases the latency that is yet not accepted by many JAP users [START_REF] Köpsell | Entwicklung und Betrieb eines Anonymisierungsdienstes für das WWW[END_REF], so that this function is disabled in favour of low-latency. Therefore we refer to JAP as a lowlatency system. The total number of users that repeatedly use the Dresden-Dresden JAP cascade is about 50000 [START_REF] Köpsell | Entwicklung und Betrieb eines Anonymisierungsdienstes für das WWW[END_REF] in 2009, therefore we consider u in the range up to 60000. In every minute, the cascade relays on average 17000 HTTP messages [START_REF] Köpsell | Entwicklung und Betrieb eines Anonymisierungsdienstes für das WWW[END_REF], which are 283 messages per second. JAP allows users to send multiple parallel messages, so that the number of messages per second would be lower, if every user is only allowed to send one message in a Mix round to prevent linking a communication by packet counting, as in the Chaum Mix [START_REF] Chaum | Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms[END_REF]. Simulating batch sizes of up to 85 thus appears to be of reasonable order.

Number of Observations

Required by HS-Attack vs. SDA We illustrate that the SDA requires a number of observations that is by the factor of O( 1 p ) higher than those required by the HS-attack, where p is the least probability in the distribution of Alice's friends. The cover-traffic is uniformly distributed. The tables list the estimated number of observations to succeed HS-attack based on (1) labelled by (2x-excl-est) and to classify Alice's friends with a true-positive rate of 95% by the SDA based on (2) (for l = 2) labelled by (SDA 95% ). We observe that the number of observations required by the SDA increasingly exceeds that required by the HS-attack for increasing value of α, as p decreases with increasing α.

Note that (2) solely considers the true-positive rate of the SDA; the classification of a given friend as a friend with a certain rate (e.g. 95% in Table 1). However, the false-positive rate can be larger. When SDA terminates, there is thus some number of non-friends that are classified as friends, whereas there is a unique identification of Alice's set of friends, when HS-attack terminates.

Conclusion

Anonymous communication systems seek to embed senders and recipients in anonymity sets to hide their communication relations. We measure in this work the anonymity provided by the anonymity sets constructed by the Threshold-Mix to analyse its limit of achievable protection. This limit is determined by the least number of observations of the Mix rounds, until Alice's set of friends can be exactly identified, so that the protection provided by the Mix is repealed. Alice's set of friends can be exactly identified with the least number of observations by the HS-attack [START_REF] Kesdogan | Fundamental Limits on the Anonymity Provided by the Mix Technique[END_REF].

We contribute by (1) (for k = 2) the first closed formula that estimates the mean least number of observations to uniquely identify Alice's set of friends for arbitrary distribution of her traffic. It reveals that this number is O( 1 p ), whereas the SDA requires O( 1 p 2 ) observations to classify Alice's friends with some error. The variable p = min a∈ H A P A (a) denotes the least probability in the distribution of Alice's communication to her friends 11 . This implies that the difference between these two number of observations is for more realistic (non-uniform) distribution of Alice's friends notably higher than for the uniform distribution considered in past mathematical analyses [START_REF] Kesdogan | Fundamental Limits on the Anonymity Provided by the Mix Technique[END_REF][START_REF] Danezis | Statistical Disclosure Attacks: Traffic Confirmation in Open Environments[END_REF]. Section 4 experimentally confirms this difference for some zipf distributed communication of Alice which is known to model real e-mail traffic distribution [START_REF] Adamic | Zipf's Law and the Internet[END_REF][START_REF] Breslau | Web Caching and Zipf-like Distributions: Evidence and Implications[END_REF][START_REF] Glassman | A Caching Relay for the World Wide Web[END_REF]]. Alice's set of friends can thus be exactly identified with a number of observations that is asymptotically less than required by the inexact SDA. This exact identification can be even computational feasible for non-trivial cases by using the HS-attack [START_REF] Pham | A Practical Complexity-Theoretic Analysis of Mix Systems[END_REF].

Our analysis shows that the mean least number of observations for the exact identification is lowest, if Alice's friends are uniformly distributed. Past works [START_REF] Kesdogan | The Lower Bound of Attacks on Anonymity Systems -A Unicity Distance Approach[END_REF][START_REF] Kesdogan | Fundamental Limits on the Anonymity Provided by the Mix Technique[END_REF][START_REF] O'connor | Entropy Bounds for Traffic Confirmation[END_REF][START_REF] Pham | A Combinatorial Approach for an Anonymity Metric[END_REF][START_REF] Pham | A Practical Complexity-Theoretic Analysis of Mix Systems[END_REF] that measure the anonymity of the threshold Mix by the time of exact identification assume for simplicity that uniform distribution. Therefore, we can now confirm that those works address a lower bound of the anonymity of Alice's set of friends. This work explores the least number of rounds of the Threshold-Mix, such that the attacker's uncertainty about Alice's set of friends becomes 0, as a measure of anonymity. Future works might generalise this approach to quantify the attacker's uncertainty about the possible Alice's set of friends with respect to the number of observed rounds of some Mix. This would enable a more fine granular anonymity measure beyond the time of exact anonymity disclosure (i.e., 0 uncertainty), so that we can also analyse the anonymity provided by other Mix variants like the Pool-Mixe. Pool-Mixes [START_REF] Raymond | Traffic Analysis: Protocols, Attacks, Design Issues, and Open Problems[END_REF] operate like the Threshold-Mix, but they can delay the relay of a random selection of messages in the Mix, as implemented in Mixmaster. Therefore, an attacker might observe a recipient set that misses the user that Alice contacts in the observed round. Such observations induce additional uncertainty about the possible Alice's set of friends in the generalised anonymity quantification approach so that the attacker's uncertainty might remain above 0.

Fig. 1 .

 1 Fig. 1. Mix model.

5Fig. 2 .

 2 Fig. 2. Analysis scheme: Variables a, r represent arbitrary friend a ∈ H A and recipient r ∈ R.

  m,α z (i) = i -α m l=1 l -α , where P m,α z (i) is the probability mass function of the Zipf(m, α) distribution. Note that H A is uniformly distributed if α = 0. -The remaining b -1 recipients of the cover traffic in an observation are drawn uniformly from the set of |R| = u possible recipients. This means that for all r ∈ R, the probability that any of the b -1 senders other than Alice contacts r in an observation is P N = 1 -( u-1 u ) b-1 .

Fig. 3 .

 3 Fig. 3. Zipf(m, α) distribution of Alice's friends, for m = 23.

Fig. 4 .

 4 Fig. 4. Mean number of observations: to succeed HS-attack (HS) and to fulfil 2×-exclusivity (2x-excl) versus estimated mean for 2×-exclusivity (2x-excl-est).

  Number of Observations Required by HS-attack Fig. 4 visualises the empirical mean number of observations to succeed the HS-attack, labelled (HS) and to fulfil 2×exclusivity labelled (2x-excl), obtained from simulations. These are compared with the estimate (1) of the mean of the least number of observations for 2×-exclusivity, labelled (2x-excl-est), which is: E(T 2×e ) ≈ 1 p ((ln m + γ) + ln ln m) 1 -(m-1) traffic is Zipf(m, α) distributed, we get p = min a∈ H A P A (a) = P m,α z (m).

u

  = 400, b = 10, m = 23, in Zipf(23, α) distribution u = 20000, b = 50, m = 40, varying α α p 2x-excl-est SDA 95% in Zipf(40, α) distribution Table 1 provides evaluations for the Mix parameters (u = 400, b = 10, m = 23), respectively (u = 20000, b = 50, m = 40) and Zipf(m, α) distributed Alice's traffic.

Table 1 .

 1 Estimated number of required observations: HS-attack (2x-excl-est) versus SDA with 95% true-positive classification (SDA 95% ).

Otherwise, it would be trivial to identify a pair of sender and a recipient by the number of their exchanged messages in a round.

This attacker can observe any link in the network and can thus observe the anonymity sets.

The intersection attack is identical to the special case of the HS-attack, where a targeted sender has exactly one recipient.

This definition allows for cases of S = R, as well as S = R, i.e. the sender and recipient set might be distinct or identical.

This only refers to observations, in that Alice contacts a, that is OSA[a].

This is regardless whether the observations are exclusive, or not.

This law applies regardless of the magnitude of the variation of the results of single experiments.

If Alice's friends are uniformly distributed, then p = PA(a) = 1 m for all a ∈ H A , otherwise p < 1 m .

A Proof of Claim

Proof (Claim 1). Let us consider the mean number of observations, such that all Alice's friends are observed at least k times exclusively, for the case that the cover-traffic is uniformly distributed. This uniform cover-traffic implies E(T e,ai ) = E(T e,aj ) = E(T e ) for all a i , a j ∈ H

A . Since the random variables T k× and T e are statistically independent, the mean number of observations until every friend is observed at least k times exclusively, equals in this case: E(T k× )E(T e ).

Due to the definition of k×-exclusivity, observing every Alice's friend at least k times exclusively implies k×-exclusivity. Therefore, we deduce the following:

We now estimate E(T k×e ) and E(T e ), for arbitrary distribution of Alice's traffic and cover-traffic.

E(T e ): Assume that every recipient r ∈ R, |R| = u is contacted uniformly distributed by any (b -1) non-Alice senders in every observation, then the probability that r is contacted by any non-Alice sender is

A and the remaining (b -1) non-Alice senders do not, then a j is exclusive. That probability is P e (a j ) = ( u-(m-1) u ) b-1 . The random variable T e,aj is geometrically distributed with mean:

Therefore E(T e ) = E(T e,aj ) for all a j ∈ H A , in the case of uniform cover-traffic distribution. This E(T e ) serves as an upper bound for E(T e,aj ) of all cases, where r ∈ R is non-uniformly contacted with P N (r ) and max r ∈ H A {P N (r )} ≤ P N , for any recipient sets R ⊃ H

A . E(k×): Let Alice contacts a friend a ∈ H A (arbitrarily distributed) according to the probability mass function P A (a), where a∈ H A P A (a) = 1. Determining the mean number of observations E(T k× ), until Alice contacts all her friends at least k times is equivalent to the general coupon collector problem (CCP) [START_REF] Brayton | On the Asymptotic Behavior of the Number of Trials Necessary to Complete a Set with Random Selection[END_REF]. In that problem, there is a source of infinitely many coupons of the m types represented in H A , where P A (a) is the probability of drawing a coupon of type a from the source. The general CCP is to determine the mean least number of coupon collections E(T k× ) to obtain all m coupon types. The following equality was proved for large value of m (i.e. m → ∞) in [START_REF] Brayton | On the Asymptotic Behavior of the Number of Trials Necessary to Complete a Set with Random Selection[END_REF]:

The variables in this equation have the following meaning in our context:

The last estimate result from approximating γ1 (k-1)! and κ by its upper bound 1. Applying the estimates (4) and (5) to inequality (3) result in (1) and completes the proof.


Esra Erdin

Eric Klukovich

Gurhan Gunduz

Mehmet Hadi Gunes

POSN: A Personal Online Social Network

Keywords: Decentralize, Phone-to-phone, Privacy, Social Networks All {All Wall } Key Family {Family Wall } Key School {School Wall } ...... Video2 Link Key Video2 ...... Archive2 Link Key Archive2 Archive1 Link Key Archive1 ..... Port, LastOnline, .. All-Index {All Index } Key Family-Index {Family Index } Key Bob All-Index {All Index }

A growing concern for end users of Online Social Networks (OSNs) is the privacy and control of user data due to the client-server architecture of the current ecosystems. In this paper, we introduce a privacy preserving decentralized OSN platform, which mimics real life social interactions. In particular, we decentralize the OSN platform and give direct control of the information to the user. The distributed platform removes central authorities from the OSN and users share their content only with intended peers through mobile devices. This decentralized system ensures that interaction happens between friends and third parties cannot access the user content or relationships. To be able to efficiently share objects and provide timely access in the POSN platform, we take advantage of free storage clouds to distribute encrypted user content. The combination of phone-to-phone applications with cloud infrastructure would address the availability limitation of peer-to-peer systems, while enjoying the benefits of peer-to-peer systems, such as no central authority and scalability.

Introduction

Online social interactions are an integral part of our daily activity. As indicated in Milgram's experiment, we live in a small-world [START_REF] Dodds | An experimental study of search in global social networks[END_REF][START_REF] Milgram | The small world problem[END_REF]. Connecting this small-world in the digital world has been a challenge and has been addressed in various ways. OSNs enable frequent social interaction and expansion of knowledge or gossip. The emergence of OSNs sparked a major reform in information spread and how users interact with each other. From data to search to social interactions, users around the world are now more deeply connected to the Internet as user-generated content undergoes perpetual growth and expansion.

The client-server architecture of the current OSN ecosystems have raised privacy concerns. In general, users have to trust corporations (and governments) with their personal data when using OSNs. OSNs collect considerable amount of personal information about their clients and provide new services based on collected or derived information. For instance, a provider can filter advertisements based on user profile or user's circle (i.e., friends). Additionally, OSNs have predictive capabilities about the users as they continuously gather user data. Researchers have tried to address privacy concerns by user-based key management [START_REF] Baden | Persona: An online social network with user-defined privacy[END_REF][START_REF] Feldman | Social networking with frientegrity: Privacy and integrity with an untrusted provider[END_REF][START_REF] Guha | Noyb: Privacy in online social networks[END_REF][START_REF] Tootoonchian | Lockr: Better privacy for social networks[END_REF], peer-to-peer architectures [START_REF] Buchegger | Peerson: P2p social networking: Early experiences and insights[END_REF][START_REF] Cutillo | Safebook: Feasibility of transitive cooperation for privacy on a decentralized social network[END_REF][START_REF] Durr | Vegas -a secure and privacy-preserving peer-to-peer online social network[END_REF][START_REF] Graffi | Lifesocial.kom: A p2p-based platform for secure online social networks[END_REF][START_REF] Narendula | My3: A highly-available p2p-based online social network[END_REF][START_REF] Nilizadeh | Cachet: A decentralized architecture for privacy preserving social networking with caching[END_REF][START_REF] Sharma | Supernova: Super-peers based architecture for decentralized online social networks[END_REF][START_REF] Wilson | Privacy, availability and economics in the polaris mobile social network[END_REF], or decentralized platforms [START_REF]Friendica: The internet is our social network[END_REF][START_REF]Diaspora: community-run, distributed social-network[END_REF][START_REF] Liu | Confidant: Protecting osn data without locking it up[END_REF][START_REF] Seong | Prpl: A decentralized social networking infrastructure[END_REF][START_REF] Shakimov | Visa-vis: Privacy-preserving online social networking via virtual individual servers[END_REF][START_REF] Stuedi | Contrail: Enabling decentralized social networks on smartphones[END_REF][START_REF] Yeung | Decentralization: The future of online social networking[END_REF][START_REF] Zhang | Building confederated web-based services with priv[END_REF]. In general, peer-to-peer OSN architectures suffer from inefficiency due to high churn rate of users. Even though some of the proposed decentralized platforms utilize cloud resources, they rely on compute clouds which are typically fee-based and could analyze user data.

In a decentralized architecture, efficient sharing and timely access of objects play a vital role [START_REF] Narayanan | Ensuring access control in cloud provisioned healthcare systems[END_REF]. In two-way friendship OSNs, users typically access a small number of objects among vast number of posts, with many users accessing only recently posted objects. Additionally, updates by a user must be available to his/her friends in a timely manner regardless of whether the posting user has become offline. To address these challenges, we take advantage of free storage clouds to distribute encrypted user content. Even though there are OSNs that utilize cloud, they either use it as an execution platform with plaintext or as a backup store to central servers. To best of our knowledge, this is the first study to promote a decentralized OSN relying on mobile devices and storage clouds with no central server. While peer-to-peer systems require a peer to be online for data exchange, we utilize cloud to greatly enhance data availability. The free cloud storage services allows POSN to function through user clients such as smart phone or tablet apps with no infrastructure of its own. Moreover, smart phones and tablets have considerable computing capabilities that is utilized to provide direct interaction between users. The main contribution of this paper is the combination of phone-to-phone applications with cloud infrastructure to address the main limitation of peer-to-peer systems, i.e., availability, due to high churn rate while enjoying the benefits of peer-to-peer systems, i.e., no central authority and scalability. This approach can be expanded to provide other forms of social communications where data privacy is a concern. In proposed POSN, each user's data is kept in a separate location and the owner is in charge of granting access to his or her friends. The cloud can provide this storage resource free of charge. Users upload encrypted data to their cloud and fetch data from the cloud's of their friends (see Section 5). Cloud providers could only observe encrypted data and share this encrypted data with users that have access to it as shown in Figure 2.

In order to find online friends, we need to check their cloud location file where their IP address and Port number is stored. In order to access posted In general, walls containing posts will be automatically downloaded but the multimedia content and comments will be downloaded only when a user views it. Even though downloading a file is straightforward, checking hundreds of user's files across different clouds is not efficient. Knowing if your friends have a new content will speed up the process. Online friends can speed up the process as they can share their knowledge about common friends (see Section 8).

In order to see whether clouds can provide communication efficiency of OSNs, we compared the file upload/download timing of popular OSNs (i.e., Facebook and Google+) with popular clouds (i.e., Dropbox, Google Drive, Sky Drive, Mediafire, Copy Cloud). Figure 3 presents the average upload and download timing of 10 measurements using an Android tablet over WiFi at our campus. In these experiments to reduce bias due to background processes and radio status, we closed all unnecessary services, performed a small file transfer to ensure radio is on, and kept the measurement process in the foreground. As Facebook resizes and compresses pictures, we were not able to download a picture of about 1MB even though larger pictures were uploaded. Hence, 1MB and larger files are videos doubling in size whereas below 1MB are pictures resized by Facebook. We obtained comparable performances in our experiments at 10 different WiFi locations throughout the city as well (results not shown due to space limits).

When uploading a photo, Facebook becomes progressively worse for pictures (likely due to re-rendering) but is comparable to the rest for videos. Google+ seems worse than all but one cloud provider. Our in depth analysis revealed that the Google+ API streams the videos, therefore the total download time is considerably increased. Overall, upload performances are similar as videos of 1MB and larger are uploaded. Download performance of OSNs are also better than clouds for files smaller than 1MB but are comparable for larger sizes. Even though this might impact interactive communications such as chat, performance difference of 1 sec or less would not be considerable for humans to affect adaptation of POSN. These experiments shows there is no significant performance difference when uploading/downloading a file to/from an OSN or a cloud provider.

Additionally, we performed measurements with 7 mobile phones over 3G in the Reno/SFO area. Figure 4 presents the ratio of Dropbox over Facebook performance for transfer of the same file by the phone around the same time.

As each volunteer did not complete the same number of experiments, we present each point separately. Note that points above 1 indicate OSN is faster than cloud. Overall, we observe the OSN can be fast up to 10x or cloud can be fast up to 9x while in most cases OSN is faster. We believe such considerable performance variation in data transfers is due to the 3G traffic rate instability. Establishing friendship between interested people in a decentralized system is a challenge. Hence, in POSN, we need to rely on other mechanisms in establishing friendship and ensuring identities. POSN platform relies on users' existing contacts, i.e., phone numbers and email addresses, in order to establish friendship and ensure identities. POSN platform can exchange emails or SMS messages between users to establish certificates/tokens that will inform the cloud location and public keys of friends as in Figure 5. As the temporal identities need to be unique, POSN generates identities based on hash of email addresses or phone numbers. When a person wants to establish friendship with a contact, s/he sends a URI containing her/his identity, public key, and profile location. The receiving person may then respond with her/his information if s/he wants to establish a link. Note that, both messages should be exchanged via e-mail or SMS so that real identities are ensured. This approach is also in line with our focus on personalized OSN as the links in our network should correspond to real life friendships between users. Note that, a malicious email provider might tamper with message and this is a research challenge we will focus on. To address this issue, public key certificates can be obtained or secure e-mails can be sent with PGP to assure validity of public keys against potential man-in-the-middle attackers. Distributed key agreement protocols can also be utilized to verify public keys among friends [START_REF] Ateniese | New multiparty authentication services and key agreement protocols[END_REF][START_REF] Perrig | Efficient collaborative key management protocols for secure autonomous group communication[END_REF][START_REF] Rafaeli | A survey of key management for secure group communication[END_REF].

Data Dissemination

POSN utilizes cloud storage system where users upload their content to a cloud and obtain wall posts of friends from their clouds. Even though one might think the overhead would be prohibitive (e.g., Facebook has 1.2 billion users), each user needs to manage content of their friends. On average, a Facebook user has 130 friends (while the number is 214 in the United States) [START_REF] Kirschner | Facebook and academic performance[END_REF] who are typically clustered into 12 groups [START_REF] Wilson | A review of Facebook research in the social sciences[END_REF]. We keep users in groups similar to most OSNs and have a wall post file for each group in addition to individual wall file. When the user makes a post it is appended to the appropriate group.

To better understand how data is being generated in OSNs, we monitored the activities of 16 Facebook users and their circles (i.e., posts shared by their friends) for 15 days with explicit permission from the users. On average; for analyzed users, number of friends is 220 (146 of whom used a smart device) who are divided into 9 groups. Similarly, per day, average number of text posts in the user's circle is 53, links is 37, pictures is 51, videos is 7, and chat messages is 85. The monitored users themselves uploaded just a total of 25 pictures and 2 videos in total over the same period.

Figure 6 shows how multimedia (i.e., pictures and videos) posts are generated by circles of each user. We observe majority of photos are less than 100KB while none is greater than 1MB. Likewise, majority of videos are less than 10MB but exceptionally there are videos larger than 100MB. As multimedia can be very large, the multimedia should be distributed through the cloud where the user lets online friends know that there is a new post with a direct link to download data from the cloud. Otherwise, the user would send multiple copies of the file (i.e., as many as the number of online friends). Figure 7 shows the sender bandwidth overhead for a user if s/he was to post her/his friend's posts. It indicates that user overhead considerably increases if the user directly sends multimedia files to online friends. For sending average file of 93KB to 90 online friends, the user would need to send over 8MB data. Hence, rather than sending multiple copies of the file, the poster notifies online friends about the post that has been uploaded to the cloud.

Alice's Cloud

Multimedia Folder(s) Moreover, Figure 8 shows the frequency of non-multimedia posts (e.g., wall update, link, like, and comment) for the circle of a user. In the figure, points show the average number of posts when x number of friends were online and the line is the moving average. On average, during a session, a user posts 66 nonmultimedia content while there are on average 81 online friends. Even though, cloud is utilized for efficient distribution of content, non-multimedia posts can directly be delivered to online friends.

E Key!Video1 (Video1) E Key!Video2 (Video2) …. E Key!Picture1 (Picture1) E Key!Picture2 (Picture2) E Key!Picture3 (Picture3) …. … Alice's Repository

Privacy Protection

In order to provide security and privacy in the POSN platform, data is encrypted before uploading into the cloud. Every user in the POSN would have a public key. This public key is exchanged at the time of friendship establishment and shared through the cloud. However, this would be very inefficient as a separate wall post would be made for each friend. Instead, POSN keeps a wall for each group as most users forms clusters of friends [START_REF] Kardes | Six Degrees of Separation among US Researchers[END_REF][START_REF] Naruchitparames | Friend recommendations in social networks using genetic algorithms and network topology[END_REF]. Therefore, each group needs a symmetric key for the group wall, and these keys need to be exchanged securely. In order to handle the access to the wall post that belongs to a specific group, the poster embeds a symmetric key into the file as shown in Figure 9. Using this mechanism, POSN ensures security without adding considerable overhead to the system since the symmetric keys do not need to be exchanged but rather recovered through public keys. Furthermore, as multimedia files might be posted to different groups, we encrypt multimedia files with individual symmetric keys, which are shared in the wall post for the group. Each user's repository provides group keys encrypted with each user's public key along with the comment file for that user (see Section 6 for commenting). In Figure 9, Bob just has access to the "All" group while Chris has access to "All" and "Family" groups. As the symmetric keys for groups can be updated, the Key ver indicates the version number of the keys. Note that, each user has a different repository file and hence can not see other's by default. In order to assess encryption overhead, we analyzed performance overhead of encryption (using standard Android AES library) using an Android tablet over WiFi at our campus. Figure 10 presents performance ratio of Dropbox over Facebook where blue points indicate transfer without encryption and red points indicate transfer with encryption for average of 10 measurements. Overall, we observe that encryption increases the ratio on an average from 1.40 to 1.71, an average of 22% increase in time with encryption. This results are encouraging as the extra encryption is not adding significant delay overhead.

Commenting

Commenting is one of the important feature of OSNs since people typically care about their friends opinion and it should be incorporated into the framework. However, majority of the peer-to-peer and decentralized OSN platforms ignore this feature as it is very challenging to provide in a decentralized structure (see Section 10). In POSN, each user posts her/his items into the cloud. In order for friends to post a comment, they should be granted with write permission to the wall. This might introduce security problems since friends might intentionally or accidentally mess up a shared file.

One way of incorporating commenting in this framework would be opening a file with a shared write permission for each friend (such as David, Eric, Frank, and George in Figure 11). If a friend wants to make a comment about a specific post, then this comment can be posted into a file that belongs to that specific friend. Associating the comments with the posts can be done by using the previously assigned IDs of wall posts. The next challenge is how to spread this comment to friends viewing the original post. So far, we assumed wall post file will be used to exchange data. Now, we would need to look into as many as the number of friends' files to see if they have a comment about posts. The owner can aggregate all the comments under friend's comment files to be included under the original post file and remove them from individual comment files. Unfortunately, this process can be accomplished only if the owner is online.

Moreover, users have different cloud providers and might not have an account with the poster's cloud (such as Bob and Chris in Figure 11). Such users will have comment files for their friends's post in their own cloud. To handle these distributed commenting files, the original poster needs to have a file that holds the friend's information where a link to each friends commenting location is provided (such as Friend List in Figure 11). In this case Alice will not be able to erase Bob's comment after populating it to her wall.

The last issue with the commenting is the efficiency. Gathering comments from each friends' cloud will introduce considerable overhead to the system. To minimize this overhead, we implement caching schemes as described in Section 8. When making a comment to a post, the user sends this comment to all (common) online friends who can further propagate to other common friends.

Search Optimization

Another feature of OSNs that is challenging in distributed platforms is the search for objects. In POSN, the cloud is used only for storage purposes and friends' encrypted content is scattered across several locations. In order to search for content of friends, the wall files from all friends should be downloaded to a client to be searched through. Such a scheme is very inefficient since the number of content belonging to a user's circle can be very high. In order to overcome this problem in POSN, an index structure is implemented as described in Figure 12. Whenever a post is made, its keywords or tags are inserted into the index file by the content creator and uploaded to the cloud along with the post. ----------------------

Chris's Client

My-Index Alice's Cloud Bob's Cloud ###### ###### ###### … --
… xxxxxxxx xxxxxxxx xxxxxxxx ... ------ ###### xxxxxxx xxxxxxx ------ xxxxxxx ###### … ... ...

David's Cloud

Eric's Cloud ...

Fig. 12. Multi-level Indexing for Searching

Considering there are several groups for a user, one index file will not be enough to handle different groups. Because an owner might post a multimedia content to a specific group, inserting its tag information into a common index will hint other users of its existence. Hence, POSN keeps a different index file for each group encrypted with the symmetric key of the group that it belongs to as shown in Figure 9.

Since an index file is needed by all of our friends, it needs to be disseminated to them. If a user wants to search for a multimedia content, s/he needs to download the index files of each friend. These index files are then searched for the desired content, which is not very efficient either. To improve search efficiency, POSN will preemptively process the index files of all friends and create a new index structure on the client whenever the user is online. The lack of a central server results in accessing several locations to gather the posts from friends. In the worst case, the user has to check all of friends' cloud locations, which may introduce significant overhead. In POSN framework clients establish direct connection with online friends' clients. When online, clients can exchange information about common friends that are not necessarily online. The number of connections that a client needs to aggregate the information from can considerably be reduced as friends typically form clusters (i.e., communities). Figure 13 presents the network between 635 friends of a monitored user where they form several clusters among themselves. Online friends can exchange information about common friends' latest posts. As a result, the number of connections that a client needs to aggregate the information from will decrease. In POSN, when a client (such as client A in Figure 14) becomes online, it will look for friends' cloud to see if they have a new post and learn their communication address (i.e., IP address and port number) if they are online. If the friend (such as client D) is online then the client can establish direct connection and ask the friend about common friends (clients C, E, F, and G in the example). The online friend then provides its knowledge about common friends. Once other online friends (such as C) are reported then the newcomer can recursively query these friends. This operation is carried out only when a client comes online. Thereafter, rather than periodically checking for new wall posts at every friend's cloud, post notifications are pushed to online friends. As users might become online simultaneously, they need to first update the online status in the cloud and then look up for friends to assure that they are aware of each other.

Data Distribution Optimization

The order of lookup is important as finding online friends early on has considerable benefits and there can be several approaches. The first one is to rank friends by the number of common friends. The second method is to rank friends by their expected online duration. In order to implement these approaches, a user needs to keep and share the relevant information. The success rate of these methods is a research issue that we will try to optimize in our system.

In Figure 15, we compare four methods namely, ideal, most online duration, most common friends, and random for our measured data. In the figure, the x-axis indicates the percentage of online friends when a user becomes online and the y-axis indicates percentage of connections that could be eliminated. One issue is to determine when to take a snapshot of online activity. To mimic real user activity, we assumed the user came online one minute before one of her/his friends actually became online. Hence, we obtain a much larger number of data points than an individuals online pattern. The marks indicate one instance in our measurements for the user whose circle is shown in Figure 13. On average, 14.6% of friends were online while ideally one could save 76.5% of connections on average. Heuristics to first lookup at friends that are most online saves 57.9% of connections while prioritizing most common friends saves 53.2% of connections on average. Even, random ordering saves 45.7% of connections on average. Our evaluations with the user with 435 friends yield very close results (difference of less than 1% in each average). Figure 16 presents the amount of multimedia data a user would need to download when s/he became online based on the measurement of user in Figure 13. Similar to Figure 15, we assume the friends' online pattern as the user's online duration. As the time between logins increase, the amount of data the user might download from her/his friends increases. In extreme cases, we observe there is about 1GB of data when the user has not logged in for about a day and friends have posted large videos. Hence, rather than auto-downloading all multimedia content, POSN would parse most recent posts and wait for the user to fetch subsequent content as s/he is scrolling through the posts (especially for large videos). Friendships might not last forever or the level of friendship might change, as a result the content that friends exchange will change.

Discussion

The POSN framework should reflect changes in the friendship status. To reduce the level of information exchange with a friend, the group or groups that friend belongs to could be changed. As we might not want the person to be aware of unfriending, we move all other friends to new group(s) with new key(s). Hence, the unfriended person would think that there are no new posts even if they analyzed the raw data. Another challenge in real life is stalking. In order to stalk someone in our system, s/he has to know the victim in real life and be a friend in the POSN platform. If the stalker is a friend of victims friend, s/he can only see the comments of the victim. There is no way that the stalker can see the shared content of the victim through POSN if they are not friends.

To allow third party application support without harming user privacy, each user can keep an App File for each authorized application in their cloud. This App file is encrypted with a key as any other group wall. Applications will write the relevant data into the files without revealing it to the app developer. Moreover, friends who want to partner in specific app can exchange their App file location and keys so that they can collaborate/compete. Online applications can also exchange information over the socket connection that is created by the online clients.

Security Challenges

Stolen devices pose a security risk. The owner of the stolen device should send notifications immediately. This notification could be send either by email or SMS or through some automated mechanisms to minimize the damage. Once a notification is received every key that is paired with that user would be renewed. On the other side, the mechanism should be carefully deployed so that this is not employed for denial of service attacks. Hence, we will investigate a solution that provides immediate notification mechanism while it can not be used for DoS.

Finally, a cloud provider might track who is accessing individual files and gain knowledge about interactions of a user [START_REF] Gunes | Blind processing: Securing data against system administrators[END_REF][START_REF] Naruchitparames | Enhancing data privacy and integrity in the cloud[END_REF]. Note that, to download content, a friend just uses direct link to the file without logging into the cloud. Also, online users do not need to connect to the cloud to exchange non-multimedia content. To prevent even IP based analysis by cloud provider, the user might utilize multiple clouds for different groups s/he is managing. Moreover, friends can utilize proxies and anonymizer technologies in her/his communications with the cloud [START_REF] Karaoglu | Multi Path Considerations for Anonymized Routing: Challenges and Opportunities[END_REF][START_REF] Li | An Overview of Anonymity Technology Usage[END_REF]. Likewise, a user's online friends (who are not necessarily friend with the person whose encrypted data is downloaded) can be utilized in accessing clouds so that the cloud is not certain of who is accessing the content.

Related Work

We have analyzed some of the decentralized OSNs that we could identify, and found several decentralized OSNs currently in use: Diaspora [START_REF]Diaspora: community-run, distributed social-network[END_REF], Friendica [START_REF]Friendica: The internet is our social network[END_REF], and RetroShare [START_REF]Retroshare: secure communications with friends[END_REF]. Diaspora has tens of thousands of active users. Diaspora is a set of pods (currently about 130 are publicly available) that decentralize the system and is accessible through browsers. Even though an individual can deploy their private pod, the main issue with Diaspora is that each pod is a central server of many users. Similarly, Friendica builds a social web platform using set of decentralized servers. RetroShare is a peer-to-peer PC application that provides decentralized OSN support.

Additionally, there are several decentralized OSNs proposed in academia, but none of them seems to be actively used. Cachet [START_REF] Nilizadeh | Cachet: A decentralized architecture for privacy preserving social networking with caching[END_REF], PeerSon [START_REF] Buchegger | Peerson: P2p social networking: Early experiences and insights[END_REF], Safebook [START_REF] Cutillo | Safebook: Feasibility of transitive cooperation for privacy on a decentralized social network[END_REF], and LifeSocial [START_REF] Graffi | Lifesocial.kom: A p2p-based platform for secure online social networks[END_REF] build a peer-to-peer (p2p) system where peers are not necessarily trusted. Polaris [START_REF] Wilson | Privacy, availability and economics in the polaris mobile social network[END_REF], My3 [START_REF] Narendula | My3: A highly-available p2p-based online social network[END_REF] and Vegas [START_REF] Durr | Vegas -a secure and privacy-preserving peer-to-peer online social network[END_REF] build a p2p network among friends to replicate data. Confidant [START_REF] Liu | Confidant: Protecting osn data without locking it up[END_REF], Tent [START_REF] Tent | All your data in one place[END_REF], and Vis-a-Vis [START_REF] Shakimov | Visa-vis: Privacy-preserving online social networking via virtual individual servers[END_REF] build a distributed platform by building a protocol among servers that process user data. Persona [START_REF] Baden | Persona: An online social network with user-defined privacy[END_REF] proposes to use attribute based encryption to store user data in untrusted storage servers with web based OSN platform. PrPl [START_REF] Seong | Prpl: A decentralized social networking infrastructure[END_REF] allows a user to use personal or 3rd party server to store their encrypted content.

Finally, there are privacy preserving social networks that are not traditional OSNs. Pythia attempts to present a privacy aware p2p network for social search [START_REF] Nilizadeh | Pythia: A privacy aware, peer-to-peer network for social search[END_REF]. Gossple is an anonymous social network that helps users build new relationships with others based on mutual interests [START_REF] Bertier | The gossple anonymous social network[END_REF]. Priv.io [START_REF] Zhang | Building confederated web-based services with priv[END_REF] builds a decentralized web based platform to securely share data. Contrail is a communication platform that provides content filtering in decentralized social networks [START_REF] Stuedi | Contrail: Enabling decentralized social networks on smartphones[END_REF]. NOYB [START_REF] Guha | Noyb: Privacy in online social networks[END_REF] and Lockr [START_REF] Tootoonchian | Lockr: Better privacy for social networks[END_REF] can be integrated into current social networks in order to guarantee the users privacy in OSNs.

Friendship Establishment: The decentralized networks that provide security as a feature tend to be more careful with revealing the very existence of certain users, thus finding friends becomes a challenge. Others are more cavalier with this information so making more friends is easier. There is a tradeoff of how privacy protecting the system is and how difficult it is for users to find and add their friends. As Diaspora and Friendica has member directories, friends can can easily be found. In Cachet, LifeSocial, and Vis-a-Vis users can locate friends through a DHT. PeerSon, Persona, Polaris, RetroShare, and Vegas exchange certificate files to establish friendship. In proposed POSN, we rely on existing identities, i.e., email addresses, to exchange credentials and establish friendship.

Data Storage: In a decentralized OSN, the data is, by definition, not stored in a single location. Some applications store the data in a distributed manner as a security precaution, some do it in order to promote inter-connectivity between users, and others do it for a combination of reasons. Diaspora and Friendica store data in a set of servers, which can be private. P2p systems store encrypted data amongst all peers (i.e., Cachet, LifeSocial, and PeerSon) or only in trusted peers (i.e., My3, Safebook, and Vegas). Confidant, Tent, and Vis-a-Vis decentralize the data among the users selected servers (potentially cloud providers), but the servers actually process the user data. Persona stores data in servers but only stores encrypted data. Some store data only in the user's PC (i.e., RetroShare) or smart phone (i.e., Polaris). In the proposed POSN, we build a p2p platform between mobile devices and utilize the cloud for encrypted data storage.

Support for Content Search: Among analyzed systems only Confidant, Diaspora, and Friendica users can search for content in their own server (or other servers in case of Diaspora), and Vegas users can perform controlled friend flooding to search for content. Different from p2p platforms that typically do not allow search function, POSN provides search of encrypted content by preemptively building search indexes.

Support for Commenting: Among analyzed systems only Confidant, Diaspora, and Friendica allow comments to posts as content is stored on a set of servers. Different from p2p platforms that do not allow commenting function, POSN provides commenting by propagating comments through the system.

Conclusions

OSNs have gained a great importance in our daily life. People prefer to communicate and interact with their friends through OSNs. In this paper, we propose a privacy preserving decentralized OSN so that users have direct control of their information. POSN can be easily deployed by installing an application and using a free-of-charge cloud storage provider. The POSN platform focuses on the community of individuals and tries to optimize the system through encrypted cloud storage. The combination of phone-to-phone applications with cloud infrastructure addresses the main limitation of peer-to-peer systems, i.e., availability, while enjoying the benefits of peer-to-peer systems, i.e., no central authority and scalability. POSN ensures that interactions happen between friends and third parties cannot access the user content or relationships.

Fig. 1 .

 1 Fig. 1. Snapshots of the POSN prototype In this paper, to address privacy concerns, we introduce a Privacy Preserving Decentralized Online Social Network (POSN) which mimics real life social interactions. Figure 1 presents sample snapshots of Android app in development.The main contribution of this paper is the combination of phone-to-phone applications with cloud infrastructure to address the main limitation of peer-to-peer systems, i.e., availability, due to high churn rate while enjoying the benefits of peer-to-peer systems, i.e., no central authority and scalability. This approach can be expanded to provide other forms of social communications where data privacy is a concern.

Fig. 3 .

 3 Fig. 3. Upload and Download times (log scale)content of a friend, a user should download the content i.e. the wall post file. In general, walls containing posts will be automatically downloaded but the multimedia content and comments will be downloaded only when a user views it. Even though downloading a file is straightforward, checking hundreds of user's files across different clouds is not efficient. Knowing if your friends have a new content will speed up the process. Online friends can speed up the process as they can share their knowledge about common friends (seeSection 8).In order to see whether clouds can provide communication efficiency of OSNs, we compared the file upload/download timing of popular OSNs (i.e., Facebook and Google+) with popular clouds (i.e., Dropbox, Google Drive, Sky Drive, Mediafire, Copy Cloud). Figure3presents the average upload and download timing of 10 measurements using an Android tablet over WiFi at our campus. In these experiments to reduce bias due to background processes and radio status, we closed all unnecessary services, performed a small file transfer to ensure radio is on, and kept the measurement process in the foreground. As Facebook resizes and compresses pictures, we were not able to download a picture of about 1MB even though larger pictures were uploaded. Hence, 1MB and larger files are videos doubling in size whereas below 1MB are pictures resized by Facebook. We obtained comparable performances in our experiments at 10 different WiFi locations throughout the city as well (results not shown due to space limits).When uploading a photo, Facebook becomes progressively worse for pictures (likely due to re-rendering) but is comparable to the rest for videos. Google+ seems worse than all but one cloud provider. Our in depth analysis revealed that the Google+ API streams the videos, therefore the total download time is considerably increased. Overall, upload performances are similar as videos of 1MB and larger are uploaded. Download performance of OSNs are also better than clouds for files smaller than 1MB but are comparable for larger sizes. Even though this might impact interactive communications such as chat, performance difference of 1 sec or less would not be considerable for humans to affect adaptation of POSN. These experiments shows there is no significant performance difference when uploading/downloading a file to/from an OSN or a cloud provider.Additionally, we performed measurements with 7 mobile phones over 3G in the Reno/SFO area. Figure4presents the ratio of Dropbox over Facebook performance for transfer of the same file by the phone around the same time.

BridegumFig. 4 .

 4 3G Performance Comparison (log scale)

Fig. 5 .

 5 Fig. 5. Friendship establishment

Fig. 6 .

 6 Photo Size (KB)

Fig. 7 .

 7 Fig. 7. Sender overhead for multimedia (log-scale)

Fig. 9 .Fig. 8 .

 98 Fig. 9. Key Hierarchy to Protect User Content

  Fig. 11. Comment propagation

Fig. 13 .

 13 Fig. 13. Friends inter-connections

Fig. 14 .

 14 Fig. 14. Phone-to-Phone exchange

Fig. 15 .

 15 Fig. 15. Help from online friends

Fig. 16 .

 16 Photo and Video Posts Between Logins

Acknowledgments. We would like to thank James Bridegum for initial App development and Davut Ucar for collecting public WiFi measurements.

This material is based upon work supported by the National Science Foundation under grant number EPS-IIA-1301726.