This position paper first summarizes work done by the first author on location privacy and differential privacy. These techniques will help to solve privacy problems in decentralized mobile social networks, which is the main theme of his PhD research. The paper then briefly reviews the state-of-the-art in privacy-preservation of social graphs and clarifies the lack of attention to graph sharing in decentralized setting. Finally, some initial ideas on how to realize such soft decentralized access controls are described.
The prevalent architectures of social networks mainly rely on the central
repository of user data, so users must trade their privacy for free service. The
centralized setting makes offline data processing operations (e.g. publishing a anonymized
version of a social graph) easier and attracts a lot of interest in the security
community. Parallel to this line of research, there also exists another line dedicated
to decentralized alternatives 1 in which users manage their own data and access
policies. Shifting from the free-service (centralized) paradigm to the user-centric
(decentralized) one should, in principle, increase user confidence or trust, but
understanding how to properly share information in this architecture remains a
huge challenge in user privacy preservation. For example, early efforts such as
Diaspora 2 and Persona [
As a specific sub-problem, anonymizing social network data is more
challenging [
The two following subsections summarize two main contributions of the first author in his master course. In each subsection, an anticipated application of the corresponding technique will be presented. 1.2
Anonymization methods (e.g. k-anonymity) are extensively used in location
privacy with a typical configuration of a anonymizer between the LBS server and
mobile users. By cloaking user locations into bigger sets satisfying certain
thresholds, users’ true locations are concealed. Privacy in this setting means ”privacy
by blending yourself in a crowd”. MeshCloak [
Our technique and the anonymization methods applied to the publication of
whole social graphs [
The second work [
With strong theoretical foundations, differential privacy is a promising tool
for formulating and solving certain privacy issues in both centralized/decentralized
and offline/online settings for data publication within social networks [
Social graphs considered in the state-of-the-art vary in a wide range, from unlabeled, simple, undirected ones to data-rich ones. This section reviews a few typical privacy-preserving techniques in centralized and decentralized settings. 2.1
There is a large body of work focusing on how to share social graphs owned by organizations without revealing the identities or links between users involved. The existing anonymization methods fall into four main categories. The methods of first category provide k-anonymity by deterministic edge additions or deletions, assuming attacker’s background knowledge regarding some property of its target node. The second category includes random additions, deletions and switches of edges to prevent the reidentification of nodes or edges. The methods falling in the third category assign probabilities to edges to add uncertainty to the original graph. Finally, the fourth class of techniques cluster together nodes into supernodes of size at least k. Note that the last two classes of schemes induce possible world models, i.e., we can retrieve graph samples that are consistent with the anonymized output graph. 2.2
Decentralized social networks consist of federated and distributed models. In
distributed setting, the social graph is split between many holders, and even
between users in which each node only knows his friends. To privately aggregate
the global graph, we need collaborative privacy-preserving sharing mechanisms.
Unfortunately, not much attention has been given to this topic except in a few
works, for example [
As we aim at mechanisms for decentralized social networks, the access control
on network data is of importance. One of our concerns is how to devise “soft”
access policies via collaborative anonymization. An anticipated scenario, presented
in the next section, is that given different trust levels between a user and his
friends, the user adds different noises to his true friend list before transmitting
them to his neighbors.
At the early stage of the thesis, we survey the state-of-the-art of privacy-preserving
methods in decentralized social networks as well as in the centralized ones.
Privacy protection techniques can be classified roughly as cryptography-based
and anonymization-based. Cryptographic primitives support a wide range of
OSN-related operations like encryption to a group, group key revocation with
attribute-based encryption (ABE) [
Parallel to the success of centralized social network services based on the freemium model, decentralized alternatives have also been proposed as a response from the research community in order to better address privacy concerns of users. Following this direction, our methodology is to see first the big picture of decentralized social networks by studying their challenges and opportunities. We then aim to formalize problems of moderate size that can be stated and solved efficiently using both tools in cryptography and anonymization. One such in-focus problem is the collaborative and autonomous relationship sharing in cloud-based peerto-peer architectures.