pith. sign in

arxiv: 2604.07797 · v1 · submitted 2026-04-09 · 💻 cs.CR

BRASP: Boolean Range Queries over Encrypted Spatial Data with Access and Search Pattern Privacy

Jing Zhang , Ganxuan Yang , Yifei Yang , Siqi Wen , Zhengyang Qiu This is my paper

Pith reviewed 2026-05-10 18:30 UTC · model grok-4.3

classification 💻 cs.CR
keywords searchable encryptionspatial datarange queriessearch pattern privacyaccess pattern privacydual-server modelforward security
0
0 comments X

The pith

BRASP enables efficient Boolean range queries on encrypted spatial data while hiding both search and access patterns from the servers.

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

The paper proposes BRASP to let users run range-based spatial searches combined with keyword conditions on cloud-stored encrypted data without revealing the query contents or the returned records. It encodes spatial locations with Hilbert-curve prefixes, builds inverted indexes over those prefixes and keywords, then shuffles the index entries and redistributes record identifiers across two separate servers. A sympathetic reader would care because location queries are common in mapping or sensor applications, yet prior encrypted search methods typically leak enough pattern information for servers to infer interests or habits. The scheme adds proofs for confidentiality and pattern hiding plus support for data updates that preserve forward security, and experiments indicate the added privacy steps keep computation and communication costs modest on real data.

Core claim

BRASP combines Hilbert-curve-based prefix encoding with encrypted prefix-ID and keyword-ID inverted indexes to support efficient spatial range filtering and conjunctive keyword matching. To hide the search pattern and access pattern under a dual-server setting, BRASP integrates index shuffling for encrypted keyword and prefix entries with ID-field redistribution across two non-colluding cloud servers. The scheme also supports dynamic updates and achieves forward security, with formal security analyses covering confidentiality, shuffle indistinguishability, query unforgeability, and forward security.

What carries the argument

Hilbert-curve prefix encoding paired with index shuffling and ID redistribution across two non-colluding servers, which together turn spatial range and keyword conditions into encrypted lookups while randomizing what each server sees.

Load-bearing premise

The two cloud servers never collude or pool their views of the shuffled indexes.

What would settle it

If an attacker with simultaneous access to both servers can consistently link multiple queries to the same spatial range or the same returned records despite the shuffling steps, the pattern-hiding claim is false.

Figures

Figures reproduced from arXiv: 2604.07797 by Ganxuan Yang, Jing Zhang, Siqi Wen, Yifei Yang, Zhengyang Qiu.

