Search Me If You Can: Privacy-preserving Location Query Service

I. INTRODUCTION

• Existing controls rely on user groups and binary disclosure choices, and leave locations visible to the server even when users disable disclosure.Users may want to share an exact location with some friends and only an approximate location with others.Source: §I · p. 1

A. Contributions

• Condition-based access control lets users add scalable privacy rules without hand-picking large groups of friends.The protocol controls who can access location information based on whether users satisfy a specified condition.Source: A. Contributions · p. 2
• The protocol supports multiple disclosure levels, from revealing nothing to revealing an exact location, with intermediate levels providing indirect location information.The paper describes this as semi-functional encryption.Source: A. Contributions · p. 2
• PLQP processes encrypted location information so friends learn only query results controlled by the publisher, while the server learns nothing from stored ciphertexts.The protocol supports location queries without directly applying functions to raw location information.Source: A. Contributions · pp. 1–2

II. RELATED WORK

• Prior k-anonymity methods face dynamic-location, utility, and user-specific privacy-level concerns; dummy locations target providers, while mix zones rely on dense, unpredictable users and often trusted servers.The paper distinguishes its interest in privacy against other users from dummy-location protection against the LBS provider.Source: §II · p. 2
• Cloaking-region approaches disclose a location range that users do not control, whereas the paper argues users should configure location disclosure themselves.The cited approaches send a cloaking region rather than an actual location to the LBS.Source: §II · p. 2

A. System Model

• Users can act as both location publishers and queriers, while service providers issue keys used for access control.The model considers one service provider for simplicity.Source: A. System Model · p. 2
• Users and service providers are semi-honest, do not collude, and communicate over an anonymized network; hiding packet origin is outside the paper's scope.The model assumes they follow the protocol while trying to extract information from ciphertexts.Source: A. System Model · p. 2

B. Location Assumption

• Locations are modeled as integer-coordinate points in Euclidean space, with a one-meter grid yielding at most two meters of Euclidean-distance error.The paper assumes a planar ground surface and meter units.Source: B. Location Assumption · pp. 2–3
• The paper focuses on Euclidean distance, converts surface-distance conditions to equivalent Euclidean-distance conditions, and states the protocol works when distance is polynomial in location points.The surface-distance conversion assumes a spherical Earth.Source: B. Location Assumption · p. 3

C. Problem Statement

• A querier uses their location and attributes to query a publisher's location, receiving a result determined by both inputs without learning useful extra location information.The query is represented as f(x_i, S_i, x_j).Source: C. Problem Statement · p. 3
• Publishers specify access policies as boolean functions over user attributes, enabling rules such as city disclosure to friends or exact distance disclosure to university peers.The policies are represented by an access tree.Source: C. Problem Statement · p. 3
• The four query levels reveal, respectively, a publisher-chosen distance-threshold result, a querier-chosen threshold result, exact distance, or a publisher-defined function of location.Higher query levels generally disclose more information: level 4 can return a city, zipcode, or exact location.Source: C. Problem Statement · p. 3

A. Attribute-Based Encryption (ABE)

• Attribute-based encryption represents identity through attributes, allowing encryption policies to specify boolean access conditions; PLQP uses ciphertext-policy ABE as an access-control component.In CP-ABE, the policy is specified in the ciphertext rather than the decryption key.Source: A. Attribute-Based Encryption (ABE) · p. 3, §IV · p. 3
• An access tree encodes policy with attribute leaves and threshold-gate nodes, and can express arbitrary conditions for flexible, scalable privacy control.A leaf is satisfied when the key contains its attribute; a gate is satisfied when enough child nodes are satisfied.Source: 1) Access Tree T · p. 3

2) Definition:

• The ABE interface comprises setup producing public and master keys, encryption under an access tree, key generation from attributes, and decryption when those attributes satisfy the tree.The master key is kept secret by the key issuer.Source: 2) Definition · p. 4

B. Homomorphic Encryption (HE)

