prof. Rek Molva

prof Thorsten Strufe

Dr Melek Onen

prof Pietro Michiardi

Dr Oliver Blass

Carmelo Velardo

Alessandro Duminuco

Marco Paleari

Antonio Barbuzzi

Giuseppe Reina

Mario Pastorelli

Dennis Roch

Yao Liu

Jens Trinh

Etienne Peron

Jean Baptiste Barrau

Luca Boasso

Paolo Viotti

Mustafa Zengin

Marco Garieri

Wenting Li

Girolamo Piccinni

Andrea Milazzo

Esko Mattila

Waqas Liaqat

Rajendra Hubli

Yu Liu

Yuling Shi

Keywords:

a decentralized and privacy-preserving online social network application. Based on the two design principles, decentralization and exploiting real-life trust, various mechanisms for privacy and security are integrated into Safebook in order to provide data storage and data management functions that preserve users'privacy, data integrity, and availability.

Apart from the design of Safebook, a signicant part of the thesis is devoted to its analysis and evaluation using various methods such as experimenting with real social network platforms.

Finally, this thesis presents an implementation of Safebook that is written in python and can be executed on multiple operating systems such as Windows, Linux and MacOs. The Safebook implementation is a multithread event-driven application composed by dierent managers in charge of building and keeping the social network and P2P overlays, performing cryptography operations and providing the main social network facilities such as friendship lookup, wall posting and picture sharing through a user interface implemented under the form of a webpage.

Abstract

Social network applications allow people to establish links and exchange information based on various interests such as professional activities, hobbies, et similia. Several commercial social networking platforms that came to light recently suddenly became extremely popular at the international arena. Apart from obvious advantages in terms of fast community building, rapid exchange of information at the professional and private level, social network platforms raise several issues concerning the privacy and security of their users. The goal of this thesis is to identify privacy and security problems raised by the social networks and to come up with the design of radically new architectures for the social network platform.

As current social network platforms are based on centralized architectures that inherently threat user privacy due to potential monitoring and interception of private user information, the goal is to design social network platforms based on a distributed architecture in order to assure user privacy. New mechanisms are investigated in order to solve some classical security and trust management problems akin to distributed systems by taking advantage of the information stored in the social network platforms. Such problems range from trust establishment in self-organizing systems to key management without infrastructure to cooperation enforcement in peer-to-peer systems. This thesis suggests a new approach to tackle these security and privacy problems with a special emphasis on the privacy of users with respect to the application provider in addition to defense against intruders or malicious users. In order to ensure users' privacy in the face of potential privacy violations by the provider, the suggested approach adopts a decentralized architecture relying on cooperation among a number of independent parties that are also the users of the online social network application. The second strong point of the suggested approach is to capitalize on the trust relationships that are part of social networks in real life in order to cope with the problem of building trusted and privacy-preserving mechanisms as part of the online application. The combination of these design principles is Safebook, i List of Tables 3.1 Attacks vs. Security Objectives in Online Social Networks . . . . . . . . . . . Introduction Social Networking Services (SNS), like Facebook, LinkedIn, or Google+, are a predominant factor of Internet. Catering for a very large user population with a vast dierence in social, educational and national background, they allow even users with limited technical skills to publish personal information and to communicate with ease. In general, the Online Social Networks (OSN) resulting from these SNSs are digital representations of a subset of the relations that their participants, the registered persons or institutions, entertain in the physical world. Spanning participating parties through their relationships, they model the social network as a graph. However, the popularity and broad acceptance of social networking services as platforms for messaging and socialising attracts not only faithful users who are trying to add value to the community, but parties with rather adverse interests, be they commercial or plain malicious, as well.

The main motivation for members to join an OSN, to create a prole, and to use the dierent applications oered by the service, is the possibility to easily share information with selected contacts or with the public for either professional or personal purposes. In the rst case, the OSN is used as a facility geared toward career management or business goals, hence SNS with a more serious image, like XING or LinkedIn, are chosen. As members in this case are aware of the professional impact of the OSN, they usually pay attention to the content of the data they publish about themselves and others. In the case of a more private use, they share more personal information like contact data, personal pictures, or videos. Other members in the shared pictures can be marked ( tagged), and links to their respective proles are created automatically.

The core application used by OSN members is the creation and maintenance of their contact lists, which describe the members' milieux and maps them into the digital OSN graph. By informing members automatically on prole changes of their contacts, the SNS thus helps users to stay up to date with news of their contacts and very often the popularity of users is measured in the number of contacts their prole links to.

Analyzing the OSN with respect to their security properties and the privacy of their users, some obvious threats become apparent. Generally, a wealth of personal data on the participants is stored at the providers, especially in the case of OSN targeting nonprofessional purposes. This data is either visible to the public, or, if the user is aware of privacy issues and able to use the settings of the respective SNS, to a somewhat selected group of other members. As proles are attributed to presumably known persons from the real world, they are implicitly valued with the same trust as the presumed owner of the prole. Furthermore, any actions and interactions coupled to a prole are again attributed to the presumed owner of this prole, as well.

Dierent studies have shown that participants clearly represent the weak link for security in OSN and that they are vulnerable to several types of social engineering attacks. This is partially caused by a lack of awareness to the consequences of simple and presumably private actions, like accepting contact requests, or tagging pictures, as well as communication operations like commenting on proles or posting on walls. The low degree of usability of privacy controls oered by the SNS, and nally and most importantly inherent assumptions about other participants and trust in other proles, which are actually a desired characteristic, certainly add to the problem.

By analyzing the privacy problems in current OSN, it becomes apparent that even if all participants were aware of exposures and competent in the use of SNS, and even if a concise set of privacy measures were deployed, the OSN would still be exposed to potential privacy violations by the omniscient service provider: the data, directly or indirectly supplied by all participants, is collected and stored permanently at the databases of the service provider, which potentially becomes a Big Brother capable of exploiting this data in many ways that can violate the privacy of individual users or user groups. The importance of this privacy exposure is underlined by the market capitalization of these providers, which reaches 1.1 Research objectives 3 50 billion U.S. Dollars (Facebook Inc, according to the investment of Goldman Sachs and Digital Sky Technologies in 2011) [START_REF]Goldman oering clients a chance to invest in facebook[END_REF], and by the OSN worldwide advertisements revenue, which reached 5 billion U.S. Dollars in 2011 and is estimated to double by 2013 (according to eMarketer [START_REF]Social network ad revenues to reach $10 billion worldwide in 2013[END_REF]).

This thesis claims that the user's privacy can be easily jeopardized due to the centralized architecture of OSNs, and current providers are not likely to address this problem due to their business model. This work considers instead the protection of private data in OSN a pressing topic and proposes a new architecture for OSN with the purpose of privacy by design.

Research objectives

This thesis assumes the protection of the user's privacy against the omniscient SNS provider to be the main objective for OSN and aims at identifying the main characteristics an OSN should meet to achieve such an objective and at providing a new architecture for privacy preserving OSN. As an additional objective, the protection of the user's privacy against malicious users is also addressed.

We dene the objective of privacy as the possibility to hide any information about any user at any time, even to the extent of hiding users' participation and activities within the OSN. Therefore, privacy not only encompasses the protection of personal information which users publish at their proles, but also takes into account the communication between users, that is, it requires that no parties other than directly addressed or explicitly trusted ones should have the possibility to trace communication patterns. The details of messages have to be unobservable, so only the requesting and responding parties should know one another's identity and the content of the request. Access to the content of a user prole may only be granted by the user directly, and this access control has to be as ne-grained as the prole itself.

Together with the objective of privacy, this thesis addresses further security objectives of integrity and availability , which in OSN come in slightly dierent avors than in traditional systems.

In the context of OSNs, integrity has to be extended beyond the basic goal of protecting users' data and identity against unauthorized modication to cover a variety of attacks such as the creation of personae, bogus proles, cloned proles, or other types of impersonation.

Each prole should then be unambiguously associated to an individual in the real world.

Availability should prevent denial-of-service attacks that in the context of OSN may aim at seizuring a victim's prole or disrupting the possibility to communicate with the user.

Moreover, availability should not only achieve the basic goal of guaranteeing SNS even in face of attacks and faults, but also target robustness against censorship.

Main contributions

The centralized nature of OSNs allows SNS providers to monitor and intercept user's sensitive data. This problem recently attracted quite some interest in the research community and the outcome of the research can be summarized in a family of solutions known as Decentralized Online Social Networks (DOSN). Such DOSNs aim at distributing the user's data with the adoption of a client-server (or cloud) approach, where users do not participate in the storage service and the stored data is always available, or through a peer-to-peer (P2P) approach, where users participate in the storage service and the stored data may not be always available.

Even though the user's shared data is protected by encryption in all the current DOSNs, such solutions are not suitable to achieve our research objectives. Client-server (or cloud) approaches do not always evade the potential control of a single party, as e.g. a company or an organization, on the hosted user's data. Such control evasion might have been achieved

if users had set up and maintained their own servers to host their data and that one of other users, thus leading to a P2P-like approach.

However, current P2P DOSNs suer from exposures to communication tracing by malicious peers. In the context of OSN, such communication traces are likely to correspond to friendship relationships in the social network, and therefore they can even disclose details on the structure of the social network graph. Among the current P2P-based DOSN approaches, none of them addresses this problem. In addition, current P2P DOSNs often leverage on existing P2P architectures suering from the well known problems of lack of cooperation due to selshness of nodes and denial-of-service attacks due to the creation of multiple peer identities under the control of a malicious party. For these reasons, current P2P DOSNs no not seem suitable for the goal of privacy preserving OSN.

With this work, we hope to provide a basis for new research focusing on privacy in OSN.

Business statistics, newspapers and current research let us strongly believe the relevance of this topic is nowadays very high and will become even more important in the next years.

Reliable solutions are therefore needed to accomplish the task of providing privacy to OSN users through the users' education and the proposal and implementation of appropriate OSN architectures.

The rst contribution of this thesis consists in an analysis of Online Social Networks that includes the main OSN actors, the OSN functionalities, the nature of the sensitive data shared by users, and the main threats resulting from potential misuse of such data.

The second contribution of this thesis consists in lling the lack of privacy preserving OSN by proposing a new decentralized architecture for OSN targeting user's privacy as the main goal. Decentralization is based on a new P2P system that leverages the real life trust between OSN members resulting from the OSN application as a natural cooperation enforcement mechanism to build the social network application itself. In the proposed solution, called Safebook , neighbor peers are arranged according to their maintainers' real life trust that is, according to the social network graph. Nodes maintained by one user's friends store such user's data and serve it even when the user is o-line. As with anonymous routing, data requests and replies are recursively delegated to dierent peers to hide the actual requester's identier and prevent the disclosure of the trust relationships between OSN members. Data condentiality is assured by adoption of encryption techniques and integrity of proles is assured by o-line trusted identication service(s) whose jurisdiction is limited to the purpose of identication only.

The Safebook architecture has been designed with the main goal of preserving user's privacy by the very beginning: prole integrity through adoption of certied identiers that are signed by a trusted identication service, together with data condentiality and integrity through adoption of classical encryption techniques, protect the social network graph vertices as represented in the OSN, i.e. the users'proles; multi-hop routing of messages and further encryption techniques provide communication untraceability and condentiality, and protects the social network graph edges as represented in the OSN, i.e. the user's contact list. Therefore, Safebook achieves privacy by design .

The third contribution of this thesis consists in the evaluation of the feasibility and performance of Safebook. Starting from the online probability of peers, the number of user's friends, and the length of the hop-by-hop trusted paths providing communication untraceability, analytical models estimate the probability of retrieving a target user's data and the maximum size of each message containing such data.

The fourth contribution of this thesis consists in the investigation of the strong relationship between the topological properties of the social network graph and the achievable users' privacy in Online Social Networks. We observe three metrics, namely clustering coecient, degree distribution and mixing time, and show that they give fundamental insights on the privacy degree of both centralized and distributed OSNs.

Further investigation is conducted on the impact of the social network graph topology on both the performance and privacy of Safebook. In Safebook there is a strong trade-o between performance and privacy because delay and reachability are inversely proportional to privacy. In fact, the lower the length of the hop-by-hop trusted paths, the higher the probability of deriving the friendship relationships between Safebook users. Nevertheless, the higher such length, the lower the probability of retrieving data, and the higher the retrieval delay. We observe that the optimal choice for this length depends on the social graph itself.

The fth and last contribution of this thesis consists in the implementation and deployment of Safebook. The Safebook prototype is written in python and can be executed on multiple operating systems such as Windows, Linux and MacOs. A web based user interface helps the user to benet from the available privacy tools such as those allowing her to share data with limitations.

Thesis organization

The rst part of this thesis discusses the security and privacy issues in Online Social Networks.

Chapter 2 introduces Online Social Networks, provides details on the OSN actors such as the user and the provider, and illustrates the main functionalities of an OSN. Then, the core information stored in OSNs is identied and classied into several main areas.

Chapter 3 presents privacy, integrity and availability objectives for OSN. A detailed spectrum of attacks that may be perpetrated in OSNs is discussed against these objectives, and countermeasures are proposed to contrast such attacks. However, most of the countermeasures reveal to be ineective against the Social Network Service provider itself, that plays the role of an omniscient centralized entity, a Big Brother . An overview of the main centralized OSNs is also provided.

Chapter 4 gives an overview of the solutions that researchers presented to contrast the Big Brother problem together with their limitations. Characterized by a decentralized approach through client-server, cloud or peer-to-peer architectures, these solutions mostly focus on the protection of the user's prole data rather than that one of the trust relationships between users.

The second part of this thesis introduces a new approach for privacy preserving Online Social Networks. Privacy against centralized omniscient entities is achieved thanks to the adoption of a decentralized P2P approach. Privacy against malicious users is achieved thanks to communication obfuscation through anonymous routing techniques, data condentiality and integrity through the use of encryption, integrity of proles'identity through certied identiers.

Chapter 6 analyzes the feasibility of Safebook with the help of real network measurements. Online session times of peers and analytical models are taken as a basis to evaluate the probability of building trusted paths in Safebook and their residual lifetime. Therefore, data availability and the performance of data management operations are evaluated.

Chapter 7 introduces with an analysis of privacy from the graph theory perspective. The basic nding shows that three metrics, namely the degree, the clustering coecient and the mixing time, give fundamental insights on the privacy degree of the OSN regardless of its particular centralized or distributed nature. The chapter further investigates the impact of

Online Social Networks

This chapter introduces Online Social Networks. At the beginning, the chapter provides details on the OSN actors such as the user and the provider, and illustrates their relations.

Then, the main functionalities of an OSN are discussed. Finally, the core information stored in OSNs is identied and classied into several main areas.

Social Network Services (SNS) are drastically revolutionizing the way people interact, thus becoming de facto a predominant service on the web, today. The impact of this paradigm shift on socioeconomic and technical aspects of collaboration and interaction is comparable to those caused by the deployment of the World Wide Web in the 1990's.

Catering for a broad range of users of all ages, and a vast dierence in social, educational, and national background, SNS allow even users with limited technical skills to publish Personally Identiable Information (PII) and to communicate with an extreme ease, sharing interests and activities.

An Online Social Network (OSN) oering, usually centralized, online accessible SNS contain digital representations of a subset of the relations that their users, both registered persons and institutions, entertain in the physical world. geared towards career management or business contacts; such networks typically provide SNS with a more serious image. In contrast, OSNs with a more private and leisure-oriented background are typically used for 11 sharing and exchanging more personal information, like, e.g., contact data, photographs, and videos; OSNs provided by such networks have usually a more youthful interface. The core OSN application is the creation and maintenance of contact lists. Through informing users automatically on prole changes of their contacts, the SNS help users to remain up to date with news of their contacts.

These properties of the SNS have led to the denition of boyd and Ellison [START_REF] Boyd | Social network sites: Denition, history, and scholarship[END_REF], according to which Social Network Sites or Online Social Network Services are:

... web-based services that allow individuals to (1) construct a public or semi-public prole within a bounded system, (2) articulate a list of other users with whom they share a connection, and (3) view and traverse their list of connections and those made by others within the system.

This denition, however, leaves aside some additional services that become apparent when observing the use of SNS. In particular, the communication of members through direct, sometimes instant message exchange, the annotation of proles (e.g., via comments and recommendations), or the creation of links pointing to other proles (picture tagging).

The publication and browsing of images has grown to become a core function of these services [START_REF] Schneider | Understanding Online Social Network Usage from a Network Perspective[END_REF]. Additionally, SNS typically provide support for a variety of third-party applications featuring advanced interactions between members ranging from simple poking of another member or the support for interest groups for a common topic to likeness testing with other members.

Maintenance and access to the OSN and their services are oered by commercial Social Network Providers (SNP), like Facebook1 , LinkedIn2 , Google3 , XING 4 , and the likes.

In general, a large amount of PII provided by the users is stored at the databases being under control of these providers, especially in the case of OSN targeting non-professional purposes. This data is either visible to the public, or, if the user is aware of privacy issues and able to use the settings of the respective SNS, it is accessible by selected group of other users. As proles are attributed to presumably known persons from the real world, they are implicitly valued with the same trust as the assumed owner of the prole. Furthermore, any actions and interactions coupled to a prole are again attributed to the assumed owner of this prole, as well.

A SNP can, together with its SNS, also oer an application programming interface (API), allowing interested users to program a Social Network Application (SNA), thus extending and enhancing the functional range of the service.

Social Network Providers and Their Customers

Social network providers oer social networking services to the users and may further provide additional interfaces and services to other customers. These customers may come from dierent domains and pursue various goals.

In particular, sponsors belong to customers who advertise their services to the users through the OSN platform. Their advertisements may be of dierent kinds: plain commercial sponsors buy banner space or other marketing services from the SNP to advertise their products; SNS frequently contain market pages at which users can publish classied advertisements (ads), job oers, and the likes, for which they may be billed. Also sponsors may create commercial interest groups or proles inside the OSN.

Another type of OSN customers are third party service providers, who extend the content and functionality of SNS with their own applications. These applications such as quizzes and games are typically executed on the servers under control of these third parties connected to the SNS via appropriate APIs. Often these applications have extensive access to the personal data of OSN users.

Finally, all sorts of data analysts may act as customers of SNP. These customers typically have data mining interests and may also get access to the personal information of users and their activities within the OSN. The analysis carried out by data analysts may serve dierent purposes, including scientic research (such as statistics, social behavior, or network-relevant aspects) and non-scientic data mining, typically for commercial purpose such as marketing.

Functional Overview of Online Social Networks

Even though each OSN is usually tailored to some specic use, the functional range of these platforms is essentially quite similar. Generally speaking, OSN functionality can be classied into three main types: The networking functions serve the actual purpose of OSN to foster social relationships amongst users within the virtual platform. In particular, they provide functionality for building and maintaining the social network graph. The data functions are responsible for the management of user-provided content and communications amongst the users. Their variety contributes to the enhancement of users' interactions and makes the platform more attractive. Finally, the access control functions aim to implement the user-dened privacy measures and to restrict unauthorized access to the user-provided data and information.

Networking functions.

