BRASP: Hiding Where You Look in Encrypted Spatial Keyword Search

arXiv:2604.07797 · cs.CR · Submitted 2026-04-09 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: We're looking at the paper: "BRASP: Hiding Where You Look in Encrypted Spatial Keyword Search".

Elias: Here's the gist of the paper. Searchable encryption (SE) enables users to query outsourced encrypted data while preserving data confidentiality.

Nadia: 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.

Elias: This paper presents BRASP, a searchable encryption scheme for Boolean range queries over encrypted spatial data.

Nadia: 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.

Paper summary: Nadia: Looking at BRASP: Hiding Where You Look in Encrypted Spatial Keyword Search, the paper presents a scheme that uses Hilbert-curve based spatial encoding, prefix-based range decomposition, and encrypted prefix ID and keyword ID indexes to support efficient query processing in the encrypted domain.

Elias: The authors integrate dual-server index shuffling and ID field redistribution to protect both the search pattern and access pattern, which is what makes it more robust than schemes that only focus on data confidentiality alone.

Priya: What this means for us is that we can now think about outsourcing spatial databases where we need to query ranges of locations combined with keywords without the cloud server being able to figure out exactly what kind of areas or specific businesses you are interested in, just from observing your repeated searches.

Nadia: It's about making sure that the mechanism for finding data and the pattern of finding it are hidden, not just the data itself.

Elias: They also achieve forward security and support dynamic updates, so you can add new spatial records without compromising queries you already ran on older data.

Priya: The performance results show that BRASP achieves relatively low computation and communication overhead across all the phases compared to other comparable schemes like VPBRQSupL.

Nadia: So, BRASP seems to be a practical approach for privacy-preserving spatial queries that balances strong pattern hiding with acceptable operational cost.

Conclusion: Nadia: So we're wrapping up on BRASP, which is about hiding where you look in encrypted spatial keyword search for data that’s already been encrypted.

Elias: Yeah, the authors are tackling a big problem with searchable encryption where people can see what you’re searching for just by looking at the results.

Priya: What I'm seeing here is that they've built a system that doesn't just hide the data, but hides *how* you search it too—the pattern and the access pattern.

Nadia: Exactly, so it’s not just about keeping the data secret; it’s about keeping your search habits secret from anyone watching.

Elias: They did this by combining a Hilbert curve based spatial encoding with these encrypted prefix ID and keyword ID indexes. It sounds like they have a clever way to structure the data that helps hide those patterns.

Priya: From my side, I'm wondering if this means we can finally use outsourced spatial databases for things that need privacy beyond just keeping the locations and names secret.

Nadia: It could mean someone can query data about a specific neighborhood or type of business without the cloud provider knowing exactly what you’re poking around with.

Elias: They also added this dual-server design using index shuffling and ID field redistribution, which they claim makes it more robust against that kind of snooping.

Priya: That sounds like a real practical step towards making these types of systems usable in real-world scenarios where privacy matters a lot.

Nadia: And the experiments showed it actually works better than some other schemes on things like Yelp business data, showing lower overhead in most parts.

Elias: The theoretical analysis also suggests that even with all those extra hiding techniques, the computation costs stay reasonably low for the search and update operations.

Priya: So what this paper really suggests is that we can build these spatial query systems that are not just secure but also reasonably fast to run in a cloud setting.

Nadia: It opens up possibilities for a lot of privacy-preserving applications in databases where you need to find things based on both location and specific terms.

Elias: So, the next thing we need to look at is how this scheme handles those dynamic updates they mentioned—how it keeps working when the data keeps changing.

Jing Zhang, Ganxuan Yang, Yifei Yang, Siqi Wen, Zhengyang Qiu

Lancaster University · Beijing Jiaotong University

cs.CR

Submitted: 2026-04-09

Updated: 2026-11-01

Code: https://github.com/Egbert-Lannister/BRASP

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 82/100

The gist: Searchable encryption (SE) enables users to query outsourced encrypted data while preserving data confidentiality.

Key concepts

Hilbert-curve-based prefix encoding
This technique is used to efficiently encode spatial data into a structure that allows for fast range queries. It organizes spatial points in a way that enables the scheme to handle Boolean range filtering over encrypted locations without revealing the exact coordinates of the data points.
Encrypted prefix–ID and keyword–ID indexes
These are specialized indexes used to quickly find relevant data based on both spatial ranges (prefixes) and specific keywords. They are encrypted, meaning that even if a cloud server inspects them, it cannot easily determine which specific data items or search terms they correspond to.
Index shuffling and ID-field redistribution
This dual-server security mechanism protects the search pattern and access pattern. By shuffling index entries and redistributing unique identifiers across two non-colluding servers, the scheme prevents any single server from linking a specific query to a specific data record.
Forward security
This property ensures that even after new data is added to the system, previous search queries cannot be used by the cloud servers to infer information about the newly added object. This maintains privacy over time as the database evolves.

