PaperlayerView exact revision on arXiv

Source-linked AI summary

Privacy in geo-social networks: proximity notification with untrusted service providers and curious buddies

Sergio Mascetti, Dario Freni, Claudio Bettini, X. Sean Wang, Sushil Jajodia

arXiv:1007.0408v2cs.DBcs.CR

TL;DR

Proximity services must notify users about nearby buddies without exposing precise locations to an untrusted service provider or beyond users’ chosen precision to buddies. The paper develops two protocols, formally analyzes and experimentally evaluates them, and finds complete service-provider protection with controllable buddy privacy and differing cost trade-offs. The main scope boundary is collusion: service-provider privacy is not guaranteed when the provider obtains a user’s secret key, and differentiated buddy granularities can enable collusion attacks.

  • Problem

    Proximity services repeatedly release location data, creating a need to protect users from an untrusted service provider while controlling the precision disclosed to buddies.

  • Method

    The paper formalizes privacy preferences and develops two centralized protocols, C-Hide&Seek and C-Hide&Hash, with theoretical analysis, experiments, and implementation.

  • Results

    Both protocols provide complete protection with respect to the service provider and controllable buddy privacy; C-Hide&Hash offers stronger buddy privacy at higher communication and computation cost.

  • Takeaways & Limitations

    The protocols preserve service precision while trading privacy guarantees against system costs, with C-Hide&Seek having efficiency comparable to a no-privacy solution.

  • Takeaways & Limitations

    If the service provider colludes with a buddy who shares the user’s secret key, service-provider privacy is not guaranteed; assigning different buddy granularities can also expose collusion attacks.

Abstract

from arXiv · show

A major feature of the emerging geo-social networks is the ability to notify a user when one of his friends (also called buddies) happens to be geographically in proximity with the user. This proximity service is usually offered by the network itself or by a third party service provider (SP) using location data acquired from the users. This paper provides a rigorous theoretical and experimental analysis of the existing solutions for the location privacy problem in proximity services. This is a serious problem for users who do not trust the SP to handle their location data, and would only like to release their location information in a generalized form to participating buddies. The paper presents two new protocols providing complete privacy with respect to the SP, and controllable privacy with respect to the buddies. The analytical and experimental analysis of the protocols takes into account privacy, service precision, and computation and communication costs, showing the superiority of the new protocols compared to those appeared in the literature to date. The proposed protocols have also been tested in a full system implementation of the proximity service.

1 Introduction

Geo-social networks use participants’ geographic positions to support services such as proximity alerts between known buddies. Existing proximity services centrally collect location updates and compute range queries through a service provider.

  • 1 Introduction: Geo-social networks combine social connections with participants’ geographic positions to enable location-based information services.Their growth is supported by GPS-enabled mobile devices and access to social networks.
  • 1 Introduction: A proximity service alerts users when a buddy is nearby and may support map visualization or communication.Such services are also called friend finders.
  • 1 Introduction: Proximity detection is a moving-user range query over moving entities, using a user-selected distance threshold.The service provider computes proximity from location updates acquired from mobile devices.

Privacy threats in LBS

Repeatedly releasing users’ locations in proximity services creates serious privacy concerns, but location plays competing roles in location-based services. The literature therefore distinguishes protecting location from preserving identity anonymity.

  • Privacy threats in LBS: Repeated release of where users are at particular times creates severe privacy concerns in proximity services.The broader location-based-services literature lacks consensus on defining, measuring, and alleviating this problem.
  • Privacy threats in LBS: Location can itself be sensitive or enable inferences about sensitive attributes such as religious belief.For example, presence at a synagogue during an important ceremony may reveal information about a user.
  • Privacy threats in LBS: Location privacy protects a user’s precise location from untrusted parties, whereas identity privacy protects anonymity against location-based re-identification.These are distinct privacy notions in the location-based-services literature.

The location privacy problem in proximity services

