Differential Privacy at Snapchat

15 Dec 2022

Problem

A social app wants to use friendships and friends' place visits to recommend people and places. These signals also leak. A viewer who sees a recommendation, a count or a rank can work backwards to who is friends with whom, or where a friend has been. Snapchat does not show friend lists, so such leaks would break its own privacy promise.

Example from the article: a new user Bob has one friend, Alice. If Eve is recommended to Bob and no other signal explains it, Bob concludes that Eve and Alice are friends.

Solution in brief

Add calibrated random noise before the signal is consumed. For friend recommendations, randomly add and drop edges of the social graph first, then recommend. For counts, use only the noisy value. The viewer cannot tell whether a result reflects a real friendship or visit or the noise.

Questions this case answers
  • How to use signals derived from other users' private relationships or actions in a ranking or a displayed count so that a curious viewer cannot reverse-engineer any single person's data
  • How to recommend friends from the social graph without letting a user infer who his friends are friends with?
  • How to show a mutual-friend count on a recommendation without revealing which friendships exist?
  • How to use friends' place visits to rank place recommendations without exposing any single friend's visit?

Tools and methods

  • Differential privacy — a guarantee that the output looks nearly the same whether or not one person's data was used.
  • Graph perturbation with stochastic traversal — creates and removes edges before friend recommendations are generated.
  • Noisy counts — mutual-friend counts and per-place friend-visit counts get random noise before display or ranking.
  • User controls and visit expiration — location-sharing settings and expiring visits, used together with the noise.
Continue reading — it's free

Google or a one-time email code. No password.