An OSN can be represented as a social graph whose vertexes are constituted by users and whose edges are constituted by social ties such as friendship, kinship and the like (see

Data functions.

OSN users can typically advertise themselves via their own proles and communicate with each other using various applications like blogs, forums, polls, chats, and on-line galleries.The prole update function allows the OSN users to maintain details on their own proles and provide fresh information to other users, who may call the prole retrieval function to visit the prole. Communication amongst users via blogs and forums is typically implemented through the post function, which inserts the message in the main prole page which sometimes is called the `wall' or `stream'. This block of information is not limited to plain text and can also contain videos, pictures, or hyperlinks. An OSN user willing to setup multimedia galleries typically calls the upload function, which transfers digital data from the user's device to the OSN database. In case of content depicting other users, the tag function can create a link pointing to their prole. OSN users can typically evaluate content published by other users through the like or dislike functions. These functions can also be considered as a feedback to the publisher from other users. In consequence, the user may either be encouraged, or discouraged to provide similar uploads and posts. Using the comment function OSN users can articulate their point of view in a more explicit way. OSN users can also exchange personal messages. Here, in particular, the write to function simulates the asynchronous oine communication (e.g., e-mail), whereas the chat to function allows for the synchronous real-time communication. An OSN user can send messages to individuals and also to subgroups of users from his or her contact list.

Access control functions.

OSN users are usually allowed to dene their own privacy settings through some access control functions. In particular, an OSN user may have control over the

• visibility of her on-line presence within the OSN;

• visibility of contacts from her contact list;

• visibility and access to her own prole information;

• access to her own uploaded content and posted communications.

All these functions usually take as input the information to be protected and the list of proles having the rights to access it. The eligible proles can be clustered into generic groups such as `friends', `friends of friends', `everybody', or user-dened groups, such as `family members', `colleagues' or the like.

For example, the prole lookup function takes as an input a target's prole identier, such as the name of the prole owner, and returns a list of possible candidates. An OSN user can apply output restrictions on this function to partially hide her own presence in the OSN. However, the protected prole would remain reachable due to the prole browsing functionality of the OSN. Nevertheless, sensitive relationships can be hidden from unauthorized users by imposing restrictions on the output of the contact list browsing function.

Thus, combined with the restrictions on prole lookup, this constraint can completely hide some prole in the OSN, since this prole will become unreachable from other users outside of the prole's contact list. Note that new contacts could still be added to the prole owner's contact list on the initiative of the latter. Another example is the control on the output of the prole retrieval function, which allows the prole owner to control the disclosure of the prole to other users. This allows some OSN user to hide parts of the private prole information from selected partners. Finally, the data related to online or oine indicators, one-to-one or one-to-many communications, such as posts, walls, comments, positive or negative marks, tags and the like can be protected by the means of restrictions on the huge set of the networking and data functions. The core information stored in OSN, the self generated and maintained data of the users and their proles can be classied into the following ve types (see gure 2.3):

1. personal contact details, describing the user's identity;

2. connectivity, representing the connections in the social network graph;

3. interests of the user;

4. information on the curriculum vitae of the user;

5. communication, including all interactions with other OSN users of the SNS.

These types constitute the personally identiable information which is provided directly by the OSN user. Additional information about the OSN user is often generated and made accessible within the OSN by other users. Personal contact details describe `who the user is', providing not only some basic information such as the user's name, picture, gender, birthday, birthplace and marital status, but also some additional meta information with regards to the membership in the OSN, the contact information aside of the OSN platform such as (e)mail addresses, phone numbers, instant messaging identiers and personal web sites. Furthermore, it describes the personal prole of the user and may report about sexual, personal, political or religious interests and preferences. Users frequently can include a quick summary about themselves, describing their professional expertise, views and opinions, skills they have to oer, as well as a short

text on what they are looking for.

Connectivity describes `whom the user knows', providing the user's contact list, possibly with annotated information about the type of the relationship (cf. family, colleagues, best friend, sports partner). Especially, OSN platforms with more private and leisure-oriented focus frequently ask the user to provide information on the relationship status, and in consequence the name and prole of their signicant other contact. Users may further ask for recommendations by others. These recommendations may contain very detailed information about the user and shed light on the relationship between the both.

Interests describe `what the user likes and is interested in'. These may contain user's personal interests, hobbies, and preferences: In particular, information about favorite movies or music style, their sexual, religious, and political views, recreational activities of the user (such as personal pictures and videos showing situations from their personal lives), and their subscription to fan-pages as well as membership in special interest groups inside the OSN.

Information on the curriculum vitae describes the professional career and educational background, including attended schools, colleges, and universities, advanced studies, academic titles and professional certicates, as well as professional and soft skills. Such information may be very detailed and include the description of job positions the user currently holds or has previously had, including information on the duration and type of the position, the duties and responsibilities fullled in the job, and experiences being collected.

In addition to the description of the career progression, some OSN platforms ask the user to provide information on her membership in professional organizations (past and present), her community and political services (memberships and positions in clubs, associations, political parties, and professional societies), awards and distinctions, as well as recommendations and references.

Communication describes `which messages the user has exchanged and with whom'. OSN platforms generally oer exchange of personal oine messages, asynchronous communication via posts on walls and guestbook entries which the prole owner may hide or disclose to other users, and synchronous communication such as chats. These are examples of direct communications initiated by the user. However, there are also some less direct communications provided by other functionalities of the OSN platforms, such as the utilization of SNS applications (e.g. poking, likeness tests, quizzes), as well as public or targeted invitations to organized events.

Indirect information disclosure about OSN users may occur through posted opinions and comments, or any type of annotations to proles of other users. Even though the owners of the annotated proles may be able to remove undesired annotations, they need to notice the annotations in the rst place. Since many users do not explicitly search for annotations made by other users about their proles, this indirectly disclosed information may remain publicly accessible over a longer period of time. Similarly, information about users may be disclosed via third party statements about the user made in forums of the interest groups, or as annotations or comments at the proles of other users.

Any form of user-generated digital content may also cause third party information disclosure. For example, some OSN try to prevent users from posting photographs showing people on their proles if the owner of the prole is not depicted there 5 . However, this does not prevent users from posting photographs picturing them together with others. Additionally, many OSN platforms oer tagging of pictured users, whose proles will usually be directly linked to that picture. These tags may contain further comments added by the user who uploads the picture.

Summary

In this chapter we presented Online Social Networks as digital representations of a social network graph whose vertices correspond to the registered users, and whose edges correspond to a subset of those users' relationships in real life. These OSNs are maintained by usually commercial social network service providers and allow users to easily share even sensitive information, such as the user's personal contact details, her contact list, her interests, her professional and educational background, and her communication traces. Such data, often uniquely identifying a user, is stored at the databases being under control of the SNP.

Potential misuse of this data from a malicious SNP or an attacker taking control on it may threaten users' privacy as discussed in the next chapter.

Chapter 3

Main threats in OSN

In this chapter we provide an overview of important security objectives for online social networks. First of all we notice that classical requirements (cf. [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF]) of condentiality, integrity, and availability, have a special touch when considered in the scope of OSNs. While integrity and availability have only subtle dierences compared to other communication systems, in that they mostly address the content provided by the users, the requirement of condentiality (usually associated with encryption) is no longer sucient and should be extended to the more comprehensive security objective that is privacy.

While potential breach of user privacy and integrity of user-provided contents may lead to economic damages for the users, cause embarrassing situations, and also tarnish their reputation (even in the real world), the missing availability of contents or services may also decrease the attractiveness of the actual OSN platform and harm its provider. It is extremely dicult to cope with all these goals simultaneously. Especially privacy of OSN users is challenging since the amount of personal information is huge and this information may be available not only from a particular OSN platform but also from the web. 23

Security and privacy objectives

In the following, we describe privacy, integrity and availability objectives for on-line social networks, while also mentioning potential threats with regard to not only the prole owner, but also other users and the system itself.

Privacy

Privacy is a relatively new concept, born and evolving together with the capability of new technologies to share information. Conceived as `the right to be left alone' [START_REF] Samuel | The right to privacy[END_REF] during the period of newspapers and photographs growth, privacy now refers to the ability of an individual to control and selectively disclose information about him.

The importance of privacy is so relevant to have been reported in the Universal Declaration of Human Rights (art.12):

No one shall be subjected to arbitrary interference with his privacy, family, home or correspondence, nor to attacks upon his honor and reputation. Everyone has the right to the protection of the law against such interference or attacks.

In the internet age, where huge amount of sensitive data can be easily gathered, stored, replicated and correlated, the protection of privacy is even more seen as the main objective for the services provided by an OSN platform [START_REF] Gross | Information revelation and privacy in online social networks[END_REF][START_REF] Boyd | Facebook's privacy trainwreck[END_REF].

The problem of users'data privacy can be dened as the problem of usage control [START_REF] Park | Towards usage control models: beyond traditional access control[END_REF]: usage control ensures access control together with additional control on the later usage of the data, even once information has already been accessed.

Access to the content of a user prole may only be granted by the user directly, and this access control has to be as ne-grained as the prole itself. For example, if the prole contains several information blocks then access to each block has to be managed separately.

In addition, communication privacy calls for inference techniques aiming at deriving any type of information with regard to: (1) anonymity, meaning that users should access resources or services without disclosing their own identities; (2) unobservability, i.e. the requirement that no third party should gather any information about the communicating parties and the content of their communication; (3) unlinkability, which requires that obtaining two messages, no third party should be able to determine whether both messages were sent by the same sender, or to the same receiver; (4) untraceability, which demands that no third party can build a history of actions performed by arbitrary users within the system; in other words, it demands both anonymity and unlinkability.

In summary, the objective of privacy is to hide any information about any user at any time, even to the extent of hiding their participation and activities within the OSN in the rst place. Moreover, privacy has to be met by default, i.e. all information on all users and their actions has to be hidden from any other party internal or external to the system, unless explicitly disclosed by the users themselves.

Integrity

In OSN, any unauthorized modication or tampering of user-generated content and prole information have to be prevented (see gure 2.3). This encompasses the protection of real identity of users within the OSN platforms. In this sense, the denition of integrity in such networks is extended in comparison with the conventional detection of modication attempts on data. Moreover, problems with integrity of user proles and their contents may have devastating impact on the objectives put forth with respect to the privacy of OSN users. Since the creation of proles in traditional OSNs is easy, protection of real identities is insucient in today's platforms. In particular, none of the current major OSN providers is able (and perhaps even not interested in) to ensure that a prole is associated to the corresponding individual from the real world.

As users inherently trust the OSN providers, the aforementioned vulnerabilities can be thwarted through the appropriate authentication procedures to assure the existence of real people behind registered OSN proles. Identity checks do not necessarily have to be performed by a centralized service, however, all identication services have to be trusted by all participants.

Availability

The objective of availability for OSN aims at assuring the robustness of the social network services in the face of attacks and faults. The insucient guarantees for availability may prevent users from accessing the service and make the OSN platform less attractive. Especially, for OSNs with professional focus, e.g. OSNs that aid their users to foster business relations or nd new job positions, it is mandatory to keep users' data continuously available.

Therefore, we consider availability of user-generated data and proles as a basic requirement that should be provided by the platforms, even though for leisure-oriented OSN platforms the availability of certain content may appear not of prime importance at rst sight.

In the context of social network services denial-of-service attacks aim at either seizuring a victim's prole (or selected parts of it) or disrupting the possibility to communicate with the user. Such attacks have a direct impact on the availability of users' data. Furthermore, also integrity threats like data pollution and cloning may impair the availability of network services by aecting the quality of the service perceived by the users.

Also distributed services, which are implemented in a decentralized way, possibly via peer-to-peer systems, or which follow other types of service delegation, may be vulnerable to a series of attacks against availability as well. These attacks include black holes, aiming at collecting and discarding a huge amount of messages; selective forwarding, where some trac is forwarded to the destination, but the majority is discarded; and misrouting, which aims to increase the latency of the system or to collect statistics on the network behavior.

In any case, attacks on distributed social networks are more eective in case of collusion amongst malicious users or in the presence of Sybil nodes controlled by the attacker, which is not the case for the centralized OSNs.

In the following, we introduce and discuss the impact of a series of OSN attacks on the above presented security objectives.

Attacks

Attack Spectrum and Countermeasures

The diversity of available OSN platforms opens doors for a variety of attacks on privacy of the users, integrity of their proles, and the availability of the user-provided contents. In this section, we will highlight main attack types against OSN platforms and discuss their impact on the aimed security objectives. Table 3.1 will serve as a background for our discussion.

It illustrates dierent types of attacks and shows their relevance for the mentioned security objectives of privacy, integrity, and availability. We will discuss not only the purpose and impact of each attack but also explain the techniques needed to mount it, while referring to some real-world examples, where possible. We note, however, that technical realization behind an attack may strongly depend on the functionality and in particular on the use of dierent protection mechanisms within the OSN platform. Therefore, not every attack technique will have the same impact when used against dierent OSN platforms. Moreover, since OSN providers typically have full control over the network resources, no meaningful protection appears possible if the attacks are mounted by the provider itself.

Plain Impersonation With plain impersonation attack the adversary aims to create fake proles for real-world users as depicted in gure 3.1. In this sense a real-world user will be impersonated within the OSN platform. The success of this attack strongly depends on the authentication mechanisms deployed in the registration process. Since many OSNs tend to authenticate email addresses by requesting conrmations for the registration emails, this attack can be easily performed if an email address is created in advance. The consequence of plain impersonation is that the adversary can participate in the OSN applications on behalf of the impersonated user with all damaging consequences for the user. A currently very prominent secondary eect of all kinds of impersonation (Sections 3.2 3.2) is the misuse of the trust that users inherently have in messages from their accepted contacts, and especially the `419' scam [START_REF]scam -advance fee / fake lottery[END_REF]: impersonating attackers engage in a dialog with contacts of the impersonated individual, and, by producing a credible story, (`My wallet was stolen in London and now I can't pay my ight home') successfully defraud the victim. This attack can be thwarted only through the deployment of stronger authentication techniques. In particular, it is desirable to require some form of real-world identication from the user prior to switching on her account.

Prole Cloning By prole cloning we understand a special type of impersonation attack that occurs within the same OSN platform [START_REF] Bilge | All your contacts are belong to us: automated identity theft attacks on social networks[END_REF], as depicted in gure 3.1. The goal of the adversary here is to create a prole for some user that is already in possession of some valid prole in the same network. From the technical point of view this attack can be realized through the registration of the new prole using the same (or similar) content as the existing one. This is feasible in most OSN platforms since each prole is associated with some unique administrative id and an email address used during the registration. Furthermore, users can hide their email address so that OSN users would not be able to distinguish between the original proles and their clones registered with other email addresses. As a consequence the adversary can create confusion through impersonation of other registered users and possibly gain access to the private information communicated to that users. Moreover, with tools like iCloner [START_REF] Bilge | All your contacts are belong to us: automated identity theft attacks on social networks[END_REF] prole cloning can be automated. Such tools are able to collect public data of OSNs members, match them, create cloned proles and then send friendship requests on their behalf. A possible solution for OSN providers to prevent prole cloning is to deploy mechanisms that are able to detect similarities between dierent proles, in particular with regard to the personal information that is visible to the OSN users. Since cloned proles typically have later registration date than the original ones, it should be feasible for the OSN provider to distinguish them and remove from the network.

Prole Hijacking The goal of the adversary mounting a prole hijacking attack is to obtain control over some existing prole within an OSN platform. Many OSN platforms protect user access to their own proles via passwords. Hence, from the technical point of view prole hijacking is successful if the adversary can obtain passwords of other users. This can be done by many means. First, it is a well-known fact that the majority of users choose weak passwords that can be recovered via an automated dictionary attack [START_REF] Florencio | A Large-Scale Study of Web Password Habits[END_REF]. However, OSN providers typically deploy protection against such attacks by restricting the number of login attempts or by using techniques that require human interaction such as CAPTCHAs [START_REF] Luis Von Ahn | CAPTCHA: Using Hard AI Problems for Security[END_REF]. Nevertheless, there exist eective tools, e.g. as the one included in iCloner [START_REF] Bilge | All your contacts are belong to us: automated identity theft attacks on social networks[END_REF], that are able to analyze and bypass CAPTCHAs. Alternatively, the adversary may try to obtain passwords via social-engineering attacks such as phishing [START_REF] Tom | Social phishing[END_REF], or obtaining passwords for other online services, relying on the fact that most people use the same passwords across the majority of their accounts at dierent sites. The OSN functionality can be misused to distribute messages aiming to lure users to fake login websites [START_REF]Facebook hack reveals trend in targeting social networks[END_REF]. Finally, we shouldn't forget that OSN providers themselves have full control over the registered proles. Therefore, if some prole appears attractive for the OSN provider to be hijacked the password access to the prole can be changed accordingly.

Prole Porting By prole porting we understand another type of impersonation where some prole that exists within one OSN platform is cloned into another OSN platform [START_REF] Tom | Social phishing[END_REF][START_REF] Bilge | All your contacts are belong to us: automated identity theft attacks on social networks[END_REF], as depicted in gure 3.1. From the technical point of view this attack can be realized via registration of a prole using some new email address. Prole porting is appealing since not every user has her own prole on every available OSN platform. On the other hand, there might be some users that participate in both OSN platforms and thus will not be able to distinguish amongst ported proles. The signicance of prole porting (e.g. in comparison to prole cloning) is that users may be completely unaware that their proles have been ported. The impact of prole porting is that the adversary can impersonate users in dierent OSN platforms. Thwarting prole porting is not that easy. In particular, prole similarity detection tools can still be used but only if they can work across multiple OSN platforms. Since every OSN platform is administrated by a dierent provider, the deployment of such tools would require cooperation amongst the providers. This is dicult to achieve, since OSN providers are cautious about granting any form of access to their prole database to competitors.

ID Theft Under ID theft we consider the impersonation of OSN users in the real-world [START_REF] Bilge | All your contacts are belong to us: automated identity theft attacks on social networks[END_REF], as depicted by the example of user A impersonating user Z in gure 3.1. An adversary mounting the ID theft attack should be able to convince anyone about the ownership of some particular OSN prole. In this way, the adversary can possibly misuse the reputation or expertise of the real prole owner for own benet, while leaving the owner unaware of the attack. One way for a successful ID theft attack is to take control over the target prole.

This requires the same eort as for the prole hijacking attack. However, this eort seems necessary only if the adversary has to actively use the prole for the ID theft attack, e.g. communicate via the OSN platform. Often it would simply suce to claim the ownership of a prole and perform the actual communication via other channels. In this case, thwarting ID theft attacks by technical means seems impossible. The only solution is to rely on other means of real-world identication such as national identity cards, driver's licenses, etc.

Proling In addition to the maintenance of own proles modern OSNs provide users with various applications to express themselves via forums, guest books, discussions, polls, multimedia data, etc. These activities are observable by other users within the OSN platform. By proling we understand an attack against any target OSN user aiming to collect information about OSN activities or further attributes of that user, e.g [START_REF] Balduzzi | Abusing Social Networks for Automated User Proling[END_REF], see also gure 3.2. This attack can be typically performed by OSN users, possibly in an automated way, since the collectable information is usually publicly accessible by all OSN users. The risk of proling attacks performed by OSN users can be diminished via ne-grained access control and anonymizing techniques. For example, users should be able to allow access to the personal parts of their prole on the individual basis and not only based on roles (e.g. friends) as realized in many current OSN platforms. However, recent studies, e.g. [START_REF] Mislove | You are who you know: inferring user proles in online social networks[END_REF], show that even if the personal information is hidden, it can still be inferred from public information and social activities of the user. An alternative solution could be to let users decide whether their activities (e.g. discussion comments) should be kept unlinkable to their proles. Although these measures may help to reduce the risk of proling performed by other OSN users, preventing potential proling performed by OSN providers [START_REF]Myspace user data for sale[END_REF] appears to be much more dicult. Secondary Data Collection By secondary data collection we understand an attack that aims to collect information about the owner of some OSN prole via secondary sources apart of the OSN platform as depicted in gure 3.2. A typical example of secondary data collection is to use some Internet search engine to nd information that can be linked to the prole owner. More eective is to use some Internet service 1 that aggregates all information it can nd about some particular person. Through such an attack the adversary may obtain much more information about some user than available in the prole and misuse it against the user both in the virtual environment of the OSN platform and in the real life. Another example are recent de-anonymization attacks [START_REF] Wondracek | A Practical Attack to De-Anonymize Social Network Users[END_REF] that misused the group memberships of social network users for their unique identication. Furthermore, the existence of OSNs with public and private proles simplies the secondary data collection as many users tend to 1 http://www.123people.com/ have accounts on dierent platforms [START_REF] Zheleva | To Join or Not to Join: The Illusion of Privacy in Social Networks with Mixed Public and Private User Proles[END_REF]. There is no meaningful protection against secondary data collection attacks since the data is typically aggregated from dierent locations.

Therefore, it appears in responsibility of the user to limit information kept in the prole in order to avoid its linkability with secondary sources.

Fake Requests One of the main objectives of OSN platforms is to establish social contacts. This proceeds via connection requests that can be either accepted or rejected by the users. An adversary with a OSN prole that sends fake requests to other users aims less on the social contact with these users but is more interested to expand its own network. The dissemination of fake requests can be automated. Since many OSN users tend to accept fake requests [START_REF] Bilge | All your contacts are belong to us: automated identity theft attacks on social networks[END_REF], the adversary can simplify access to their proles and activities and possibly obtain additional information whose visibility is subject to the available direct or nth-grade connections. These connections can then be misused for the automated collection and aggregation of information. The actual dissemination of fake requests cannot be prevented since establishment of new connections is an important goal of OSN applications. Therefore, it is desirable that users behave more responsibly upon accepting new connection requests.

Crawling and Harvesting

The goal of crawling is to collect and aggregate publicly [START_REF] Bilge | All your contacts are belong to us: automated identity theft attacks on social networks[END_REF][START_REF] Balduzzi | Abusing Social Networks for Automated User Proling[END_REF]; see also gure 3.2. Unlike proling this attack does not target any particular user and unlike secondary data collection it is executed within the OSN environment. The expansion of own network connections by the adversary using fake requests can be seen as a preliminary step for crawling. The adversary is simply interested in collecting as much public information within the OSN platform as possible. This information can then be misused for dierent purposes, for example for selling data to marketing agencies, etc. Also it would allow for the oine analysis of social relationships and user activities, thus paving the way for targeted attacks on OSN users. Although some OSN platforms try to protect from crawling through the deployment of CAPTCHAs, the latter can be passed over with the appropriate solving tools [START_REF] Bilge | All your contacts are belong to us: automated identity theft attacks on social networks[END_REF]. Another attack by which the adversary simultaneously crawls across dierent OSN platforms is called harvesting. Typically harvesting results in larger datasets with larger amount on private information about the OSN users.

Image Retrieval and Analysis Upload of images or other digital content and its discussion stimulates social interactions of OSN users. However, free accessibility to images and videos bear potential risks to the privacy of users. By image retrieval and analysis we understand an automated attack aiming to collect multimedia data (incl. images, videos, etc.) available with the OSN platform. This attack is typically followed by the subsequent analysis via automated pattern recognition tools (see e.g. [START_REF] Zhao | Face recognition: A literature survey[END_REF] for a survey on face recognition) to nd links to the OSN proles of displayed users. Information distilled in this way can reveal more private information about users than they are willing to give. In particular, it may reveal information about friends or colleagues that are not necessarily part of the user's social network, or information about visited locations (location-tracking) shown on the photographs. The analysis of digital content can be further strengthened by considering secondary sources such as search over the Internet. Digital content retrieval attacks can be possibly thwarted through a more restrictive access control policies for the digital content.

Communication Tracking OSN users communicate with each other using diverse OSN applications. By communication tracking we understand a proling attack aiming to reveal information about communications of the same user. In this way the attacker may collect more information about the user than available in the prole. This attack can be mounted in an automated way by searching for comments left by the target user in various OSN applications.

Fake Proles and Sybil Attacks In many OSN platforms users can easily create several proles under possibly dierent identities and contents. Since many OSN platforms lack of proper authentication such creation of fake proles becomes easy [START_REF] Bilge | All your contacts are belong to us: automated identity theft attacks on social networks[END_REF]. On the technical side, the user has only to create a new email for the registration of a fake account. Fake proles pave the way for Sybil attacks [START_REF] Douceur | The Sybil Attack[END_REF] that may serve dierent purposes [START_REF] Laursen | Fake facebook pages spin web of deceit[END_REF][START_REF]Facebook users at risk of `rubber duck' identity attack[END_REF]. For example, owners of fake proles can establish new connections without disclosing their real identities.

In this way they may obtain more information about some person than by using some real account. Sybil account may also be created on behalf of the whole groups [START_REF]Facebook fan pages need security upgrade, says victim[END_REF]. Furthermore, Sybil accounts can be misused against the functionality of the OSN platforms. This includes distribution of spam messages [START_REF]Facebook users targeted in massive spam run[END_REF] or other illicit content such as malware [START_REF]Facebook users unwittingly spread koobface worm[END_REF] and phishing links [START_REF]Facebook responds to massive phishing scheme[END_REF][START_REF]Twitter warns of new phishing attack[END_REF], illegal advertisement, bias of deployed reputation systems, etc. Creation of fake proles can be seen as a special form of impersonation attacks. One solution for OSN providers to recognize fake proles is to use IP traceback. Indeed, if logins to several proles come from the same IP address then it is likely that some of these proles are fake. However, an attacker may try to avoid IP traceback by using dierent proxies. Therefore, stronger identication and authentication mechanisms for admission of new users would oer a better protection.

Group Metamorphosis A popular application provided by OSN platforms is the establishment of shared interest groups. These groups are usually administrated by OSN users and provide a platform for more focused discussions, specialized contact establishment, and dissemination of information, which may be interesting for a targeted audience. By group metamorphosis we understand an attack where group administrators change the group subject to persuade own interests, e.g. political 2 . Other OSN users who joined the group earlier may remain unaware of this change, which in turn may have negative impact on their reputation. A possible solution for OSN providers to thwart group metamorphosis attacks is to restrict control of administrators over the interest groups, in particular to prevent them from modifying any information that may have impact on the group as a whole.

Ballot Stung and Defamation OSN platforms serve primarily the contact establishment and interaction amongst users. Hence, attacks biasing public perception and recognition of a target OSN user by others are undesirable. By ballot stung we understand an 2 One incident has been reported for facebook, where a multitude of groups have been fostered under general topics and concertedly renamed to support Silvio Berlusconi, in 2009 http://www.repubblica.it/ 2009/12/sezioni/politica/giustizia-21/gruppi-facebook/gruppi-facebook.html attack by which the attacker wishes to increase public interest to some target OSN user. This attack may increase the amount of personal messages or connection requests received by the target user resulting in a DoS attack on the physical resources of the OSN user.

The attack may place the victim into the focus of public, possibly embarrassing discussions.

On the other hand, ballot stung may increase popularity of the prole belonging to the attacker. This can be achieved through recommendations submitted by the attacker using fake proles. In contrast, defamation attacks aim at decreasing public interest of a target user, in particular by tarnishing the reputation of the latter [START_REF]Rachel uchitel threatens lawsuit over facebook `defamation[END_REF]. In particular, defamation may lead to blacklisting of the user in contact lists of other users and keep the user away from participation in communication applications such as shared interest groups and discussion forums. It may further have negative impact on the user's life in the real world [START_REF]Man bust for facebook insults[END_REF].

Another form of defamation is the anti-advertising against companies [START_REF]Nestle's facebook page: How a company can really screw up social media[END_REF] aiming to damage the reputation of the latter on the market.

Both ballot stung and defamation attacks have to be performed at a large scale in order to have a signicant impact. An attacker may create fake proles and use automated tools to disseminate information needed to increase or decrease interest to a specic OSN user. Another technique is to use the poll application provided by many OSN platforms and let users vote on information related to the victim.

Censorship OSN providers typically have control over the whole data available within the network. As such they can deliberately manipulate the user-provided information and contents. In some cases this ability is necessary to prevent dissemination of illicit content.

On the other hand, censorship when applied without substantial reasons may have negative impact on the OSN users. For example, in OSN platforms focusing on business contacts users often advertise their expertise. In this scenario censorship may be misused to favor some users over their competitors. Censorship may have many facets. It can be performed by active modication of user-provided contents, which might remain unnoticed by the user.

Higher impact can be achieved through the target manipulation of search engines within the network. Since censorship can be performed by the OSN provider [START_REF]Myspace censors user-generated content[END_REF] without involving any other parties, there is little one can do to prevent this threat. Censorship may be applied not only by OSN providers but also by administrators of shared interest groups.

They can deliberately modify or drop messages of group members. Although restricting group administrators from modication of other user contents appears to be an eective protection measure, it is unlikely to be used in practice, since this ability contradicts to the responsibility of group administrators for the content disseminated within the group.

Collusion Attacks

The impact of a crowd can be exhibited in OSNs through a collusion of users. In this attack several users join their malicious activities in order to damage other OSN users or mount attacks against applications of the OSN platform. In particular, colluding users may start defamation or ballot stung campaigns, increase each over reputations, bias the outcome of public polls or inuence public discussions. Since colluding users have valid OSN proles these attacks do not require creation of fake proles. Furthermore, these attacks are more dicult to recognize than similar attacks mounted via fake proles. The reason is that IP traceback would not help even if colluding users do not deploy any additional proxies.

The analysis of the privacy problems in current OSN demonstrates that even if all participants were aware and competent in the use of SNS, and even if a concise set of privacy measures were deployed, the OSN would still be exposed to potential privacy violations by either the omniscient service provider or an external attacker taking control of the OSN [START_REF] Jones | Facebook: Threats to Privacy[END_REF][START_REF]Monday morning madness[END_REF].

The Big Brother problem

The complete PII, directly or indirectly supplied by all participants, is collected and stored permanently at the databases of the providing company, which potentially becomes a Big Brother capable of exploiting this data in many ways that can violate the privacy of individual users or user groups.

The importance of this privacy exposure is underlined by multiple factors. First of all, according to a recent study from comScore [START_REF]It's a social world: Top 10 need-to-knows about social networking and where it's headed[END_REF], one every ve minutes spent on-line is spent in browsing social networking sites, that nowadays reach 82% of the overall on-line population. Secondly, SNS providers make prot through displayed advertisements: emarketer evaluates the worldwide social network advertisement revenue will hit 8 billion US$ in 2012 and 10 billion US$ in 2013 [START_REF]Social network ad revenues to reach $10 billion worldwide in 2013[END_REF]. Finally, the market capitalization of SNS providers was able to reach up to 50 billion US$ as in the case of Facebook Inc, according to the 1.5 billion US$ funding led by Goldman Sachs Group Inc. in January 2011 [START_REF]Goldman oering clients a chance to invest in facebook[END_REF].

In the following, privacy policy aspects of well known OSNs are briey introduced. The main characteristics of such OSNs are reported in table 3.2.

Facebook Appeared in 2004 as a service accessible by Harvard students only, Facebook reaches now the 55% of the world global audience and accounts for one every seven minutes spent on-line [START_REF]It's a social world: Top 10 need-to-knows about social networking and where it's headed[END_REF]. Owned by Facebook Inc., its value has been always increasing and nowadays is worth 50 billion US$ (according to the investment of Goldman Sachs and Digital Sky Technologies in 2011 [START_REF]Goldman oering clients a chance to invest in facebook[END_REF]).

When a user creates an account in Facebook, according to the terms of service [START_REF]Facebook statement of rights and responsibilities[END_REF], she provides the required information consisting on name, email address, birthday, and gender. While user's name, prole picture, networks, username and User ID are made public, all remaining user generated information can be shared with audience limitations.

Facebook is granted `a non-exclusive, transferable, sub-licensable, royalty-free, worldwide license to use any IP content' the user posted (IP License). Such a license ends when the user deletes this content, that persists at the SNS provider in backup copies `for a reasonable period of time', `unless it has been shared with others'.

User has the right to create a single personal prole and guarantees she will provide true information. When Facebook provides this information to advertising partners or customers, PII is always removed. In contrast, the user cannot exploit her own information for personal gain.

Content infringing someone else's copyright can be removed by Facebook. In this case, the censored user is provided with the opportunity to appeal. When user's friends upload pictures showing the user, automatic face recognition suggests the user's name for the tag by default. The user can opt-out from this service in her privacy control panel accessible from her Facebook prole homepage.

Twitter Twitter is a microblogging platform allowing users to send 140 characters long messages, also known as Tweets. Launched in July 2006, Twitter now has 100 million users and is valued at 8 billion US$ (as of October 2011) [START_REF]Twitter is now valued at $8 billion[END_REF].

Terms of Service [START_REF]Twitter terms of service[END_REF] specify tweets are public, and limits on use and storage may be applied at any time without prior notice. However, Twitter also gives its users the opportunity to limit the access on their tweets to people whom they approve.

`The Services may include advertisements, which may be targeted to the Content or information on the Services, queries made through the Services, or other information'.

By submitting, posting or displaying Content on or through the Services, the user grants Twitter a `worldwide, non-exclusive, royalty-free license (with the right to sublicense) to use, copy, reproduce, process, adapt, modify, publish, transmit, display and distribute such Content in any and all media or distribution methods'.

Twitter reserves the `right at all times (but will not have an obligation) to remove or refuse to distribute any Content on the Services and to terminate users or reclaim usernames'.

While non personal information may be shared or disclosed, in the event that Twitter is involved in a bankruptcy, merger, acquisition, reorganization or sale of assets, the user information `may be sold or transferred as part of that transaction'.

Process of account deletion starts after 30 days from the reception of the communication from the user, and may take up to a week.

LinkedIn With the mission of `connect the world's professionals to enable them to be more productive and successful', LinkedIn is mainly devoted to business-related social networking.

This OSN was launched in March 2003 and accounts 135 million users as of November 2011 [START_REF]Linkedin about[END_REF] for a value of 8 billion US$ (May 2011) [START_REF]Linkedin's $8b ipo -silicon valley, get ready for housing recovery[END_REF].

To create an account, according to the User Agreement [START_REF]Linkedin user agreement[END_REF], the user should not be a competitor of LinkedIn, nor use the service for reasons that are in competition with the OSN. User agrees in providing accurate information and update it as necessary, and has to avoid transferring her account to another party.

A LinkedIn user grants the SNP `a nonexclusive, irrevocable, worldwide, perpetual, unlimited, assignable, sublicenseable, fully paid up and royalty-free right' `to copy, prepare derivative works of, improve, distribute, publish, remove, retain, add, process, analyze, use and commercialize, in any way now known or in the future discovered, any information ' the user provides `directly or indirectly to LinkedIn, including, but not limited to, any user generated content, ideas, concepts, techniques or data to the services' `without any further consent, notice and/or compensation' [START_REF]Linkedin user agreement[END_REF].

User's data can be deleted at any time, unless the user shared information or content with others and they have not deleted it, or it was copied or stored by other users. Moreover, user information can be provided in response to customer service inquiries, to send service or promotional communications through email and notices on the LinkedIn website, or to create social ads for the user's network on LinkedIn using the user's prole photo and name.

Google+ Launched in July 2011, Google+ reached 25 million unique visitors in just less than a month, faster than any other OSN in history [START_REF]It's a social world: Top 10 need-to-knows about social networking and where it's headed[END_REF]. With 90 million users as of December 2011 [13], this OSN is the last essay of its owner Google Inc. whose market value as of the beginning of February 2012 is 155.47 B according to Yahoo [START_REF]Yahoo nance: statistics on google inc[END_REF], to become a competitor in the OSN market.

Google+ users agree on the new privacy policy eective since the 1st of March 2012 [START_REF]Google privacy policy[END_REF]. This policy explicits Google `may combine personal information from one service with information, including personal information, from other Google services'. The user is asked to quickly update wrong personal information or delete it. Deletion can be propagated to active servers with some latency and may not be applied to data stored in backup systems.

User personal information may be shared with trusted companies, organizations or individuals outside Google whose role is to process the information for Google itself. Additionally, aggregated non-personally identiable information may be shared publicly or with partners like publishers, advertisers or connected sites. The privacy policy specic to Google+ [START_REF]Google+ policy[END_REF] tells the users `need to have a public Google Prole visible to the world, which at a minimum includes the name chosen for the prole.

OSNs

That name will be used across Google services and in some cases it may replace another name used when sharing content under the Google Account'. Google Prole identity may be shown to people who have the user's email address or other identifying information.

Users may dene groups or circles of people to share information with. According to the default settings, people in circles except the name of the circle will appear to others.

When uploading photos or videos in Google+ the user aiming at hiding the metadata information associated to such a content needs to remove it before the upload. Automatic face recognition is provided as an opt-in functionality and makes easier for the user to tag her contacts in the picture, that remains however a non automated action since the user needs to validate each tag.

Summary

In this chapter we dened security requirements for OSNs and investigated their main security and privacy issues. We showed they derive, on one hand, from the user's lack of awareness on the consequences of simple actions such as accepting a friend request, and, on the other hand, from the usability of the privacy controls oered by SNS.

However, even if the OSN provided a satisfying set of privacy tools to privacy aware and competent users, the directly or indirectly high valuable shared user's data could still be exploited by the omniscient service provider, as often stated in the subscribed terms of service.

Even considering the commercial bodies that act as social network service providers to be trusted, hackers may be able to compromise their systems to gain access, unsatised employees may abuse their access to the data, or even imprudent publication of seemingly anonymized data may lead to the disclosure of PII.

Researchers realized the importance of this privacy exposure and proposed a set of countermeasures addressing the basis of the problem: the centralized storage of users' data.

Their solutions are examined in the next chapter.

Chapter 4

Decentralized OSN

In this chapter we give an overview of the solutions that researchers presented to contrast the Big Brother problem together with their limitations. Characterized by a decentralized approach through client-server, cloud or peer-to-peer architectures, these solutions propose to store all users' data in a distributed fashion.

The Big Brother problem intrinsically aects all the centralized OSNs. In the last years, several solutions [START_REF] Paul | Decentralizing social networking services[END_REF] have been proposed with the goal of preventing the presence of any omniscient entity. These solutions, known as Decentralized Online Social Networks (DOSNs) [START_REF]Handbook of Social Network Technologies and Applications[END_REF] aim at distributing the user generated contents: in all of them the users' data is made available from multiple locations. Access restriction on such sensitive data is often provided with the adoption of encryption techniques or access control lists.

Current DOSNs can be divided into two main groups:

• Client-Server based decentralized OSNs;

• P2P based OSNs.

While in Client-Server based DOSNs every user controls one or more (at least logically) centralized computing and storage services running in a real or virtual infrastructure, in 43 P2P-based DOSNs every user node joins a well known or dedicated P2P network where computing and storage resources are shared among members.

These two categories are discussed further in this chapter.

Client-Server based Decentralized OSNs

Distributed dedicated server approaches require acquisition or deployment of web space hosting users' sensitive data whose access is restricted to authorized users only.

At the benet of guaranteeing full data availability, they often require the OSN user to pay for the storage service, or for the maintenance of proprietary infrastructure. When third party storage service is provided for free, these solutions often lack incentive mechanisms guaranteeing the service reliability.

Yeung et al. [START_REF] Man | Decentralization: The Future of Online Social Networking[END_REF] propose a framework allowing users to choose one or more trusted servers to host several resources, each of them identied by a URI, such as their activity log, their photo album, and, most importantly, their Friend-Of-A-Friend (FOAF)

1 information, that can be edited through open protocols such as WebDAV 2 . In this framework, users obtain an identity in the form of a URI (a Web ID) pointing to a reference in the user's FOAF le stored on a trusted server, that, in turns, points to their contacts' Web ID. Policy languages such as AIR [START_REF] Kagal | Using dependency tracking to provide explanations for policy management[END_REF] allow publishers to restrict access to their data, and protocols such as OpenID [START_REF] Recordon | Openid 2.0: a platform for user-centric identity management[END_REF] 3 allow requesters to authenticate and access it.

Similarly, in Diaspora4 several servers called pods host users'accounts, or seeds . Pods can be run by users or institutions and together form the social network service infrastructure.

Newcomers unable to setup their own pod nor to nd place in another user or institution pod may host their prole in one of the open pods 5 . Every user generated content is encrypted with a random key in turn distributed to every authorized user.

In Vis-'a-Vis [START_REF] Shakimov | Vis-à-vis: Privacy-preserving online social networking via virtual individual servers[END_REF] users store their sensitive data on a paid virtualized cloud-computing infrastructure, such as the Amazon Elastic Compute Cloud (EC2). The infrastructure is assumed to support a Trusted Platform Module (TPM) proving the customer what software is executing under their account. Vis-'a-Vis is designed to interoperate with existing OSNs rather than replace them. Existing OSNs are treated as untrusted services storing opaque pointers to the user's data in the cloud while compute utility has access to cleartext data.

In Persona [START_REF] Baden | Persona: An online social network with user-dened privacy[END_REF] each user is identied using a single public key and stores his encrypted data with a trusted storage service. Public keys and storage service location are exchanged out of band at the act of friendship establishment. Users interact and publish references to Lockr [START_REF] Amin Tootoonchian | Lockr: better privacy for social networks[END_REF] decouples OSN social information such as the user's published data from functionality such as the social network facilities. Users do not further need to reveal a full copy of their social network to every OSN they use, and may decide which OSN provider or storage service can store their sensitive data, and which third party can access it. Users may also decide to store their data themselves. In Lockr, identities are represented by a public/private keypair, while address books by a list of public keys associated to the user's contacts. Access control policy on the user published data is provided through social attestations: digitally signed metadata encapsulating a social relationship. Social attestation proof of ownership is performed with WHPOK [START_REF] Goldwasser | The knowledge complexity of interactive proof-systems[END_REF], a variant of zero-knowledge protocols, so that the digitally signed attestation is never revealed. Dierently from previous solutions, Lockr can also rely on P2P systems such as BitTorrent to verify the attestations and deliver content. In this approach, signed torrent les specify the relationship that downloading peer must have with the torrent's owner.

their

P2P-based Decentralized OSNs

In P2P-based approaches OSN members also participate in the setup of a P2P overlay and share data storage and computing facilities. Due to the on-line behavior of peers, these approaches inherently relax the data availability requirements and provide best-eort services. At the benet of no server acquisition or maintenance costs, these approaches often leverage on existing P2P overlay architectures originally conceived for the purpose of le sharing.

On the other hand, prole sharing asks for dierent requirements. In the context of le sharing, few large data objects have to be reliably distributed among requesting peers that in turn distribute the same object again. Noticeably, when appropriate incentive mechanisms enhance the collaboration of peers, the popularity of the content determines its availability. In the absence of such mechanisms, on the contrary, peers often engage in free riding [START_REF] Adar | Free riding on Gnutella[END_REF][START_REF] Shneidman | Rationality and self-interest in peer to peer networks[END_REF][START_REF] Locher | Free riding in BitTorrent is cheap[END_REF] due to their inherent selshness: they immediately disconnect from the network and not even popular content can be made highly available.

Additionally, access to le objects in le sharing P2P networks is rarely restricted, and delays in the data transfer are often tolerated. On the contrary, prole sharing asks for restricted and fast access to a very high number of protected published contents.

Finally, by relying on existing architectures, current P2P-based approaches suer not only for this le-sharing eect, but also from the security leaks inherent to the adopted P2P architecture.

Peerson [START_REF] Buchegger | PeerSoN: P2P Social Networking Early Experiences and Insights[END_REF] achieves decentralization thanks to an external DHT system such as

OpenDHT [START_REF] Rhea | Opendht: a public dht service and its uses[END_REF], a centrally managed deployment of the Bamboo DHT on PlanetLab 6 .

The security is assured thanks to the encryption of stored objects, and communications between users are directly peer-to-peer when both are online, while the implementation supports asynchronous messaging when this is not the case. In Peerson, a lookup in the DHT provides the meta-data information of the resource a requesting peer is looking for. Such a metadata can contain the ip address of a target peer to be contacted, or user's notications.

Once a target peer's ip is obtained, peers connect directly, then disconnect immediately except when doing instant messaging. Resistance against impersonation attacks is guaranteed by associating each user to a Global Unique Id. Such a GUID is obtained as the result of an hash function applied to a mail address, under the assumption that everyone today has an email address that is unique. Peerson does not assume any kind of trust relationship between peers, but provides access control by encryption and key management.

Lifesocial.KOM 7 [START_REF] Gra | Lifesocial.kom: A secure and p2p-based solution for online social networks[END_REF] is an extendible plugin-based P2P OSN providing totally distributed P2P-based OSN. Initially conceived as a pure P2P solution, it has been extended to allow users for acquiring storage space at a dedicated server [START_REF] Paul | Decentralized social networking services[END_REF]. Reliable storage is delegated to FreePastry [START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF], a p2p overlay based on PAST [START_REF] Druschel | Past: A large-scale, persistent peer-to-peer storage utility[END_REF]. Data objects can either 6 http://www.planet-lab.org 7 http://ki3.de/lifesocial/ contain nal data or link other objects to be retrieved. Protected data objects are encrypted with symmetric cryptographic keys which are further encrypted with the allowed recipient public key and appended to the object itself.

Prometheus [START_REF] Kourtellis | Prometheus: user-controlled p2p social data management for socially-aware applications[END_REF] is a P2P service managing social information from multiple sources.

It allows users to select the peers storing sensitive information based on social trust. Built and uses Past [START_REF] Druschel | Past: A large-scale, persistent peer-to-peer storage utility[END_REF] for replicated storage of sensor data. Each user has a group of trusted peers storing replicas of her social subgraph for the purpose of increasing its availability.

Prometheus uses Scribe [START_REF] Castro | Scribe: A large-scale and decentralized application-level multicast infrastructure[END_REF], an application-level DHT multicast infrastructure, to manage the communication with the trusted peer group. In Prometheus, every user holds a publicprivate keypair. At the time of registration, newcomer peer connecting from a trusted device is assigned to a unique UID, and species an initial set of trusted peers contributing to the storage of the newcomer's data. While service requests can be sent to any peer, only the trusted peers of a user can provide data about that user.

Finally, Likir relies on the Kademlia [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the xor metric[END_REF] DHT to allow for data storage decentralization.

In Likir, the user's peer node is furnished with an identier in the form of an OpenId [START_REF] Recordon | Openid 2.0: a platform for user-centric identity management[END_REF] by a certication service, and communications are encrypted and authenticated by both communicating parties. Together with the presence of a reputation system (RS), the adoption of OpenId mitigates the impact of Sybil attacks and pollution in the retrieved data. Many RS can be adopted in Likir, under the assumption that they exibit a simple API allowing any application to evaluate other user's behavior to single out the misbehaving peers. In this case, when a resource is inserted with a lookup key unrelated to its content, the resource can be marked as invalid and its publisher as a polluter.

Main Limitations

The access restriction on the user's published data by means of encryption or access control lists together with the migration from a full centralized architecture to a decentralized one constitute two signicant steps toward the protection on the user's security and privacy in OSNs. Nevertheless, this thesis claims that these steps are not sucient. As a matter of fact, current DOSNs still allow the data storage service to link a requester's (often anonymous) identier to the target user's prole she is looking for, and derive as a consequence trust relationships between users. A series of works pointed out that the information on the sole social network topology in addition to the data that most users publish in current OSNs is sucient to de-anonymize the input topology [START_REF] Narayanan | De-anonymizing social networks[END_REF][START_REF] Wondracek | A Practical Attack to De-Anonymize Social Network Users[END_REF][START_REF] Backstrom | Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography[END_REF] and retrieve information on the social network. Therefore, current DOSNs just propose their users to choose another Big Brother with a more limited view of the overall network.

Literature on P2P networks already addressed the problem of anonymous communication [START_REF] Rogers | How to Disappear Completely: A Survey of Private Peer-to-Peer Networks[END_REF][START_REF] Chothia | A survey of anonymous peer-to-peer le-sharing[END_REF], and proposed solutions that are suitable for le sharing, but reveal to be inadequate in the context of DOSNs. As an example, the well known Onion Routing technique [START_REF] Michael | Anonymous connections and onion routing[END_REF], where a sender node recursively encrypts secret content with the public key of the nodes composing the path this content must follow, when adopted in a Friend-to-Friend (F2F) network, where peers cooperate thanks to their friendship, would require the sender to know the social network graph topology, i.e. the information the DOSN itself aims to protect. On the other hand, when the P2P network is not a F2F one, appropriate incentive mechanisms for cooperation among peers are required.

In this thesis we propose a radically new P2P architecture for secure, privacy preserving, distributed OSN to properly target the user's security and privacy in OSN. Such a solution addresses privacy by design, avoids the Big Brother problem and guarantees cooperation between peers.

The main characteristics of this new solution are described in the following chapters.

Summary

In this chapter, we gave an overview of Distributed Online Social Networks (DOSN). We classied such DOSN approaches in two categories: client-server (or cloud), and peer-to-peer.

Client-server (or cloud) approaches require acquisition or deployment of web space hosting users' sensitive data and do not always evade the potential control of a single party, as e.g. a company or an organization, on such data. At the benet of guaranteeing full data availability, they often require the OSN user to pay for the storage service, or for the maintenance of proprietary infrastructure.

On the other hand, current peer-to-peer approaches inherently relax the data availability requirements and provide best-eort services. Whereas such approaches do not suer from single party control, they expose users to potential communication tracing by malicious peers. In the context of OSN, such communication traces may disclose details on the structure of the social network graph.

We therefore concluded that none of current approaches is suitable to achieve the goal of preserving user's privacy in OSNs This problem is addressed through leveraging the trust relationships that are available as part of the SN itself. Trust relationships akin to SN, such as `friendship' or `acquaintance' are thus exploited to build trusted links among the nodes of the P2P SNS system.

This chapter begins with the rationale behind Safebook, followed by a description of its main components and functionalities.

At the end, the core protocols of Safebook are described in detail following the main steps a newcomer has to take to join the OSN and benet from its services. 53

Rationale

As mentioned in chapter 3, current Online Social Networks severely suer from a large number of security and privacy threats that may lead to irreversible loss of sensitive data, and consequently, to loss of money and reputation. These threats are mainly due to two concurrent factors: users lack awareness regarding the consequences of simple and sometimes presumably private actions, like accepting contact requests, tagging pictures, commenting on proles or leaving wall posts, and SNS providers do not develop, oer or advertise appropriate security and privacy tools.

While the rst factor is probably a consequence of the user's implicit trust in other proles and on the OSN provider itself, the second one is probably due to the OSN business model, where OSN value increases together with the number of its members and the volume of the shared data [START_REF] Bonneau | The Privacy Jungle: On the Market for Privacy in Social Networks[END_REF].

One might ask: is it more convenient to propose yet another OSN, or to design and implement a set of security and privacy tools for existing ones?

In current OSNs, the main threat is the lack of protection for the user's data from the SNS provider itself. As a matter of fact, the data directly or indirectly supplied by all participants is collected and stored permanently at the databases of the service provider.

This makes it an omniscient entity, that may act as a Big Brother monitoring and tracing users.

Uploading encrypted data to current OSNs may appear as a good solution to prevent the Big Brother problem. Unfortunately, even assuming that users store their data in an encrypted form at the OSN servers, still the monitoring of prole data lookups may reveal to the SNS provider insightful information on the social network graph itself, such as the OSN members' contact list.

Therefore a new architecture for OSNs is needed to address the current security and privacy threats, and this architecture should not propose any central entity storing all users' data.

Design principles

As discussed in chapter 4, in order to meet the main privacy objective, distributed data storage for OSNs may be achieved either through a client-server (or cloud) approach, where users do not participate in the storage service and the stored data is always available, or through a peer-to-peer approach, where users participate in the storage service and the stored data may not be always available.

The P2P approach inherently lends itself to the design of an architecture with the main objective of evading control by a single party such as an organization or a company. Hence we decided to opt with the P2P approach taking into account additional advantages thereof such as scalability and fault tolerance.

As a rst design principle, we envision a P2P system and we rely on peer nodes to perform basic OSN operations such as:

• storage of user's data;

• lookup of user's data;

• communication among users. Nevertheless, P2P system severely suer for a major problem, that is the lack of cooperation among peer nodes. The absence of a-priori trust characterizing any P2P system increases the intrinsic selshness of nodes, that often engage in free riding [START_REF] Adar | Free riding on Gnutella[END_REF][START_REF] Shneidman | Rationality and self-interest in peer to peer networks[END_REF][START_REF] Locher | Free riding in BitTorrent is cheap[END_REF] and try to consume as more resources as possible without contributing to the network services.

Cooperation enforcement hence poses as a mandatory requirement to eectively setup a distributed P2P OSN.

Cooperation enforcement mechanisms encourage nodes to perform a fair share of both networking and storage operations. Inducing cooperation between nodes can be based either on some reputation or on rewarding mechanisms: reputation mechanisms [START_REF] Buchegger | Nodes bearing grudges: Towards routing security, fairness and robustness in mobile ad hoc networks[END_REF][START_REF] Michiardi | CORE: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF][START_REF] Satsiou | Reputation-based resource allocation in p2p systems of rational users[END_REF][START_REF] Dewan | P2p reputation management using distributed identities and decentralized recommendation chains[END_REF] ensure that each node accepts to cooperate with its neighbors based on their past behavior; credit based schemes [START_REF] Buttyán | Enforcing service availability in mobile ad-hoc wans[END_REF][START_REF] Zhong | Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks[END_REF][START_REF] Vishnumurthy | KARMA: A Secure Economic Framework for Peer-to-Peer Resource Sharing[END_REF][START_REF] Belenkiy | Making p2p accountable without losing privacy[END_REF] provide node collaboration by rewarding cooperating nodes with a certain amount of credits in the form of E-cash [START_REF] Chaum | Blind signatures for untraceable payments[END_REF][START_REF] Chaum | Blind signature system[END_REF] or a tradable good/service, that they further can use for their own benet.

However, due to the specic context of P2P OSN where peer nodes are maintained by OSN members, we decided to ll the lack of cooperation among peer nodes with the real life trust between OSN members derived from the OSN itself. Therefore, as a second design principle, we connect peer nodes in such a way that if one peer serves another, the user maintaining the serving peer and that one maintaining the served one are real-life friends.

Idea of the solution

Based on these design principles, we propose a new privacy-preserving distributed OSN and call it Safebook . In the following, we discuss how we came up with the core design of the Safebook solution.

As a straightforward implementation of the two design principles, a simple P2P system whereby each user's data is stored and made available by peer nodes operated by users who are friend of that user (friend nodes) seems to be a reasonable rst step toward the main security objective of privacy against a centralized omniscient party.

Therefore, we dene a ring structure where each user is at the center of a ring, and her friend nodes hosting the user's data constitute the rst ring.

Nevertheless, such a simple scheme would suer from a further privacy problem that is due to the scheme itself. Since all the social network services pertaining to a user will be Security and privacy of the system might be compromised if malicious users were able to impersonate legitimate ones. In addition to the attacks discussed in chapter 3, malicious users would then be able to intrude into the rings surrounding a target victim and derive the friendship relationship we aim to protect. As a consequence, a third step toward ensuring user authentication has been taken.

In Safebook, a Trusted Identication Service (TIS) that does not take part in the OSN provides users with unambiguous certied identiers associated to their real identities. Such TIS does not contrast with the purpose of decentralization, as it can be implemented in a decentralized fashion. TIS is not involved in any communication or data management operation among users, is contacted only once, and can be provided o-line.

Finally, classical encryption techniques have been adopted to ensure data condentiality and data integrity.

In summary, Safebook has been designed as an OSN addressing privacy from the very beginning. Privacy against centralized omniscient entities is achieved with the adoption of a decentralized P2P approach. Privacy against malicious users is achieved with communication obfuscation through anonymous routing techniques, data condentiality through the use of encryption, and prole integrity through certied identiers. For these reasons, Safebook achieves privacy by design.

Availability of basic services such as data storage, data lookup and communication is guaranteed by the cooperation among peer nodes. Such cooperation is enforced by real-life trust among OSN members.

Nevertheless, in the specic context of OSN, we realize that the real life trust between users can serve much more than simple cooperation: it can be used to build the online social network itself (see gure 5.1). Therefore, the OSN helps user to establish friend relationships, and friend nodes provide the basic services of data storage, retrieval and communication, and consequently build the OSN.

Main components

The real life trust between OSN users as in the SN graph is mapped into ring structures called Matryoshkas, where node neighborhood is based on user friendship. Direct trust relationships are leveraged for the purpose of data storage and data availability. Since friend nodes are considered honest but curious, data is stored in an encrypted form.

In Safebook, a target prole data can be accessed through hop-by-hop trusted paths whose endpoints can be retrieved from an additional Peer-to-Peer system maintained by the OSN users themselves. Dierently from the Matryoshkas, this P2P system is used for indexing purpose only: it does not store user's prole data and does not take into account user's friendship relations.

Safebook can thus be seen as an overlay network composed by two dierent layers:

• the Social Network Layer consisting of Matryoshkas and providing each member with a set of functions corresponding to social interactions in the real life, such as prole data retrieval, message exchange et similia;

• the Peer-to-Peer layer oering the infrastructure to build and to access the Matryoshkas.

A Safebook user is represented as a host on the Internet, a peer node in the P2P layer and a user in the SN layer (see gure 5.2, left). Dierent identiers are used to address the same party in each layer: a user Id denotes a node in the SN layer, a node Id in the P2P layer, nally an IP address in the Internet layer.

In addition to Matryoshkas and the P2P system, the last component of Safebook is an oline Trusted Identication Service (TIS) (see gure 5.2, center) in charge of generating the identiers needed to address users in the SN layer and peer nodes in the P2P layer.

Since these identiers are issued together with corresponding certicates, they can never be manipulated nor forged.

Matryoshka

A Matryoshka is a friend-of-friend structure providing the user with data storage and communication obfuscation services.

A user V's Matryoshka Θ V consists of a group of nodes surrounding V's node (see gure 5.2, right). The nodes of a Matryoshka are organized into several concentric rings, namely shells, and several paths lead from the nodes in the innermost shell Λ V to the nodes in the outermost shell Ω V . With θ j V ∈ Θ V being a node in the jth shell, with j ∈ [0, . . . , M axShell],

each Matryoshka further features the following properties:

1. V 's node θ 0

V is located at the center of the Matryoshka and is called the core;

2. if a pair of nodes θ j V , θ j+1

V is connected, a friendship relation between them exists in the social network layer;

3. each node θ 1 V , located on the innermost shell Λ V and called a mirror , is a trusted contact of the core V and stores V's data in an encrypted form; 4. each node θ M axShell V , located on the outermost shell Ω V and called an entrypoint , acts as a gateway for all the requests destined to V;

5. each node θ j V , j ∈ [2, M axShell -1]
, located on a shell between Λ V and Ω V , is called a prism of V;

6. the set of prisms is denoted as ∆ V .

In summary V's Matryoshka Θ V is the union of the set of mirrors Λ V , the set of prisms ∆ V , the set of entrypoints Ω V and the core V. The number of V's mirrors represents the number of available partitions of V's prole data, while there are as many entrypoints as paths that can lead to a mirror. Each i th mirror λ i ∈ Λ V represents the root of a subtree with leaves that are lying in the outermost shell Ω V . The branching of all the subtrees, the span factor , is set by V. The cardinality • of the set Ω V in consequence is Ω V = Λ V Span M axShell-1 .

Peer-to-peer substrate

The P2P substrate of Safebook is a DHT similar to KAD [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the xor metric[END_REF][START_REF] Steiner | Faster content access in kad[END_REF] in charge of storing and retrieving the entrypoint references of all the users' Matryoshkas. Such a substrate comprises of all user nodes and allows any node to issue a lookup query to reach the Matryoshka of any user.

The DHT is dened as:

DHT = K, N, R, id n (•) , id r (•) , ρ (•)
where K is the DHT keyspace, N and R correspond to the set of nodes and the set of resources, respectively, and id n : N → K, id r : R → K denote the functions associating a node and a resource to their identier respectively. Finally, ρ : K → {N } denotes the mapping function which outputs the set of peers responsible for a resource given the resource identier.

A resource consist on a list of entrypoint references of a target user's Matryoshka. The corresponding resource identier DhtKey is represented by a user identier or by an hash of the user's attributes such as her full name, her birthday etc.

Redundant copies of (key value) pairs (DhtK ey, resource) can be stored by nodes whose identier matches DhtKey on a predened amount of rst bits.

Much alike KAD, Safebook implements a greedy routing, minimizing the distance measured in an XOR-metric between the DhtKey to locate and the node Id of neighboring nodes.

Due to the privacy-by-design constraint, unlike KAD, the lookup queries are not always processed iteratively: Safebook uses recursive processing with hop-by-hop anonymization as a basic technique to assure the untraceability of requesting parties in case a list of entrypoint reference is queried.

Trusted Identication Service

The TIS is a trusted third party that generates and grants for each Safebook user V a pair of identiers: a node Id (N Id V ), unambiguously identifying V as a peer in the P2P layer, and a user Id (U Id V ) unambiguously identifying V as a user in the social network layer.

Both identiers are computed starting from a set of V's properties such as V's full name, birthday, birthplace etc.

A pair of certicates link each identier to a respective public key provided by V. Corresponding private keys are known by V and nobody else. Since the P2P system allows to retrieve a node IP address given a node Id, the separation of node-and user-identiers is required to prevent malicious users from deriving a victim's IP address. Only trusted contacts of a node are able to link these two identiers, as they serve as mirrors and in consequence know both. TIS constitutes an exception, as it is the only party in Safebook that is able to link the user Id and node Id of users other than their own trusted acquaintances. If compromised, in addition to the users' location, TIS may also disclose users' participation in Safebook. However, the TIS does not possess any user's private keys, therefore it cannot impersonate any victim, nor retrieve her set of trusted contacts or access data content published with restrictions.

While the TIS is a centralized infrastructure and in consequence might appear to break the paradigm of a decentralized architecture of Safebook, it can easily be implemented in a distributed fashion. Furthermore, it is an o-line service used only once by each Safebook user and, unlike a central SNS server, it does not threaten the privacy of users, as it is not involved in any communication or data management operation among users or peer nodes.

A collusion of the TIS with the Internet Service Provider would circumvent the concept of separation of identiers. However, this attack is only successful if the ISP controls the access to all users of Safebook, as only the privacy of users using the directly monitored Internet connections can be disclosed. Entirely protecting the privacy against a malicious ISP is only possible when leveraging much more complex concepts of anonymization, which for the sake of eciency is refrained of. Safebook indeed does not provide anonymous communications on the network level.

In the following section we present the main functionalities of Safebook, which allow the users to share their sensitive data with limitations and communicate between them.

Functionalities

The main functionalities of Safebook may be divided into three main categories:

• data management;

• key management;

• communication management.
Each functionality is detailed in the following of this chapter.

Data Management

Data management functionalities allow users to generate, modify and delete sensitive information in the OSN.

In Safebook, data objects, also referred as data items, are user-generated pieces of information describing the user's prole as detailed in chapter 2.3.

A data item D is represented as a tuple < DId, type, value, version >, where type describes the nature of the data, such as personal contact details, connectivity, interests etc.

(see gure 2.3), value constitutes its content, and version its current version. A data item identier DId D unambiguously identies D among all the data objets, and allows for the basic operations of item storage, retrieval or deletion.

A Distributed Data Storage Space (DDSS) S V is dened for each user based on her friendship relations. Authorization to store content on such a space comes from the real life friendship relations of V, and therefore is granted to V only.

The size of S V is dynamic: at friendship establishment, each friend F i of V reserves an arbitrary amount of her own Local Data Storage Space (LDSS) L V F i for V. The sum of each friend's LDSS allocated for V nally builds V's DDSS.

Due to the distributed nature of DDSS, data is partitioned into n blocks and for a given amount of redundancy these blocks are coded in n + l fragments such that any n fragments are sucient to reconstruct the original object.

Before being partitioned, encryption operations may be performed on D to guarantee its condentiality and limit the access on it.

Key Management

As stated previously, user's data may be encrypted based on the willingness of the owner.

Key management functionalities allow users to limit access on their shared sensitive data.

Safebook ensures data condentiality thanks to traditional public-key and symmetric cryptography. Access to the content can be restricted to several user-dened (overlapping) groups of contacts.

In order to minimize the storage overhead at the DDSS, data is encrypted with only one key, namely the Data Encryption Key (DEK). This DEK needs to be distributed among all users that are authorized to decrypt the data. The distribution of a DEK requires the encryption of it with a Key Encryption Key (KEK) which is previously distributed among members during friendship establishment. Users do not rely on any third party to perform key distribution; they send the keying material to all the group members they manage.

Friends of V access S V within the limits of the Access Control Policy (ACP) dened by V.

Basically, users in Safebook create groups of contacts by dening several attributes, such as `Family', `Colleagues' etc. and associate them to each contact. Data protected under these attributes will then be accessible to all the contacts associated to the appropriate attributes only.

In Safebook, attributes are dened through Badges. Users in Safebook know which badges they provided to which contact, but cannot know how many badges they received from a given contact, nor the description of the associated attribute. For instance, V may grant U a `Professional' badge without disclosing the attribute `Professional' to U, and without revealing who among V's contacts holds this badge too. This happens since, from a system perspective, a badge b corresponds to a set of DEKs used to encrypt the data accessible to all the contacts provided with that badge. Such a set is dened as:

D n b = h i (s b ) : i ∈ {1 . . . n} 1
where h i (s b ) denotes a well known one-way hash function h () sequentially applied i times to an initial seed s b . The idea of sequential password hashing was originally proposed in [START_REF] Lamport | Password authentication with insecure communication[END_REF] and afterward leveraged to design one-time password authentication systems such as S/Key [START_REF] Haller | The s/key one-time password system[END_REF]. Safebook does not perform authentication of requesting users and uses each hash as a 1 In this notation, the colon (`:') means `such that'.

DEK rather than a one-time password.

When V grants U a badge b, U receives a DEK h i (s b ) that does not reveal anything about the badge attribute nor the list of V's friends who received that badge too.

After the reception of h i (s b ), U is able to derive all the keys h j (s b ) : j ∈ {i . . . n} ⊆ D n b and access all the data stored in S V encrypted with such DEKs.

Safebook does not ensure backward secrecy : in a Social Network context, in fact, users are likely to allow a new group member to access the data previously shared for that group.

When V revokes b from U, V advertises h i-1 (s b ) to all the contacts previously granted with b, one by one, except U. Future data previously accessible by contacts granted with b will be encrypted by V with the DEK h i-1 (s b ). Previously published data encrypted with h j (s b ) (being j ∈ {i, . . . , n}) will not be encrypted again and will thus still be accessible by

U.

Since reversing the hash function h () is computationally infeasible, Safebook ensures forward secrecy as future communication will not be accessible by the leaving member U.

Generally speaking, V denes her ACP by specifying a set of badge rules r ∈ R V and assigning a seed s r to each rule.

When a contact U is granted with a set of badges B U V from V, a DEK set

E U := h i s r U j : r U j ∈ R U V ∀j ∈ {1, . . . , R V } , i ∈ {1, . . . , n}
corresponding to the rules R U V satised by U is sent to him. When revoking a badge b from U, V advertises a new set of DEKs E X to every contact X satisfying one or more rules U was also satisfying before b was revoked from him. From this point on, V encrypts her data with the new DEKs.

Communication Management

Communication management functionalities allow users to establish unobservable friendship links and to communicate with each other while ensuring condentiality and message integrity.

Communication between two users V and U can take place either in a synchronous or asynchronous fashion. In the rst case, both parties exchange messages in real time. Each user stores such messages in her own DDSS and shares it with trusted contacts if needed.

In the second case, V generates a message for U and stores it in her DDSS S V . Once U looks up for new available V's data, she retrieves the message. To reply, U follows the same steps:

she stores the reply in her own S U , then V retrieves this reply while querying for V's new data.

Message integrity is guaranteed by the use of digital signature, while communication condentiality is achieved by encrypting messages with a symmetric DEK computed (in case of synchronous communication) or previously shared (in case of asynchronous one)

between the sender and receiver.

Communication is obfuscated through multi-hop routing of messages along friend-offriends chains in such a way that information on data requester cannot be retrieved. In case of synchronous communication, this hides the IP address of communicating parties 2 and therefore their location. In case of asynchronous communication, this also prevents a user V's friend F i storing V's data from deriving the trust relationships between V and the data requester U.

2 However, synchronous communication between trusted parties may be directly established.

Core protocols

Core functions of Safebook implement three main groups of operations:

• prole creation , where the user's identity is created and granted with the certicates issued by the TIS;

• SNS setup and maintenance, where user's node takes part in the distributed SNS architecture of Safebook;

• SN communication and relations management , where user benets from the SNS.

Each operation calls for the execution of a series of secure protocols aiming at obtaining credentials, building and keeping the consistency of the Safebook overlays and establishing secure communication channels. Throughout the description of these protocols, {M } SK X denotes a message M being signed by user X 's private key K - X , and E K Y {M } denotes the message M being encrypted with the user Y's public key K + Y 3 . The distinct identiers of Safebook users are associated with keypairs: while N X = N - X , N + X denotes the keypair for the node ID, U X = U - X , U + X denotes the keypair for the user ID of node X 4 .

To assure integrity and condentiality, all messages at each hop are signed with the sender's (X ) node ID private key and encrypted with the receiver's (Y ) node ID public key.

For the sake of clarity, the resulting term E N Y {M } S N X is simplied and is denoted as M in the remainder of this thesis.

Prole Creation

The identity creation protocol (see gure 5.4) is responsible for providing a new user V with the credentials required to participate in Safebook.

In order to join, a new node V must be invited by a registered user A that needs to be an acquaintance in real life. Initially, A sends out-of-band V an invitation request invReq message, signed using the private key U - A . It contains a tuple N ame A of properties that 3 More precisely, session keys are used to encrypt the payload. Such keys are advertised at the beginning of the message encrypted with the target node Id public key. 4 Each private key associated with a node-or user-identier is generated by the owner of the identier and known to nobody else. identify the user A, the certicate Cert h (N ame A ) , U + A , as granted by the TIS, and the public key T IS + of the TIS. The invReq message is the only message that is sent in clear text, since V's public node-and user-ID keys haven't yet been generated nor certied and it is sent out of band anyway.

Upon reception of the invReq message, V generates the two keypairs N Id V and UId V . Subsequently, it starts another out of band process: it creates its own identity tuple N ame V together with a proof of ownership of N ame V , and transmits both together with the public key U + V , in a credReq message, to the TIS. The TIS then generates V's user ID U Id V and node ID N Id V by applying two distinct keyed hash functions h M K 1 (•) and h M K 2 (•) on N ame V . Additionally, it generates and signs the registration keys of V DhtKey V by hashing and signing all permutations of elements in N ame V .

The TIS responds with a credRep message out of band, with the generated identiers and DHT keys, together with the respective certicates Cert U Id

V , U + V , Cert N Id V , N + V ,
and Cert DhtKey V , U + V .

On reception of credRep, V joins Safebook and hence the P2P substrate and can start creating her own Matryoshka. Subsequently, all messages sent from and received by V in the P2P overlay are signed using the sender's N -and encrypted using N + of the receiver.

Social Network Service setup and maintenance

Once created her account, the user V is able to setup her Matryoshka and to get reachable by other users.

Matryoshka Setup Protocol

The Matryoshka setup protocol (see gure 5.5) allows for the creation of Matryoshkas.

During the rst execution of this protocol, the initiating node V sends the inviting node A a path creation request P athReq. This message contains a registration token RegT ok, a data structure T tlM atr for the number of hops on the created paths, the span factor Span for the tree through the Matryoshka, and a signed random number Rnd. The registration token includes the DHT keys to be registered, in order for V to be found in the OSN, V's user ID certicate, authenticating U Id V , and the lifetime ExpireT ime of the DHT registration of the DhtKey V . The T tlM atr is a recursively signed data structure generated by V including a set of decreasing time-to-live values based on the desired hop length from V's core to one of its Θ V 's entrypoints. Each node on reception of the P athReq removes one or more of T tlM atr's signatures, thus potentially causing a continuous decrease of the ttl value at each hop. The value in Span indicates to the mirrors and prisms of V how many next hop nodes should be selected in order to guarantee the desired availability of the data that V publishes.

Upon receipt of a pathReq message, each mirror of V veries the integrity of the registration token by checking its signature with the key U +

V contained in the TIS certicate. It then removes one or more signatures 5 from T tlM atr and selects a next hop B from its friendlist for the path and forwards the updated pathReq. In case the core has set a spanning factor greater than 1, it selects further nodes to forward the updated pathReq in order to achieve the requested branching. This process is recursive: B removes a signature from T tlM atr and forwards the updated pathReq to a number Span of his selected trusted contacts, and 5 Removing more signatures allows Matryoshka chains to have dierent lengths. However, the value of a T tlM atr can never be increased to protect against DOS attacks. so on, until, at one node D, the last signature from T tlM atr is removed. D becomes in consequence an entrypoint for the Matryoshka of V.

For this purpose it routes one registration request for each key in DhtKey through the P2P system. Since D's reference as a Θ V 's entrypoint is going to be a public domain information, D can nd a node K, whose node ID is closest enough to the registration key, in an iterative way: D selects from its neighbors the node N 1 with the node ID being closest to the registration key, measured using the XOR-metric, as the next hop. N 1 provides D with the reference to (one or more) closest node N 2 and so on, until a suciently close node K is reached. Such a node K, called dock , is in charge of storing the association (DhtK ey,EP T entry) in the P2P system. D then sends K a register message containing the eld EP T entry S N D , and the random number Rnd SU V (see gure 5.6). The Rnd SU V poses as an authorization and D can claim to be a valid entry point for V. EP T entry is the new record that K adds to its Entrypoint Table (EPT) and contains the registration token RegT ok, D's node ID certicate, D's ip address and a timestamp time. K then updates its EPT and responds with a pathRep message that is forwarded back to V along the inverse path. Additionally, much alike KAD, in Safebook K stores all registered values in k nodes around the target node of a registration request, the RespArea of docks for a registration key.

Matryoshka Update Protocol

User V's Matryoshka plays a fundamental role in guaranteeing both communication privacy to V and the availability of V's data to all the other users, without the need for V to be online. For this reason, the structure of Θ V always automatically has to be kept valid using the Matryoshka update protocol (see gure 5.7), even in case of node arrival and departure, the latter possibly being due to choice (a user logging out from Safebook) or failure (an Internet connection problem). Considering that a node B leaves Safebook, it sends a nodeLeaving message to the neighbors inward (A) and outward (C,. . .) on the path through the Matryoshka. The message contains the user identier U Id V of the aected Matryoshka and is forwarded to all entry points, thus pruning the subtree rooted in B. The entry points send an unregister message to all the docks K previously addressed in the registration phase. A at the same time resends the pathReq message and sends it to a new selected contact E without requiring V to be online. From this point on, the update process is analogous to the path creation.

Social Network Communication and Relationship management

Matryoshkas allow users to access the OSN facilities (see gure 2.2). In the following, we will examine in detail the protocols in charge of looking up for a target prole data friend lookup/data retrieval, befriending an user friendship establishment, and store data at friends node data storage.

Lookup Protocol

The lookup protocol (see gure 5.8) allows for the retrieval of the entrypoint list of a user V's Matryoshka Θ V . A requesting user U initiates a recursive lookup in the P2P system by computing DhtKey V . As soon as the lookup message epLook reaches one of V's docks, the dock responds with an epRep message, containing the EPT entry corresponding to

DhtKey V 6 : epRep = EP T entry (DhtKey V ) , Cert N Id K , N + K S N K
.

The EPT entries are cached on reception in order to avoid multiple redundant requests.

Data Retrieval Protocol

Once the entrypoints of the Matryoshka of a user V are discovered, the data retrieval protocol enables the user U to retrieve V's prole data P rof V in an encrypted form. First of all, U delegates one of his innermost shell nodes Z to send a prole request message prof Req for V's data to D, one of the entrypoints of V's Matryoshka. This request is recursively forwarded through the Matryoshka to A, one of the mirrors of V, that is storing P rof V . A then responds with a prole reply message prof Rep containing a list of encrypted signed data items of V. This message reaches U by following the same path in the reverse order (see gure 5.8). According to its privileges, U subsequently is able to decrypt and access certain parts of this data.

Figure 5.8: V's data lookup. 6 Several DHT lookup keys for the same target user can be computed starting from dierent properties such as rst name, birthday etc. and served from dierent docks.

Friendship Establishment

In Safebook the trust relations are not considered as symmetric. Rather than requesting for a target user V's friendship, a Safebook user U advertises her friendship to V.

This advertisement takes place in three steps: rst of all, U looks up for all the publicly available data of the users holding a set of properties corresponding to several DhtLkey; secondly, among all the retrieved proles, U selects the target user V to be advertised; nally, a friendship advertisement message f rAdv is sent to V through V's Matryoshka (see gure 5.9). Such a message includes U Id V 7 and a friend token consisting on the certied identity of U, her node and user identiers, a short friendship message, and a list of symmetric keys to be used to decrypt U's protected data.

Friendship advertisements may be repeatedly delegated to a trusted contact Z in the advertiser (or her friend-of-friend) Matryoshka through a f rDel message containing f rAdv together with the entrypoint list of V's Matryoshka.

In case V is oine, her mirror A will act as a mailbox and keep the friendship advertisiement until V will get on-line again.

If V replies U with her friendship advertisement, the trust relation becomes symmetric: U can become a new mirror of V and vice-versa. Figure 5.9: Friendship advertisement in Safebook. 7 nodes may serve more than a single Matryoshka.

Data storage

A user U's data item D is assembled into a token together with the corresponding DId and Dversion. Tokens are further signed with U - U and encrypted with DEK. Such an encrypted signed data token ESDtok is further stored at U's new mirror V in a dataStore message together with DId, Dversion and the DEK identier DEKid that are used by V as a lter while replying to a prole data request addressing U.

At the reception of dataStore, V indexes ESDtok with Did, Dversion, DEKid, at U's DDSS, before replying with a storeConf message. Upon the conrmation reception, U can keep track on which (partitioned) (encrypted) item is stored at which mirror.

Summary

In this chapter we pointed to the centralized architecture of existing on-line social networks as the key privacy issue and suggested a solution that aims at avoiding any centralized control. Our solution, namely Safebook, is an on-line social network based on a peer-to-peer architecture. Thanks to its fully distributed nature, the peer-to-peer architecture inherently avoids centralized control by any potentially malicious service provider. In order to cope with the lack of trust and lack of cooperation that plague peer-to-peer systems and to assure basic privacy among the users of the social network, Safebook leverages the trust relationships that are part of the social network application itself. Privacy in basic data access and exchange operations within the social network is achieved thanks to an anonymization technique based on multi-hop routing among nodes that trust each other in the social network. Similarly cooperation among peer nodes is enforced based on hop-by-hop trust relationships derived from the social network itself.

Chapter 6 Performance of the Approach

The new architecture described in chapter 5 raises new challenges with respect to performance. This chapter therefore presents a performance evaluation, and analyzes the feasibility of Safebook.

We evaluate the feasibility of Safebook in an incremental way. First, we evaluate the probability of reaching at least one mirror in order to retrieve data, based on the behavior of users (on-line probability) and the privacy degree. We further focus on the feasibility of a real Matryoshka graph since data can be large and therefore be partitioned. Finally, we evaluate the performance of the underlying data storage and data availability mechanisms.

Preliminary discussion As explained in the previous chapter, Safebook allows each core to set two parameters Span and h for the purpose of building its Matryoshka. Such parameters indicate to mirrors and prisms the number of next hops to be selected, and the number of shells to be built, respectively. However, since a mirror or a prism can select an arbitrary number of next hops, and may also decrease T tlM atr by 1 or more (or may not decrease it at all), Matryoshkas are dynamic structures with varying branching and variable number of shell for each branch.

Nevertheless, for the purpose of our analysis, we will assume Matryoshka as static structures with h shells for each branch. In this setting, with Span > 1, dierent groups of entrypoints share the same predecessor. A malicious user with extra knowledge could derive then the cut set of the entrypoints' contact lists it obtained, thus generating a good estimate for some of the nodes on the rst hidden shell. Therefore, we will also assume Span = 1.

Mirror reachability -building one chain

In order to retrieve a target Safebook user's data, a requester contacts the entrypoints of the target user's Matryoshka. Each entrypoint then forwards the request to the next hop in the predened path in the Matryoshka graph. Since the data retrieval is successful only if all nodes in the path are on-line at the same time, we rst evaluate the probability of building one chain and further compute the residual lifetime of a chain. Reaching one mirror strongly depends on the length of the chain which basically corresponds to the number of shells h of the Matryoshka graph. Since h also plays a role on the privacy degree of the application, we analyze the impact of its increase on the performance assuming a homogeneous behavior of the nodes in terms of their on-line probability p and their average number of friends f . The probability of building a h -1 hop chain, p chain , connecting a mirror to an entrypoint in the h-th shell is dened by the probability for each node in the chain, excluding the entrypoint, to consecutively nd at least one online friend among its friends. Since the probability of nding at least one online friend among an average number f of friends is dened by a binomial distribution, the mirror reachability is dened by the following equation:

p chain =   f j=1 f j p j (1 -p) f -j   h (6.1)
In addition to the computation of the online probability of h nodes, the residual lifetime of the chain, during which data retrieval is performed, should be evaluated. Assume S on , S of f are random variables drawn by the distributions On (x), Of f (x) of online and oine session times of a single node respectively, and R is a random variable from the residual lifetime distribution Res (x). Authors in [START_REF] Yao | Modeling heterogeneous user churn and local resilience of unstructured p2p networks[END_REF] dene the probability of reaching a lifetime t by the following equation:

P r [R < t] = 1 E [S on ] t 0 (1 -P r [S on < u]) du (6.2)
Since all nodes in one chain are assumed to be online at the same time, we dene the residual lifetime Rc h of a (h -1)-hops chain as the minimum node residual lifetime Rn i among all the h nodes involved in that chain. Hence:

Rc h = min {Rn 1 . . . Rn h } (6.3)
In [START_REF] Guha | An experimental study of the skype peerto-peer voip system[END_REF], authors conducted some measurements of online and oine session times of users using the Skype application 1 . Figure 6.1 plots the residual lifetime deriving from equation 6.2 based on this real data set: since R is stochastically larger than S on , the lifetime of a newcomer is likely to be lower than the residual lifetime of an already online node.

We compute the online node probability p as it is dened in [START_REF] Yao | Modeling heterogeneous user churn and local resilience of unstructured p2p networks[END_REF]:

p = E [S on ] E [S on ] + E [S of f ] (6.4)
Based on this equation and the length h of a chain, we evaluate the residual lifetime of a chain using simple Monte Carlo techniques on the distribution Res (x). Figure 6.2 shows the result based on dierent values of h. From this analysis, we conclude that the lifetime of a chain rapidly decreases with the increase of h. For example, a 3-hop chain composed by 4 nodes will keep being online for at least 19.2 minutes with 90% of probability. As a result, h should be as large as possible to enforce privacy but small enough to oer a better performance in terms of reachability.

Data availability -Matryoshka feasibility

In order to ensure both data availability and reliability in Safebook several mirrors have to be reached. Indeed, data can be partitioned or replicated. We therefore extend our feasibility analysis to the complete Matryoshka graph, with respect to the users' online probability and the number of shells h. Reaching at least m mirrors requires the construction of m independent chains. Based on the probability of building a single chain already dened in equation 6.1, since m mirrors among f have to be online, the probability of building a complete Matryoshka with depth h is computed as follows:

p M atr = f i=m f i p i (1 -p) f -i   f -1 j=1 f -1 j p j (1 -p) f -j-1   h-1 (6.5)
In this equation, we assume that friends of each node are chosen independently. However, while choosing the next hop, there is a chance of choosing a friend who is already involved in the Matryoshka. Therefore, while dening p M atr , we introduce a new parameter f l , which Figure 6.2: Chain residual lifetime with respect to h corresponds to the average of eligible friends of one node at shell l. We then have:

p M atr = f i=m f i p i (1 -p) f -i h-1 l=1   f l j=1 f l j p j (1 -p) f l -j   (6.6)
Therefore, p M atr depends on p, h, m and f l . Evaluating f l is not trivial; nevertheless we distinguish the best and worst f l by taking the overlapping ratio between friend lists into account. In the best case, with no overlapping between friend lists, we have f l = f -1, while in the worst case, with full overlapping between friend lists, we have f l = f -ml.

The probability p M atr is evaluated through some experiments where the online probability is set to p = 0.53 (based on equation 6.4 and the Skype dataset2 ), and the average and gure 6.4. In gure 6.3, illustrating the best case where there is no overlapping between friend lists, p M atr does not depend on h, therefore the equation can be simplied to:

p M atr = f i=m f i p i (1 -p) f -i (6.7)
On the contrary, in the worst case, as shown in Figure 6.4, h plays an essential role.

The eect of overlapping between friend lists thus has a major impact on the performance.

Such an impact will be evaluated in the next chapter. 3 According to Facebook statistics, the average number of friends is 130 [START_REF]Average facebook user has 130 friends[END_REF].

Data storage and availability

Given the new privacy preserving communication architecture, we would like to evaluate the amount of data that a peer is required to serve in order to achieve an ecient data retrieval operation.

As illustrated in chapter 5.4. In order to propose an ecient resource management solution for Safebook, the following questions should be answered:

• how to replicate data? can we fragment it?

• how much should one fragment size be?

• how large can the retrieved ESDtok be?

Notwithstanding the signicant amount of research on data storage and reliability in P2P networks [30,[START_REF] Tahoe | [END_REF][START_REF] Leng | Maintaining replicas in unstructured p2p systems[END_REF][START_REF] Bhagwan | Total recall: system support for automated availability management[END_REF], we propose an initial evaluation of the load at each peer using a very simple redundancy mechanism.

We propose to implement a simple parity encoding mechanism [START_REF] Reed | Polynomial Codes Over Certain Finite Fields[END_REF] where each ESDtok is partitioned into n blocks and for a given amount of redundancy these blocks are coded in n + l fragments such that any n fragments are sucient to reconstruct the original object.

As a result of the previous section, since a node can contact m online mirrors in order to reconstruct the core's ESDtok, we set n = m. Moreover, assuming that all f friends store one fragment, the number of additional fragments is set to l = f -m.

Maximum fragment size evaluation

The amount of data a peer is required to serve for each of its friend depends on the number of requests it receives, the residual life time of the chain and its capacity.

We rst dene X(t) as the random variable corresponding to the number of requests that are served by a peer during time t. With probability α, X(t) does not exceed a value

X (α) t : p X(t) ≤ X (α) t = α (6.8)
We assume that the request rate originating from one user for a single prole follows a

Poisson process with rate λ. Since a node is involved in q Matryoshkas, the total request rate follows a Poisson process with rate λqf on where f on is the number of online friends and thus who can send the request. Therefore, the maximum number of requests X (α) R that are encountered with probability α during the residual life time R of a chain respects the following condition:

p   X(R) ≤ e -λ×q×fon×R X (α) R k=0 (λ × q × f on × R) k k! ≤ X (α) R    = α (6.9)
The last parameter which is required to compute the size of a data fragment is the capacity of the user. We assume that each node N i has a xed capacity c i which represents the bandwidth in this particular environment. As previously mentioned, a peer node N i involved in the Matryoshka of another peer N j serves requests originating from N j 's friends.

In order to serve the corresponding X (α) R requests, the fragment size s(b i ) should be computed as follows:

s(b i ) = c i × R X (α) R (6.10)
We consider that both the capacity is identical for any node in the network and we set ∀i c i = c. Thus, the size of a data fragment in a homogeneous network is dened by the following equation:

s(b) = c × R X (α) R (6.11)

Retrieved data evaluation

Once the size of each fragment is computed based on the capacity of each user, the residual lifetime of chains and the request rate, the maximum size of an ESDtok can easily be computed using the underlying reliability parameters. Hence, as previously stated, the number of fragments n which is sucient to reconstruct the whole content, that is, the requested data, is equal to the number of mirrors m estimated based on the online probability of users. Thus, the size of an ESDtok, that is s(ESDtok), is computed as follows:

s(ESDtok) = m × s(b) (6.12)
If we take into account the expected value of X(R), from 6.11 we have:

s(ESDtok) = m × c × R E [X(R)] = m × c λ × q × f on (6.13)
However, since the number of online friends corresponds to the number of mirrors for a user's Matryoshka, m = f on . Then we can simplify equation 6.13 and obtain:

s(ESDtok) = c λ × q (6.14)
A user V takes part in several friend of friends Matryoshkas, depending on the value of h.More precisely, V takes part in each of her m h online friend of friends with probability

1 m h-1 4 .
Therefore, q can be further related to the Matryoshka parameters m and h as follows:

q = h i=1 1 m h-1 × m h = m × h (6.15)
We thus have:

s(ESDtok) = c λ × m × h = c λ × f on × h (6.16)
Then, even if with a high f on the possibility to build Matryoshka chains increases, the trac in the network also increases, therefore the size of data decreases that can reliably be retrieved by the data requester in a residual time of R.

Prole size evaluation

For every data request dataReq, a data reply dataRep cannot exceed s(ESDtok) without incurring in the risk of connection breakdown due to chain residual lifetime expiration 5 . However, multiple dataReq can be triggered 6 and several ESDtok, thus several data items, can be collected to enrich and update the prole prof V of a target friend V.

In section 5.3.1 we already mentioned that the total amount of prole data prof V a user V can setup at her DDSS S V is dynamic, and depends on the amount of LDSS L V F i each friend F i of V allocates for V.

If a tit-for-tat strategy is adopted, V benets from a DDSS S V and makes available to friends the same space in her LDSS. The remaining L V -S V is available for V to store a local copy of her generated data items, i.e. her prole. Therefore, the maximum prole size s(prof V ) can be computed as:

s(prof V ) = L V 2
(6.17)

Example

We assume that the number of online friends, i.e. the number of prole requesters, ranges between the 10th and the 90th percentile, respectively f min and f max , of the binomial be applied. 5 A high value of α decreases this risk but leads to a lower s(ESDtok) at the same time. 6 Up to λ × m per friend every R time, even if such friend is oine, assuming her Matryoshka is connected and served by m mirrors. distribution where the online probability for nodes is 0.53 and the average number of friends is 130. Therefore, with the 90% of probability, no less than f min = 61 friends and no more than f max = 75 ones will be online in Safebook.

We assume the number of shells in Matryoshkas h is 4.

We assume α = 0.9, therefore no more than X(R) 0.9 requests will be served by a user in Safebook with 90% of probability in the residual lifetime R being previously computed, and set to 19.2 minutes. Figure 6.5 shows, for dierent upload bandwidth values, the maximum size of fragments served by a user based on the number of users q = f max × h for which the peer is involved in the Matryoshka and the request rate λ expressed in data requests per day. From this gure, we can conclude that, if ADSL connection with 0.5Mbps upload bandwidth is used 7 , when 3 prole requests per friend (target Matryoshka) per hour are triggered (i.e. λ 1 hrs = 36),

the maximum size of fragments to be forwarded is around 3.4 KB. Therefore, with 90%

of probability, at least f min of such fragments will be collected by the requester, that will download at the end around 200KB of data (see gure 6.6).

Summary

In this chapter we have investigated the performance of Safebook. In the rst part of the study, an analytical model of the feasibility of Safebook has been provided in an incremental fashion: since the correct execution of Safebook depends on the reachability of at least one mirror, the residual life time of a path between a mirror and an entrypoint was rst dened and evaluated based on the Matryoshka setup parameters and the online probability of nodes.

This analysis conrms the fact that choosing a large value for the depth h of the Matryoshka (which is a privacy requirement) can have a severe impact on the data retrieval and thus, h should be dened as small as possible but should still allow for a good privacy degree.

Furthermore, in order to ensure data availability, the feasibility of the complete Matryoshka graph is evaluated. Since a successful data retrieval depends on the reachability of more than one mirror towards dierent and independent paths, the ratio of overlapping between friend lists has to be taken into account. Finally, Safebook's feasibility being conrmed, the maximum amount of data that may be retrieved at every request is also evaluated based on 7 Standard ITU G.993.2.

Chapter 7

Impact of social graphs on performance and privacy

In this chapter, we analyze the impact of social network graph topology on security and performance and we prove that regardless of the particular centralized or distributed nature of the OSN, the achievable security and privacy degree strongly depends on the graphtheoretical properties of the social graph representing the real friendship relations between the users. We rst observe three metrics, namely the degree, the clustering coecient and the mixing time, and show that they give fundamental insights on the privacy degree of the OSN. We further evaluate the privacy degree of Safebook based on the previous analysis.

Finally, we observe a strong trade-o between privacy and performance such that delay and reachability are inversely proportional to privacy.

Privacy from the graph theory perspective

An Online Social Network can be represented as an undirected social graph G (V, E)

comprising a set V of users and a set E of edges representing social ties, such as friendship, kinship, trust and the like.

In this section, we rst remind the denition of three main characteristics of graphs Each graph is represented by an adjacency matrix A whose non diagonal elements a ij are set to one if user ν i ∈ V is a friend of user ν j ∈ V , or zero otherwise. As each adjacency matrix is symmetric, the represented social graph is undirected.

Node degree

In graph theory, the degree of a vertex ν, denoted by deg(ν) is dened as the number of edges incident to the vertex. Since in a social graph G (V, E) a vertex represents a user and the edges represent social links such as friendship, acquaintanceship etc., a user's degree corresponds to the number of contacts a user has. This degree has a direct impact on privacy since with the increase of the degree the number of contacts increases, hence the probability of connecting to a misbehaving user increases. Therefore, the impact of the degree of a node on security can be evaluated by computing the probability of having at least one misbehaving contact.

Assume p mal denotes the probability a user η is malicious, and assume the events of befriending a malicious user are independent. The number of malicious contacts F mal (ν) of ν then follows a binomial distribution with parameters p mal and deg (ν):

F mal (ν) ∼ B (p mal , deg (ν))
In particular, the probability p ν of having at least one misbehaving contact is:

p ν = 1 -(1 -p mal ) deg(ν) (7.1)
Once a malicious contact η gets access to ν's sensitive data because of the simple befriending operations, η can disclose them out of band, or inside the social network itself. In this latter case, the disclosure targets, among all η's friends, the common contacts between η and ν, 1 http://people.maths.ox.ac.uk/ porterm/data/facebook5.zip and can turn out to severely damage ν.

Therefore, the outdegree of a node is directly related with usage control (see section 3.1.1). The more a node has friends, the larger the probability of having a malicious friend which can disclose sensitive personal data.

Figure 7.1 shows the distribution of the node degree for the ve Facebook datasets.

We observe the degree of the Caltech social network is much lower than the degree of the other four social networks. This is probably due to the fact that the Caltech dataset is signicantly smaller than the others, and, as a consequence, the opportunities to add friends are lower. Assuming that the probability of choosing a malicious friend is the same for all the ve graphs, then Caltech network would be the most secure network given its lowest node degree. Indeed, following eq.7.1, we observe that the probability of having at least a misbehaving contact is lower in the Caltech network. Table 7.1 shows in Caltech, when p mal is set to 0.01, p ν is on average as high as 0.35, while in the other networks this value ranges from 0.59 to 0.64.

Clustering Coecient

In an undirected graph, the clustering coecient c (ν) of a node ν with deg (ν) edges is dened as the number of existing links between these nodes, denoted as e deg(ν) , divided by the number of all possible links which by denition is

deg(ν)(deg(ν)-1) 2
. We therefore have:

c (ν) = 2e deg(ν) deg (ν) (deg (ν) -1) (7.2)
The clustering coecient of the overall graph denoted as C (G) is dened as the average clustering coecient of all nodes in the graph, hence:

C (G) = ν∈V c (ν) V (7.3)
Computing or estimating the clustering coecient of a graph can give an idea on the impact of the propagation of unauthorized information by malicious users on nodes friendship.

Once a malicious node, η, is added in the contact list of ν, η can access ν's sensitive data, and disclose it indiscriminately using the social network facilities like wall posting, picture publishing and the like. In particular, if η clones a user prole ν strongly trusts, all sensitive data that ν shares with η will be disclosed.

Such an impact can be measured by computing the average ratio Q ν of ν's friends which can obtain sensitive information disclosed by a malicious η as follows:

Q ν = p ν c (ν) (7.4)
From this equation, we conclude that the degree of propagation is proportional to the clustering coecient. The tighter the friendset, the broader the disclosure of sensitive data to the user's contacts.

Figure 7.2 shows the distribution of the clustering coecient for the dierent social networks that were previously introduced with respect to the degree of the graph since Q ν depends both on p ν and c (ν). Similarly to the previous analysis, the clustering coecient of the Caltech social network strongly diers from those of other networks, as it is almost twice in size. This is probably due to the small size of the Caltech dataset. A smaller community is in fact more likely to be tightly knit.

We observe that in case a friend misbehaves, the victim in the Caltech social graph exposes his sensitive data to a ratio of friends two times higher compared with the one of a victim in the other networks. Nevertheless, due to the lower p ν derived from the graph degree, the average ratio Q ν does not strongly vary in all networks, ranging from 0.11 to 0.14.

Mixing time

Random walks [START_REF] Mitzenmacher | Probability and Computing : Randomized Algorithms and Probabilistic Analysis[END_REF] in a graph have an important property: when the random walk approximates its steady state distribution after a sucient number of hops, the startpoint and endpoint of the walk are uncorrelated. This number of hops is called mixing time, and the smaller it is, the faster the abovementioned property is met.

We will introduce the mixing time starting from the steady state distribution.

The steady state distribution [START_REF] Lovász | Random walks on graphs: A survey[END_REF] for a node θ represents the probability that a random walk reaches θ after a sucient number of hops no matter where this random walk originated from:

ssd (θ) = deg (θ) 2 E (7.5)
The mixing time [START_REF] Mitzenmacher | Probability and Computing : Randomized Algorithms and Probabilistic Analysis[END_REF] τ x ( ) is then computed as follows:

τ x ( ) = min {h : ∆ x (h) ≤ } (7.6)
∆ x (h) the the variation distance between the random walk distribution R h (x) after h hops, and the steady state distribution ssd (x):

∆ x (h) = R h -ssd = 1 2 x∈V R h (x) -ssd (x) (7.7)
For the complete social graph, the mixing time is:

τ ( ) = max x∈V τ x ( ) (7.8)
In social networks, mixing time is varying widely: in [START_REF] Dell | A measurement of mixing time in social networks[END_REF]

Results

Table 7.1 summarizes the main topological properties of the analyzed social network dumps, where the probability p mal of befriending a misbehaving user is set to 0.01. In this scenario, even if on the average p ν is high (ranging from 0.35 to 0.64), the UNC network ensures the best privacy protection (in terms of anonymity and usage control) with respect to the other networks because it shows the lowest average value for Q ν . In terms of communication untraceability and prole integrity, the Caltech network provides the best protection due to the faster mixing time.

Regardless of the particular centralized or distributed architecture, the above mentioned ndings are relevant for any security solution in OSN. 2 We presented such properties in section 3.1.1.

Impact of social graphs on Safebook

This section focuses on the particular architecture proposed as Safebook, and further investigates the impact of social graph topology on privacy. However, the social graph topology also have an intrinsic impact on the performance of Safebook, since according to the second design principle thereof (see section 5.1.1) peer nodes are connected depending on their maintainers' real life trust. This section also analyzes such impact.

Impact on privacy

In Safebook, the social network characteristics play an important additional role on privacy:

a malicious user M can guess a core V's friend list if in the underlying social network the ratio of common friends between M and V is very high.

Such a ratio u h does not decrease indenitely with the increase of the number of hops in the social network graph h required to connect M to V, but rather converges to a value u ∞ .

V deg (ν) C (G) p ν Q ν τ (0.
Assume to start a random walk connecting a user V with a user M. Assume the number of hops h ∞ of such a random walk is suciently high to reach its steady state distribution.

Given x the number of friends of V and y the number of friends of M, we can compute u ∞ as follows:

u ∞ = x,y xy f V f (x) s (y) (7.9)
f (x) and s (y) are the density functions of x and y respectively. Since s(y) corresponds to the steady state density function resulting from a random walk, s(y) is dened as follows:

s (y) = z∈V {ssd (z) f (z) = y} = yf (y)
j∈V jf (j)

Thus, equation 7.9 denes the number of all common edges between the rst node and the last one divided by the number of all the edges of the graph E = f V 2 .

Table 7.2 reports the value of u ∞ for all the Facebook datasets. Again, due to the high clustering, Caltech network oers the worst privacy level.

Impact on performance

Social graph topology have a strong impact on data availability in Safebook.

As discussed in Chapter 6.2, the probability of building a complete Matryoshka (see equation 6.6) depends on the probability of nding a sucient number of online friends that can act as mirrors and on the probability that each mirror will manage to build a chain of h -1 hops where h is the desired number of shells. Since a user cannot take two positions in a single Matryoshka, the probability of building chains may drastically decrease in case of low node online probability and high overlapping factor between friend lists.

The strong clustering coecient of the Caltech network (see table 7.1) suggests Safebook will not perform as well as in the other four Facebook datasets. We simulated the creation of 4-shells Matryoshkas in a challenging environment where the on-line probability of nodes p has been set to 0.1. Results reported in table 7.2 conrm our belief: in Caltech, the ratio between the chains successfully built ch and the average number of friends f 3 is much lower than in the other datasets.

This simulation also conrms the number q of Matryoshkas a node participates in is almost h times higher than the average number of reachable mirrors, thus, chains, in the system (see eq. 6.15).

f ch q ch f q ch u ∞ Caltech 43

Performance and privacy trade-o

As stated in chapter 5.1.1, since the data storage operation strongly depends on some sensitive information such as the list of users' friends, there is a strong link between the depth h of a Matryoshka and the privacy degree: indeed, h should be as large as possible to prevent a malicious requester from discovering these friendship information and achieve a good privacy level.

While increasing the number of shells decreases the chance of discovering one core's contact list, on the other hand, messages should still follow a (h -1)-hop path to reach the mirror (see section 6.1). During the data retrieval process, all nodes along this path are required to be simultaneously on-line for a sucient amount of time. Increasing h 3 The value of f corresponds to the average degree of the nodes in the social network (see table 7.1)

naturally decreases the probability of reaching one mirror and can have a severe impact on the performance of data retrieval. Hence, there is a trade-o between the privacy and the data availability depending on the value chosen for h.

We analyze the trade-o between privacy and performance in order to come up with optimal values for the Matryoshka parameter h. Assume a malicious requester M retrieves D as an entrypoint of V, and by chance D is one of M's friends. In this case, when h = 1, M will derive D is also a friend of V. Assume h ∞ as the minimum number of hops to make the ratio of common friends between D and V u DV approach u ∞ . When h < h ∞ and M has access on D's contact list4 , D's contacts are more likely to M's ones to be V's contacts too. Finally, when h > h ∞ , even assuming M has access on D's contact list, M will not derive any additional information from any retrieved entrypoint of V.

We run several simulations where, for each user, a h-shell Matryoshka with varying h is built, and based on this set-up the ratio u h of common friends between the entrypoint θ h and the core V is evaluated. Figure 7.4 shows the results with respect to the distance between the two nodes. We observe that h ∞ is lower for social network with faster mixing time, while u ∞ is in line with the values computed from eq. 7.9. Hence, a Matryoshka with a depth higher than h ∞ will not increase the privacy level of V noticeably.

To summarize, the highest privacy degree that can be reached given a social network is the one where h = h ∞ : increasing h after this optimal value does not have an impact on the privacy level anymore. Furthermore peer-to-peer based OSN applications implemented over social networks with high clustering coecient and slow mixing time unfortunately show a lower privacy degree with respect to fast mixing networks without strong local clustering.

Privacy preserving OSN architectures, including Safebook, should address this problem by discouraging the indiscriminate action of adding friends. Moreover, the OSN should guarantee the fast mixing property to the network. This can be done by ensuring the small world property of the social network graph, and encouraging `long links' connecting dierent clusters together, otherwise most of the random walks would be conned to the originating cluster.

Summary

This Chapter investigated the strong relationship between the topological properties of the social network graph and the achievable users' privacy in centralized or distributed OSN.

We observed that metrics such as the degree and the clustering coecient of nodes severely aect users' privacy as dened in chapter 3 with respect to identity/friendship privacy and usage control, while the mixing time of random walks in the social network graph plays an essential role in preserving the users' communication untraceability.

An analysis on real social network dumps reveals that the probability of befriending at least a misbehaving contact is not negligible. In this case, the number of nodes which can discover unauthorized data depends on the number of common friends between the victim and the attacker.

Further specic analysis on Safebook conrms that the presence of strong local clustering In case the Safebook host is assigned a private address, the application tries to open and forward the UDP and TCP server ports from the NAT via UPNP protocol.

When no UPNP compatible NAT device is found, the client proposes the user to manually congure port forwarding on her NAT. However, if the user is behind a corporate rewall, the user cannot operate any port forwarding operation, therefore the Safebook host cannot be reached by any node in the Internet. Moreover, under strict corporate rewall policies, outgoing UDP connections could also be ltered out, while TCP ones could be allowed to contact a predened web proxy only. To overcome this limitation, Safebook establishes a tunnel over HTTPS to peer nodes assigned with a public IP address, or behind a home NAT 3 under their control. The network packets generated by the S2S manager (S2S trac) and those generated by the Matryoshka Manager (Matryoshka trac) are then sent in the HTTPS payload, and the usual P2P and Matryoshka services are granted.

As a main limitation, being unreachable from the outside, user nodes behind corporate rewalls can build their Matryoshka and take part in those of other users, but cannot play the role of entrypoints.

Account creation

Account creation in Safebook can take place in two ways: by invitation, as explained in Chapter 5.4.1, or without, as implemented in the current prototype. While joining Safebook by invitation allows the newcomer to bootstrap her Matryoshka with the trusted inviter, in the second approach the newcomer needs to refer to an untrusted contact to build her rst Matryoshka chain. Once created the rst chain, the newcomer will start establishing friendship links, therefore creating new Matryoshka chains, and remove the untrusted bootstrapper from her friendlist.

The identiers and the list of certied DhtKey are computed by the TIS starting from a set of the newcomer V's properties name v =< f irstN ame, lastN ame, gender, birthDate, birthP lace, nationality >

The TIS holds an asymmetric key pair {T IS -, T IS + } used for message condentiality and integrity, and three master keys

M K 1 , M K 2 , M K 3 used to compute U Id v and N Id v .
The account creation takes place in two steps: in the rst one, out of band, V sends to the TIS his name v together with a chosen password pwd, and receives a symmetric key K = h M K3 (name v , pwd); in the second one, in band, V generates two keypairs {U -, U + } and {N -, N + } and sends the public keys U + and N + together with name v and pwd to the TIS. This message is double signed to let the TIS verify the ownership of U -and N -. The TIS then checks the identity of V with a challenge, computes and certies the user and node identiers, and provides a set of certied DhtKey by applying a well known hash function to all the possible combinations of elements in name v . In our prototype, since name v is composed by six elements but we don't take the gender into account, the TIS will provide

2 5 -1 DhtKey 4 .
Finally, the TIS selects a random Matryoshka bootstrapper 5 and sends its certied user and node identiers together with its IP address to V. Once received the Matryoshka bootstrapper information, V sends a bootstrap request containing a friend token (see section 5.4.3) to the bootstrapper, that automatically accepts the friendship and allows V to start the usual Matryoshka creation procedure.

The account creation steps are resumed in gure 8.3.

User interface and OSN facilities

Once created the rst Matryoshka chain, the newcomer can use Safebook facilities.

The user interface (see g. 8.5) has been implemented as a webpage (see g. A Safebook user V can browse into three main sections:

• Square, containing the information shared by V's contacts;

• Podium , containing V's shared information;

• Contacts, containing the V's contact list.

The Square section is similar to the Diaspora and Google+ stream page, and to the Facebook wall. In this section, the user quickly gets updates and sends comments on the new content shared by her trusted contacts or people she is simply interested in.

The podium section hosts the user-generated information, including the subset of the wall threads where user's posts appear, the prole page containing the user's identity, the gallery page containing user's pictures, and the user's mailbox 7

Finally, the Contacts page displays the user's contacts and oers links to the contacts' prole, wall and gallery pages.

The user may share new content with a subset of friends. Access restriction is achieved by associating the new content with one or more badges (see section 5.3.2), that may be compared to Google+ circles, Diaspora aspects, or Facebook user-dened lists. Safebook users sharing new content without specifying an associated badge are asked to perform this action as a requirement for the successful sharing. In case the user does not associate any badge, a default private one is chosen and the new information is made available for the user only and nobody else. Badges can be sent to trusted contacts at the act of friendship establishment or later. Badge reception is transparent for the recipient user, as it simply consists on the reception of new symmetric data encryption keys (DEK). Friendship lookup can always be performed thanks to a form at the left of the page.

The user can choose more than a keyword 8 and get the publicly available information on all users associated with these keywords. The user further selects her trusted contacts and sends them a friendship advertisement together with a list of DEKs corresponding to the associated badges.

Friendship lookup leverages on the P2P overlay of Safebook. The characteristics of the S2S Manager in charge of building such overlay are discussed in the following section. 8 A keyword must correspond to an element in namev as explained in the previous section.

S2S: the P2P overlay of Safebook

The P2P substrate of Safebook, namely S2S, is a DHT similar to Kademlia [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the xor metric[END_REF] where nodes are arranged according to their identier and store information on where to locate resources.

Every resource can be identied by a hash value DhtKey in the same 160-bit keyspace of the node identiers, so that an XOR based distance function can be used to determine which set of nodes is responsible for which resource.

S2S diers from Kademlia since the lookups are performed in a recursive fashion to hide the identity of the real requester. Moreover, messages are signed with the sender's node private key N - sender and encrypted with the receiver's node public key N + receiver 9 .

Contact Management and Refresh Mechanism Similarly to Kademlia, the peer routing table of S2S is organized into several `K -buckets' which are the leaves of a binary routing tree. Each K-bucket represents one subtree and has up to K representative contacts sharing the same distance range with respect to the peer itself. The routing table is managed dynamically: contacts are added as they are encountered and the buckets are splitted or merged as needed.

In S2S, a contact N is represented as:

< Cert N Id N , N + N , @N, ConnSince, LastP ing, Zombie, https >

The node certicate contains N 's node Id and its node public key, @N represents N 's IP address, while ConnSince and LastPing keep track of the rst and last interaction between N and the current node. Finally, Zombie and https are independent boolean values: the rst one is set to true in case N is not reachable, the second one when N can be reached through an HTTPS connection.

In S2S every bucket is periodically refreshed. When called, the refresh procedure pings the contact, preferably a zombie, with the lowest LastP ing -ConnSince value 10 . In case the peer answers, the Zombie ag is set to false, and the LastP ing value is updated. Every time a peer A is contacted by a peer B, A inserts B in the appropriate bucket, if needed.

Store and Delete function In S2S, the function store (DhtKey, V alue) is called by an entrypoint D of a core V's Matryoska while registering the chain leading from D to a mirror 9 More precisely, session keys are used to encrypt the payload. Such keys are advertised at the beginning of the message encrypted with the target node Id public key. 10 Uptime is on average a good indicator of the remaining uptime as measured in [START_REF] Stutzbach | Understanding churn in peer-to-peer networks[END_REF].

A of V. A tolerance zone is dened as the area of the key space around a target DhtKey which is populated by all the nodes in charge of storing the value associated to that DhtKey.

A DhtKey can be both the user Id of V or an hash of her identity properties, and is always certied by the TIS and associated to a user Id public key to prevent malicious users from claiming a bogus identity. The value associated to DhtKey is an entry EP T entry represented as:

< RegT ok, Cert N Id D , N + D , @D, T ime >
where RegT ok is the registration token containing information on the target user V, while the following information proves the entrypoint D is a valid node in the system. Finally, @D represents D's IP address and T ime is used to synchronize V alue between neighboring docks.

More specically, RegTok is represented as:

< Cert DhtKey V , U + V , Cert U Id V U + V , ExpireT ime >
Therefore V can never register an hash of an identity property she does not hold. After ExpireT ime is reached, the dock storing this EP T entry removes it from its hash table.

In case a malicious user M aims at intruding to a target user V's Matryoshka by colluding with the dock K responsible for storing the entrypoint references of the victim's Matryoshka, an additional protocol explained in Appendix B.1 is needed 11 .

When a chain gets broken or D leaves the network, to prevent a requester U from connecting to a node D that is not anymore an entrypoint for V, S2S provides a function remove (DhtKey, V alue) giving the node D the opportunity to unregister itself as an entrypoint of V.

Since the information on the role of entrypoint is not sensitive, the store and remove operations can be executed after an iterative search for DhtKey. Moreover, in S2S it is sucient to reach a single dock K in the tolerance zone of DhtKey to store or remove a value, since the command is by default forwarded to all the on-line neighbors of K within the tolerance zone of DhtKey.

Iterative and Recursive lookup

S2S provides two dierent ways to look up for a DhtKey: a classical iterative one, as in 11 Such a protocol has not been implemented in the current prototype.

Additional challanges

Future develompent of Safebook can address both usability and ubiquity. Many users, even those concerned about privacy in OSNs, may see the software installation or their home NAT conguration as a barrier. It would be interesting to evaluate a possible development of Safebook as a web application (webapp) too. One user could connect to the Safebook website and execute the Safebook client coded in a browser-supported language. Users' data may be downloaded from the online friends. Such users could also download their friends' data items and serve as a mirror for them.

Open listening sockets would be a main challenge to tackle. In case users executing Safebook as a webapp could not play the role of entrypoints, an evaluation on the impact on data availability should be conducted too. Due to the ubiquity of web browsers, Safebook could also be executed by several user devices without requiring the user to install each time the Safebook client.

Summary

This Chapter presented the rst prototype of Safebook, a multi-thread event driven application written in python that can be executed on multiple operating systems such as Windows, Linux and MacOs.

Once started, the client runs locally and opens four main services: a local web server to implement the user interface, a UDP server to receive P2P trac, a TCP server to receive Matryoshka trac, and a HTTPS server to receive encapsulated Matryoshka and P2P trac from those peers that are behind strict policy corporate rewalls.

The web based user interface helps user to benet from Safebook as easily as in current OSNs. A simple interface helps a Safebook user to discriminate which information was generated by her or specically needs her attention, that is collected in the Podium, from all the information generated by the user's contacts, that is collected in the Square. A last section, the Contacts page, allows the user to browse her friend list.

User generated content is shared with limitations, and is private by default. Access control is achieved with the use of badges, representing user-dened overlapping groups of contacts, consisting on symmetric Data Encryption Keys distributed among trusted contacts at the act of friendship establishment or later.

Friendship lookup requires the untrusted environment of the P2P overlay to achieve the same security and privacy properties of the Matryoshka overlay. To this goal, a DHT inspired by Kademlia has been implemented to achieve unforgeability of node identiers, recursiveness of lookups, and message integrity and condentiality. Moreover, to increase the responsiveness of the system, entrypoint references can be also removed from the DHT so that requesting users don't retrieve endpoints of broken Matryoshka chains.

Chapter 9

Conclusion and future work

Social Network Services (SNS) maintain Online Social Networks (OSN) as digital representations of users and their relationships, and allow even users with limited technical skills to share a wide range of personal information with a theoretically unlimited number of partners. This advantage comes at the cost of increased security and privacy exposures for users for two main reasons: rst of all, users tend to disclose private personal information with little guard, and secondly, existing SNSs severely suer from vulnerabilities in their privacy protection or the lack thereof. Even assuming a perfect protection from malicious users, legitimate users are still exposed to a major orthogonal privacy threat, since in all existing SNSs the service provider has access to all the data, including some private information, stored and managed by the SNS itself, and can misuse such information easily. Since the access to users' private data is the underpinning of a promising business model, current

SNSs are not likely to address this problem in the near future.

This thesis tackled the security and privacy issues in Online Social Networks with a special emphasis on the privacy of users against the omniscient Social Network Service provider.

In the rst part of this thesis, we discussed the security and privacy issues in OSN.

119

In chapter 2, we introduced Online Social Networks and illustrated their main functionalities. We identied and classied the large amount of core information stored in OSNs into several main areas. Misuse of such information has been examined in chapter 3 that dened privacy, integrity and availability objectives for OSNs, and discussed a detailed spectrum of attacks that can be perpetrated in OSNs against such objectives. Most of the countermeasures we proposed to prevent such attacks revealed to be ineective against the Social Network Service provider itself which plays the role of an omniscient centralized entity.

An overview of the main centralized OSNs underlined the market capitalization of their providers.

Researchers recently proposed to design OSN applications based on a distributed architecture in order to avoid centralized control over users' data. In chapter 4 we classied existing solutions, known as Distributed Online Social Networks (DOSN), and analyzed them together with their limitations. We showed that client-server (or cloud) approaches do not always evade the potential control of a single party, as e.g. a company or an organization, on the hosted user's data. On the other hand, although current peer-to-peer approaches do not suer from such control, they expose users to potential communication tracing attacks.

In the context of OSN, such communication traces disclose details on the structure of the social network graph. We therefore concluded that none of current approaches is suitable to achieve the goal of preserving user's privacy in OSNs.

In the second part of this thesis, we proposed Safebook as a solution to security and privacy threats in OSN.

In chapter 5 we presented the main design principles of Safebook: a P2P architecture to avoid the need for a central provider, and the real life trust among peers resulting from the OSN application itself to enforce their cooperation. In Safebook, friend nodes provide the basic services of data storage, retrieval and communication, and consequently build the OSN. A rst ring of friends serves all requests for one user's data even when such user is oine, and further rings of friend-of-friends build such user's Matryoshka and prevent the disclosure of the user's friendship relationship from tracing attacks. Privacy is achieved with communication obfuscation through anonymous routing techniques, data condentiality through the use of encryption, and prole integrity through the adoption of certied identiers.

In chapter 6 we analyzed and evaluated the feasibility of Safebook. Based on the Matryoshka setup parameters and the online probability of nodes we computed the probability of building Matryoshkas and their lifetime. We observed that choosing a large value for the depth h of the Matryoshka (which is a privacy requirement) can have a severe impact on the data availability and retrieval. Thus, h should be set as small as possible while still allow for a good privacy degree. We further discussed the data availability of Safebook by evaluating the amount of data a user can retrieve at each request and showed an example based on a realistic scenario.

In chapter 7 we analyzed privacy in centralized or distributed OSNs from the graph theory perspective with the help of real social network dumps. We observed that metrics such as the degree and the clustering coecient of nodes severely aect users' privacy as dened in chapter 3 with respect to identity/friendship privacy and usage control, while the mixing time of random walks in the social network graph plays an essential role in preserving the users' communication untraceability. Further specic analysis on Safebook conrmed that the presence of strong local clustering negatively impacts the privacy of the solution.

Experiments also conrmed a strong trade-o between privacy and performance such that delay and reachability are inversely proportional to privacy.

In Chapter 8, we presented the rst prototype of Safebook, a multi-thread event driven application written in python that can be executed on multiple operating systems such as Windows, Linux and MacOs. The web based user interface helps users to benet from Safebook as easily as in current OSNs. User generated content is private by default. Access control is achieved with the use of badges, representing user-dened overlapping groups of contacts, consisting on symmetric Data Encryption Keys distributed among trusted contacts at the act of friendship establishment or later.

In conclusion, this study showed that privacy concerns in current OSNs are mainly due to the centralized storage of all users' data at the SNS provider's databases. Among all the current solutions that allow for the distributed storage of the user generated contents, Safebook has been designed with the main goal of preserving user's privacy from the very beginning, and achieves such goal. Safebook does not only protect the digital representation of users, but also their relationships, from any malicious party. The evaluation of Safebook shows that a realistic compromise between privacy and performance is feasible. Furthermore, the underpinnings of Safebook can serve as a model to tackle various well known problems in the area of secure communications. Thus, a decentralized approach relying on social links can shed new light on hard problems of the past such as anonymous communications, secure routing, or cooperation enforcement in self-organizing systems.

Directions for future research

We envision three main directions for future research towards privacy, performance, and business model of Safebook.

The rst research direction is toward privacy in terms of usage control over the shared prole data. The problem of usage control, which refers to the control of the data after its publication, is becoming a very challenging problem due to the rapid growth of the number of users involved in content sharing. Since Safebook relies on the collaboration of users for any operation including data management and security, the collaboration of a sucient number of legitimate peers may be leveraged to enforce control on the data forwarded along the trusted Matyroshka chains. For instance, the message could have to follow a dedicated path of sucient intermediate nodes which perform the dedicated tasks dened in the usage control policy before reaching its nal destination. Thanks to this multihop enforcement mechanism, users would be able to control the usage of their shared data since the very beginning stage of its publication.

We propose an initial solution using Safebook for the particular picture sharing application (see appendix C). Nevertheless, the protection of the picture and the enforcement of this control is only ecient in the conned environment of Safebook and when pictures are not encrypted.

The second research direction is towards performance in terms of data availability. Due to the particular approach in Safebook, data served by friend nodes with limited bandwidth and storage capacities may not be always 100% available. To increase such availability, Safebook users may store their data at some non friend nodes, or in an untrusted storage service outside Safebook. In the rst case, new cooperation enforcement mechanisms should be designed to prevent selshness. Such mechanisms could take advantage of the distributed nature of P2P networks. We have started to design an initial incentive mechanism where transactions should be approved by a predened certain number of peers (see appendix D).

Directions for future research 123

In the second case, new features should prevent the external storage service provider from deriving sensitive information such as friendship relationship between Safebook users.

One last research direction is towards the denition of a business model that can attract users to Safebook. Privacy alone may not be sucient to serve this goal, at least for non professional users. On the contrary, economic incentives may facilitate users' migration on

Safebook. Even if one user's prole data is valueless, it may be valuable if it is aggregated with other users'prole data. In this case, Safebook users proles may be aggregated and sold to provide anonymous statistics to companies, that would in turn pay users for this data, improve their products, sell them and return on their investment.

B.2 Specic vulnerabilities

Notwithstanding the fact that privacy, integrity and availability is assumed by Safebook, new vulnerabilities arise due to some exposures through the misuse of Safebook protocols by potentially malicious parties. This section presents vulnerabilities that are specic to Safebook protocols and the countermeasures that are implemented as part of Safebook.

B.2.1 Denial of Service and Trac Analysis

No user can access the content that is exchanged between other parties. However, due to its cooperative nature in which all messages are forwarded by other participating nodes, Safebook is fundamentally vulnerable to black hole (a malicious node intercepting and dropping messages for a destination) and white hole (interception and monitoring for reasons of deriving statistical properties) attacks. For this purpose, a malicious node M would need to intrude the Matryoshka of the target V. Since for M it is impossible to generate pathReq or register messages, and since M can not change its node Id in order to become a dock of V, the only way of mounting this attack is by nding colluding docks of the target, or colluding users of the target's Matryoshka. The rst approach leads to entrypoint table poisoning, the second implies misbehavior in some trust relationship.

EPT poisoning -Attacks External to the Matryoskha

Poisoning the entrypoint tables for a target node can only be mounted in collusion with one of the docks of the target's Matryoshka, K.

Even a colluding K can not simply add a fake entry pointing to the attacking node M and advertise it to the RespArea, as the signature of M is needed. However, assuming K's EPT has DhtKey V,1 = hash (N ame V ), K could supply M with one of the signed random numbers it received by an authorized entrypoint of Θ V . M in consequence could create, sign, and send a bogus coreReg message back to K, or even to a dock J for a dierent registration key of V. Since M provides a seemingly correct coreReg message, J (and K)

advertise the new EPT record to the respective RespArea. The complete set DhtKey V is not stored anywhere in Safebook, other than at V itself. However, presuming M by external means got to know DhtKey V , it could, in collusion with K, register its node Id as a valid entrypoint for all keys in DhtKey V throughout the entire P2P system to increase chances to be on the forwarding path to V (cmp. g.B.1). Even though this scenario describes packet must pass through a threshold number of nodes before reaching its destination in order to guarantee a certain security degree.

Such peer-to-peer online social networks can be considered as a good candidate for usage control mechanisms in picture sharing. In such an environment, a well behaving node would automatically obfuscate all faces in any picture it receives from other nodes. Therefore, given a threshold number of misbehaving or malicious nodes, in order to guarantee the correct execution of the usage control mechanism, the application can dene a maximum number n max of nodes a legitimate message has to pass through, before reaching its nal destination. Among these n max nodes at least one node should behave legitimately and apply the required protection operations. Additionally to the owner of the picture, only the owner of the face included in that picture should be able to have an initial access to the face in that picture. The further usage control rules for the dedicated face have to be dened by the corresponding user and the correct appliance of these rules should be veried at each node in the path towards the destination.

C.3 The proposed usage control mechanism

In this section, we describe a usage control mechanism enforced thanks to the cooperation among multiple users that perform multi-hop forwarding.

The idea of the proposed mechanism is to exploit the distributed nature of peer-to-peer online social networks and to leverage real-life social links to control the access to pictures:

as opposed to centralized solutions, all operations are performed with the collaboration of multiple nodes. Thanks to this multi-hop enforcement in this distributed setting, cleartext pictures will only be accessible based on the rules dened by users whose faces gure in those pictures.

An interesting system that answers the previously described requirements is proposed in [START_REF] Antonio Cutillo | Safebook: a privacy preserving online social network leveraging on real-life trust[END_REF] as a distributed privacy preserving online social network named as Safebook. We briey summarize its characteristics before presenting the main contributions of this paper.

C.3.1 Safebook: a P2P DOSN leveraging real life social trust

The main aim of Safebook is to avoid any centralized control over user data by service providers. Safebook relies on the cooperation among a number of independent parties that the last component of Safebook, the Trusted Identication Service(TIS). The TIS is contacted only once during the user registration phase and does not impact the decentralized nature of Safebook's architecture since it is not involved in any data communication or data management operation.

We now present a new usage control mechanism taking Safebook as a basis. • she can publish a picture: in this case, she is represented as the core of her own Matryoshka and her friends will store this picture. She also has the option to tag some of her friends who might appear in the picture.

• She can act as a forwarder for some pictures: in this case, she belongs to the Matryoshka of either the owner of the picture or the owner of a face tagged in that picture.

Picture publication

To make her picture P available in the network, the publisher V has to perform the following main tasks:

• Picture insertion and face detection : To publish her picture P , the user V provides P to her Safebook client. One of the main components the system consists of the face detection mechanism. The face detector aims at nding the presence of faces in the input picture P and, if this is the case, it returns their location L P .

Faces can vary in size, shape and color, and must be detected regardless of their position, orientation and light conditions. Existing face detection algorithms such as in [START_REF] Yang | Detecting faces in images: A survey[END_REF] can directly be used in the proposed system. Their robustness directly aects the privacy achieved by this scheme. We assume that face detection algorithms are secure enough. Their design is out of the scope of this paper.

• Picture tagging : When the face detector derives L P , the client uses the second component, namely the face extractor, which is in charge of copying every face f P i ∈ F P detected in l P i ∈ L P in a separate le.

After this extraction task, the publisher V is asked to tag each face, i.e. to associate

Forwarding pictures

Every intermediate node T storing or forwarding an obfuscated picture OP runs by default the face detector and obfuscator components on OP . These tasks ensure the required privacy property in case some clients are manipulated by malicious nodes.

When storing or forwarding a user V's publicly available face, a legitimate node T rst checks the validity of the signature S φ V , the expiration time, and the relation between the face features f V in the certicate and the ones extracted from f P V . In case of verication failure, V's face is dropped.

Picture retrieval

To retrieve V's pictures, a user U who is not included in V's contact list sends a picture request pctReq message to V and receives a set of identiers I P j related to V's publicly available pictures P j . U then asks for the identiers she is interested in. For every identier I P j U retrieves an obfuscated picture OP j and the message Cert f V , φ + V , I P j , f

P j V , expT ime j S φ V
The proposed usage control scheme does not put any constraints on the face detection and recognition architecture: when the adopted face descriptor is bigger than the face image itself, a reference face image r V rather than the feature descriptor f V itself can be certied by the FCS. This change does not have a concrete impact on the time necessary to compare the reference face in the certicate with that one a user wants to make publicly available.

The feasibility of Safebook has been presented in [START_REF] Antonio Cutillo | Performance and privacy tradeo in peer-to-peer on-line social networks[END_REF]. The study discusses an inherent tradeo between privacy and performance: on one hand, the number of shells in a user's Matryoshka should be dened as large as possible to enforce privacy in terms of communication obfuscation and protection of the friendship links, but small enough to oer a better performance in terms of delays and reachability; on the other hand, increasing the number of shells after a certain trheshold does not increase the privacy anymore. Such a threshold depends on the social network graph itself [START_REF] Antonio Cutillo | Analysis of privacy in online social networks from the graph theory perspective[END_REF], more precisely on the number of hops after which a random walk on the social network graph approximates with a pre-dened error its steady state distribution [START_REF] Mitzenmacher | Probability and Computing : Randomized Algorithms and Probabilistic Analysis[END_REF]. In this case, the endpont and the startpoint of the random walk are uncorrelated.

Based on the results of the study in [START_REF] Antonio Cutillo | Performance and privacy tradeo in peer-to-peer on-line social networks[END_REF], we conducted our experiments by setting a number of shells as high as 4. We assumed the number of online nodes as high as 30%. For every social network dump, we measured the average number of user's friends d, the average number of chains p a user managed to build, and the average number of Matryoshka q a user is part of. and 10% of the nodes misbehave. We also assume that misbehaving nodes are always online.

In case of absence of collusion, misbehaving nodes are randomly selected. In case of collusion, misbehaving nodes are selected between and in the friendlists of all the nodes with higher weight w V dened as:

w V = d V * cc V
where d V represents the degree of node V, i.e. the number of V's contacts, and cc V its clustering coecient, i.e. the ratio between the number of existing links between V's contacts divided by the number of possible links that could exist. We dene as compromised chain a chain entirely composed by misbehaving nodes. Data condentiality and Anonymity Given an obfuscated picture OP , it should be impossible to retrieve any information about users whose depicted faces are not made publicly available. Since by the very design of the Safebook client, there is no way to query the OSN for the identity of the users whose faces are missing, it is, indeed, not possible for an adversary to extract any useful information from an obfuscated picture. Only friends of a user N can discover this information and retrieve f P N . Whenever N 's friend U receives the list of identiers of the pictures she is allowed to access, she checks the list of picture not be that important.

C.5 Conclusion and Future Work

As it is not feasible to design a perfect usage control mechanism to control the management of any type of data in any environment, we proposed a preliminary solution dedicated to picture sharing tools widely used in the context of online social networks. Although it might be feasible to design such a mechanism in a centralized environment, current OSN providers

are not yet interested in such protection mechanisms. On the contrary, decentralized, P2P

based online social networks rely on the collaboration of users for any operation including data management and security. The proposed usage control mechanism takes advantage of this inherent cooperation between users and ensures the enforcement on the control of the pictures thanks to a dedicated multihop picture forwarding protocol. The message has to follow a dedicated path of sucient intermediate nodes which perform the dedicated tasks dened in the usage control policy before reaching its nal destination. Thanks to this multihop enforcement mechanism, users whose face appears in a given picture will be able to control its usage in the very beginning stage of its publication. Nevertheless, the protection of the picture and the enforcement of this control is only ecient in the conned environment of the DOSN and when pictures are not encrypted; however, the impact of attacks launched outside this environment or aiming at encrypting the message is very limited within the DOSN.

D.1 Introduction

Peer-to-Peer systems are nowadays broadly adopted to provide several services such as le sharing [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the xor metric[END_REF][START_REF] Pouwelse | The bittorrent p2p le-sharing system: Measurements and analysis[END_REF], data storage [START_REF] Haeberlen | Glacier: highly durable, decentralized storage despite massive correlated failures[END_REF][START_REF] Weatherspoon | Design and evaluation of distributed wide-area on-line archival storage systems[END_REF], secure communication [START_REF] Rogers | How to Disappear Completely: A Survey of Private Peer-to-Peer Networks[END_REF][START_REF] Chothia | A survey of anonymous peer-to-peer le-sharing[END_REF], social networking [START_REF] Antonio Cutillo | Safebook: a privacy preserving online social network leveraging on real-life trust[END_REF][START_REF] Buchegger | PeerSoN: P2P Social Networking Early Experiences and Insights[END_REF][START_REF] Ngyuen | What's up: P2p spontaneous social networking[END_REF]. The correct execution and the availability of such services strongly depend on the collaboration among peers. Several studies [START_REF] Adar | Free riding on Gnutella[END_REF][START_REF] Shneidman | Rationality and self-interest in peer to peer networks[END_REF][START_REF] Locher | Free riding in BitTorrent is cheap[END_REF] pointed out that, unfortunately, peers often engage in free riding , i.e. they try to consume as more resources as possible and on the contrary, contribute with as few resources as possible. This kind of selsh behavior has a strongly negative impact on the overall performance of the system and may even lead to its failure.

Several cooperation enforcement solutions [START_REF] Buchegger | Nodes bearing grudges: Towards routing security, fairness and robustness in mobile ad hoc networks[END_REF][START_REF] Michiardi | CORE: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF][START_REF] Buttyán | Stimulating cooperation in self-organizing mobile ad hoc networks[END_REF][START_REF] Zhong | Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks[END_REF][START_REF] Karthik Tamilman | Swift: A system with incentives for trading[END_REF][START_REF] Vishnumurthy | KARMA: A Secure Economic Framework for Peer-to-Peer Resource Sharing[END_REF][START_REF] Belenkiy | Making p2p accountable without losing privacy[END_REF] have been proposed to foster cooperation among peers in P2P or Mobile Ad-hoc Networks (MANETS).

Most of them rely on credit-based mechanisms whereby nodes receive a reward whenever they cooperate for the execution of the requested action. These credit-based incentive mechanisms often rely on the existence of a centralized authority that ensures a fair distribution of the credits and also acts as a mediator in case of litigation during transactions. The adoption of such a centralized authority raises serious security and privacy concerns: Indeed, this online trusted authority has a direct access on the history of actions of any peer since it is in charge of distributing rewards corresponding to each granted service. Therefore, as in all existing centralized services, current credit-based incentive mechanisms suer from privacy problems such as traceability or monitoring [START_REF] Vishnumurthy | KARMA: A Secure Economic Framework for Peer-to-Peer Resource Sharing[END_REF][START_REF] Belenkiy | Making p2p accountable without losing privacy[END_REF].

In this paper, we propose PRICE, an incentive mechanism that can be adopted as a builtin service for any DHT-based P2P system. PRICE takes advantage of the distributed nature of the P2P network itself to manage credits and ensures the correctness and the security of transactions. The management of credits, dened as coins in PRICE, is distributed among peers in the network based on the use of the inherent P2P functionality, that is, a distributed hash table (DHT). A coin transaction only succeeds if a quorum among a predened number of peers agrees on it. Although the task of credit management is distributed among several peers and therefore it can decrease the privacy of the system, PRICE oers an original approach by assigning the management of each single coin to a dierent set of peers instead of the account of a given peer. Therefore, on the one hand, no entity in the system is able to discover the total amount of credits a user holds; hence, as opposed to centralized solutions, a user's history of actions cannot be traced by any node; on the other

D.3.1 Environment

As previously mentioned, the correct execution of PRICE relies on the use of a distributed hash table (DHT) based P2P network where every peer node is also considered as the application user. A peer is assigned to a unique identity, the Peer Identier , and the assignment of coins to peers is managed by the DHT: in addition to P2P services such as data storage or data retrieval, peers also participate on the management of coins. To prevent DoS attacks including Sybils [START_REF] Douceur | The Sybil Attack[END_REF] or eclipse [START_REF] Singh | Eclipse attacks on overlay networks: Threats and defenses[END_REF] the mechanism denes an o-line Trusted Identication Service (TIS) which mainly computes the Peer Identier and ensures that this value is unique and is assigned to its corresponding peer by generating a cryptographic certicate over the identier. Any attack due to the multiple identities creation or identity manipulation is thus unfeasible in PRICE. In order to ensure the security of the rewarding mechanism, coins are generated and signed by a trusted entity named as Coin Generator (CGEN) whose unique role is to ensure the correctness and validity of the coin.

D.3.2 Scenario

In the following, we present a scenario in which two users Alice and Bob take part in a P2P network oering data storage services and use PRICE to manage their transactions.

In the P2P network, let Alice be a user interested in storing her le using Bob's resources.

Whenever Alice sends her request to Bob, she grants him with a coin for this additional service. This transfer should of course be considered as valid and Bob should be able to verify that he is the new owner of the coin. Therefore there is a strong need for dening a third entity or a witness to validate such a transfer. In the proposed mechanism, a set of peers is assigned for this role and they are dened as notaries. • account creation , whereby a newcomer receives his peer identier (P I) from the TIS and an initial number of coins from the CGEN;

• payment order , whereby the newcomer requests to grant a coin to a beneciary by sending a P AY message to the caretaker notary;

• payment notication , whereby the caretaker notary collects the agreement of a sucient number of notaries, and informs the payer and the beneciary about the success of the transaction.

D.4 Description

In this section, we rst dene the security properties of a coin and introduce the main components of PRICE which are the Coin Generator, the DHT based P2P substrate, and the Trusted Identication Service. We then formally describe the three steps of the proposed incentive mechanism, namely, the account creation, the payment order and the payment notication.

D.4.1 Preliminaries

The P2P substrate and the Trusted Identication Service

In the DHT, every user is associated to a peer node by a unique Peer Identier P I which is computed by the TIS. By granting a certicate together with every identier, the TIS protects the PRICE mechanism from dierent DoS attacks such as Sybil [START_REF] Douceur | The Sybil Attack[END_REF], impersonation, or eclipse [START_REF] Singh | Eclipse attacks on overlay networks: Threats and defenses[END_REF]. Following the very denition of a DHT, a P I is dened as a number over a key space in order to facilitate the functions of data lookup.

The rewarding mechanism and the Coin Generator PRICE relies on a specic implementation of rewards which are named as coins, generated by a trusted entity, the Coin Generator , and are dened by a tuple with the following parameters:

• a Coin Identier CI, which is a pseudo-random number generated by the Coin Generator over the keyspace K and will be used as the input of a coin lookup operation in the P2P network;

• the signature of CI computed by the Coin Generator with its secret key as a proof of the validity of the coin.

Thanks to the security of the pseudo-random generator used by the CGEN, a coin c is unique. The signature of the CGEN provides the protection against forging attacks.

Table D.1 summarizes the notation used for the description of PRICE.

D.4.2 Account creation

Whenever a new user enters the system, it rst needs to receive its peer identier and its set of initial coins. Therefore, the account for a new user A is created in three separate steps:

1) identity creation and authentication, where A obtains its identier, 2) P2P substrate join, where A takes its place in the DHT, and 3) welcome coin attribution, where A is granted with a predened number of coins by the CGEN.

Identity creation

In order to get its peer identier, A generates an asymmetric keypair K A = K - A , K + Once A has successfully received its coins, it can join the P2P system and actively participate to any application or service oered by the P2P network and use PRICE for transactions accordingly.

P2P substrate join

On reception of the certicate, A joins the P2P substrate, and contacts other peers to advertise its presence and populate its routing table following usual P2P protocols. It also nds out the identities of the notaries corresponding to each of its coins using a map function ρ which, as an input of the identity of the coin c, outputs the set of peer identities responsible for its management, that are, the notaries. Upon reception of the initial coin, a caretaker notary, adds in its current coin registry the following information:

• the coin identier,

• the signature of the CGEN,

• A's certicate,

• A's peer identier which further will be replaced by the previous owner of the coin at each transaction of this coin,

• a serial number which is used to synchronize notaries and prevent replay attacks,

• a group signature generated by a subset of dedicated notaries.

D.4.3 Payment order

In order for A to transfer a coin c to B, A has to indicate to the P2P system the new owner of the actual coin. This action takes place in two steps: 1) notary lookup, 2) payment request.