• HE supports direct addition and multiplication on ciphertexts while preserving decryptability.The paper notes that this is an example HE scheme and that detailed operations vary by system.Source: B. Homomorphic Encryption (HE) · p. 4
• Paillier’s system is chosen because fully homomorphic encryption’s decryption is too slow for real applications, while most cases need only a few additions or multiplications.The paper describes Paillier’s system as simpler and more efficient, using one multiplication per homomorphic addition and one exponentiation per homomorphic multiplication.Source: B. Homomorphic Encryption (HE) · p. 4

1) Definition of Paillier’s Cryptosystem:

• Paillier’s cryptosystem has KeyGenerate, Encrypt, and Decrypt algorithms, and ciphertext randomness prevents dictionary attacks.The decryption key works only with ciphertexts encrypted under its paired encryption key; the paper omits the random value in later notation.Source: 1) Definition of Paillier’s Cryptosystem · p. 4
• Paillier ciphertext multiplication yields an encryption of the sum of the plaintexts, modulo n^2.E(m1, r1) · E(m2, r2) = E(m1 + m2, r1r2) mod n^2.Source: 1) Definition of Paillier’s Cryptosystem · p. 4

C. Functional Encryption (FE)

• Functional encryption lets a key holder learn a specified function of encrypted data, but nothing else about the data.Unlike traditional encryption, different keys can yield different function results rather than the same plaintext.Source: C. Functional Encryption (FE) · p. 4
• Prior FE work mainly hides encryption policies, and the paper reports no formal construction satisfying the stated FE definition.The authors describe their knowledge of related work as limited to the works cited in and.Source: C. Functional Encryption (FE) · p. 4

V. PRELIMINARY DESIGN

• The preliminary design describes four function levels over location data and uses distance computation to support them.The protocol lets the querier securely compute distance without learning the publisher’s coordinates or disclosing the querier’s own location.Source: §V · p. 5, 1) Privacy Preserving Distance… · p. 5

1) Privacy Preserving Distance Computation:

• The querier generates Paillier keys, the publisher performs homomorphic operations on received ciphertexts, and the querier decrypts the result to obtain distance.The stated procedure uses a 1024-bit modulus.Source: 1) Privacy Preserving Distance… · p. 5
• Repeated distance queries let the querier infer the publisher’s location after four runs in Euclidean space or three in a Euclidean plane.A single protocol run keeps the querier’s location secret from the publisher and gives the querier only the encrypted distance.Source: 1) Privacy Preserving Distance… · p. 5

2) Privacy Preserving Distance Comparison:

• The querier may instead supply the threshold by sending its encrypted square, which the publisher masks and processes in the same comparison protocol.The masking parameters are chosen from specified ranges because other choices can make the comparison incorrect under modular operations.Source: 2) Privacy Preserving Distance… · p. 5
• The querier can compare distance with a publisher-determined threshold by decrypting masked distance and threshold values and checking their ordering.The paper requires the values to remain below the modulus so modular operations do not invalidate the comparison.Source: 2) Privacy Preserving Distance… · p. 5

VI. PRIVACY PRESERVING LOCATION SERVICES

• The construction’s security assumes no probabilistic polynomial-time algorithm solves DDH or DBDH with non-negligible advantage,,.The paper motivates this assumption by the considered intractability of discrete logarithm problems in large number fields,,.Source: §VI · p. 6
• CP-ABE enforces fine-grained query access: satisfying a location condition alone reveals nothing unless the querier’s identity attributes also satisfy the encryption policy.The section introduces the bilinear-group setting used by CP-ABE.Source: §VI · pp. 5–6

A. Initialize

• The service provider runs CP-ABE setup to create public and master keys, then generates private keys for users according to their attributes.The paper assumes private keys are delivered securely over channels between users and service providers.Source: A. Initialize · p. 6

B. Protocol for Level 4 Query

