pith. sign in

arxiv: 1907.03045 · v1 · pith:HAXDXYYInew · submitted 2019-07-05 · 💻 cs.CR

Oblivious Location-Based Service Query

Jinguang Han This is my paper

Pith reviewed 2026-05-25 01:51 UTC · model grok-4.3

classification 💻 cs.CR
keywords privacy-preserving location-based servicesoblivious querylocation privacyconstant-cost querycryptographic schemedecrypt key generationsemi-trusted third party
0
0 comments X

The pith

The paper proposes an OLBSQ scheme allowing private location-based service queries with constant costs and no trusted third party.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents an oblivious location-based service query scheme that removes the need for any semi-trusted third party. A user can request services while the provider learns only the size of the query and never the exact location. Both the work to create the query and the data exchanged stay fixed no matter how large the queried region is. The provider generates the necessary decryption keys in an oblivious, step-by-step manner. Security rests on reductions to standard complexity assumptions.

Core claim

The central claim is that an OLBSQ scheme can be built so a user queries services without revealing her exact location, the service provider learns only the query size, computation and communication costs remain constant rather than linear in the queried area, and no semi-trusted third party is required; the scheme achieves this by letting the provider obliviously and incrementally generate decrypt keys for the queried services.

What carries the argument

The OLBSQ scheme's method for oblivious incremental decrypt-key generation by the service provider, which keeps query costs constant.

If this is right

  • Users obtain services privately without relying on any trusted intermediary.
  • Query preparation work and bandwidth stay fixed even for large regions.
  • The provider cannot distinguish which precise point inside the query area was intended.
  • Security follows directly once the underlying complexity assumptions hold.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The incremental key-generation technique could be reused in other settings where a server must release data pieces without learning which pieces are requested.
  • Constant-cost queries might make private location services practical on resource-limited mobile devices.
  • Removing the trusted party simplifies deployment in fully decentralized or peer-to-peer environments.

Load-bearing premise

Security holds because the scheme reduces to well-known complexity assumptions.

What would settle it

An efficient algorithm that recovers a user's exact location from the query transcript while the protocol runs correctly would falsify the privacy claim.

Figures

Figures reproduced from arXiv: 1907.03045 by Jinguang Han.