Notary lookup

In this step, A performs a lookup in the DHT using the coin identier CI c as a lookup key.

In O(log (n)) steps, A reaches a node P in the notary set of the coin. P will act as the 180Appendix D PRICE: PRivacy preserving Incentives for Cooperation Enforcement caretaker of the transaction A is going to make.

Payment request

In order for A to grant a coin c to B, A sends a signed payment message P AY to P containing the signed coin identier CI c proving c is a valid coin, the certicate of the new owner B proving B is a valid node in the system, B's IP address, and a serial number SN used to avoid replay attacks. This message is encrypted with P's public key to prevent eavesdropper from tracing the transaction. In case A is not the current owner of the coin or there is a mismatch between the serial number in the P AY message and that one in the coin registry, P simply discards the message, otherwise P forwards it to its neighborhood in the notary set N S (CI c ).

Please note that P is responsible for more than a single coin in the system and can receive several P AY messages for several coins from dierent users at the same time.

D.4.4 Payment notication

In order for the payment to succeed, a predened quorum among the notaries of c has to agree on the update (or creation) of the entry associated to c in the coin registry performed by the caretaker P. Once this agreement is met, the caretaker can notify the payer, the beneciary and the notaries about the success of the transaction. These actions take place in two steps: 1) coin registry update, 2) payment conrmation.