Figure 1
Figure 1. Figure 1: System model. As illustrated in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: An example of a BRQ [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Example of a prefix membership verification scheme for queries. [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Two inverted indexes of spatio-textual database:(a):Prefix-ID inverted [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The process of shuffling the indexes in CS1 Index Shuffle. To hide both the access pattern and the search pattern, BRASP re-randomizes and permutes the encrypted indexes after initialization and after each search. The two cloud servers jointly execute the shuffle procedure. Algo￾rithm 3 illustrates the shuffle procedure for the index shares stored at CS1; the procedure for the shares stored at CS2 is symme… view at source ↗
Figure 7
Figure 7. Figure 7: Performance of Secure Index Building. (a) (b) [PITH_FULL_IMAGE:figures/full_fig_p018_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Performance of Token Generation. Secure Index Building [PITH_FULL_IMAGE:figures/full_fig_p018_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Performance of Search. Search [PITH_FULL_IMAGE:figures/full_fig_p019_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Performance of Update. significantly reduces the dominant computation cost of search while maintaining practical communication overhead. Update [PITH_FULL_IMAGE:figures/full_fig_p020_10.png] view at source ↗
read the original abstract

Searchable Encryption (SE) enables users to query outsourced encrypted data while preserving data confidentiality. However, most efficient schemes still leak the search pattern and access pattern, which may allow an honest-but-curious cloud server to infer query contents, user interests, or returned records from repeated searches and observed results. Existing pattern-hiding solutions mainly target keyword queries and do not naturally support Boolean range queries over encrypted spatial data. This paper presents BRASP, a searchable encryption scheme for Boolean range queries over encrypted spatial data. BRASP combines Hilbert-curve-based prefix encoding with encrypted prefix--ID and keyword--ID inverted indexes to support efficient spatial range filtering and conjunctive keyword matching. To hide the search pattern and access pattern under a dual-server setting, BRASP integrates index shuffling for encrypted keyword and prefix entries with ID-field redistribution across two non-colluding cloud servers. BRASP also supports dynamic updates and achieves forward security. We formalize the security of BRASP through confidentiality, shuffle indistinguishability, query unforgeability, and forward-security analyses, and we evaluate its performance experimentally on a real-world dataset. The results show that BRASP effectively protects query privacy while incurring relatively low computation and communication overhead. To facilitate reproducibility and further research, the source code of BRASP is publicly available at https://github.com/Egbert-Lannister/BRASP

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 / 0 minor

Summary. The paper presents BRASP, a searchable encryption scheme supporting Boolean range queries over encrypted spatial data. It encodes spatial locations via Hilbert curves into prefix codes, maintains separate encrypted prefix-ID and keyword-ID inverted indexes, and achieves search/access pattern privacy by shuffling encrypted entries and redistributing IDs across two non-colluding servers. The construction also supports dynamic updates with forward security. Formal security claims cover confidentiality, shuffle indistinguishability, query unforgeability, and forward security; performance is evaluated experimentally on real datasets with reported low overhead, and source code is released publicly.

Significance. If the security analyses hold, the work fills a gap by extending pattern-hiding SE to spatial Boolean range queries, which prior schemes handle inefficiently or without pattern privacy. The public code release is a clear strength that enables direct reproducibility and follow-on research.

major comments (2)
  1. Abstract and security definitions: shuffle indistinguishability (the mechanism for hiding search and access patterns) is achieved exclusively via index shuffling and ID redistribution under the explicit non-collusion assumption between the two servers. The manuscript must supply a concrete security-game reduction or simulation argument showing that a joint view of both servers does not allow reconstruction of the original index structure or query access pattern; without this, the central privacy claim rests on an unmitigated trust assumption rather than cryptographic hardness.
  2. Security analyses section: the claimed formal proofs for confidentiality, shuffle indistinguishability, query unforgeability, and forward security are referenced but not reproduced or sketched in sufficient detail to verify the reductions. Because these proofs are load-bearing for all privacy and update guarantees, the full proof strategy (including how Hilbert-curve prefixes interact with the shuffled indexes) must be included or clearly referenced.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and constructive feedback on our manuscript. We address the major comments point by point below and will revise the paper to provide more rigorous and detailed security arguments as requested.

read point-by-point responses

  1. Referee: Abstract and security definitions: shuffle indistinguishability (the mechanism for hiding search and access patterns) is achieved exclusively via index shuffling and ID redistribution under the explicit non-collusion assumption between the two servers. The manuscript must supply a concrete security-game reduction or simulation argument showing that a joint view of both servers does not allow reconstruction of the original index structure or query access pattern; without this, the central privacy claim rests on an unmitigated trust assumption rather than cryptographic hardness.

    Authors: We agree that the presentation of shuffle indistinguishability would benefit from an explicit security game and reduction that accounts for the joint view of both servers. Although the non-collusion assumption is stated explicitly in the manuscript and the shuffling is performed using cryptographic primitives, we will add a formal security game in the revised version. This game will model an adversary observing the combined views of the two servers (without collusion) and provide a simulation argument proving that the combination of index shuffling and ID redistribution prevents reconstruction of the original index structure or access patterns. The argument will rely on the pseudorandomness of the shuffling and the semantic security of the underlying encryption, thereby grounding the privacy claim in cryptographic hardness rather than trust alone. revision: yes

  2. Referee: Security analyses section: the claimed formal proofs for confidentiality, shuffle indistinguishability, query unforgeability, and forward security are referenced but not reproduced or sketched in sufficient detail to verify the reductions. Because these proofs are load-bearing for all privacy and update guarantees, the full proof strategy (including how Hilbert-curve prefixes interact with the shuffled indexes) must be included or clearly referenced.

    Authors: We acknowledge that the security analyses in the current manuscript are described at a high level without full proof sketches. In the revision, we will expand the Security Analyses section to include detailed proof sketches for confidentiality, shuffle indistinguishability, query unforgeability, and forward security. We will specifically elaborate on the interaction between Hilbert-curve prefix encoding and the shuffled indexes, showing how the prefix-based range filtering is preserved under shuffling and ID redistribution while the security reductions remain valid. The expanded proofs will be placed in the main text where space permits or moved to an appendix, with clear references from the main body. revision: yes

Circularity Check

0 steps flagged

No circularity: security claims rest on external non-collusion assumption and standard primitives

full rationale

The BRASP construction uses Hilbert-curve prefix encoding, encrypted inverted indexes, and index shuffling with ID redistribution across two non-colluding servers to achieve pattern hiding. Security is formalized via separate definitions (confidentiality, shuffle indistinguishability, query unforgeability, forward security) that do not reduce by construction to fitted parameters, self-definitions, or self-citation chains. The non-collusion premise is stated explicitly as an assumption rather than derived from the scheme itself, and no load-bearing steps equate predictions or uniqueness theorems to inputs. The approach is self-contained against external cryptographic benchmarks without tautological reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The scheme rests on standard cryptographic assumptions (e.g., IND-CPA security of underlying encryption) and the non-collusion of two servers; no free parameters fitted to data or new invented entities are mentioned.

axioms (2)
  • standard math Standard cryptographic assumptions such as semantic security of the underlying encryption primitives
    Invoked implicitly for confidentiality and indistinguishability claims in the security analysis.
  • domain assumption The two cloud servers do not collude
    Central to the dual-server shuffling mechanism for hiding patterns; stated in the abstract description of the setting.

pith-pipeline@v0.9.0 · 5553 in / 1280 out tokens · 31782 ms · 2026-05-10T18:30:17.098513+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

35 extracted references · 35 canonical work pages

  1. [1]

    In: International conference on the theory and applications of crypto- graphic techniques

    Blaze, M., Bleumer, G., Strauss, M.: Divertible protocols and atomic proxy cryp- tography. In: International conference on the theory and applications of crypto- graphic techniques. pp. 127–144. Springer (1998)

    work page 1998

  2. [2]

    IEEE Transactions on Knowledge and Data Engineering (2023)

    Chang, Z., Xie, D., Wang, S., Li, F., Shen, Y.: Towards practical oblivious join processing. IEEE Transactions on Knowledge and Data Engineering (2023)

    work page 2023

  3. [3]

    IEEE Transactions on Cloud Computing (2024)

    Chen, D., Liao, Z., Xie, Z., Chen, R., Qin, Z., Cao, M., Dai, H.N., Zhang, K.: Mfsse: multi-keyword fuzzy ranked symmetric searchable encryption with pattern hidden in mobile cloud computing. IEEE Transactions on Cloud Computing (2024)

    work page 2024

  4. [4]

    In: 2019 IEEE 35th International Conference on Data Engineering (ICDE)

    Cui, N., Li, J., Yang, X., Wang, B., Reynolds, M., Xiang, Y.: When geo-text meets security: Privacy-preserving boolean spatial keyword queries. In: 2019 IEEE 35th International Conference on Data Engineering (ICDE). pp. 1046–1057. IEEE (2019)

    work page 2019

  5. [5]

    In: Topics in Cryptology–CT-RSA 2004: The Cryptographers’ Track at the RSA Conference 2004, San Francisco, CA, USA, February 23-27, 2004, Pro- ceedings

    Golle, P., Jakobsson, M., Juels, A., Syverson, P.: Universal re-encryption for mixnets. In: Topics in Cryptology–CT-RSA 2004: The Cryptographers’ Track at the RSA Conference 2004, San Francisco, CA, USA, February 23-27, 2004, Pro- ceedings. pp. 163–178. Springer (2004)

    work page 2004

  6. [6]

    IEEE Systems Journal17(1), 455–466 (2022)

    Gong, Z., Li, J., Lin, Y., Wei, J., Lancine, C.: Efficient privacy-preserving geo- graphic keyword boolean range query over encrypted spatial data. IEEE Systems Journal17(1), 455–466 (2022)

    work page 2022

  7. [7]

    IEEE Transactions on Dependable and Secure Computing21(2), 746–763 (2023)

    Guo, C., Li, W., Tang, X., Choo, K.K.R., Liu, Y.: Forward private verifiable dynamic searchable symmetric encryption with efficient conjunctive query. IEEE Transactions on Dependable and Secure Computing21(2), 746–763 (2023)

    work page 2023

  8. [8]

    IEEE Transactions on Cloud Computing11(1), 336–348 (2021)

    Li, F., Ma, J., Miao, Y., Jiang, Q., Liu, X., Choo, K.K.R.: Verifiable and dynamic multi-keyword search over encrypted cloud data using bitmap. IEEE Transactions on Cloud Computing11(1), 336–348 (2021)

    work page 2021

  9. [9]

    IEEE Transactions on Infor- mation Forensics and Security (2024)

    Liang, Y., Ma, J., Miao, Y., Su, Y., Deng, R.H.: Efficient and privacy-preserving encode-based range query over encrypted cloud data. IEEE Transactions on Infor- mation Forensics and Security (2024)

    work page 2024

  10. [10]

    IEEE Transactions on Services Computing16(5), 3621–3635 (2023)

    Lv, Z., Shang, K., Huo, H., Liu, X., Peng, Y., Wang, X., Tan, Y.: Rask: Range spatial keyword queries on massive encrypted geo-textual data. IEEE Transactions on Services Computing16(5), 3621–3635 (2023)

    work page 2023

  11. [11]

    IEEE Transactions on Intelligent Transportation Systems (2023)

    Miao, Y., Yang, Y., Li, X., Choo, K.K.R., Meng, X., Deng, R.H.: Comprehensive survey on privacy-preserving spatial data query in transportation systems. IEEE Transactions on Intelligent Transportation Systems (2023)

    work page 2023

  12. [12]

    IEEE Transactions on Knowledge and Data Engineering36(1), 122–136 (2023)

    Miao, Y., Yang, Y., Li, X., Wei, L., Liu, Z., Deng, R.H.: Efficient privacy-preserving spatial data query in cloud computing. IEEE Transactions on Knowledge and Data Engineering36(1), 122–136 (2023)

    work page 2023

  13. [13]

    Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes.In:Internationalconferenceonthetheoryandapplicationsofcryptographic techniques. pp. 223–238. Springer (1999)

    work page 1999

  14. [14]

    Cryptology ePrint Archive (2020)

    Patranabis, S., Mukhopadhyay, D.: Forward and backward private conjunctive searchable symmetric encryption. Cryptology ePrint Archive (2020)

    work page 2020

  15. [15]

    IEEE In- ternet of Things Journal9(16), 15285–15296 (2022)

    Shang, S., Li, X., Lu, R., Niu, J., Zhang, X., Guizani, M.: A privacy-preserving multidimensional range query scheme for edge-supported industrial iot. IEEE In- ternet of Things Journal9(16), 15285–15296 (2022)

    work page 2022

  16. [16]

    arXiv preprint arXiv:2102.09651 (2021) 22 J

    Shang, Z., Oya, S., Peter, A., Kerschbaum, F.: Obfuscated access and search pat- terns in searchable encryption. arXiv preprint arXiv:2102.09651 (2021) 22 J. Zhang et al

    work page arXiv 2021

  17. [17]

    IEEE Internet of Things Journal9(8), 6184–6198 (2021)

    Song, F., Qin, Z., Xue, L., Zhang, J., Lin, X., Shen, X.: Privacy-preserving keyword similarity search over encrypted spatial data in cloud computing. IEEE Internet of Things Journal9(8), 6184–6198 (2021)

    work page 2021

  18. [18]

    IEEE Transactions on Information Forensics and Security16, 1795–1809 (2020)

    Song, Q., Liu, Z., Cao, J., Sun, K., Li, Q., Wang, C.: Sap-sse: Protecting search pat- terns and access patterns in searchable symmetric encryption. IEEE Transactions on Information Forensics and Security16, 1795–1809 (2020)

    work page 2020

  19. [19]

    IEEE Transactions on Dependable and Secure Computing17(5), 912–927 (2018)

    Song, X., Dong, C., Yuan, D., Xu, Q., Zhao, M.: Forward private searchable sym- metric encryption with optimized i/o efficiency. IEEE Transactions on Dependable and Secure Computing17(5), 912–927 (2018)

    work page 2018

  20. [20]

    IEEE Transactions on Services Computing16(5), 3766–3781 (2023)

    Sun, L., Zhang, Y., Zheng, Y., Song, W., Lu, R.: Towards efficient and privacy- preserving high-dimensional range query in cloud. IEEE Transactions on Services Computing16(5), 3766–3781 (2023)

    work page 2023

  21. [21]

    IEEE Transactions on Information Forensics and Security (2024)

    Tong, Q., Li, X., Miao, Y., Wang, Y., Liu, X., Deng, R.H.: Beyond result verifica- tion: Efficient privacy-preserving spatial keyword query with suppressed leakage. IEEE Transactions on Information Forensics and Security (2024)

    work page 2024

  22. [22]

    In: IEEE INFOCOm 2020-IEEE conference on computer communications

    Wang, X., Ma, J., Liu, X., Deng, R.H., Miao, Y., Zhu, D., Ma, Z.: Search me in the dark: Privacy-preserving boolean range query over encrypted spatial data. In: IEEE INFOCOm 2020-IEEE conference on computer communications. pp. 2253–

    work page 2020

  23. [23]

    IEEE Transactions on Services Computing 15(2), 1012–1025 (2020)

    Wang,Y.,Sun,S.F.,Wang,J.,Liu,J.K.,Chen,X.:Achievingsearchableencryption scheme with search pattern hidden. IEEE Transactions on Services Computing 15(2), 1012–1025 (2020)

    work page 2020

  24. [24]

    The VLDB journal28(1), 25–46 (2019)

    Wu, Z., Li, K.: Vbtree: forward secure conjunctive queries over encrypted data for cloud computing. The VLDB journal28(1), 25–46 (2019)

    work page 2019

  25. [25]

    IEEE Transactions on Computers (2024)

    Xie, H., Guo, Y., Miao, Y., Jia, X.: Access-pattern hiding search over encrypted databases by using distributed point functions. IEEE Transactions on Computers (2024)

    work page 2024

  26. [26]

    IEEE Transactions on In- formation Forensics and Security14(4), 870–885 (2018)

    Xu, G., Li, H., Dai, Y., Yang, K., Lin, X.: Enabling efficient and geometric range query with access control over encrypted spatial data. IEEE Transactions on In- formation Forensics and Security14(4), 870–885 (2018)

    work page 2018

  27. [27]

    Computers & Security p

    Xu, T., Ge, X., Shao, C.: Pmkr: Privacy-preserving multi-keyword top-k reacha- bility query. Computers & Security p. 104525 (2025)

    work page 2025

  28. [28]

    IEEE Transactions on Information Forensics and Security (2024)

    Zhang, S., Lu, R., Zhu, H., Zheng, Y., Guan, Y., Wang, F., Shao, J., Li, H.: Per- formance enhanced secure spatial keyword similarity query with arbitrary spatial ranges. IEEE Transactions on Information Forensics and Security (2024)

    work page 2024

  29. [29]

    IEEE Transac- tions on Dependable and Secure Computing20(5), 3770–3786 (2022)

    Zhang, S., Ray, S., Lu, R., Guan, Y., Zheng, Y., Shao, J.: Efficient and privacy- preserving spatial keyword similarity query over encrypted data. IEEE Transac- tions on Dependable and Secure Computing20(5), 3770–3786 (2022)

    work page 2022

  30. [30]

    IEEE Transactions on Services Computing15(3), 1358–1370 (2020)

    Zheng, Y., Lu, R., Shao, J., Yin, F., Zhu, H.: Achieving practical symmetric search- able encryption with search pattern privacy over cloud. IEEE Transactions on Services Computing15(3), 1358–1370 (2020)

    work page 2020

  31. [31]

    Cryptology ePrint Archive (2020) A Theoretical Analysis We evaluate the performance of BRASP both theoretically and experimen- tally, making comparisons withVPBRQSupL

    Zuo, C., Sun, S.F., Liu, J.K., Shao, J., Pieprzyk, J., Wei, G.: Forward and back- ward private dynamic searchable symmetric encryption for conjunctive queries. Cryptology ePrint Archive (2020) A Theoretical Analysis We evaluate the performance of BRASP both theoretically and experimen- tally, making comparisons withVPBRQSupL. BRASP 23 Table 1 COMPARISON O...

    work page 2020

  32. [32]

    the forged token collides with the image of an honestly generated token derived from a different query component or a different shuffle state; or

    work page

  33. [33]

    BRASP 27 The first event directly gives a collision in the keyedT P Fimage space

    the adversary produces a fresh accepted image for a secret-key-dependent input that it has never obtained from an honest execution. BRASP 27 The first event directly gives a collision in the keyedT P Fimage space. The second event is precisely the type of event ruled out by the collision-resistant keyed encoding used byT P F, because acceptance requires c...

    work page

  34. [34]

    correlate update tokens across different shuffle states by reversing or colliding the state-dependentT P Fderivation; or

    work page

  35. [35]

    link a re-randomizedT U Rciphertext to a ciphertext observed before the update. The first event occurs only if the adversary breaks the collision resistance of T P F, and the second occurs only if the adversary breaks the unlinkability of re-randomizedT U Rciphertexts. Under these assumptions, both events have at most negligible probability. Hence the ins...

    work page