The paper studies location privacy in proximity services where both the service provider and buddies may be adversaries. It formalizes privacy preferences, proposes and analyzes two protocols, and evaluates their privacy, costs, and service quality.

  • The location privacy problem in proximity services: The target setting assumes users know their buddies’ identities, so the paper addresses location privacy rather than buddy anonymity.The service provider is untrusted, while users control the precision of location released to buddies.
  • The location privacy problem in proximity services: Users specify privacy preferences as the finest spatial uncertainty region that may be disclosed to buddies.The paper requires the service provider to acquire no location information and lets users control buddy-visible precision.
  • The location privacy problem in proximity services: Existing services provide no protection against the service provider beyond legal policies and offer limited control over buddy-visible location precision.Prior academic solutions are identified as having limitations.
  • The location privacy problem in proximity services: The paper’s contributions are a comprehensive study of location privacy in proximity services and two formally analyzed and empirically tested protocols.The study explicitly includes privacy control with respect to buddies.
  • The location privacy problem in proximity services: The protocols are designed for centralized operation, with formal properties and experimental results covering privacy, computation, communication, and service precision.The paper also reports a system implementation and positions the centralized design as suitable for reducing client costs.
  • The location privacy problem in proximity services: C-Hide&Seek provides complete service-provider protection and buddy privacy, while C-Hide&Hash offers stronger buddy privacy at higher communication and computation cost.Both protocols have the same service precision; C-Hide&Seek has efficiency comparable to a no-privacy solution.

2 Related Work

Related work spans location, identity, and combined privacy techniques, alongside proximity-specific protocols. Existing approaches trade privacy, precision, scalability, or service-provider exposure in ways addressed by this paper’s protocols.

  • 2 Related Work: Identity-privacy approaches such as k-anonymity spatially cloak a request within a region containing at least k−1 other potential requesters.Combined privacy approaches include Casper and related algorithms, but Casper is insecure when the adversary knows the generalization technique.
  • 2 Related Work: Location-privacy techniques include fake locations, incremental retrieval from fake positions, and generalized regions sent instead of precise locations.Fake-request methods can increase system costs, while generalized regions can encode privacy preferences in advance.
  • 2 Related Work: The paper adopts generalized regions for buddy privacy and claims that buddies learn only that a user lies inside the specified region.This approach addresses location privacy rather than identity anonymity.
  • 2 Related Work: Encryption-based private-information-retrieval methods hide locations from the service provider but may provide the protection of generalizing location to the entire world.Some are designed for nearest-neighbor queries, while others address static range queries rather than proximity detection.
  • 2 Related Work: Proximity-specific work includes decentralized protocols, hierarchical grids, and transformed-location schemes with differing precision, scalability, and service-provider leakage.Buddy-to-buddy protocols can guarantee service-provider privacy but may require communication with every buddy after each movement.
  • 2 Related Work: Some prior proximity solutions reveal distance information to the service provider, which the paper’s adversary model treats as a potential privacy violation.The proposed solutions instead claim not to reveal inter-user distances to the service provider.

3 Problem formalization

The paper formalizes contact-list-based proximity services, defining users’ location-privacy requirements, adversaries, and privacy preservation through unchanged location distributions within user-specified regions.

  • 3.1 The proximity service: The service determines for each predetermined buddy whether the distance between reported locations is within the requesting user’s threshold.The proximity relation may be asymmetric because users can specify different thresholds.
  • 3.1 The proximity service: Without privacy concerns, the service provider stores users’ latest locations and thresholds to evaluate proximity requests.This baseline requires users to send location updates to the service provider.
  • 3.2 Privacy concerns and privacy requirements: Location privacy concerns uncontrolled disclosure of a user’s location, while exchanged information should also be protected from eavesdroppers.Users may want the service provider to learn as little as possible and buddies not to learn their exact positions.
  • 3.2 Privacy concerns and privacy requirements: A minimal uncertainty region is the geographic area an adversary may know contains the user without learning the user’s position within that area.Users specify these regions through spatial granularities that partition the domain into non-overlapping granules.
  • 3.2 Privacy concerns and privacy requirements: Each granule of a user’s chosen spatial granularity represents a minimal uncertainty region, ranging from pixel-level disclosure to the entire spatial domain.The bottom granularity models no protection, whereas the top granularity provides the entire domain as the uncertainty region.
  • 3.3 Adversary model and privacy preservation: The adversary models cover the service provider, buddies, colluding buddies, compromised systems, and eavesdroppers observing exchanged messages.The paper’s techniques guarantee users’ requirements against the service provider, buddies, and sets of colluding buddies; collusion with the service provider is discussed separately.
  • 3.3 Adversary model and privacy preservation: Adversaries are assumed to know the protocol, users’ spatial granularities, and prior location distributions, while differing in received messages and decryption ability.The location domain is modeled as a discrete set of pixels, with prior and posterior distributions defined over possible locations.
  • 3.3 Adversary model and privacy preservation: Privacy is preserved when protocol messages do not change the location distribution within the user’s specified granule, given prior knowledge.A privacy violation occurs when messages reveal more information about the user’s position within that granule than the requirement allows.

