I study two privacy-preserving social network graphs to dis- close the types of relationships of connecting edges and provide flexible multigrained access control. To create such graphs, my schemes employ the concept of secretaries and types of relationships. It is significantly more efficient than those that using expensive cryptographic primitives. I also show how these schemes can be used for multigrained access control with various options. In addition, I describe how much these schemes are resilient to infer the types of connecting edges.
In this paper we introduce a novel scheme for key management in social networks that is a first step towards the creation of a private social network. A social network graph (i.e., the graph of friendship relationships) is private and social networks are often used to share content, which may be private, amongst its users. In the status quo, the social networking server has access to both this graph and to all of the content, effectively requiring that it is a trusted third party. The goal of this paper is to produce a mechanism through which users can control how their content is shared with other users, without relying on a trusted third party to manage the social network graph and the users' data. The specific access control model considered here is that users will specify access policies based on distance in the social network; for example some content is visible to friends only, while other content is visible to friends of friends, etc. This access control is enforced via key management. That is for each user, there is a key that only friends should be able to derive, there is a key that both friends of the user and friends of friends can derive, etc. The proposed scheme enjoys the following properties: i) the scheme is asynchronous in that it does not require users to be online at the same time, ii) the scheme provides key indistinguishability (that is if a user is not allowed to derive a key according to the access policy, then that key is indistinguishable from a random value), iii) the scheme is efficient in terms of server storage and key derivation time, and iv) the scheme is collusion resistant.