Coin registry update

Every node in the DHT stores a coin registry CR keeping the association between every coin identier it is responsible for and the peer identier of the current owner of that coin. An entry in the coin registry has the form:

CR (CI c ) = CIc, P I Z , Cert(P I A , K + A ), SN S N S(CIc )

where Cert(P I A , K + A ) identies the current owner of the coin and is used to verify the integrity of P AY messages, P I Z is the peer identier of the previous owner of c, SN is a serial number used to refresh the coin registry of the nodes coming back online in the DHT and to avoid replay attacks, and S N S(CIc ) is the group signature generated by a sucient number of nodes in the notary set.

When a notary N j receives a forwarded P AY message from P, N j checks the integrity of P AY , and computes on a temporary updated version of CR (CI c ) its own share Share j to be sent back to P through an SHR message. If a predened quorum among a representative group of N S (CI c ) is reached, P computes the group signature S N S(CIc ) , updates CR (CI c ) and advertises it along the notary set.

Payment conrmation

In case the group signature S N S(CIc ) is generated, the transaction succeeds and P sends back both A and B a notication message N T F containing the updated coin registry entry CR (CI c ). The group signature in this entry proofs the correctness of the transaction and prevents a malicious notary from arbitrarily modifying its content.

D.5 Evaluation

In this section we evaluate the feasibility of PRICE with respect to the security and privacy challenges dened in section D.2.