4 Defense techniques

The paper presents C-Hide&Seek and C-Hide&Hash, two protocols designed to protect users from both service providers and buddies. Their defenses combine location-independent update timing, single-use keyed protection, and proximity-request procedures that trade disclosure against cost.

  • C-Hide&Seek and C-Hide&Hash provide privacy protection for users against both the service provider and their buddies.
  • A naive boundary-triggered update reveals that a user is near a granule border, so updates are instead issued once per synchronized interval independently of location.
  • Each update protects the current granule index using encryption in C-Hide&Seek or keyed hashing in C-Hide&Hash, with a fresh keystream key for every interval.
  • C-Hide&Seek: C-Hide&Seek lets a requester decrypt each buddy’s last encrypted granule and determine proximity using the buddy’s disclosed uncertainty region.
  • C-Hide&Seek: C-Hide&Seek completely hides locations from the service provider but reveals the maximum tolerable location information to a requesting buddy.
  • C-Hide&Hash: C-Hide&Hash uses keyed hashes and set-inclusion processing to avoid revealing which candidate granule matched, providing higher privacy at higher computation and communication cost.
  • The update policy also addresses maximum-velocity knowledge by randomizing reported adjacent granules until a time threshold elapses, preserving uncertainty about the crossing time.

5 Analysis of the protocols

The analysis evaluates whether the protocols meet their privacy goals while also considering uncertainty, service precision, and system cost. It uses formal proofs and empirical measurements to characterize the trade-offs among these dimensions.

  • The protocols are formally proved to satisfy the paper’s privacy requirements under the considered adversary models.
  • Privacy is evaluated through the size of the uncertainty region, while service quality is evaluated through false-positive and false-negative rates.
  • The evaluation also measures overall computation and communication costs, with particular attention to client-side costs.

5.1 Privacy

The protocols provide formal privacy guarantees against the service provider and buddies, including under buddy collusion, while collusion between the service provider and buddies preserves only the weaker party’s guarantee.

  • C-Hide&Seek: C-Hide&Seek prevents the service provider from decrypting the user’s location granule and prevents buddies from learning more than that granule.A proximity request sends no location information to buddies, while a location update reveals only the granule at the selected granularity.
  • Formal privacy basis: C-Hide&Seek’s message-sending indicator is probabilistically independent of the user’s location under any a-priori knowledge.The analysis assumes discrete time and location and uses perfect secrecy with one-use keys.
  • C-Hide&Seek: Under the stated adversary model, C-Hide&Seek satisfies the user’s privacy requirement with respect to the service provider.The result assumes the service provider has no background knowledge beyond the protocol, a-priori distribution, and granularities.
  • C-Hide&Hash: C-Hide&Hash reveals only a fixed set cardinality to the service provider, so it acquires no location or distance information about the users.The cardinality is SMAX, determined by δA and GB rather than actual locations.
  • C-Hide&Hash: C-Hide&Hash gives buddies a coarser result than C-Hide&Seek, revealing only whether the user’s granule belongs to a supplied set, and still satisfies the buddy privacy requirement.On average, it provides more buddy privacy than C-Hide&Seek, but at extra cost.
  • Colluding adversaries: When buddies collude, intersecting their possible-location sets still contains the user’s privacy granule; service-provider–buddy collusion preserves only the weaker guarantee.If the service provider learns the secret key, it can learn the granule but not the user’s position within it.