Figure 2
Figure 2. Figure 2: 2.3 Bilinear Map and Complexity Assumptions Let G1, G2 and G⌧ be three cyclic groups with prime order p. Suppose g1 and g2 be generators of G1 and G2, respectively. A map e : G1 ⇥ G2 ! G⌧ is a bilinear map if it satisfies the following properties: 1. Bilinearity. For all g 2 G1, h 2 G2 and x, y 2 Zp, e(gx,hy)= e(gy,hx)= e(g, h)xy; 2. Non-degeneracy. e(g1,g2) 6=1⌧ , where 1⌧ is the identity of G⌧ ; 3. E￾cie… view at source ↗
Figure 2
Figure 2. Figure 2: The Functionality of Oblivious Location-Based Service Query Schemes [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: Setup Algorithm Service-Transfer(U((i, j), P P) ↔ SP(SK, P P)) : User: U Service Provider: SP Selects a start point O = (i, j) Q1 ←−−−SP H Generates a proof Q1 SP : and the query size S = l × k. PoK {(h) : H = e(g, h)} Selects r1, r2, r3, r4, r5, r6, r7, r8, r9, r10 $ ← Zp, and computes E1 = g −r1 g i 1, E2 = g −r2 h j 1 , F1 = g r3Ci,1, F2 = (Ci,2) r4 , J1 = g r5Dj,1, J2 = (Dj,2) r6 , I1 = (Γ i 1) r7 , I2… view at source ↗
Figure 5
Figure 5. Figure 5: Service Transfer Algorithm [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
read the original abstract

Privacy-preserving location-base services (LBS) have been proposed to protect users' location privacy. However, there are still some problems in existing schemes: (1) a semi-trusted third party (TTP) is required; or (2) both the computation cost and communication cost to generate a query are linear in the size of the queried area. In this paper, to improve query efficiency, an oblivious location-based service query (OLBSQ) scheme is proposed. Our scheme captures the following features: (1) a semi-trusted TTP is not required; (2) a user can query services from a service provider without revealing her exact location; (3) the service provider can only know the size of a query made by a user; and (4) both the computation cost and the communication cost to generate a query is constant, instead of linear in the size of the queried area. We formalise the definition and security model of OLBSQ schemes. The security of our scheme is reduced to well-known complexity assumptions. The novelty is to reduce the computation cost and communication cost of making a query and enable the service provider to obliviously and incrementally generate decrypt keys for queried services. This contributes to the growing work of formalising privacy-preserving LBS schemes and improving query efficiency.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes an Oblivious Location-Based Service Query (OLBSQ) scheme for privacy-preserving LBS. It claims to eliminate the need for a semi-trusted TTP, allow users to query without revealing exact location (service provider learns only query size), achieve constant (not linear) computation and communication costs for query generation, and support oblivious incremental decrypt-key generation by the provider. The authors formalize the scheme definition and security model, assert a security reduction to well-known complexity assumptions, and position the work as improving query efficiency while contributing to formal privacy-preserving LBS treatments.

Significance. If the construction, constant-cost claims, and security reduction hold, the result would be significant for the field: it would provide a TTP-free LBS query mechanism with sublinear costs and only query-size leakage, advancing both efficiency and formal modeling in privacy-preserving location services.

major comments (2)
  1. [Abstract] Abstract (and security model section): the claim that security 'is reduced to well-known complexity assumptions' supplies neither the specific assumptions, the security game definition, nor any reduction steps or proof sketch. This is load-bearing for the central claims of location hiding, query-size-only leakage, and constant costs.
  2. [Abstract] Abstract: the constant-cost claim (computation and communication independent of queried area size) is asserted without any construction outline, algorithm description, or complexity analysis that would allow verification against the linear-cost baselines mentioned in the introduction.
minor comments (2)
  1. [Abstract] The abstract uses 'well-known complexity assumptions' without naming them; even a high-level list (e.g., DDH, LWE) would improve readability.
  2. [Abstract] The novelty paragraph could more explicitly contrast the oblivious incremental key generation with prior TTP-based or linear-cost schemes.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable comments. We will revise the manuscript to address the concerns raised regarding the abstract by providing more details on the security reduction and construction outline. Our point-by-point responses follow.

read point-by-point responses

  1. Referee: [Abstract] Abstract (and security model section): the claim that security 'is reduced to well-known complexity assumptions' supplies neither the specific assumptions, the security game definition, nor any reduction steps or proof sketch. This is load-bearing for the central claims of location hiding, query-size-only leakage, and constant costs.

    Authors: The abstract is intended as a high-level overview. The full security model, including the game definition, specific assumptions, and the reduction proof, are provided in Section 3 and the appendix of the manuscript. To address this comment, we will expand the abstract to name the assumptions and include a brief proof sketch, ensuring the claims are better supported. revision: yes

  2. Referee: [Abstract] Abstract: the constant-cost claim (computation and communication independent of queried area size) is asserted without any construction outline, algorithm description, or complexity analysis that would allow verification against the linear-cost baselines mentioned in the introduction.

    Authors: The construction details, including the algorithms for query generation and the complexity analysis showing constant costs, are presented in Section 4 of the paper. The novelty of oblivious incremental decrypt-key generation enables the constant costs. We will revise the abstract to include a short outline of the construction approach to facilitate verification. revision: yes

Circularity Check

0 steps flagged

No circularity detected; security claim rests on external assumptions without self-referential reduction

full rationale

The provided abstract and description formalize an OLBSQ scheme, list its features (no TTP, location privacy, constant costs), and state that security reduces to well-known complexity assumptions. No equations, self-citations, fitted parameters renamed as predictions, or ansatzes are exhibited that would make any claim equivalent to its own inputs by construction. The derivation chain is presented as self-contained against external cryptographic assumptions, with no load-bearing step reducing to a prior result by the same authors or to a definitional tautology. This is the normal case of an independent construction claim.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are described.

pith-pipeline@v0.9.0 · 5750 in / 1033 out tokens · 19494 ms · 2026-05-25T01:51:02.430939+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [1]

    Short signatures without random oracles

    Dan Boneh and Xavier Boyen. Short signatures without random oracles. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science , pages 56–73. Springer, 2004

    work page 2004

  2. [2]

    Short signatures without random oracles and the sdh assumption in bilinear groups

    Dan Boneh and Xavier Boyen. Short signatures without random oracles and the sdh assumption in bilinear groups. Journal of Cryptology , 21(2):149–177, 2007

    work page 2007

  3. [3]

    Oblivious transfer with access control

    Jan Camenisch, Maria Dubovitskaya, and Gregory Neven. Oblivious transfer with access control. In Ehab Al-Shaer, Somesh Jha, and Angelos D. Keromytis, editors, ACM CCS 2009 , pages 131–140. ACM, 2009

    work page 2009

  4. [4]

    Simulatable adaptive oblivious transfer

    Jan Camenisch, Gregory Neven, and Abhi Shelat. Simulatable adaptive oblivious transfer. In Moni Naor, editor, EUROCRYPT 2007, volume 4515 of Lecture Notes in Computer Science , pages 573–590. Springer, 2007

    work page 2007

  5. [5]

    Blind filtering at third parties: An efficient privacy-preserving framework for location-based services

    Jing Chen, Kun He, Quan Yuan, Min Chen, Ruiying Du, and Yang Xiang. Blind filtering at third parties: An efficient privacy-preserving framework for location-based services. IEEE Transactions on Mobile Computing , DOI: 10.1109/TMC.2018.2811481, 2018

    work page doi:10.1109/tmc.2018.2811481 2018

  6. [6]

    Mokbel, and Xuan Liu

    Chi-Yin Chow, Mohamed F. Mokbel, and Xuan Liu. A peer-to-peer spatial cloaking algorithm for anonymous location-based services. In GIS’06, pages 171–178. ACM, 2006

    work page 2006

  7. [7]

    Protecting location privacy with personalized k-anonymity: Architecture and algorithms

    Bu˘gra Gedik and Ling Liu. Protecting location privacy with personalized k-anonymity: Architecture and algorithms. IEEE Transactions on Mobile Computing , 7(1):1–18, 2008

    work page 2008

  8. [8]

    Single-database private information retrieval with constant com- munication rate

    Craig Gentry and Zulfikar Ramzan. Single-database private information retrieval with constant com- munication rate. In Lu ´is Caires, Giuseppe F. Italiano, Lu ´is Monteiro, Catuscia Palamidessi, and Moti Yung, editors, ICALP’05, volume 3580 of Lecture Notes in Computer Science , pages 803–815. Springer, 2005

    work page 2005

  9. [9]

    Priv ´E: Anonymous location-based queries in distributed mobile systems

    Gabriel Ghinita, Panos Kalnis, and Spiros Skiadopoulos. Priv ´E: Anonymous location-based queries in distributed mobile systems. In Carey L. Williamson, Mary Ellen Zurko, Peter F. Patel-Schneider, and Prashant J. Shenoy, editors, WWW’07, pages 371–380. ACM, 2007

    work page 2007

  10. [10]

    Yavuz, and Bechir Hamdaoui

    Mohamed Grissa, Attila A. Yavuz, and Bechir Hamdaoui. Preserving the location privacy of secondary users in cooperative spectrum sensing. IEEE Transactions on Information Forensics and Security , 12(2):418–431, 2017

    work page 2017

  11. [11]

    Anonymous usage of location-based services through spatial and temporal cloaking

    Marco Gruteser and Dirk Grunwald. Anonymous usage of location-based services through spatial and temporal cloaking. In Daniel P. Siewiorek, editor, MobiSys’03, pages 31–42. ACM, 2003

    work page 2003

  12. [12]

    Leveraging spatial diversity for privacy-aware location- based services in mobile networks

    Xiaofan He, Richeng Jin, and Huaiyu Dai. Leveraging spatial diversity for privacy-aware location- based services in mobile networks. IEEE Transactions on Information Forensics and Security , 13(6):1524–1534, 2018

    work page 2018

  13. [13]

    Messages in a concealed bottle: Achieving query content privacy with accurate location-based services

    Qin Hu, Shengling Wang, Chunqiang Hu, Jianhui Huang, Wei Li, and Xiuzhen Cheng. Messages in a concealed bottle: Achieving query content privacy with accurate location-based services. IEEE Transactions on Vehicular Technology, DOI 10.1109/TVT.2018.2838041, 2018

    work page doi:10.1109/tvt.2018.2838041 2018

  14. [14]

    Efficient covert two-party computation

    Stanislaw Jarecki. Efficient covert two-party computation. In Michel Abdalla and Ricardo Dahab, editors, PKC’18, volume 10769 of Lecture Notes in Computer Science , pages 644–674. Springer, 2018

    work page 2018

  15. [15]

    Preventing location- based identity inference in anonymous spatial queries

    Panos Kalnis, Gabriel Ghinita, Kyriakos Mouratidis, and Dimitris Papadias. Preventing location- based identity inference in anonymous spatial queries. IEEE Transactions on Knowledge and Data Engineering, 19(12):1719–1733, 2007

    work page 2007

  16. [16]

    Mokbel, Chi-Yin Chow, and Walid G

    Mohamed F. Mokbel, Chi-Yin Chow, and Walid G. Aref. The new casper: Query processing for location services without compromising privacy. In Umeshwar Dayal, Kyu-Young Whang, David B. Lomet, Gustavo Alonso, Guy M. Lohman, Martin L. Kersten, Sang Kyun Cha, and Young-Kuk Kim, editors, VLDB’06, pages 763–774. ACM, 2006

    work page 2006

  17. [17]

    Oblivious transfer with adaptive queries

    Moni Naor and Benny Pinkas. Oblivious transfer with adaptive queries. In Michael Wiener, editor, CRYPTO? 99, volume 1666 of Lecture Notes in Computer Science , pages 573–590. Springer, 1999

    work page 1999

  18. [18]

    Golam Kaosar, Xun Yi, and Elisa Bertino

    Russell Paulet, Md. Golam Kaosar, Xun Yi, and Elisa Bertino. Privacy-preserving and content- protecting location based queries. IEEE Transactions on Knowledge and Data Engineering , 26(5):1200–1210, 2014

    work page 2014

  19. [19]

    A model for asynchronous reactive systems and its application to secure message transmission

    Birgit Pfitzmann and Michael Waidner. A model for asynchronous reactive systems and its application to secure message transmission. In Roger Needham and Martin Abadi, editors, IEEE S&P 2001 , pages 184–200. IEEE, 2001

    work page 2001

  20. [20]

    Roman Schlegel, Chi-Yin Chow, Qiong Huang, and Duncan S. Wong. User-defined privacy grid system for continuous location-based services. IEEE Transactions on Mobile Computing , 14(10):2158–2172, 2015. Oblivious Location-Based Service Query 15

    work page 2015

  21. [21]

    Roman Schlegel, Chi-Yin Chow, Qiong Huang, and Duncan S. Wong. Privacy-preserving location sharing services for social networks. IEEE Transactions on Services Computing , 10(5):811–825, 2017

    work page 2017

  22. [22]

    Location anonymity in continuous location-based services

    Toby Xu and Ying Cai. Location anonymity in continuous location-based services. In Hanan Samet, Cyrus Shahabi, and Markus Schneider, editors, ACMGIS’07, pages 39:1–39:8. ACM, 2007. A Correctness Correctness. Our scheme described in Fig. 4 and Fig. 5 is correct because the following equations hold. F1 = gr3 Ci,1 = gr3 gxi 2 , F 2 = C r4 i,2 = g r4 α2 +xi 2...

    work page 2007

  23. [23]

    SP sends (H, H′, c, ˆh, M 1 SP ) to U

    SP selects h′ R ← G and M 1 SP R ← {0, 1}∗, and computes H′ = e(g, h′), c = H(H||H′||M 1 SP ) and ˆh = h′h−c. SP sends (H, H′, c, ˆh, M 1 SP ) to U

    work page

  24. [24]

    An Instance of Zero Knowledge Proof ∏ U

    U checks c ? = H(H||H′||M 1 SP ) and H′ ? = e(g, ˆh) · H c. An Instance of Zero Knowledge Proof ∏ U

    work page

  25. [25]

    U selects r, s, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, s1, s2, s3, s4, s5, s6, s7, s8, s9, s10 R ← Zp, MU R ← {0, 1}∗, and computes E1 = g−r1 gi 1, E2 = g−r2 hj 1, F1 = gr3 Ci,1, F2 = C r4 i,2, J1 = gr5 Dj,1, J2 = Dr6 j,2, I1 = (Γ i 1)r7, I2 = (Γ j 2 )r8, I3 = (Γ i+l 1 )r9, I4 = (Γ j+k 2 )r10, E′ 1 = gs1 gr 1, E′ 2 = gs2 hs 1, Θ1 = e(g, F2)s3, Θ2 = e(g2...

    work page

  26. [26]

    SP checks c1 ? = H(E1||E′ 1||MU), c2 ? = H(E2||E′ 2||MU), c3 ? = H(Θ5||Θ6||MU), c4 ? = H(Θ7||Θ8||MU), c5 ? = H(Θ9||Θ15||MU), c6 ? = H(Θ10||Θ16||MU), c7 ? = H(Θ1||Θ2||MU), c8 ? = H(Θ3||Θ4||MU), c9 ? = H(Θ6||Θ11||MU), c10 ? = H(Θ8||Θ12||MU), c11 ? = H(Θ9||Θ13||MU), c12 ? = H(Θ10||Θ14||MU), E′ 1 ? = gz1 gz2 1 Ec1 1 , E′ 2 ? = gz2 hz4 1 Ec2 2 , Θ5Θ6 ? = e(g1,...

    work page

  27. [27]

    SP sends (Kµ,ν, Lµ,ν, Υ 1 µ,ν, Υ 2 µ,ν, Υ 3 µ,ν, c1 µ,ν, c2 µ,ν, z1 µ,ν, z2 µ,ν, hµ,ν, ˜H, L′ µ,ν) to U

    For µ ∈ { 1, 2, · · · , l} and ν ∈ { 1, 2, · · · , k}, SP selects ωµ, ψν R ← Zp, ˜h R ← G and M 2 SP R ← {0, 1}∗, and computes Kµ,ν = E1gµ 1 E2hν 1F xµ 1 J yν 1 , Lµ,ν = e(Kµ,ν, h), Υ 1 µ,ν = F ωµ 1 J ψν 1 , Υ 2 µ,ν = e(Cµ,2, g2)−ωµ, Υ 3 µ,ν = e(Dν,2, h2)−ψν, c1 µ,ν = H(Kµ,ν||Υ 1 µ,ν||Υ 2 µ,ν||Υ 3 µ,ν||M 2 SP ), c2 µ,ν = H(Lµ,ν||H||M 2 SP ), z1 µ,ν = ωµ −...

    work page

  28. [28]

    U checks c1 µ,ν ? = H(Kµ,ν||Υ 1 µ,ν||Υ 2 µ,ν||Υ 3 µ,ν||M 2 SP ), c2 µ,ν ? = H(Lµ,ν||H||M 2 SP ), Υ 1 µ,ν ? = F z1 µ,ν 1 J z2 µ,ν 1 ( Kµ,ν E1gµ 1 E2hν 1 )c1 µ,ν, Υ 2 µ,ν ? = e(Cµ,2, g2)−z1 µ,ν( e(Cµ,2,W2) e(g2,g2) )c1 µ,ν, Υ 3 µ,ν ? = e(Dν,2, h2)−z2 µ,ν( e(Dν,2,W′ 2) e(h2,h2) )c2 µ,ν, L′ µ,ν ? = e(Kµ,ν, hµ,ν)· L c2 µ,ν µ,ν , ˜H ? = e(g, hµ,ν) · H c2 µ,ν

    work page