Building on the popularity of online social networks (OSNs) such as Facebook, social content-sharing applications allow users to form communities around shared interests. Millions of users worldwide use them to share recommendations on everything from music and books to resources on the web. However, their increasing popularity is beginning to attract the attention of malicious attackers. As social network credentials become valued targets of phishing attacks and social worms, attackers look to leverage compromised accounts for further financial gain.

In this paper, we analyze the state of privacy protection in social content-sharing applications, describe effective privacy attacks against today's social networks, and propose anonymization techniques to protect users. We show that simple protection mechanisms such as anonymizing shared data can still leave users open to social intersection attacks, where a small number of compromised users can identify the originators of shared content. Modeling this as a graph anonymization problem, we propose to provide users with k-anonymity privacy guarantees by augmenting the social graph with "latent edges." We identify StarClique, a locally minimal graph structure required for users to attain $k$-anonymity, where at worst, a user is identified as one of k possible contributors of a data object. We prove the correctness of our approach using analysis. Finally, using experiments driven by traces from the del.icio.us social bookmark site, we demonstrate the practicality and effectiveness of our approach on real-world systems.