5.2 Service precision

The protocols generalize locations to regions and support different proximity semantics, trading false positives against false negatives and precision against recall. The maximum-distance semantic avoids false positives, while the minimum-distance semantic can improve recall but may report users who are not actually nearby.

  • Region-based semantics: Proximity is evaluated between a known point and a generalized region rather than between two exact locations.The region-based representation hides the user’s exact position within the area.
  • Minimum-distance semantics: The minimum-distance semantic reports proximity when any point in the region may satisfy the threshold, including uncertainty cases.Its false positives can be undesirable, such as contacting a buddy who is elsewhere in the same reported city.
  • Alternative semantics: The maximum-distance semantic reports proximity only when all possible positions satisfy the threshold, eliminating false positives but producing false negatives.The mostly-in-proximity semantic reduces false results by requiring at least half the area to be in proximity, but still has both error types.
  • Semantic flexibility: The semantics can be changed client-side without modifying the server or other peers, allowing selection through the user interface.This flexibility supports different application preferences without deployment-wide changes.

5.3 Size of uncertainty regions

The protocols guarantee buddy privacy, while C-Hide&Hash can provide additional privacy by making a buddy’s possible location span multiple granules.

  • Both proposed protocols are proven to guarantee the privacy requirement with respect to buddies.
  • C-Hide&Hash gives additional privacy by revealing only whether a buddy lies within a set of proximity granules, not which granule.If the buddy is outside the set, the uncertainty region is the entire domain minus that set; if inside, it is the region identified by the set.
  • When δ is 5 times larger than l, the uncertainty region is 60 or 88 times larger than the minimum requirement under maximum-distance or minimum-distance semantics, respectively.

5.4 System costs

The proposed protocols have analytically characterized client, service-provider, computation, and communication costs, with several operations remaining constant-time or constant-size.

  • The analytical cost evaluation is complemented by experimental results in Section 7.
  • A proximity request has client-side computation linear in the number of buddies, because the client decrypts an index and computes its granule distance for each buddy.
  • Location updates have constant computational complexity and constant communication cost for C-Hide&Hash.The client applies hashing in constant time, while the service provider only stores the received information and the exchanged message is a hashed value.
  • For C-Hide&Hash, proximity-request computation and communication depend on the number of encrypted and hashed granule indexes, bounded by sMax for each buddy.The exchanged messages contain encrypted sets of hashed values whose size is linear in the number of buddies times the maximum sMax.

6 System implementation

The authors implemented the proposed proximity protocols in a complete instant-messaging system, extending XMPP with server and client components.

  • The implementation couples proximity notification with typical instant-messaging functionality and evolves the earlier Hide&Crypt system architecture.
  • The system extends XMPP with custom XML messages and implements the service provider as a pluggable XMPP component.
  • Clients include a multiplatform web application and an iOS mobile application implementing the proximity protocols and location-based notifications.
  • Key management uses public-key cryptography to distribute each user’s shared key securely to individual buddies.
  • Key distribution is linear in the number of buddies but occurs mainly at subscription or buddy-removal events, which are described as sporadic.

7 Experimental results