We assume the DHT as follows: DHT = K, N, R, C, id n (•) , id r (•) , id c (•) , ρ (•) K is the DHT keyspace, N , R and C correspond to the set of nodes, the set of resources and the set of coins, respectively. id n : N → K, id r : R → K and id c : C → K, denote the functions respectively associating a node, a resource, a coin to their identier. Finally, as previously dened ρ : K → {N } denotes the mapping function which outputs the set peers responsible given a resource. In particular, this responsibility function determines the notary set of a coin: ρ : id c → {N S (CI c )}. We will call k-bit zone the subset of the id space containing all the peers whose id agrees in the high order k bits.

D.5.1 Security

Coin integrity/unforgeability The integrity or unforgeability of a coin c is guaranteed thanks to the signature S CGEN of the Coin GENerator authority that generated that coin. Such a signature cannot be computed by anybody else, as the private key of the CGEN is never disclosed. Moreover, to keep fresh versions of the coin registry, a serial number in every entry of the coin registry helps a notary to come back online to update his registry from the other notaries.

Identiers integrity In PRICE, peers receive their peer identier P I from the TIS as an output of a one-way function h M K (•) over their real identity ID. Since the secret M K used in the keyed hash function h M K (•) is known by the TIS only, identiers cannot be arbitrarily computed or guessed by any user. Moreover, the account creation procedure can be repeated several times but the result always leads to the same identier. Therefore, even though certicates can be re-issued, peer identiers never change. This prevents any malicious user from stealing a legitimate user's identity, or from creating dierent identities, namely Sybils, and launch Denial of Service attacks.