• For a level 4 query, the publisher creates an access tree and encrypts each location coordinate under it using CP-ABE.The encrypted coordinates are sent to the querier.Source: B. Protocol for Level 4 Query · p. 6
• A querier whose private key satisfies the level 4 access tree decrypts the coordinates and learns the publisher’s exact location.The paper states that the querier learns the exact location after the query ends.Source: B. Protocol for Level 4 Query · p. 6

C. Protocol for Level 3 Query

• The querier decrypts an access-tree-protected ciphertext with an eligible private key, then uses the Paillier key to recover the squared distance and obtain the distance.The ciphertext is doubly nested, with the access tree controlling who can decrypt it.Source: C. Protocol for Level 3 Query · p. 6
• More than three level-3 queries in Euclidean space, or more than two in the plane, make level 3 equivalent to level 4.The proof uses four distances from different locations to solve for the publisher’s three coordinates in Euclidean space.Source: C. Protocol for Level 3 Query · p. 6
• Four distance equations from distinct locations determine the publisher’s three coordinates, explaining the Euclidean-space reconstruction result.Source: C. Protocol for Level 3 Query · p. 6

D. Protocol for Level 2 Query

• Θ(log D) level-2 queries make level 2 equivalent to level 3, where D is the greatest possible distance in the location space.Source: D. Protocol for Level 2 Query · p. 6
• Binary search over querier-chosen thresholds finds the distance by narrowing the threshold until it equals the querier–publisher distance.The search begins with τ = D.Source: D. Protocol for Level 2 Query · p. 6
• The querier compares decrypted, doubly nested ciphertext values to learn whether the distance is less than, equal to, or greater than τ.The publisher encrypts the values under the level-2 access tree; only a querier whose private key satisfies that tree can decrypt them.Source: D. Protocol for Level 2 Query · p. 7

E. Protocol for Level 1 Query

• A level-1 query reveals whether the distance is less than, equal to, or greater than the publisher-chosen threshold τ.Source: E. Protocol for Level 1 Query · p. 7
• Within τ, level 1 becomes equivalent to level 4 after O(log τ) queries; when farther than τ, expected queries to locate P are Ω((D/τ)^d log D).Here d is 2 for the Euclidean plane and 3 for Euclidean space.Source: E. Protocol for Level 1 Query · pp. 7–8
• When the querier is inside the τ-radius circle, binary search along a line finds a point on the circle; three such points locate P.Each point on the circle takes at most log2(2τ) queries to find, for at most 3 log2(2τ) queries total.Source: E. Protocol for Level 1 Query · p. 7, Figure 1 · p. 7
• Limiting responses when comparison results change can restrict what the querier learns; the publisher can also limit level-3 queries during a period when its location is unchanged.For level 1, withholding further answers leaves the circle point somewhere between two points.Source: E. Protocol for Level 1 Query · p. 8
• Paillier comparison requires both masked squared-distance values to remain below the modulus; the authors select δ and δ′ for their estimated global-distance bound.The paper estimates that the same restrictions apply in Euclidean space as in the plane.Source: F. Restrictions for δ, δ′ · p. 8

VII. PERFORMANCE EVALUATION

• The protocol was implemented on a single-CPU computer underclocked to 900 MHz, with computation ability described as similar to a smartphone.The implementation used GMP and a CP-ABE toolkit in Ubuntu 11.04.Source: §VII · p. 8
• Total runtime for each query is less than 1.5 seconds, and communication overhead is less than 10 Kilobytes.The runtime is dominated by CP-ABE encryption and decryption.Source: §VII · p. 8, Table I · p. 9, Table II · p. 9
• The tables report extra overhead only; total communication also includes regular control messages and acknowledgments.Source: §VII · pp. 8–9

• PLQP uses distance computation and comparison to implement semi-functional encryption for multi-level access control, with CP-ABE providing finer-grained control.Source: §VIII · p. 9
• Location information remains secret to others throughout the protocol unless the publisher intends disclosure.Source: §VIII · p. 9
• Experiments indicate that PLQP's performance is applicable in a real mobile network.Source: §VIII · p. 9