Functional Pseudonyms: Securing the "Where" and "Who" in Mobile Social Networks

TL;DR

Researchers have developed a new location-sharing framework that uses Lagrange Polynomials to create "functional pseudonyms." Unlike current LBS apps that know who you are and who your friends are, this system allows you to broadcast your location such that only your intended friends can decrypt it. It eliminates the need for trusted servers, pre-shared passwords, or the requirement to meet in person to "sync" keys.

The Privacy Dilemma: The Server Knows Too Much

In most Geosocial networks (like Foursquare or Find My Friends), the service provider is a "silent stalker." Even if the server is "honest-but-curious," it possesses enough metadata to link your identity to your location and, more dangerously, map out your entire social circle (Spatio-Temporal Relation Privacy).

Previous solutions were often impractical:

• SMILE: Required you to have met your friend in person at least once to exchange "encounter keys."
• MobiShare: Required pre-established secrets between every pair of friends, leading to a "key management nightmare" as your friend list grows.

The Core Innovation: Functional Pseudonyms

The genius of this paper lies in the Functional Pseudonym. Instead of a static ID, the user generates a pseudonym that acts like a cryptographic lock.

1. The Mathematical Intuition

The system uses the Lagrange Interpolating Polynomial. Imagine a polynomial $f(x)$ of degree $au-1$. To "solve" or reconstruct this polynomial, you need a specific number of points.

The sender takes the public IDs of their friends and treats them as coordinates on this polynomial. They then compute a secret $\chi =f(0)$.

• The Pseudonym is a package: $\{g^{r\cdot extpart},g^r,exthash(extID||extLoc)\cdot g^{r\cdot \chi }\}$.
• To the server, this looks like random noise (due to the Decisional Diffie-Hellman problem).

2. How Friends "Unlock" the Identity

When a friend receives the list of pseudonyms from the server, they use their own Secret Identity (SI) to perform Lagrange interpolation. If they were "included" in the polynomial's creation, the math resolves perfectly, revealing the sender's identity. If they aren't on the list, the result is simply mathematical gibberish.

Architecture and Workflow

The process follows four distinct stages:

1. Setup: Generation of global parameters and public/private key pairs.
2. Identity Registry: Users register with a Public Identity (PI) that functions as an asymmetric key.
3. Pseudonym Generation: The sender "merges" their friends' PIs into a single value using the polynomial.
4. Location Multicasting: The server broadcasts these pairs. Users "check" the pairs locally on their phones.

Efficiency vs. Prior Art

A critical advantage of this method is efficiency. In MobiShare, if you have 100 friends, you might have to send 100 different request messages. In this scheme, you send one request.

While the "Friends Confirmation" step on the receiver's side scales with the number of people currently in the area ($n$), for most mobile users, this is a much lighter load than managing hundreds of individual encrypted connections.

Critical Insight & Conclusion

The implementation of Lagrange-based cryptography here effectively shifts the burden of trust from a central authority to the mathematical properties of the protocol itself.

Takeaway: This paper proves that we don't need to sacrifice our social graph to enjoy location-based convenience. However, the system's performance does depend on the density of users in a given area. Future work could look into optimizing the "checking" phase for high-density urban environments where $n$ (the number of nearby users) might be very large.