D.5.2 Privacy

Data condentiality In PRICE, P AY and N T F messages are encrypted with the recipient's public key found in its certicate signed by the TIS. The user's private and public keys are computed by the user himself at the act of the account creation, and the private key is never disclosed. In case the private key is stolen, the certicate can be re-issued.

Anonymity As the TIS and the CGEN are separate entities, nobody can link a coin identier to a real user's identity. In fact, the TIS is the only party being able to link a peer identier to a real identity, but it does not hold any information about that user's coins. On the other hand, the CGEN distributes welcome coins to new peers, but it does not manage identity information. In case the TIS and the CGEN services are merged, no information rather than the initial association between coins and users can be derived. In fact, both the TIS and the CGEN are o-line services contacted only once by each legitimate user and do not play any role neither in communication nor in data management. Perhaps, they can be built in a distributed fashion.

In the DHT, a caretaker P can link a coin identier CI c to the owner's peer identier P I A for all the coins P is responsible for. Anyway, this does not reveal the owner A's real identity to P, as no information about P I A can be retrieved from A's certicate Cert(P I A , K + A ) S T IS .

Transaction untraceability In PRICE, the number of coins held by a user A and the history of all the transactions A did in the system is known by A and no one else. A single coin transaction can be traced by the notary set of that coin. However, this does not reveal anything about the other transactions of the same actor A. Moreover, due to the security of the pseudo-random function used by the CGEN to generate a coin c, the association mapped by ρ (•) between the coin registry entry CR (CI c ) and a notary N j ∈ N S (CI c ) responsible for it is also random.

D.5.3 Performance

In this section, we provide and evaluation of the performance of PRICE in terms of latency, storage and bandwidth consumption. In the following, we will consider Kad [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the xor metric[END_REF] as the underlying P2P overlay.

Latency The total transaction time T for a coin c can be seen as the sum of the time T L required to the payer A for looking up for a coin identier, the time T R for transferring the P AY message, the time T F required for the caretaker P to forward P AY along the notary set, the time T S to collect the shares in order to compute the group signature and, nally, Storage overhead An entry in the coin registry contains the coin id, the signature of the CGEN stating this coin is valid, the current owner's certicate, the old user's peer identier, a serial number, and nally the notary set group signature validating the correct association between the coin and its current owner. Assuming a keyspace of 128 bits, a signature length of 512 bits, public keys of 512 bits and a 32 bits integers length, an entry requires 308 Bytes.

The number of coins q every peer is responsible for, and as a consequence the size required to store the coin registry, strongly depends on the number of peers and the number of coins in a notary set. Assume the id space is divided into 2 k zones, and in each of them peers and resources agree on the k high-order bits. Assume the responsibility function ρ (CI c , k) maps a coin c to the set of peers in the k-bit zone dened by k. In this case:

q = N 2 k w (D.2)
where N is the cardinality of the set N , i.e. the total number of peers in the system, and w is the number of welcome coins every peer receives at the very rst join. Table D.3

shows the size every peer should allocate, on average, to store its coin registry in a network of 5.12 millions peers 1 and where each node initially receives 100 welcome coins. When k is set to 8, then 20,000 peers populate a zone, and can act as notaries for a maximum of 2 millions of coins. Their coin registry can then reach a maximum size of 587 MB. By increasing k to 16, the number of coins every peer is responsible for decreases to 7800, leading the size of a coin registry to 2.29 MB. Each of these t notaries receives the P AY message forwarded by the caretaker P, furhter computes the share of the group signature and sends it back to P. Assuming a keyspace of 128 bits, a signature length of 512 bits, public keys of 512 bits and a 32 bits integers length, a P AY message requires 246 Bytes, while s' size is 64 Bytes. 1 Steiner et al. [START_REF] Steiner | A global view of KAD[END_REF] observed between 12 and 20 thousand active peers in one 256-th of the entire KAD id space. In MANETS, credit-based incentive mechanisms were designed for enforcing the cooperation among nodes for the specic operation of forwarding. To achieve fairness, [START_REF] Buttyán | Enforcing service availability in mobile ad-hoc wans[END_REF] was relying on tamper proof hardware whereas [START_REF] Zhong | Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks[END_REF] dened a centralized on-line trusted entity. PRICE does not focus on the nature of a specic operation and does not require any tamper proof hardware nor centralized entities to manage credits.

In the P2P scenario, authors in [START_REF] Vishnumurthy | KARMA: A Secure Economic Framework for Peer-to-Peer Resource Sharing[END_REF] proposed a micropayment scheme where each peer is associated to a scalar value called Karma. A set of randomly chosen bank set nodes increase or decrease a peer's karma in case this peer contributes with-or consumes-resources. An atomic transaction scheme ensures fairness in the payment since the key to decrypt resources and certicate of receipt are provided simultaneously to the resource consumer and the provider respectively. When a le transfer occurs from a peer B to a peer A such a le is encrypted with a secret DES, then upon A's authorization, each member of A's bank set independently send a karma transfer request to all members of B's bank set, that in turn ask again A's bank set nodes for an acknowledgment. Once veried a majority quorum exists, B proceeds with the le transfer, and A provides B with a receipt. If B gets the receipt, A receives the key to decrypt the le.

In BitTorrent 3 , a variant of "`tit-for-tat"' [START_REF] Cohen | Incentives Build Robustness in BitTorrent[END_REF] mechanism encourages fairness in the exchange of le chunks. Such a mechanism aims at seeking pareto eciency, meaning in this case that peers reciprocate uploading to peers which upload to them, aiming at having all the time several connections actively transferring data in both directions. In case of lack of reciprocity, a peer can temporarily refuse to upload a chunk to-, or choke a-, lazy peer.

An optimistic unchoke mechanism, corresponding to always cooperating on the rst move in prisoner's dilemma, solves the problem of discovering if current unused connections are better than the ones being used.

D.7 Conclusion

PRICE is a new cooperation enforcement mechanism which relies on credit-based incentives and takes advantage of the underlying DHT based P2P network to cope with security and privacy challenges. The task of coin management is distributed among several peers and in order to ensure transaction untraceability, PRICE assigns each single coin to a dierent set of notaries. The assignment function on the inherent functionality of a P2P network which is the DHT and the randomness of each assignment is ensured thanks to the security of the pseudo-random function used to generate the coin. The number of notaries is dened based on the ratio of malicious nodes and the average online probability and can have a direct impact on the robustness and performance of the P2P network. The communication overhead increases when more notaries are solicited for computing the threshold signature.

3 . 2

 32 Current OSN and their characteristics. . . . . . . . . . . . . . . . . . . . . . . 4.1 Current DOSN proposals as an answer to the Big Brother problem in centralized OSNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 An example of ACP based on set operations between contacts granted with user-dened badges. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Main characteristics of ve social graphs from Facebook (p ν computed as- suming p mal =0.01). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Characteristics summary of examined SN graphs. . . . . . . . . . . . . . . . . D.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.2 Time statistics in seconds for the three main distributions in gure D.2 . . . . D.3 Coin registry size in MB for dierent values of k . . . . . . . . . . . . . . . . xv Acronyms These are the main acronyms used in this document. The meaning of an acronym is usually indicated once, when it rst occurs in the text.

B

  ACP of user V B V the set of all the badges dened by V R V the set of all the rules dened by V S V the distributed data storage space of user V r a rule in the ACP A s r a seed associated to a rule r xix D n r a set of n DEKs associated to rule r F V the set of all the contacts of V E U V the set of all the DEKs sent byV to U {M } SK V a message M signed by the user V's private key K - V E K U {M } a message M encrypted with the user U's public key K + U N ame V a tuple of properties identifying user X N Id V node identier of user V U Id V user identier of user V Cert N Id V , N + V node identier certicate for user V Cert U Id V , U + V user identier certicate for user Vmin expected value of a random variable X f i the ith element of vector f, if the latter is denedf arithmetic mean of vector f set union \ set element exclusion v ∈ V an element v in a set V V cardinality of a set V G (V,E) a graph composed by a set V of vertexes and and a set E of edges deg (•) (n, p) binomial distribution with number of trials n and success probability in each trial p R h random walk distribution after h hops ssd steady state distribution ∆ x (h)

Chapter 5

 5 motivates the need for a new privacy preserving OSN addressing the objectives of security and privacy presented in Chapter 3 and proposes a new decentralized approach for OSN achieving privacy by design. Such an approach, namely Safebook, targets decentralization and cooperation enforcement with the help of an ad-hoc peer-to-peer network mapping the real life social network graph. The trust relationships established in such an OSN are leveraged to build the OSN itself and provide data storage and communication obfuscation services.

Figure 2 .

 2 Figure 2.1 illustrates and summarizes the diversity of OSN customers and reects their relationship to the SNS functionality and possible access to the personal information of the OSN users.

Figure 2 . 1 :

 21 Figure 2.1: OSN customers and their relationships to PII and SNS

gure 2 . 2 )

 22 . OSN users can typically build their proles and establish relationships with each other. The set of networking functions includes all functions that update the vertices and the edges of the social network graph. In particular, the OSN user invokes the prole creation function upon his or her registration to the OSN platform. This function adds a new vertex representing that user in the social network graph. Thereafter, with prole lookup the user can nd other users who are also represented via vertices. Through the call to the relationship link establishment function the user can set up a new relationship with some other user. This function typically sends notication to that user, who in turn can accept or ignore the request. If the user accepts the request then users are added to the contact lists of each other and a new edge representing their relationship is added to the social network graph. The OSN users can also encounter proles for possible relationships thanks to the contact list browsing function, which is realized through the traversal along the edges of the graph. Additional networking functions can be used to remove vertices and edges from the graph, for example upon the deletion of the user's prole.