Experiments evaluate privacy-preserving proximity protocols through service precision, recall, accuracy, computation, and communication costs. The results show strong privacy and practical performance, with quality depending on granularity and update intervals.

  • Quality of service: The evaluation measures two approximation sources: granularity approximation and time-dependent approximation from using previously reported buddy locations.
  • Quality of service: C-Hide&Seek and C-Hide&Hash achieve significantly better precision than Pierre and FriendLocator when the privacy granularity cells are small.Under the controlled experiment excluding time-dependent effects, the comparison protocols have precision below 0.4, while the proposed protocols improve as cell size decreases.
  • Quality of service: When a cell edge is 200m, C-Hide&Seek and C-Hide&Hash achieve precision 0.59 and 0.57, respectively, under the combined approximation analysis.
  • Quality of service: The recall of C-Hide&Seek is always above 0.95, while C-Hide&Hash is always above 0.9.Recall increases for coarser granularities because fewer incorrect “not in proximity” answers occur.
  • System costs: A location update takes about half a millisecond on the client for both proposed protocols.
  • System costs: C-Hide&Hash requires about 40ms to issue a proximity request for 100 buddies on the tested mobile device.Its computation time is higher than C-Hide&Seek, especially as the number of buddies grows.
  • System costs: C-Hide&Hash takes less than 0.4ms for a single-buddy proximity request on a mobile device, making it more than 800 times more efficient than Pierre in the reported comparison.
  • System costs: Centralized protocols exchange only two messages per proximity request, independent of the number of buddies, while total exchanged data grows linearly with that number.

8 Discussion and conclusions

The paper concludes that its two protocols preserve location privacy while reducing costs and retaining service quality, but their applicability depends on shared keys and specific privacy assumptions. It also identifies extensions involving time-dependent knowledge, collusion, and anonymity.

  • Conclusions: The protocols prevent the service provider from acquiring new location information, even when it has a-priori probabilistic knowledge of users’ locations.The formal model and proofs cover arbitrary a-priori probabilistic location knowledge.
  • Conclusions: Users retain full control over the location information disclosed to buddies through configurable privacy preferences.The protocols use spatial uncertainty regions to specify the finest precision disclosed to buddies.
  • Conclusions: The centralized protocols reduce computation and communication costs relative to decentralized solutions while maintaining low impact on service quality.Their centralized architecture also supports current business models and reduces client-side costs.
  • Limitations: The centralized solutions require users to share keys with buddies, making them less suitable for query-driven services.The paper points to decentralized versions as more suitable for that setting.
  • Open directions: Time-dependent location knowledge remains an open adversary-model extension, and it is unclear whether protocol modifications would be needed for privacy proofs.The current analysis addresses atemporal a-priori location knowledge and related velocity knowledge.
  • Limitations: Different privacy preferences across buddy groups can enable collusion attacks unless the corresponding granules satisfy additional relationships.The paper gives non-partially-overlapping hierarchical grids as a sufficient condition.
  • Limitations: The solution protects location privacy but does not enforce anonymity, although existing anonymization techniques could potentially be adapted for that purpose.The limitation arises because participating buddies often already know one another.

A Proofs of formal results

The proofs establish privacy by showing that protocol messages do not reveal additional location information under the paper’s adversary models. They reduce the argument to message issuance patterns, message-content secrecy, and consistency with disclosed spatial granules.

  • Theorem 4: Fixed-time update intervals make message issuance independent of the user’s location in the corresponding lemma.This protocol property supplies the needed equality for the proof.
  • Theorem 1: Theorem 1 proves that exchanged messages do not change the service provider’s knowledge of a user’s location.The proof establishes P(postA) = P(priA) by showing message probabilities are independent of the user’s location.
  • Lemma 1 and Lemma 2: The proof represents each message by whether an update or request was sent, disregarding encrypted content.Perfect secrecy makes a particular encrypted message as probable as the corresponding issuance pattern.
  • Theorem 2: For buddy privacy, messages intended for a buddy additionally reveal only the granule associated with the message, not the location within that granule.The proof incorporates the disclosed granule into the privacy information and shows finer location details remain irrelevant.
  • Theorem 2: Theorem 2’s argument shows that encrypted message content and granule consistency do not provide buddies with more location information than their prior knowledge.Inconsistent messages have probability zero; otherwise their probability depends only on the permitted granule-level information and prior knowledge.
  • Theorem 3: Theorem 3 applies the same independence strategy while relying on hashing with stronger secrecy than encryption.The proof again targets P(M|locA, priA) = P(M|priA).
Loading 1007.0408v2…