Terminology

Summary

Searchable encryption (SE) enables users to query outsourced encrypted data while preserving data confidentiality. p. 0 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. p. 0 This paper presents BRASP, a searchable encryption scheme for Boolean range queries over encrypted spatial data. p. 0 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. p. 0 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. p. 0

Scheme Design and Components

BRASP is designed to support Boolean range queries over encrypted spatial data by combining Hilbert-curve-based prefix encoding with encrypted prefix–ID and keyword–ID indexes. The scheme integrates a dual-server design that combines index shuffling with ID-field redistribution to protect both the search pattern and the access pattern. p. 1 The scheme also supports dynamic updates and achieves forward security. p. 1 The system model involves a data owner (DO), an authorized client, and two non-colluding cloud servers CS1 and CS2. p. 3

Security Formalization

The security of BRASP is formalized through four properties: confidentiality, shuffle indistinguishability, query unforgeability, and forward security. Confidentiality requires that an honest-but-curious cloud server should learn no information about the plaintext objects, queried keywords, or queried ranges beyond the explicitly allowed leakage. p. 4 Shuffle indistinguishability requires that after an index-shuffle operation, a cloud server cannot determine which pre-shuffle entry corresponds to which postshuffle entry with non-negligible advantage. p. 2 Query unforgeability requires that no PPT adversary can produce a valid search token for an unseen Boolean range query without knowing the authorized client’s secret key. p. 7 Forward security requires that after inserting a new object, the cloud servers cannot use information leaked by searches issued before the update to determine whether the new object would have matched any earlier query. p. 1

Theoretical Analysis and Performance

The theoretical analysis compares BRASP with VPBRQSupL [21] and shows that BRASP achieves lower computation costs in most operations. Specifically, the Encrypted Index Build and Token Generation phases in BRASP are more efficient due to the optimized use of TPF and TUR. p. 5 The Search and Update operations in BRASP also demonstrate improved efficiency, making it a more practical solution for privacypreserving data queries in cloud environments. p. 3

Experimental Validation

In experiments using the Yelp business dataset, BRASP achieves lower overhead than VPBRQSupL and PPSKS across secure index building, token generation, search, and update phases. BRASP consistently incurs the lowest token-generation overhead. p. 0 The results show that BRASP effectively protects query privacy while incurring relatively low computation and communication overhead. p. 0 p. 0 BRASP achieves practical performance across secure index building, token generation, search, and update operations. p. 0

Conclusion

In this paper, BRASP presents a searchable encryption scheme for Boolean range queries over encrypted spatial data. BRASP combines Hilbertcurve-based spatial encoding, prefix-based range decomposition, and encrypted prefix–ID and keyword–ID indexes to support efficient query processing in the encrypted domain. p. 1 To protect query privacy beyond data confidentiality alone, BRASP integrates dual-server index shuffling and ID-field redistribution to hide both the search pattern and the access pattern. p. 3 The scheme further supports dynamic updates and achieves forward security, making it suitable for outsourced spatial databases whose contents evolve over time. p. 1 The results show that BRASP effectively protects query privacy while incurring relatively low computation and communication overhead. The source code of BRASP is publicly available at https://github. p. 0com/Egbert-Lannister/BRASP. p. 0

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Privacy-preserving spatial query capability: The improved AI system can perform Boolean range queries over encrypted spatial data while hiding both search patterns and access patterns, as BRASP enables users to query outsourced encrypted data while preserving data confidentiality.

  2. Search pattern obfuscation: The system can prevent an honest-but-curious cloud server from inferring user intent or returned records by integrating index shuffling for encrypted keyword and prefix entries with ID-field redistribution across two non-colluding cloud servers.

  3. Dynamic data ingestion support: The AI system can handle evolving databases by supporting dynamic updates, as BRASP supports dynamic updates and achieves forward security, allowing for the insertion of new objects without leaking information about earlier queries.

  4. Efficient spatial range filtering: By combining Hilbert curve-based prefix encoding with encrypted prefix–ID and keyword–ID indexes, the system can efficiently evaluate spatial range predicates and conjunctive keyword conditions, leading to lower computation overhead than baseline schemes in index building.

  5. Robust query unforgeability: The system ensures that no PPT adversary can produce a valid search token for an unseen Boolean range query without knowing the authorized client’s secret key, as BRASP achieves this if the proxy pseudorandom function T P F is collision-resistant.

Sources

Related papers