Figure 2 . 2 :

 22 Figure 2.2: Main functionality of a typical OSN platform

Figure 2 . 3 :

 23 Figure 2.3: Types of data commonly stored in OSN proles.

Figure 3 . 1 :

 31 Figure 3.1: Impersonation attacks: victim U doesn't have any OSN account, victim V has an account on OSN1 and victim Z on OSN2. The attacker A generates U's account on OSN2, a copy of V's account on OSN1 and OSN2, and logs on OSN2 with the credentials of Z.

Figure 3 . 2 :

 32 Figure 3.2: Main PII related threats in current OSNs.

  the design of a newly distributed OSN addressing the security objectives presented in chapter 3. The new mechanism, called Safebook[START_REF] Antonio Cutillo | Privacy preserving social networking through decentralization[END_REF][START_REF] Antonio Cutillo | Leveraging social links for trust and privacy in networks[END_REF], leverages peer-to-peer concepts and capitalizes on the trusted links from the managed social network, thus transferring the trust between the OSN users to the collaborating parties of the system. Decentralization circumvents the need for a central provider and leads to a distribution of data, communication, and control. While the alternative approach of privacy protection based on encryption is considered as a partial solution only, decentralization eliminates the privacy threats resulting from a centralized SNS entirely. However, P2P systems being devoid of any central point of control inherently suer from a lack of trust between the parties.

  provided by this user's friend nodes, tracing of communications by very simple means would disclose the friendship relationships in the social network.The adoption of anonymous communication techniques seems then an obvious second step toward the security objective of protection of social trust links against OSN members. However, such anonymous communication technique should be in line with the design principles previously mentioned. Therefore, we protect the rst ring with a second one consisting of nodes that each are a trusted contact of a node on the rst ring. Further rings are built through similar trust relationships, without requiring nodes on the same ring to have trust relationships with one another, and without requiring transitivity of trust.Data requests are then addressed to the nodes in the outermost ring, and are forwarded to the nodes in the rst one along hop-by-hop trusted links. Data is served by nodes in the innermost ring and replies are sent back along the same paths. Safebook thus consists of the collection of concentric layers of peers nodes organized around each user in order to assure data storage and communication privacy.

Figure 5 . 1 :

 51 Figure 5.1: Cyclic relation showing how real life trust between users can build the OSN itself.

Figure 5 . 2 :

 52 Figure 5.2: Safebook overlays (left), main components (center) and Matryoshka (right).

Figure 5 .

 5 Figure 5.3 shows a communication scenario between users in Safebook.

Figure 5 . 3 : 1 n- 3 B F amily s r 2 n- 2 B T eam s r 3 n- 1 B 4 n- 3 Table 5 . 1 :

 531322314351 Figure 5.3: An example of communication between users with dierent ACPs.

Figure 5 . 4 :

 54 Figure 5.4: Account creation for user V.

Figure 5 . 5 :

 55 Figure 5.5: Matryoshka setup for user V.

Figure 5 . 6 :

 56 Figure 5.6: Entrypoint registration for user V's Matryoshka.

Figure 5 . 7 :

 57 Figure 5.7: A V's prism is leaving Θ V .

Figure 5 .

 5 Figure 5.10 shows the details of the data storage protocol.

Figure 5 . 10 :

 510 Figure 5.10: Prole data storage for V.

Figure 6 . 1 :

 61 Figure 6.1: online, oine and the corresponding residual life distributions derived from the Skype dataset

Figure 6 . 3 :

 63 Figure 6.3: Data availability where f = 130, p = 0.53 and f l = f -1 (no overlapping between friend lists

Figure 6 . 4 :

 64 Figure 6.4: Data availability where f = 130, p = 0.53 and f l = f -ml (full overlapping between friend lists

Figure 6 . 5 :

 65 Figure 6.5: Fragment size evaluation for dierent upload bandwidth c with varying request rate λ.

Figure 6 . 6 :

 66 Figure 6.6: Maximum size of data retrieved at every request for dierent upload bandwidth c with varying request rate λ.

93 and

 93 compute them for existing social graphs. These characteristics are the node degree, the clustering coecient , and the mixing time. The impact of the evolution of these characteristics is also evaluated based on existing social graphs: in September 2005, Facebook published anonymous social graphs of 5 universities in the United States 1 : California Institute of Technology (Caltech), Princeton University (Princeton), Georgetown University (Georgetown), University of North Carolina (UNC), Oklahoma University (Oklahoma).

Figure 7 . 1 :

 71 Figure 7.1: Log-log plot of the degree complementary cumulative distribution of real-life social networks.

Figure 7 . 2 :

 72 Figure 7.2: Average clustering coecient of real-life social networks with respect to node degree.

Figure 7 . 3 :

 73 Figure 7.3: Mixing time of real-life social networks.

Figure 7 . 4 :

 74 Figure 7.4: Ratio of common friends between two nodes V and θ h at social distance h in the social network

Figure 8 . 2 :

 82 Figure 8.2: Internal (left) and external (right) message exchange in Safebook

  8.5), such as all current social network services which are accessible via internet browsers. The User Manager runs a http server in localhost at port 8080 intercepting and executing the user's commands, and drawing XHTML 1.0 webpages 6 as a result.

6

  http://www.w3.org/TR/2000/REC-xhtml1-20000126/7 The mailbox has not yet been implemented in the current prototype.

Figure 8 . 3 :

 83 Figure 8.3: Account Creation: out of band step on the left, in band step on the right.

Figure 8 . 4 :

 84 Figure 8.4: The Safebook logo: two persons shaking hands represent the process at the basis of Matryoshka and, more generally, of Safebook.

Figure 8 . 5 :

 85 Figure 8.5: Graphical interface of Safebook: on the top-left the Safebook join; on the top-right the prole page in the podium section; on the middle-left picture sharing in the gallery page; on the middle-right wall posting in the square; on the bottom-left friendship advertisement; on the bottom-right friend browsing in the contacts page.

  Figure A.1 Clients des services de réseaux sociaux et leur relations avec les informations personnellement identiables.

Figure A. 8

 8 Figure A.8 Un exemple de communication entre les utilisateurs avec des diérents politiques d'access aux donnés partagés.

Figure A. 9

 9 Figure A.9 Les distributions des temps en ligne, hors ligne et correspondantes à la vie résiduelle provenant de l'ensemble de données Skype.

Figure A. 10

 10 Figure A.10 Durée de vie résiduelle de la chaîne par rapport à sa longueur h.

Figure A. 11

 11 Figure A.11 Taille maximale des données récupérées à chaque demande avec bande passante c en upload et diérents taux de demandes λ.

Figure A. 14

 14 Figure A.14 Temps de mélange (en pas) dans des réseaux sociaux réels.

Figure A. 15

 15 Figure A.15 Ratio des amis communs entre les deux noeuds V et θ h à une distance sociale h dans le reseau social.

Figure A. 16

 16 Figure A.16 Architecture globale de Safebook.

Figure A. 17 L

 17 Figure A.17 L'échange interne (à gauche) et externe (à droite) de messages en Safebook.

Figure B. 2 :

 2 Figure B.2: A black hole B in Θ V (right).

Figure C. 1 :

 1 Figure C.1:The Matryoshka graph of a user V, from[START_REF] Antonio Cutillo | Safebook: a privacy preserving online social network leveraging on real-life trust[END_REF]

Figure C. 3 :

 3 Figure C.3: Picture publication steps for V, with V's face f V made publicly available: 1picture input; 2-face detection; 3-face tagging; 4-face extraction; 5-face obfuscation; 6picture and publisher face publication.

Figure C. 4 :

 4 Figure C.4: Public picture advertisement: 1-N is informed about P; 2-face detection; 3-face tagging; 4-publisher face extraction; 5-face obfuscation; 6-picture and N's face publication according to N's access control policy on her face.

  Figure C.5 shows p is always about one fourth of d and both p an q increase linearly with d by a factor of around 1.2.

Figure C. 5 :

 5 Figure C.5: Average outdegree, average number of 4-hops chains, average number of served Matryoshka for dierent social network graphs when 30% of nodes are on-line.

Figure C. 7

 7 Figure C.7 shows the number of compromised chains in case of absence of collusion, m u , and in case of collusion, m c . One can see that in case of collusion, this number drastically increases by a factor ranging between roughly 4 and 32. When assuming the fraction of misbehaving nodes as high as 25% (see gure C.8), almost all the chains get compromised.

Figure C. 7 :

 7 Figure C.7: Average number of compromised chains when 10% of nodes misbehave for dierent social network graphs.

Figure C. 9

 9 Figure C.9 summarizes the characteristics of the proposed solution.

Figure C. 9 :

 9 Figure C.9: Spread of information vs usage control: in case of unprotected picture publication, automatic face obfuscation is guaranteed by peer collaboration even when there is software manipulation; in case of encrypted publication, the software manipulation may violate user's privacy, but with limited impact within the DOSN.

Figure D. 1 :

 1 Figure D.1: Payment scheme.

AA

  and sends an out of band request to the TIS. This request contains A's public key K + A , together with his claimed identity ID A . Once this request is received, the TIS generates A's peer identier as P I A = h M K (ID A ), where h M K (•) is a keyed hash function whose master secret M K is known only by the TIS and nobody else. The TIS sends back to A the certicateCert(P I A , K +A ) S T IS and informs the coin generator a new user has joined the system.Welcome coins attributionAs the CGEN receives a message from the TIS stating a new user A has arrived, it generates a new set of coins {c i }, and provides A with this set by sending him a P AY message for every 178Appendix D PRICE: PRivacy preserving Incentives for Cooperation Enforcement Table Dprivate and public keys of A {•} S A signature generated with the private key of A Cert(I, K + ) certicate associating an identier I to a public key K + M K master key h M K (•) keyed hash function with master secret M K E B {M } S A message M signed by A and encrypted for Bc coin c CI c coin identier of c CR (CI c ) coin registry of c N S (CI c ) notary set of c K DHT keyspace N set of all the peer nodes in the DHT R set of all the resources stored in the DHT C set of all the coins in the DHT id x (x) map of x to an identier in K ρ (x) responsibility function mapping x to a set {P I} q number of coins every notary is responsible for w number of welcome coins granted to a newcomer coin signed by the CGEN itself. A can collect CGEN's coins by sending these messages to the DHT. The signature of the CGEN prevents a malicious user from modifying the P AY messages and steal the welcome coins by changing the beneciary.

  182Appendix D PRICE: PRivacy preserving Incentives for Cooperation EnforcementTransaction integrity The integrity of a transaction involving a coin c is represented by the integrity of the record CR (c) in the coin registry, and is guaranteed by the group signature S N S(CIc ) . Therefore PRICE prevents the double spending of coins. Computing such a signature requires the collusion of a sucient number of notaries and can therefore be mitigated by increasing the minimum notaries quorum at the expense of higher computation cost and communication overload.

- 1 T RT T and F - 1 T 2 AverageFigure D. 2 :

 1122 Figure D.2: Total transaction time evaluation: T RT T and T L from [110], T from Monte Carlo techniques (10000 samples).

t = N 2 k 1 (D. 3 )Figure D. 3

 2133 Figure D.3 outputs the t values with respect to dierent m and p values where k is set to 16. t varies between 2 and 21 where both m and p take values between 0.1 and 0.5.

  Figure D.3: Evaluation of the number of notaries t to be contacted for every transaction for dierent online-p and misbehaving-m probabilities.

Figure D. 4 :

 4 Figure D.4: Evaluation of the bandwidth consumption for dierent transaction rates λ (per hour) and notaries to be contacted t.

Table DEK

 DEK

	xviii		Acronyms
	SNS	Social Network Services
	Notations
	Generally, boldface upper-case letters denote matrices and boldface lower-case letters de-
			Data Encryption Key
		DOSN	Distributed Online Social Network
		KDC	Key Distribution Center
		KEK	Key Encryption Key
		OSN	Online Social Network
		P2P	Peer-to-peer
		PII	Personally Identiable Information
		SN	Social Network
		SNA	Social Network Application
		SNP	Social Network Providers
			xvii

note vectors (unless stated otherwise). Calligraphic upper-case letters denote sets. The superscript T stands for transpose.

  The latter subgroup can be dened via the regroup function. Additionally, users may create interest groups, advertise own interest groups to other users, and join interest groups created by other users. The user who creates an interest group obtains administrator rights for this group by default;

however, these rights can be changed thereafter, and distributed to other group members.

Table 3 .1: Attacks vs. Security Objectives in Online Social Networks

 3

			Security Objectives
		Privacy	Integrity	Availability
	Plain Impersonation	x	x
	Prole Cloning	x	x
	Prole Hijacking	x	x
	Prole Porting	x	x
	Id Theft	x	x	x
	Proling	x
	Secondary Data Collection	x
	Fake Requests	x
	Crawling and Harvesting	x
	Image Retrieval and Analysis	x
	Communication Tracking	x
	Fake Proles and Sybil At-		x
	tacks
	Group Metamorphosis		x
	Ballot Stung and Defama-		x
	tion
	Censorship		x	x
	Collusion Attacks	x	x	x

Table 3 .

 3 2: Current OSN and their characteristics.

			Characteristics
		SNP	Unique visitors	Market value (billion
			(million)	US$)
	Facebook	Facebook Inc.	845 (dec 2011)	50 (Jan 2011)
	Twitter	Twitter Inc.	100 (Oct 2011)	8 (Oct 2011)
	LinkedIn	LinkedIn	135 (Nov 2011)	8 (May 2011)
		Corporation
	Google Plus	Google Inc.	90 (Dec 2011)	155 (Feb 2012)

  data through Persona applications, providing a set of APIs over which social network facilities like wall posting or prole publishing operate. Access to user data is controlled through Attribute Based Encryption (ABE), and traditional public key cryptography. The attributes a user has determines what data they can access: private user data is always encrypted with a symmetric key, that is in turn encrypted with an ABE key corresponding to the group that is allowed to read this data.

  -in public-key cryptography primitives ensure data access control. Prometheus users allow this OSN to collect their social information from social sensors, i.e. applications that report to Prometheus the user's interactions with other users via e-mail, phone, instant messaging et similia. Information collected by these sensors is collected by Prometheus and used to create

a social graph where the edges, i.e. the trust relationships, are weighted by the strength of the trust. Both the information of the social graph and that one coming from sensors are stored in an encrypted form and accessible from user's trusted peers. Users' social graph is stored on her trusted peers. Similarly to Lifesocial.KOM Prometheus runs on top of Pastry

[START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF]

Table 4 .

 4 1 reports the aforementioned solutions for DOSNs with their main characteristics.

			Characteristics
		Storage place	Incentives for	Access control on
	DOSNs		SNS	published data
	FOAF	trusted web	absent	by means of data
		server		encryption
	Diaspora	trusted web	absent	by means of data
		server		encryption
	Vis-à-Vis	cloud computing	commercial	by means of requester
		infrastructure	contracts	authorization
	Persona	trusted web	commercial	by means of data
		server	contracts	encryption
	Lockr	trusted web	commercial	by means of requester
		server	contracts	authorization
	Peerson	OpenDHT	absent	by means of data
				encryption
	Lifesocial.KOM	Pastry	absent	by means of data
				encryption
	Prometheus	Pastry / trusted	absent / social	by means of data
		peers	trust	encryption
	Likir	Kademlia	reputation system	by means of data
				encryption

Table 4 .

 4

1: Current DOSN proposals as an answer to the Big Brother problem in centralized OSNs

Table 5 .

 5

1 shows an example of ACP.

  3, at every prole request prof Req one mirror replies with a prof Rep message. Such message contains one or more encrypted signed data tokens ESDtok, i.e. data items signed by the core and encrypted with a symmetric DEK. In the rest of this analysis, we consider the worst case in which only one ESDtok is contained in each prof Rep.

Table 7 .

 7 1) 1: Main characteristics of ve social graphs from Facebook (p ν computed assuming p mal =0.01).

	Caltech	769	43.32	0.41	0.35	0.14	11
	Princeton	6596	88.93	0.24	0.59	0.14	34
	Georgetown	9414	90.43	0.22	0.60	0.13	53
	UNC	18163	84.44	0.20	0.57	0.11	17
	Oklahoma	17425	102.44	0.22	0.64	0.14	22

Table 7 . 2

 72

		.32	2.35	9.4	0.05	4.00	0.097
	Princeton	88.94	9.06	36.24	0.10	4.00	0.024
	Georgetown	90.43	8.59	34.37	0.10	4.00	0.017
	UNC	84.44	8.18	32.73	0.10	4.00	0.010
	Oklahoma	102.44	10.32	41.26	0.10	4.00	0.013

: Characteristics summary of examined SN graphs.

  The track of each coin is kept by a dierent set of notaries. Therefore, whenever Alice would like to grant a coin to Bob, she contacts one of the notaries corresponding to this specic coin, namely the caretaker notary , and informs it about the new ownership of the coin. With the agreement of the other notaries, the caretaker then sends a proof of this transfer to Bob. Even if a malicious node succeeds in discovering current transfer of this coin, it will not be able to trace all actions taken by Alice or Bob since the management of each coin is assigned to dierent

	176Appendix D PRICE: PRivacy preserving Incentives for Cooperation Enforcement
	notaries.
	Based on this scenario which is illustrated in gure D.1, we identify three main steps
	among the proposed incentive mechanism:

Table D .

 D 3: Coin registry size in MB for dierent values of k k [bit] CR [MB] 587.46 146.87 36.72 9.18 2.29Communication Bandwidth Overhead In order to evaluate the communication overhead, we rst evaluate the minimum number of peers t required to compute a group signature. This threshold number should be dened according to the underlying privacy and robustness challenges: t strongly depends on the ratio m of malicious users and the online probability p of nodes. t can therefore be computed as follows:

	8	10	12	14	16

Uno solo è il mio desiderio, quello di vedervi felici nel tempo e nell'eternità.sac. Giovanni Bosco

http://www.facebook.com

http://www.linkedin.com

https://plus.google.com

http://www.xing.com

http://www.odnoklassniki.ru

available information across multiple OSN proles and applications in an automated way

http://xmlns.com/foaf/spec/

http://www.webdav.org

http://openid.net/specs/openid-authentication-1_1.html

http://www.joindiaspora.com

http://podupti.me/

We rely on this data since Skype, as Safebook, operates on a P2P model and its application client, once executed, runs in the background.

http://www.cs.uiuc.edu/homes/pbg/availability

We assume a single next hop can always be found in the Matryoshka creation so that equation 6.7 can

In Safebook, user may not decide to share their contact list, or share it with limitations.

Of course, when more than one Safebook host is behind the same NAT, only one of them can run a HTTPS server.

we don't consider the empty set among the set of combinations.

Matryoshka bootstrappers are syntetic Safebook nodes that do not belong to real users and are trusted by the TIS.

aux utilisateurs de rester à jour avec les nouvelles de leur amis et très souvent la popularité des utilisateurs est mesuré avec le nombre de contacts. L'analyse de l'OSN à l'égard des propriétés de sécurité et de la vie privée de leurs utilisateurs revèle une serie évidente des menaces. En règle générale, une multitude de données personnelles des participants est stockés par les fournisseurs de SNSs, en particulier dans le cas d'OSN avec ns non professionnelles. Ces données sont soit visible pour le public, ou, si l'utilisateur est conscient des problèmes de la vie privée et capables de régler les paramètres de le SNS, à un groupe sélectionné d'autres membres. Comme les prols sont attribués à des personnes vraisemblablement connues du monde réel, ils sont implicitement évaluées avec la même conance du propriétaire présumé du prol. En outre, toutes les actions et les interactions couplées à un prol sont de nouveau attribué au propriétaire présumé de ce prol. Diérentes études ont montré que les participants représentent clairement le maillon faible de la sécurité dans les OSNs et qu'ils sont vulnérables à plusieurs types d'attaques d'ingénierie sociale. Ceci est en partie causée par un manque de sensibilisation aux conséquences des actions simples et sans doute privé, comme accepter les demandes d'amitié, ou marquer les images, ainsi que les opérations de communication comme commenter les prols ou acher des messages sur les murs. Le faible degré de facilité d'utilisation de contrôles de condentialité oertes par le SNS, et enn et surtout la conance dans les autres prols aggravent certainement le problème.En analysant les problèmes de la vie privée dans les OSNs actuels, il devient évident que, même si tous les participants fussent au courant des expositions et ils fussent compétents

dans l'utilisation des SNS, et même si un ensemble concis des mesures de protection de la vie privée fût déployé, l'OSN serait toujours exposé à violations potentiels de la vie privée par le fournisseur omniscient du service : les données, directement ou indirectement fournis par tous les participants, sont en fait collectées et stockées de façon permanente dans des bases de données du fornisseur de service, qui devient potentiellement un Grand Frère capable d'exploiter ces données à de nombreux égards qui peuvent violer la vie privée des utilisateurs individuels ou des groupes d'utilisateurs.L'importance de cette exposition de la vie privée est soulignée par la capitalisation boursière de ces fournisseurs, qui atteint 50 milliards de dollars (Facebook Inc, selon l'investissement de Goldman Sachs et Digital Sky Technologies en 2011)[START_REF]Goldman oering clients a chance to invest in facebook[END_REF], et par les revenus globales des annonces publicitaires, qui ont atteint 5 milliards de dollars en 2011 et sont estimés à doubler avant le 2013 (selon eMarketer[START_REF]Social network ad revenues to reach $10 billion worldwide in 2013[END_REF]).Cette thèse arme que la vie privée de l'utilisateur peut être facilement mis en péril en raison de l'architecture centralisée de l'OSN, et les fournisseurs de SNSs actuels ne sont pas susceptibles de remédier à ce problème en raison de leur modèle d'aaires. Ce travail considère plutôt la protection des données privées dans les OSNs comme un sujet urgent et propose une nouvelle architecture pour OSN conçue avec le but de proteger la vie privée de ses utilisateurs.A.1 Objectifs de rechercheCette thèse suppose que la protection de la vie privée de l'utilisateur contre le fournisseur omniscient des SNSs soit l'objectif principal pour l'OSN et vise à identier les caractéristiques principales qu'une OSN devrait satisfaire pour atteindre un tel objectif ainsi que à fournir une nouvelle architecture pour préserver la vie privée dans l'OSN. Comme objectif supplémentaire, cette these vise à protéger aussi la vie privée des utilisateurs honnêtes contre les utilisateurs mailvellants.Nous dénissons l'objectif de protéger la vie privée comme la possibilité de dissimuler des informations au sujet de n'importe quel utilisateur à tout moment, même dans la mesure de cacher la participation des utilisateurs et des activités au sein de l'OSN. Par conséquent, la vie privée englobe pas seulement la protection des renseignements personnels que les utilisateurs publient sur leurs prols, mais prend également en compte la communication entre les utilisateurs, c'est-à-dire, il faut qu'aucune des parties sauf que celles adressées directement

Figure A.7 Les recouvrements de Safebook (à gauche), les composants principaux (au centre) et la Matryoshka (à droite).

http://www.facebook.com/

http://twitter.com/

http://www.linkedin.com/nhome/

https://plus.google.com/

http://www.bbc.co.uk/news/business-12106652

This doesn't violate V's privacy, since V aims at making P publicly available.

In Safebook, this phase corresponds to the storage of the picture at V's friend nodes.

http://people.maths.ox.ac.uk/ porterm/data/facebook5.zip

i.e. nodes trying to maximize the benets they get from the network while minimizing their contribution to it.

http://www.bittorrent.com

Acknowledgments

Chapter 5 Safebook

The characteristics of Safebook are described in detail in the following sections.

negatively impacts the privacy of the solution, as measured as the ratio of common friends between an entrypoint and a core in one user's Matryoshka. When choosing a large value for the depth h of the Matryoshka, which is a privacy requirement, such ratio decreases. On the other hand, a large value of h leads to the creation of a Matryoshka with fewer branches, therefore has a direct impact on data availability. However, increasing h after an optimal value h ∞ does not have an impact on the privacy level anymore. We observe that social networks with faster mixing time reach such optimal value faster.

Chapter 8 Implementation

In previous chapters we have motivated the need for new privacy preserving OSNs and we proposed Safebook, an OSN based on a distributed architecture where real life friends provide communication and storage services, ensuring user privacy. This chapter describes a rst implementation of Safebook.

The current prototype of Safebook 1 consists of 50 les and 14000 lines of code, one half of the latter consisting in the python scripts running the main application, one other half consisting in HTML, CSS, and Javascript used to design the user interface.

Once the python interpreter and a series of prerequisite libraries 2 have been installed, execution of Safebook is started with the command: >p y t h o n s a f e b o o k . py Double clicking on the Safebook executable identied by the icon in gure 8.4. Due to the high availability of python interpreters for dierent operating systems, including Windows, Linux and MacOs, Safebook can be executed by all end-users' personal computers. 1 The Safebook client is available for download [START_REF]Safebook prototype[END_REF] under GNU General Public License Version 3 [START_REF]Gnu general public license[END_REF]. 2 Twisted, pyOpenSSL, M2Crypto, pysqlite, PIL. Once started, the Safebook client spawns a dispatcher thread spawning, in turn, all the managers in the following order: Communication, S2S, User and Matryoshka. While the Chapter 8 Implementation Kademlia, and a recursive one. While the rst one is more robust against the node churn, the second one protects the node identier of the real requester. Two parameters α and β can be set up to tune the lookup parallelism: in the iterative case, the requester triggers a lookup to the α nodes closest to the DhtKey, that will answer, in turn, with their β closest contacts; in the recursive case, these α nodes forward the request to their β closest contacts, each of them forwarding the request, in turn, to their own β closest contacts and so on.

