DistSD: Thwarting Stalking Attacks in Social Discovery via Posterior Screening

TL;DR

With the rise of "nearby" features in apps like Tinder and WeChat, location privacy has become a critical concern. DistSD introduces a paradigm shift: instead of hiding your location from the server, your phone "screens" who gets to know you're nearby. By selectively choosing which "seeking users" to notify, it ensures your location can never be narrowed down to a dangerous precision, effectively defeating trilateration attacks.

The "Over-share" Dilemma: Why Current Apps Fail

Most social discovery apps work on a simple logic: you share your location with the server, and the server tells everyone within a certain radius that you are there. This creates a massive security loophole. A malicious user (or a group of colluding users) can use multiple accounts to map out exactly where the "intersection" of their proximity regions (PRs) lies.

If three people see you are "nearby," they can mathematically "pinpoint" you within a tiny gray area. In real-world tests, researchers have used these "Over-share Discovery Attacks" to locate individuals within 5 meters.

Fig 1: How multiple seeking users can intersect proximity regions to pinpoint a discovered user.

Methodology: The Posterior Screening Logic

The core insight of DistSD (Distance-based Social Discovery) is that a discovered user should not be discovered passively. Instead, the mobile device performs a Posterior Screening.

1. Index Downloading: The client downloads an index of "seeking users" nearby (HGrid or DGrid).
2. Safety Calculation: The device calculates the intersection of PRs for all potential seekers.
3. Selective Notification: If notifying everyone makes the "uncertainty area" too small (violating the user's minu requirement), the algorithm selects a maximal subset of users to notify so that privacy is preserved while maximizing social reach (QoS).

FBuck vs. LCF2

The paper proposes two algorithms to solve the NP-hard problem of finding the optimal safe group of users:

• FBuck (Global): Uses a sorting-based approach with four buckets (Left, Right, Bottom, Top boundaries) to prune users. It is highly efficient for servers but requires downloading more data.
• LCF2 (Local): A clever approach using DGrid (Departure-cell Grid). It only downloads data for specific cells and "extends" user rectangles locally. This drastically reduces the communication cost—a vital feature for mobile battery life and data plans.

Fig 2: The DGrid structure allows LCF2 to manage local "m-rects" efficiently without global overhead.

Experiments & Performance

The researchers tested DistSD using 20 million check-ins from Foursquare.

• Efficiency: While a baseline "Brute Force" or greedy algorithm slows down exponentially as more users join the network, LCF2 maintains near-constant query times (around 0.03s), making it perfect for real-time mobile use.
• Privacy vs. Utility: Even with strict privacy requirements (e.g., a 200m uncertainty zone), DistSD managed to notify the vast majority of nearby users, sacrificing less than 10% of social "discoverability" to guarantee safety.

Fig 3: LCF2 shows superior query efficiency as the privacy requirement (minu) increases.

Critical Insight & Conclusion

The brilliance of DistSD lies in the "Posterior" part. Traditional Priori Protection (obfuscating location before sending it) often ruins the service quality because the server can't calculate accurate distances. By allowing the client to filter results, DistSD allows the Service Provider (SP) to remain "semi-honest" and curious without actually gaining the ability to stalk the user.

Future Outlook: While DistSD is robust, it assumes a semi-honest server. In fully malicious environments, combining this posterior screening with Differential Privacy or Trusted Execution Environments (TEEs) could represent the "Holy Grail" of geo-social privacy.