Both the iterative and recursive search succeed when a node suciently close to DhtKey is reached and answers with the V alue associated to the lookup key.

Join and Leave To join the S2S network, a node needs to obtain a certied node identier from the TIS. Afterward, to ll its buckets, the newcomer triggers an iterative lookup for its node identier. Even if no V alue is associated to any node Id, still the iterative lookup can take place and allows the newcomer to get in touch with a set of new peers that may populate its routing table. However, the newcomer refers to a set of predened bootstrapping peers at the very rst join, when its buckets are empty. When logging out, all the buckets are saved.

Appendices

Appendix A

Résumé étendu

Les Services des réseaux sociaux (SNS) tels que Facebook, LinkedIn ou Google +, sont desormais devenus un facteur prédominant de l'Internet. En s'addressant à une population d'utilisateurs très grande avec une grande diérence de provenance social, éducative et national, ils permettent même aux utilisateurs ayant une connaissance des moyens techniques limitée de publier des renseignements personnels et de communiquer facilement.

En général, les réseaux sociaux en ligne (OSN) résultant de ces SNSs sont des représentations numériques d'un sous-ensemble des relations que leurs participants, des utilisateurs inscrits ou des institutions, entretiennent dans le monde physique. En comprenant les participantes avec leurs relations, ils modélisent le réseau social sous forme de graphe.

Cependant, la popularité et l'acceptation générale des services de réseau social comme plateformes de messagerie et de socialisation attire pas seulement les utilisateurs dèles qui tentent d'ajouter de la valeur à la communauté, mais aussi les parties ayant des intérêts plutôt défavorables, soit commerciales, soit malveillants. L'activité principale des membres des OSNs est la création et l'entretien de leurs listes de contacts, qui permit de construire le graphe numérique de l'OSN. En informant automatiquement les membres sur les modications des prols des leurs contacts, le SNS permet ainsi The Matryoshkas pose as infrastructure vital for the availability of the data published by their core, and for their core's reachability. Considering their distributed organization, failures may always remain undetected over a period of time. Even worse, it introduces uncontrolled dependencies to other parties, thus making the Matryoshka potentially vulnerable to misbehavior. The cores in consequence need a means to verify the integrity of their Matryoshkas. The Matryoshka verication protocol enables the core V both to verify the integrity of the trees, dened by the maximum number of shells and the spanning factor, through the Matryoshka, and the set of nodes that are registered as entrypoints. It thus allows for the detection of incidents in which another node for reasons of failure or misbehavior deviates from the protocol by either selecting much more than Span neighbors for the next shell, or registered as entrypoint without authorization.

To get Ω V , the set of authorized entrypoints to V's Matryoshka, V sends a f indOutShell message through the Matryoshka, generating dierent signed random numbers for each ith mirror node λ V ∈ Λ V : Rnd SU V ,i . On reception of f indOutShell, the authorized entrypoints create an outShellM emb message, which contains Rnd SU V ,i , a list of entrypoints retrieved from V's docks (RetrEP list), and their node Id certicate. outShellM emb is then encrypted for V in order to prevent any information about trust relationships on the trees through the Matryoshka being leaked, and sent back to V. Collecting these responses, V can check the integrity of its Matryoshka by verifying that each tree leads to almost Span T tlM atr entrypoints. On detection of underpopulated trees or overbranching, V performs aimed Matryoshka updates. If one or a set Γ V of third party nodes exist that advertise V's Matryoshka without being authorized nor part of it, they can be identied by V, as they will be element of RetrEP list but not in the set of nodes that answered to the f indOutShell message:

V in consequence sends an intruders message to Θ V containing the signed set Γ V of intruders. The authorized entrypoints of V forward this list of intruders to the docks K, with which they are registered. These in consequence remove the intruders from their entrypoint tables and forward the information to the other registering nodes in the RespArea.

Trusted Friend Misbehavior -Internal Attacks

A misbehaving prism in Θ V that mounts a black-or white hole attack is detected by the Matryoshka verication protocol, as well. As a matter of fact, if a node θ j ∈ Θ V placed in the jth shell of V's Matryoshka selects a number higher than Span of next hops in order to attract more trac (cmp. g. B.2), its predecessor θ j-1 directly detects this misbehavior by simply checking the number of outShellM emb messages received. If the number is too high, θ j is obviously misbehaving. Its predecessor will purge it from the Matryoshka and it will not be selected a trusted next hop in the future. Even if the number is comparable to Span and the predecessor is unable to detect the misbehavior, the exceeding leafs of the respective tree are identied as intruders and removed from Ω V as described in section B.1.

In both the cases, the attack is detected and suppressed.

Appendix C Privacy Preserving Picture Sharing in

Distributed OSNs

The problem of usage control, which refers to the control of the data after its publication, is becoming a very challenging problem due to the exponential growth of the number of users involved in content sharing. While the best solution and unfortunately the most expensive one to cope with this particular issue would be to provide a trusted hardware environment for each user, in this paper we address this problem in a conned environment, namely online social networks (OSN), and for the particular picture sharing application. In current OSNs, the owner of an uploaded picture is the only one who can control the access to this particular content and, unfortunately, other users whose faces appear in the same picture cannot set any rule. We propose a preliminary usage control mechanism targeting decentralized peer-to-peer online social networks where control is enforced thanks to the collaboration of a sucient number of legitimate peers. In this solution, all faces in pictures are automatically obfuscated during their upload to the system and the enforcement of the obfuscation operation is guaranteed thanks to the underlying privacy preserving multi-hop routing protocol. The disclosure of each face depends on the rules the owner of the face sets when she is informed and malicious users can never publish this content in clear even if they 153 have access to it.

C.1 Introduction

Widespread adoption of Online Social Networks (OSNs) like Facebook 1 , Twitter 2 , LinkedIn 3 , and recently Google Plus 4 is due to the ease of communication allowing users, even those with limited technical skills, to share a wide range of personal information with a theoretically unlimited number of partners. This advantage comes at the cost of increased security and privacy exposures, since they tend to disclose private personal information with little guard [START_REF] Mislove | You are who you know: inferring user proles in online social networks[END_REF][START_REF] Gross | Information revelation and privacy in online social networks[END_REF][START_REF] Zheleva | To Join or Not to Join: The Illusion of Privacy in Social Networks with Mixed Public and Private User Proles[END_REF] and existing OSN applications seem to have an inherent economical interest in keeping this disclosure huge. Probably, such a strategy aims to attract other users and increase the OSN market value, that can reach, as in the case of Facebook in a deal of January 2011, up to 50 billion dollars 5 .

Nevertheless, the overall protection oered by current centralized OSN on users personal private information is far from being satisfactory: unfortunately, all information cannot be protected and those that can be controlled are rarely protected by default [START_REF] Krishnamurthy | On the leakage of personally identiable information via online social networks[END_REF]. Even with a very strong and specic access control policy, where the user who uploads or posts" a content can, indeed, prevent unauthorized access, he unfortunately looses the control on it after its very rst publication.

The problem of usage control which refers to the previously described issue is becoming a very challenging problem due to the exponential growth of the number of users involved in such content sharing applications. Recently, several peer-to-peer (P2P) based distributed online social networks (DOSN) have been proposed to preserve users' privacy ( [START_REF] Antonio Cutillo | Safebook: a privacy preserving online social network leveraging on real-life trust[END_REF][START_REF] Gra | Lifesocial.kom: A secure and p2p-based solution for online social networks[END_REF][START_REF] Buchegger | PeerSoN: P2P Social Networking Early Experiences and Insights[END_REF][START_REF] Amin Tootoonchian | Lockr: better privacy for social networks[END_REF][START_REF] Kalofonos | Mynet: A platform for secure p2p personal and social networking services[END_REF]). In all these solutions, users' data is not stored by a centralized OSN provider anymore. Such a DOSN can be considered as a good candidate for designing usage control mechanisms since it leverages on the collaboration of the users for any operation including data management and privacy protection. However, even in this distributed environment, usage control is dicult to achieve since a default mobile code protection mechanism does not exist and, hence, malicious users can manipulate the DOSN software running at their peer node. While the best solution to cope with such problems would be to provide a trusted hardware environment for each user, it is unfortunately a very expensive alternative.

In this paper we propose to exploit the advantage of the underlying peer-to-peer architecture in DOSNs in order to enforce the control of the usage of some specic content, namely pictures. The proposed mechanism relies on the collaboration of nodes and control is enforced thanks to the forwarding of any packets towards several hops before reaching the nal destination. The proposed usage control mechanism is designed over a recently proposed DOSN named as Safebook [START_REF] Antonio Cutillo | Safebook: a privacy preserving online social network leveraging on real-life trust[END_REF] which overcomes the problem of selshness by leveraging on the real life social trust relationships among users. The underlying multi-hop forwarding solution can directly be used as a basis for the usage control mechanism. Dierently from other P2P DOSNs, Safebook [START_REF] Antonio Cutillo | Safebook: a privacy preserving online social network leveraging on real-life trust[END_REF] overcomes the lack of cooperation among peers by leveraging on the real life social trust that is available as part of the very application.

The untraceability of the communications during look-up and data retrieval operations is assured thanks to an additional feature of Safebook in that the messages between a requester node and a friend's node that serves the request always route through several hops in order to hide a user's social links that are reected by the OSN graph. In a collaborative P2P DOSN such as Safebook, the multihop routing feature can provide the users with the usage control on their data.

In this paper we address the problem of usage control in Safebook focusing on pictures, as picture sharing is one of the most popular application oered by OSNs 6 , and also one of the most exploited by malicious users: the privacy concerns derived by the misuse of stolen or accessed pictures are overblown [START_REF] Antonio Cutillo | Security and Privacy in Online Social Networks[END_REF], ranging from identity theft [START_REF] Bilge | All your contacts are belong to us: automated identity theft attacks on social networks[END_REF] to defamation. We propose, to the best of our knowledge, the rst solution leveraging on peer collaboration guaranteeing data usage control on pictures in a P2P DOSN. Usage control [START_REF] Park | Towards usage control models: beyond traditional access control[END_REF] becomes a mandatory requirement given the very large number of users sharing dierent types of content. The ideal goal of guaranteeing the control over any type of data in any type of platform seems very dicult to achieve. We address this problem in a conned environment which is online social networks and in the context of picture sharing since, as previously mentioned, this application is one of the most popular applications for OSN users.

Current picture sharing tools in online social networks allow users to upload any picture.

Access rules to these pictures are dened by the owner of the picture that is the one who uploads it. This user has also some abilities to associate an area of the picture to a label: such a function, namely tag , can be used to inform other users about their presence in the picture. This solution, recently patented by Facebook 7 , seems unsatisfactory since users whose faces appear in pictures they do not own, are only informed about these pictures whenever they are tagged"; they can further untag their faces if needed. Unfortunately, if users are not tagged in the picture, they will never be aware of these pictures. We assume that each person whose face appears in any picture should decide whether her face in that picture should be disclosed or not and therefore she should dene the usage control policy regarding her own face.

C.2.2 Decentralized online social networks

As previously mentioned, online social networks severely suer from the centralized control on users' data: potential misuse of private data by the OSN provider can be considered as a major threat in terms of privacy. In order to avoid such a centralized control by service providers over user data, some solutions [START_REF] Antonio Cutillo | Safebook: a privacy preserving online social network leveraging on real-life trust[END_REF][START_REF] Gra | Lifesocial.kom: A secure and p2p-based solution for online social networks[END_REF][START_REF] Buchegger | PeerSoN: P2P Social Networking Early Experiences and Insights[END_REF][START_REF] Amin Tootoonchian | Lockr: better privacy for social networks[END_REF][START_REF] Kalofonos | Mynet: A platform for secure p2p personal and social networking services[END_REF] propose to design new applications based on a peer-to-peer architecture while leveraging real life social links to construct a network with trusted peers. The correct execution of any network/application operation depends on users' behavior. In order to achieve a good performance degree, these solutions dene a threshold for the number of misbehaving users and analyze the trade-o between security and performance based on this degree: for example, in some solutions a are also the users of the OSN application. The correct execution of dierent services depends on the trust relationships among nodes which are by denition deduced from real-life social links. Tn order to prevent a malicious node from acting as a legitimate user and hence having access to the information related to its relations and data, Safebook denes for each user a particular structure named as Matryoshkas ensuring end-to-end condentiality and providing distributed storage while preserving privacy. As illustrated in gure C.1,the Matryoshka of a user V, namely the core, is composed by several nodes organized in concentric shells. Nodes in the rst shell are the real life friends of V, and store her prole data to guarantee its availability. For this reason, nodes in the innermost shell are also called mirrors and serve requests if V is oine. If a requester U directly contacted one of V's mirrors, say A, U would be able to infer the friendship relation between V and A. To protect such an information, several multihop paths, chains of trusted friends, are built where every user's node selects among her own friends one or more next hops that are not yet part of the core's Matryoshka. A can then be seen as the root of a subtree with branching span 8 whose leaves, namely the entrypoints, lie in the outermost shell.

When a user U looks for V's data, her request is served by the entrypoints of V's Matryoshka and forwarded to the mirrors along these predened path. The answer follows the same path in the opposite direction. To protect the user's privacy expressed by the links in the Matryoshka, not even the core of a Matryoshka knows its entire composition. Apart from the list of the entrypoints, that is publicly available, the core knows the composition of the rst shell, and nothing about the intermediate ones. Nodes in the intermediate shells do not know one eachother and their understanding of the Matryoshka is limited to the previous and next hop of the path they belong to. Every user in Safebook can play dierent roles in dierent matryoshkas, but can be a core only for her own. The list of the entrypoints is public, and is stored by the second component of Safebook, the P2P system . By looking up for an hash value of a property of V, such ash her full name, the P2P system provides the list of the entrypoints of V's Matryoshka. FigureC.2 resumes the data lookup process in Safebook.

Every user in Safebook has thus an identity in the Matryoshka overlay and in the P2P one. Nodes in the P2P overlay are arranged as in Kademlia [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the xor metric[END_REF], but all the requests are served recursively in order to obfuscate the peer identity of the real requester. To prevent malicious users from creating multiple identities, identiers are granted and certied by

• She can also request to retrieve some pictures which belong to one of her friends: in this case, she rst needs to contact one of the entrypoints of the corresponding core in order to reach that particular user. Dedicated tasks have been dened for each of these three roles. Indeed, some tasks are required at the stage of user registration. For example, before publishing a picture, the client has to perform some picture obfuscation operation. Similarly, as a forwarder, the node has to perform some verication operations in order to check whether the picture it is forwarding is correctly protected" or not. All these tasks will be described in detail in the following section.

In the sequel of the paper, we use the following notation:

• L P denotes the regions in a picture P where a face appears;

• F P denotes the set of faces that appear in P ;

• f P V denotes user V's face in P ;

• f P V denotes V's face features which are used for face detection algorithms;

• φ + V , φ - V denotes user V's public and private keys, respectively;

• a message M signed using user V's private key φ - V is denoted by {M } S φ V ;

• E K {M } denotes the encryption of a message M encrypted with the symmetric key K.

C.3.3 Solution description User registration

Whenever a user V registers to Safebook and joins the network, she rst generates a pair of public and private keys φ - V , φ + V and sends the public key φ +

V and some samples of her face f V to an o-line trusted third party, namely the Feature Certication Service(FCS).

The FCS generates a certicate for V denoted by Cert f V , φ + V , which proves that the user with some face features f V owns the public key φ + V . This face feature certication phase is performed only once and the user does not need to contact the third party anymore. every f P i to a prole in V's contact list. If a face f P N is tagged with the prole of its owner N , N receives a copy of the original picture P 9 and can decide to publish it again on her own prole. Furthermore, the publisher also decides whether her own face can be made available for the network or not.

• Picture publication : Once all known faces f P ∈ F P are tagged, the client can execute its last component which is the face obfuscator: The face obfuscator transforms the face location areas L P to uninterpretable areas using any human or computer vision algorithm, thus generating an obfuscated picture OP . In our solution, the face obfuscator simply replaces every pixel in L P with a black one. The obfuscated picture can thus be seen as the original one with black shapes hiding every detected face. From the resulting obfuscated picture OP , an unambiguous picture identier I is computed as I P = h (OP ), where h (•) denotes a cryptographic hash function. V's face f P V is then signed together with the certicate Cert f V , φ + V , the identier I P , and an expiration time expT ime.

and OP are published. 10 • Picture advertisement : Once advertised by V about the presence of P , a user N can control the disclosure of her face f P N in that picture.

N may decide to make f P N publicly available, and publish OP together with the following signed message:

If N wishes to disclose this picture to a subset of its contact list only, she can encrypt the corresponding message with a symmetric key K previously distributed to the dedicated users. In this case, N will publish OP together with E K f P N , I P .

Picture publication and advertisement actions are illustrated in gures C.3 and C.4, respectively. containing V's publicly available face in that picture. When interacting with her friend N , U sends him a picture request containing some secret s, and receives a list of picture identiers I P j associated to pictures of N , which are either publicly available, or available to those contacts knowing the secret s, only. U then detects a match in I P between the identiers retrieved from V and N , and, as she previously received OP from V, she now asks for the missing information f P N . At the reception of piRes = E K f P N , I P , U can retrieve f P N since she already owns the appropriate decryption key K shared at the friendship establishment with N .

C.4 Evaluation

In this section, we evaluate the proposed mechanism with respect to dierent security issues such as eavesdropping, unauthorized access or collusion attacks. The impact of these attacks is evaluated based on existing social graphs: in September 2005, Facebook published anonymous social graphs of 5 universities in the United States 11 : California Institute of Technology (Caltech), Princeton University (Princeton), Georgetown University (Georgetown), University of North Carolina (UNC), Oklahoma University (Oklahoma). Each graph is represented by an adjacency matrix A whose non diagonal elements a ij are set to one if user ν i ∈ V is a friend of user ν j ∈ V , or zero otherwise. As each adjacency matrix is symmetric, the represented social graph is undirected.

Before presenting the evaluation results, we briey discuss about the feasibility of the proposed usage control mechanism.

Feasibility The feasibility of the proposed usage control mechanism depends on the robustness and speed of the face detection and verication procedures and on the feasibility of the DOSN at its basis, in our case Safebook.

Face detection [START_REF] Viola | Robust real-time face detection[END_REF] and face recognition [START_REF] Zhao | Face recognition: A literature survey[END_REF] procedures nowadays run in real time in common personal computers. Most of them [START_REF] Geng | Face recognition using sift features[END_REF][START_REF] Majumdar | Discriminative SIFT Features for Face Recognition[END_REF] make an intensive use of Scale Invariant Feature Transform (SIFT) [START_REF] David | Distinctive image features from scale-invariant keypoints[END_REF], a well known techique used to extract view-invariant representations of 2D objects. Recognition rates of these solutions raise up to 95% in well known databases such as the Olivetti Research Lab (ORL) one [START_REF] Geng | Face recognition using sift features[END_REF][START_REF] Majumdar | Discriminative SIFT Features for Face Recognition[END_REF]. Other techniques can also be used to improve the recognition rate [START_REF] Velardo | Face recognition with daisy descriptors[END_REF] at the expenses of a bigger face feature descriptor.

Unauthorized picture broadcast Even if malicious users manipulate the underlying software, broadcasting cleartext faces is prevented thanks to the collaborative multi-hop enforcement scheme. Indeed, it is assumed that there is at least one legitimate node which will execute the correct verication operations and the corresponding transformations in order to protect forwarded packets. Nevertheless, Safebook allows the forwarding of encrypted information to a subset of friends; a malicious member V may exploit this possibility to further send packets to all of its friends. However, V may need to set-up a virtual server and establish friendship relationships with all users to provide a picture P to all the users. This kind of attacks can be prevented by setting a maximum proper rate on friendship requests.

The malicious node would need to design some server advertisement mechanisms using additional out of band information exchange (outside the Safebook network). Furthermore, a malicious node V may also collude with one of her contacts C 1 , asking him to manipulate her Safebook client, in order to encrypt and republish an unauthorized picture P at her own prole. If recursively repeated, this hop-by-hop collusion through the social network graph may disclose P to all the contacts of every colluder C n . This attack again requires the manipulation of the OSN client itself and the impact of such an attack would only be important if the number of malicious users is very large. Fortunately, a massive scale collusion attack may end on the creation of an environment where the adversary may in turn be a victim for her own private data. The impact of collusion attacks is also analyzed further in this section. Protection against collusion As previously mentioned, the enforcement of the control on the usage of a given picture is based on the collaboration of users and the correct execution of the previously described operations. However, some users can still be malicious and avoid obfuscating some public pictures. To evaluate the impact of misbehavior and collusion, we have simulated the process of Matryoshka creation in which the chains leading from the mirrors to the corresponding entrypoints are built. We assume 30% of the nodes is online, identiers in her cache and may nd a match for I P . In this case, U can ask and obtain f P N , encrypted with a key K she received from N previously.

Invalid tagging and picture republishing A malicious user V may associate N 's face f P N with her own prole while tagging a picture P . Nevertheless, V will not manage to make f P N publicly available, unless the features of f P N are similar enough to that ones in Cert f V , φ + V . However, according to the Face Recognition Vendor Test (FRVT) of 2006 [START_REF] Phillips | Frvt 2006 and ice 2006 large-scale experimental results[END_REF] the false rejection rate for a false acceptance rate of 0.001 is 0.01 for state-of-the-art face recognition algorithms. A picture P can be accessed and republished by a third node Y that does not appear on it. Y can in fact store in her prole the obfuscated OP and any publicly available face Cert f X , φ + X , I P , f P X , expT ime S φ X for that picture.

Limitations

In order for the intermediate nodes to verify whether the rules are followed or not, the picture should of course not be encrypted (even if there is obfuscation). This security mechanism cannot be implemented over encrypted messages. However, if a malicious user would want to encrypt the picture in order to circumvent the usage control mechanism, only nodes with corresponding decryption keys can have access to these pictures. Such an attack would require an important communication overhead and its impact on the security would

In the future work, we plan to evaluate the scalability and the performance impact of the proposed solution, and integrate its features in the current Safebook prototype 12 . certain number of peers. The main novelty of the proposed mechanism is the fact that a credit is assigned to some peers using distributed hash tables, hence, peers can follow and control the history of operations with respect to this credit, only. Thanks to this new approach, a malicious node cannot easily keep track of all operations originating from a single node and the impact of cheating or similar attacks would be strongly reduced.

hand, even if there is a privacy leakage with respect to a single transaction, this will not a have an impact on the privacy of the user's overall actions. The association between the credit involved in the transaction and the peers that are responsible for the transaction itself is based on the pseudorandomness of the security functions used for the generation of the coins.

The rest of this paper is organized as follows: section D. On the other hand, credit based schemes [START_REF] Buttyán | Enforcing service availability in mobile ad-hoc wans[END_REF][START_REF] Zhong | Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks[END_REF][START_REF] Vishnumurthy | KARMA: A Secure Economic Framework for Peer-to-Peer Resource Sharing[END_REF][START_REF] Belenkiy | Making p2p accountable without losing privacy[END_REF] provide node collaboration by rewarding cooperating nodes with a certain amount of credits that they further can use for their own benet. Credits can be in the form of E-cash [START_REF] Chaum | Blind signatures for untraceable payments[END_REF][START_REF] Chaum | Blind signature system[END_REF] or a tradable good/service such as future cell phone call time.

D.2.2 Credit-based incentive mechanisms

Existing rewarding mechanisms encourage nodes to cooperate in performing the required operations (forwarding, data storage, etc.). These solutions consist of virtual currencies that nodes receive whenever they cooperate. Unfortunately, because such solutions suer from lack of fairness, they require the existence of a centralized online trusted third party mainly for credit management. Indeed, for example, in [START_REF] Zhong | Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks[END_REF], the rewarding mechanism named as Sprite requires an immediate reachability of the TTP dened as Credit Clearance Service (CCS). Such mechanisms also suer from the single point of failure problem as nodes must contact the CCS whenever they forward the message in order to receive their rewards.

174Appendix D PRICE: PRivacy preserving Incentives for Cooperation Enforcement Furthermore, this centralized entity has full control over these rewards and keeps track of any node's actions.

Distributed credit-based incentive mechanisms such as Karma [START_REF] Vishnumurthy | KARMA: A Secure Economic Framework for Peer-to-Peer Resource Sharing[END_REF] solve the single point of failure problem, since a set of peers in the DHT, namely the bank, stores a user's account.

Still, this set of notes can trace the user's actions.

D.2.3 Security and Privacy Challenges

As for any credit-based mechanism, a credit based incentive mechanism should prevent nodes from cheating. Therefore the proposed mechanism should exhibit the following security properties:

• unforgeability : a valid credit cannot be forged by any user;

• no double spending : credits resulting from duplication or copying of valid credits should be prevented or immediately detected;

• communication condentiality : any action taken under the incentive mechanism should not leak information regarding the underlying service application;

• transaction untraceability : a selsh or malicious user should not be able to monitor any legitimate's users account.

D.3 Solution Overview

In order to cope with the previously described security and privacy challenges we propose PRICE, a credit-based incentive mechanism whereby, as opposed to existing centralized solutions, the management of the credits, dened as coins, is distributed among several peers in the network. While this distributed mechanism allows a better robustness of the system and prevents the problem of single point of failure, the privacy challenge becomes even more important since many peers can be aware of others' activities. The proposed management of coins hence prevents such a possible leakage by assigning dierent sets of peers for each coin rather than dening one responsible per node's account (activities).

The peer assignment follows the inherent nature of P2P by taking advantage of distributed hash tables (DHT). In the following sections, the proposed mechanism is summarized and illustrated with a scenario.

Criticisms against the incentive mechanisms in BitTorrent assert that its eectiveness is largely due to the altruistic behavior of a small number of altruistic nodes [START_REF] Piatek | Do incentives build robustness in bit torrent[END_REF] and solutions like in [START_REF] Karthik Tamilman | Swift: A system with incentives for trading[END_REF] have been proposed to improve the overall system performance.

In Swift [START_REF] Karthik Tamilman | Swift: A system with incentives for trading[END_REF], peers exchanging le chunks are denoted as traders and employ a default trading strategy that is either good for them and for the network itself. Free riders are the most penalized in case of insucient upload capacity to satisfy demand. Authors consider three strategies for traders and classify them accordingly: paranoid, one-time risk-taking, and perioding risk-taking. Paranoid traders are reciprocative players waiting for the reception of a valid chunk before oering to send an equal amount back, one-time risk-takers can oer free chunks to a peer never encountered before to encourage trading with the chance of receiving nothing in return, while periodic risk-takers give out free chunks periodically.

Authors show that peers taking risks receive the most benet in return, and deviating from the proposed default strategy of periodic risk-taking provides little or no advantage. Swift has then been added to the ocial BitTorrent client and named as TradeTorrent 4 .

Finally, authors in [START_REF] Belenkiy | Making p2p accountable without losing privacy[END_REF] drew inspiration from BitTorrent to propose a P2P content distribution system based on endorsed e-cash [START_REF] Camenisch | Endorsed e-cash[END_REF] to provide accountability while preserving privacy in P2P systems. In such an approach, users can exchange les if they know the correct hashes on those les. In endorsed e-cash, users withdraw e-coins from a central bank maintaining all participants'accounts and spend them for digital content with a fair exchange protocol. In case a user gets paid, he must deposit e-coins in the bank before spending them again. A Trusted Third Party (TTP), namely the arbiter, is responsible for resolving disputes. Authors modify the endorsed e-cash protocol in [START_REF] Camenisch | Endorsed e-cash[END_REF] to allow the arbiter for resolving conicts by examining a much shorter amount of data. Sybyl node creation is discouraged thanks to a mechanism in which newcomers are invited by friends and receive an initial credit from them.

PRICE extends the security an privacy features oered in [START_REF] Vishnumurthy | KARMA: A Secure Economic Framework for Peer-to-Peer Resource Sharing[END_REF][START_REF] Karthik Tamilman | Swift: A system with incentives for trading[END_REF][START_REF] Belenkiy | Making p2p accountable without losing privacy[END_REF] by revisiting the concept of bank account. As a main novelty of PRICE, in fact, no entity in the system can derive the total amount of credit a node currently holds, as accounts are made available for coins rather than for users. As an important consequence, there is no entity an attacker can target to discover one or more victim's account, and derive, for instance, its participation in the network. 4 http://mnl.cs.stonybrook.edu/project/tradetorrent/