BRASP: Boolean Range Queries over Encrypted Spatial Data with Access and Search Pattern Privacy Jing Zhang1† , Ganxuan Yang1† , Yifei Yang1† , Siqi Wen2,1† , and Zhengyang Qiu1
arXiv:2604.07797v1 [cs.CR] 9 Apr 2026
Lancaster University Beijing Jiaotong University
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 Keywords: Privacy-preserving, Searchable symmetric encryption, Access pattern, Search pattern, Boolean range query.
1
Introduction
With the widespread adoption of mobile devices and geolocation technologies, Location-Based Services (LBS) have become an important component of modern data services. In many LBS applications, users issue spatial keyword queries to retrieve objects that satisfy both location and textual constraints. For example, †
These authors contributed equally to this work.
2
J. Zhang et al.
when a user searches for “coffee shops nearby” in a map application, the system must identify objects within a spatial range and then filter them according to the requested keywords. At the same time, cloud computing has made data outsourcing a common solution for scalable storage and query processing. Once spatial data are outsourced to an untrusted cloud server, however, preserving data confidentiality while still supporting efficient query processing becomes a central challenge. Searchable encryption provides an effective way to query encrypted outsourced data. Recent studies have proposed privacy-preserving spatial query schemes that support single-dimensional or multi-dimensional range filtering under encryption [9,20,15]. Nevertheless, many of these schemes mainly focus on protecting data contents and query functionality, while leaving side-channel leakages insufficiently addressed. In particular, search pattern leakage reveals whether two trapdoors correspond to the same query, and access pattern leakage reveals which encrypted objects match a query. By observing repeated queries and returned results, an honest-but-curious cloud server may infer sensitive information about user intent, query keywords, or result distributions. To reduce such leakages, several searchable encryption schemes have been proposed to protect either the search pattern, the access pattern, or both. For example, Tong et al. [21] proposed a verifiable privacy-preserving scheme for Boolean range queries that protects both patterns, and Song et al. [17] enhanced access-pattern privacy for spatial keyword similarity search. However, existing solutions still exhibit important limitations. First, many pattern-hiding schemes are designed for keyword queries and do not directly support Boolean range queries over encrypted spatial data [18,2,16,25,3,30]. Second, dynamic searchable symmetric encryption (DSSE) has made forward-secure updates increasingly important in practice, but most forward-secure constructions still focus on single-keyword or simple multi-keyword search [19,24,31,14,8,7]. Supporting Boolean range queries while simultaneously hiding both patterns and preserving update security remains challenging. To address these issues, we propose BRASP, a searchable encryption scheme for Boolean range queries over encrypted spatial data. BRASP combines Hilbertcurve-based prefix encoding with encrypted prefix–ID and keyword–ID inverted indexes, enabling efficient evaluation of spatial range predicates and conjunctive keyword conditions. To hide the search pattern and access pattern, BRASP introduces a dual-server design that combines index shuffling with ID-field redistribution, so that the cloud servers cannot stably link repeated trapdoors or query results across searches. In addition, BRASP supports dynamic updates and achieves forward security. The main contributions of this paper are summarized as follows: – We design BRASP, a searchable encryption scheme that supports Boolean range queries over encrypted spatial data by combining Hilbert-curve-based prefix encoding with encrypted prefix–ID and keyword–ID indexes. – We develop a dual-server pattern-hiding mechanism that integrates index shuffling and ID-field redistribution to protect both the search pattern and
BRASP
3
the access pattern. The scheme further supports dynamic updates and achieves forward security. – We formalize the security goals of BRASP in terms of confidentiality, shuffle indistinguishability, query unforgeability, and forward security, and we evaluate its efficiency through experiments on a real-world dataset.
2
Related Work
Privacy-preserving spatial query schemes aim to retrieve objects under spatial and keyword constraints without revealing sensitive plaintext information to the cloud server [6,10,11,26,27]. Early studies mainly focused on data confidentiality and secure query evaluation, while paying much less attention to the leakage of query patterns. For example, Cui et al. [4] designed a privacy-preserving Boolean spatial keyword query scheme based on ASPE, spatial-textual Bloom filters, and an R-tree-based secure index. Wang et al. [22] encoded spatial locations and keywords into vectors by using Gray codes and bitmaps to support secure spatial keyword queries. Miao et al. [12] proposed a unified encrypted index combined with an improved R-tree, while Zhang et al. [28] combined homomorphic encryption, spatial prefix encoding, and data packaging to support encrypted spatial queries. Although these schemes protect data contents, they usually generate deterministic or linkable trapdoors for repeated queries. As a result, the cloud server may still infer user interests or locations through search-pattern analysis. To mitigate query-pattern leakage, searchable symmetric encryption (SSE) and private information retrieval (PIR) have been extensively studied. Traditional SSE schemes are efficient for exact keyword search, but they typically leak the search pattern and the access pattern. PIR can hide the identity of retrieved records more thoroughly, but applying generic PIR directly to multidimensional spatial queries usually incurs high computational and communication costs. Therefore, spatial query systems require specialized constructions that simultaneously support expressive query functionality and strong pattern-hiding guarantees. Recent studies have started to address search-pattern and access-pattern leakage more explicitly. Zheng et al. [30] combined k-anonymous obfuscation, pseudo-random functions, and pseudo-random generators to protect search and access patterns for Boolean queries. However, k-anonymity only offers probabilistic protection and can still be vulnerable to background-knowledge attacks. Wang et al. [23] used additive homomorphic encryption together with an auxiliary server to hide both patterns, but the heavy use of homomorphic operations leads to substantial overhead on large datasets. Zhang et al. [29] adopted Bloom filters, Lagrange interpolation, and homomorphic encryption to hide the search pattern, but the interpolation procedure introduces considerable computational cost during query processing. Xie et al. [25] proposed a dynamic searchable encryption scheme based on distributed point functions and somewhat homomorphic encryption to protect the access pattern, although this design requires intensive inter-server communication. Tong et al. [21] further used a multi-server
4
J. Zhang et al.
architecture with distributed point functions and cuckoo hashing to protect access patterns for Boolean range queries. Compared with these approaches, BRASP is designed for Boolean range queries over encrypted spatial data in a lightweight dual-server setting. Our scheme combines Hilbert-curve-based prefix encoding with encrypted prefix– ID and keyword–ID indexes, and integrates index shuffling with ID-field redistribution to hide both the search pattern and the access pattern. In contrast to prior solutions that rely heavily on generic homomorphic computation or communication-intensive multi-server primitives, BRASP aims to provide a more practical balance between query expressiveness, pattern-hiding security, and search efficiency.
3
Problem Formulation
3.1
System Model
As illustrated in Fig. 1, the system involves four entities: a data owner (DO), an authorized client, and two non-colluding cloud servers CS1 and Index Shuffle CS2 . Index Shuffle Data Owner (DO). The DO owns Cloud Server Cloud Server CS CS the spatio-textual database. It initializes the system parameters, encrypts ① Secure indexes ③ Query trapdoor the outsourced objects and index en- 5 Index / Update token Redistribution tries, and builds the encrypted prefix– ID and keyword–ID indexes. The DO then splits the encrypted indexes into ②Authorization two shares and outsources them to 5 Index Redistribution Data Owner Client CS1 and CS2 , respectively (Step ①). Fig. 1: System model. Authorized Client. The client is authorized by the DO to issue Boolean range queries over the encrypted database. For each query, the client generates keyword and prefix trapdoors and sends them to the two cloud servers. After receiving the encrypted query results, the client combines the partial results, obtains the final answer, and refreshes the corresponding ID-field shares for index redistribution. For updates, the client generates update tokens and uploads them to the cloud servers (Steps ② and ④). Cloud Servers CS1 and CS2 . Each cloud server stores one share of the encrypted indexes and the outsourced encrypted objects. Before the first query and after each subsequent query, CS1 and CS2 jointly execute the index-shuffle procedure to re-randomize index entries and permute their positions. Upon receiving the query trapdoors, the two servers search their local index shares, process the encrypted ID fields according to the protocol, and return the corresponding encrypted results to the client (Step ③). 1
2
④ Query results
BRASP
3.2
5
Threat Model
We assume that the data owner (DO) and the authorized client are trusted parties that follow the protocol honestly. The DO correctly generates encrypted indexes and encrypted spatial objects, and the client correctly generates query trapdoors and update tokens. The two cloud servers, CS1 and CS2 , are assumed to be non-colluding and honest-but-curious. That is, they follow the prescribed protocols for index shuffling, search, and update processing, but each server attempts to infer additional information from the encrypted indexes, query trapdoors, update tokens, and observed query results available to it. In particular, the adversarial goal is to learn information about query keywords, query ranges, repeated queries, or returned objects beyond the leakage explicitly allowed by the security definition. We do not consider collusion between CS1 and CS2 , nor do we consider side-channel leakages outside the protocol transcript.
4
Preliminaries This section describes the techniques employed in the proposed scheme.
4.1
Tailored Proxy Pseudorandom Function (TPF)
In BRASP, the keyword and prefix fields are re-randomized during index shuffling. Instead of using a full proxy re-encryption system for these fields, we adopt a lightweight tailored proxy pseudorandom function (TPF) derived from the one-way re-encryption technique in [1]. This design reduces the cost of repeated index updates while preserving the re-encryption capability required by the shuffle procedure. The TPF construction consists of four algorithms: TPF.KeyGen, TPF.Rnd, TPF.RecKeyGen, and TPF.ReEnc. Let G be a cyclic group of order q, and let FG : {0, 1}∗ → G be a pseudorandom mapping. – TPF.KeyGen(1λ ) → k: On input a security parameter λ, output a secret key k. – TPF.Rnd(k, m) → s: On input a secret key k and a message m, output the pseudorandom string s = FG (m)k . – TPF.RecKeyGen(k1 , k2 ) → rk1→2 : On input two secret keys k1 and k2 , output a re-encryption key rk1→2 = k2 /k1 . – TPF.ReEnc(s, rk1→2 ) → s′ : Given as input a pseudorandom string s and a re-encryption key rk1→2 , the re-encryption algorithm outputs a pseudorandom string s′ under the target key. Intuitively, this algorithm converts the pseudorandom string generated with respect to key k1 into a corresponding pseudorandom string associated with key k2 , while preserving the underlying message. Formally, if s = T P F.Rnd(k1 , m) for some message m, then the output satisfies T P F.ReEnc(s, rk1→2 ) = T P F.Rnd(k2 , m).
6
J. Zhang et al.
4.2
Tailored Universal Re-Encryption (TUR)
In BRASP, each ID field is protected by a tailored universal re-encryption mechanism instantiated from the additive homomorphic Paillier cryptosystem P aillier = (KeyGen, Enc, Dec, Add) [13] and the universal re-encryption idea of [5]. The goal of TUR is twofold: it re-randomizes the encrypted bitmap shares during index shuffling, and it prevents either cloud server from decrypting an ID field on its own. To this end, BRASP employs a two-step decryption procedure. TUR consists of six algorithms: TUR.Setup, TUR.KeyGen, TUR.Enc, TUR.ReEnc, TUR.PDec, and TUR.Dec. – TUR.Setup(1λ ) → (sk, pk): On input a security parameter λ, then run P aillier.KeyGen(1λ ) and output the master secret key sk and the master public key pk. – TUR.KeyGen(sk) → pdk1 , pdk2 : On input the master secret key sk, derive two partial decryption keys pdk1 and pdk2 . – TUR.Enc(m, pk) → C: On input a plaintext m and the master public key pk, output the ciphertext C = P aillier.Enc(m, pk). – TUR.ReEnc(C, pk) → C ′ : On input a ciphertext C and the master public key pk, output the re-randomized ciphertext C ′ = C · P aillier.Enc(0, pk). – TUR.PDec(C, pdki ) → Ci : On input a ciphertext C and a partial decryption key pdki , output the partially decrypted ciphertext Ci . – TUR.Dec(Ci , pdkj ) → m: On input a partially decrypted ciphertext Ci and the complementary partial decryption key pdkj , output the plaintext m. 4.3
Hilbert Curve
A Hilbert curve recursively partitions a square region into four smaller regions and connects their centers with a continuous space-filling curve. In a ddimensional space, if each dimension is evenly partitioned into 2j intervals, then the whole space is partitioned into 2dj cells, where j is the order of the Hilbert curve. The center of each cell is assigned a one-dimensional value, referred to as its Hilbert value. By mapping each spatial object to the Hilbert value of the cell containing it, BRASP converts multidimensional spatial locations into onedimensional values while largely preserving spatial locality. Example 1. A basic illustration of a third-order Hilbert curve in a two-dimensional space is shown in Fig. 2. Each spatial object is mapped to a one-dimensional value loci by the Hilbert curve. If the client wishes to retrieve objects in range R1 or R2 , it can issue a query with R1 = [20, 24] or R2 = {[45, 51], [54, 55]}. 4.4
Prefix Membership Verification Scheme
To improve search efficiency, BRASP adopts a prefix membership verification scheme. The key idea is to preprocess Hilbert values into prefix families so that
BRASP
Fig. 2: Examples of Hilbert curve.
7
Fig. 3: An example of a BRQ.
Fig. 4: Example of a prefix membership verification scheme for queries.
membership in a range cover can be tested efficiently. Given a γ-bit Hilbert value X = a1 a2 . . . aγ , its prefix family is P(X) = {a1 a2 . . . aγ , a1 a2 . . . aγ−1 ∗, . . . , a1 ∗ . . . ∗, ∗ ∗ . . . ∗}. The i-th prefix element in P(X) is a1 a2 . . . aγ−i+1 ∗. . . ∗. Given a range [rmin , rmax ], let G([rmin , rmax ]) denote the minimum set of prefix elements whose union covers the range. If X ∈ [rmin , rmax ], then P(X) ∩ G([rmin , rmax ]) ̸= ∅. Example 2. Fig. 4 illustrates a spatial range query using the Hilbert curve and the prefix membership verification scheme. We represent the Hilbert values of the five spatial objects in Fig. 2 as prefix families. When the client queries all spatial objects in R1 = {[20, 24], [54, 55]}, the range is first converted into the minimum prefix cover G = {0101 ∗ ∗, 011000}. Since 0101 ∗ ∗ ∈ P(loc4 ), object O4 lies in R1 . To query all spatial objects in R2 = {[45, 51], [54, 55]}, the client converts R2 into the minimum prefix cover G = {101 ∗ ∗, 1100 ∗ ∗, 11011∗}. Because the prefix family of loc5 matches 101 ∗ ∗ and the prefix family of loc2 matches 1100 ∗ ∗, objects O2 and O5 lie in R2 .
8
J. Zhang et al.
4.5
Problem Definition
Let DB = {O1 , . . . , On } be a spatio-textual database owned by DO, where each object is denoted by Oi = (loci , Wi ), loci is the spatial location of Oi , and Wi is the set of keywords associated with Oi . Given a query Q = (Rq , Wq ) issued by an authorized client, Rq denotes the query range and Wq denotes the set of query keywords. Definition 1 (Privacy-Preserving Boolean Range Query (PBRQ)). Given an encrypted spatio-textual database EDB and a query token generated from Q = (Rq , Wq ), a privacy-preserving Boolean range query returns the set ∆(Q) = {Oi ∈ DB | loci ∈ Rq and Wq ⊆ Wi }. That is, an object Oi matches the query if and only if its location lies in the query range and it contains all query keywords. Example 3. An illustration of a Boolean range query is shown in Fig. 3. Suppose DB = {O1 , . . . , O5 } and the keyword universe is W = {w1 , . . . , w8 }. The client issues a query Q = (Rq , Wq ), where Wq = {w4 , w6 } and the blue region in Fig. 3 is the query range Rq . The objects O2 and O5 lie in Rq , but only O5 contains both w4 and w6 . Therefore, the final query result is {O5 }. Definition 2 (BRASP). Given an encrypted spatio-textual database EDB and a query token generated from Q = (Rq , Wq ), BRASP returns a collection of ciphertexts {ci }bi=1 corresponding to the objects in ∆(Q) = {Oi ∈ DB | loci ∈ Rq and Wq ⊆ Wi }, while hiding the search pattern and access pattern from the cloud servers. A BRASP scheme consists of the following seven algorithms: – Setup(1λ ) → K: On input a security parameter λ, output the secret key material K. – EncryptedIndexBuild(I¯h , I¯w , K) → (Ih , Iw ): On input the plaintext prefix index I¯h , the plaintext keyword index I¯w , and the key material K, output two encrypted indexes Ih and Iw . – IndexShuffle(Ih , Iw , ri , rj ) → (Ieh , Iew ): On input the encrypted indexes and two shuffle parameters ri , rj , output shuffled encrypted indexes. – TokenGeneration(Q, K, Uwk , Uhk , ri , rj ) → (Tw , Th ): On input the query Q, the key material K, the current shuffle states Uwk and Uhk , and the shuffle parameters ri , rj , output the keyword trapdoor set Tw and the prefix trapdoor set Th . – Search(Ih , Iw , Tw , Th ) → C(Q): On input the encrypted indexes and the query trapdoors, output the encrypted query result C(Q). – IndexRedistribution(Ih , Iw ) → (Ih′ , Iw′ ): On input the encrypted indexes, output refreshed encrypted indexes with redistributed ID fields. – Update(Ihi , Iwi , U Thi , U Twi ) → (IUhi , IUwi ): On input the encrypted indexes stored at CSi and the update tokens, output the updated encrypted indexes.
BRASP
9
Definition 3 (Access Pattern). Let H = (Q1 , . . . , Qt ) be a query history over DB, where each query is of the form Qℓ = (Rℓ , Wℓ ). Let ∆(Qℓ ) denote the set of objects matching Qℓ . The access pattern of H is defined as α(H) = (∆(Q1 ), ∆(Q2 ), . . . , ∆(Qt )). Equivalently, it can be represented as a t × n binary matrix such that ( 1, if Oj ∈ ∆(Qℓ ), α(H)[ℓ, j] = 0, otherwise.
(1)
The access pattern reveals which encrypted objects are returned for each query in the query history. Definition 4 (Search Pattern). Let H = (Q1 , . . . , Qt ) be a query history, where each Qℓ = (Rℓ , Wℓ ). The search pattern of H is defined as the t × t binary matrix ( 1, if Qℓ = Qm , σ(H)[ℓ, m] = (2) 0, otherwise. That is, the search pattern reveals whether two query trapdoors correspond to the same Boolean range query.
5
Scheme Construction
In this section, we initially present the construction of BRASP scheme. Next, we give a detailed construction of our scheme. 5.1
Index Construction
To support efficient search over encrypted spatio-textual data, BRASP builds two plaintext inverted indexes before encryption: a prefix–ID index I¯h and a keyword–ID index I¯w . An entry of I¯h is of the form (h, Bh ), where h is a prefix element and Bh is an n-bit bitmap whose i-th bit is 1 if and only if the location of Oi is covered by h. An entry of I¯w is of the form (w, Bw ), where w is a keyword and Bw [i] = 1 if and only if w ∈ Wi . These two indexes are illustrated in Fig. 5. For the prefix–ID index, we use a third-order Hilbert curve. This setting yields 384 possible prefix elements for the Hilbert values in the database, excluding the all-wildcard string “******”. To hide query patterns, each bitmap is split into two shares, and the resulting index shares are stored separately at CS1 and CS2 . Consequently, each cloud server maintains one sub-prefix–ID index and one sub-keyword–ID index. After a query is processed, the client refreshes the corresponding ID-field shares during index redistribution so that the two servers do not retain a stable view of the same search result. During the subsequent index-shuffle phase, the keyword field, prefix field, and ID field are re-randomized, and the entries are randomly permuted. As a result, both the ciphertexts and the physical positions of index entries change across queries, which helps conceal both the search pattern and the access pattern.
10
J. Zhang et al.
Prefix - ID
Keyword - ID
Fig. 5: Two inverted indexes of spatio-textual database:(a):Prefix-ID inverted index and (b):Keyword-ID inverted index
5.2
Our Proposed Scheme
In this subsection, we give the detailed construction of BRASP. For consistency, we use the following notation throughout. The key kM is the master key ID ID ) is the mas, skM used to encode the keyword and prefix fields. The pair (pkM ID ter public/secret key pair for the ID field. The values sk1 and sk2ID are the ID two partial decryption keys derived from skM . The value ku is the secret key of an authorized client, and rku→M denotes the authorization re-encryption key from ku to kM . A superscript i ∈ {1, 2} indicates that the corresponding index or ciphertext share is stored at CSi .
Algorithm 1: Setup Input: security parameter λ, T P F , T U R; Output: system parameters and secret material for DO, the client, CS1 , and CS2 ; λ 1 kM ← T P F.KeyGen(1 ); ID λ ID 2 (skM , pkM ) ← T U R.Setup(1 ); ID ID ID 3 (sk1 , sk2 ) ← T U R.KeyGen(skM ); $
r 1 , r2 , kT , k O ← Z + ; ID ID 5 send (pkM , r1 , sk1 ) to CS1 ; ID ID 6 send (pkM , r2 , sk2 ) to CS2 ; ID 7 send (r1 , r2 , pkM , kT , kO ) to the client; 4
Setup. The setup procedure is given in Algorithm 1. DO first generates the masID ID ter key kM for the keyword and prefix fields and the master key pair (pkM , skM ) ID for the ID field. The master secret material (kM , skM ) is retained by DO and is
BRASP
11
Algorithm 2: Encrypted Index Build Input: plaintext prefix index I¯h = {(hi , idih )}pi=1 , plaintext keyword index ID I¯w = {(wi , idiw )}m i=1 , kM , pkM , T P F , T U R; Output: encrypted indexes Ih , Iw ; i 1 Ih ← ∅, Iw ← ∅; foreach (hi , idh ) ∈ I¯h do ID 2 hsi ← T P F.Rnd(kM , hi ); IDhi ← T U R.Enc(idih , pkM ); Ih .add(hsi , IDhi ); i 3 foreach (wi , idw ) ∈ I¯w do ID 4 wsi ← T P F.Rnd(kM , wi ); IDwi ← T U R.Enc(idiw , pkM ); Iw .add(wsi , IDwi ); 5
return (Ih , Iw );
never disclosed to either cloud server. DO then derives the two partial decryption keys sk1ID and sk2ID , samples the shuffle parameters r1 , r2 , the tag-derivation key kT , and the object-encryption key kO , and distributes only the information required by each party. For an authorized client with secret key ku , DO additionally computes the authorization key rku→M = T P F.RecKeyGen(ku , kM ) and sends it to the cloud servers so that client-generated tokens can later be transformed into tokens matching the encrypted indexes.
Algorithm 3: Index Shuffle in CS1 1 ID , r1 , r2 , T P F , T U R; Input: encrypted indexes Ih1 and Iw stored on CS1 , pkM 1 Output: shuffled encrypted indexes Ieh1 , Iew ; 1 1 1 Cloud CS1 : send (Ih , Iw ) to CS2 ; 2 Cloud CS2 : foreach k ∈ {h, w} do 3 INk ← ∅; foreach (s, ID, τ ) ∈ Ik1 do ID ); τ ′ ← τ + 1; 4 s′ ← T P F.ReEnc(s, r2 ); ID′ ← T U R.ReEnc(ID, pkM ′ ′ ′ INk .insert(s , ID , τ );
5
randomly permute INk ;
send (INh , INw ) to CS1 ; 7 Cloud CS1 : foreach k ∈ {h, w} do 8 Iek1 ← ∅; foreach (s′ , ID′ , τ ′ ) ∈ INk do ID c ← T U R.ReEnc(ID′ , pkM 9 sb ← T P F.ReEnc(s′ , r1 ); ID ); τb ← τ ′ + 1; 1 c τb); Iek .insert(b s, ID, 10 randomly permute Iek1 ; 6
11
1 return (Ieh1 , Iew );
Encrypted Index Build. Algorithm 2 transforms the plaintext prefix index I¯h and plaintext keyword index I¯w into their encrypted counterparts. For each entry, BRASP computes a pseudorandom label using T P F and encrypts the
12
J. Zhang et al.
Algorithm 4: Token Generation Input: client key ku , keyword set Wq , query prefix family QP , shuffle states {Uwk }wk ∈Wq and {Uhk }hk ∈QP , r1 , r2 , T P F ; Output: keyword trapdoor set Tw and prefix trapdoor set Th ; 1 Tw ← ∅, Th ← ∅; 2 foreach wk ∈ Wq do 3 tk ← ku · (r1 r2 )Uwk ; Twk ← T P F.Rnd(tk , wk ); Tw ← Tw ∪ {Twk }; 5
foreach hk ∈ QP do vk ← ku · (r1 r2 )Uhk ; Thk ← T P F.Rnd(vk , hk ); Th ← Th ∪ {Thk };
6
return (Tw , Th );
4
corresponding bitmap share using T U R. The resulting encrypted indexes are denoted by Ih and Iw .
Assets
Assets
Assets
Assets
Assets
Assets
Fig. 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. Algorithm 3 illustrates the shuffle procedure for the index shares stored at CS1 ; the procedure for the shares stored at CS2 is symmetric. As shown in Fig. 6, the keyword and prefix labels are re-encrypted using T P F.ReEnc, the ID fields are re-randomized using T U R.ReEnc, and the entries are then randomly permuted. The state tag associated with each entry is incremented after every shuffle so that the client can generate fresh search and update tokens consistent with the current shuffled view.
BRASP
13
Token Generation. Algorithm 4 shows how the client generates the search tokens. For each query keyword wk ∈ Wq and each query prefix hk ∈ QP , the client derives a shuffle-aware key from ku , r1 , r2 , and the current shuffle state. It then computes a token using T P F.Rnd. During authorization, DO provides the cloud servers with the re-encryption key rku→M = T P F.RecKeyGen(ku , kM ), allowing the servers to transform client-generated tokens into tokens matching the current encrypted indexes. Search. Algorithm 5 describes the search phase jointly executed by the two cloud servers. After receiving the trapdoors (Tw , Th ), CS2 re-encrypts them with rku→M so that they match the labels in the current encrypted indexes. It then partially decrypts the matched ID fields and sends the partially decrypted bitmaps to CS1 . Finally, CS1 completes the decryption, reconstructs the matching object sets, unions the prefix matches, intersects the keyword matches, and outputs the encrypted query result.
Algorithm 5: Search and Result Recovery 2 Input: trapdoor sets Tw and Th , encrypted indexes Ih2 and Iw stored on CS2 , encrypted object set C1 stored on CS1 , partial decryption keys sk1ID and sk2ID , authorization key rku→M , T P F , T U R; Output: encrypted result set C1 (Q); 2 2 1 Cloud CS2 : SIh ← ∅, SIw ← ∅; foreach Thk ∈ Th do c 2h ← Ih2 .f ind(ThM ); 2 ThM ← T P F.ReEnc(Th , rku→M ); ID k
k
k
2
k
c h , sk2ID ); SIh2 ← SIh2 ∪ {IDh2 }; IDh2 k ← T U R.P Dec(ID k k 3 4
foreach Twk ∈ Tw do
2
2 c w ← Iw .f ind(TwMk ); TwMk ← T P F.ReEnc(Twk , rku→M ); ID k 2 2 2 2 2 c w , sk2ID ); SIw IDw ← T U R.P Dec(ID ← SIw ∪ {IDw }; k
k
k
2 ) to CS1 ; send (SIh2 , SIw 1 1 2 2 6 Cloud CS1 : Ch ← ∅; Cw ← C1 ; foreach IDhk ∈ SIh do ID 2 7 Bhk ← T U R.Dec(IDhk , sk1 ); Shk ← FindByBitmap(Bhk , C1 ); Ch1 ← Ch1 ∪ Shk ;
5
2 2 foreach IDw ∈ SIw do k 2 9 Bwk ← T U R.Dec(IDw , sk1ID ); Swk ← FindByBitmap(Bwk , C1 ); k 1 1 Cw ← Cw ∩ Swk ;
8
10
1 C1 (Q) ← Ch1 ∩ Cw ; return C1 (Q);
Index Redistribution. After each search, the client aggregates the encrypted results returned from the two cloud servers, re-splits the corresponding object identifiers into two fresh bitmap shares, and sends the refreshed ID fields back to CS1 and CS2 . This step refreshes each server’s local view of the search result and prevents either server from linking the redistributed ID fields to the previous
14
J. Zhang et al.
result view. The refreshed ID fields are re-randomized again during the next index-shuffle phase. Update. The update procedure consists of two phases: client-side update-token generation and server-side index refresh. The client first generates update tokens for a newly inserted object, and the two cloud servers then update the encrypted indexes without learning the update positions in plaintext. Client-side update-token generation. Algorithm 6 generates update tokens for a newly inserted object On+1 = (locn+1 , Wn+1 ). Let P (On+1 ) denote the set of prefix elements derived from locn+1 . For each prefix or keyword, the client creates two bitmap shares, encrypts them with T U R, and derives the corresponding labels and tags. Existing keywords and prefixes are mapped to shuffled positions using Pk and the current shuffle states, whereas a newly appearing keyword is inserted directly as a fresh entry. For clarity, we use domain-separated tags F (kT , (1, x)) and F (kT , (2, x)) for the two cloud views of the same logical entry.
Algorithm 6: Update Token Generation Input: client key ku , new object On+1 , keyword state set {Uwk }wk ∈Wn+1 , prefix state set {Uhk }hk ∈P (On+1 ) , tag key kT , pseudorandom function ID , T P F , T U R; F , permutation function Pk , r1 , r2 , pkM w1 h2 h1 Output: update-token sets U TO , U TO , U TO , U TOw2 ; h h w w 1 U TO1 , U TO2 , U TO 1 , U TO 2 ← ∅; 2 foreach hk ∈ P (On+1 ) do 3
4 5
6 7
8 9 10
11 12 13
$
Bh1k ← 0, Bh2k ← 0; b ← {1, 2}; Bhb k [ID(On+1 )] ← 1; ID ID ); ); IDh2 k ← T U R.Enc(Bh2k , pkM IDh1 k ← T U R.Enc(Bh1k , pkM τh1k ← F (kT , (1, hk )); τh2k ← F (kT , (2, hk )); for j ← 1 to Uhk do τh1k ← F (F (τh1k , r2 ), r1 ); τh2k ← F (F (τh2k , r1 ), r2 ); p1 ← Pk (τh1k ); p2 ← Pk (τh2k ); U TOh1 .insert(p1 , IDh1 k , ⊥); U TOh2 .insert(p2 , IDh2 k , ⊥); foreach wk ∈ Wn+1 do $
1 2 b Bw ← 0, Bw ← 0; b ← {1, 2}; Bw [ID(On+1 )] ← 1; k k k 1 1 ID wsk ← T P F.Rnd(ku , wk ); IDwk ← T U R.Enc(Bw , pkM ); k 2 2 ID 1 IDwk ← T U R.Enc(Bwk , pkM ); τwk ← F (kT , (1, wk )); τw2 k ← F (kT , (2, wk )); if Uwk > 0 then for j ← 1 to Uwk do τw1 k ← F (F (τw1 k , r2 ), r1 ); τw2 k ← F (F (τw2 k , r1 ), r2 ); 1 l1 ← Pk (τw1 k ); l2 ← Pk (τw2 k ); U TOw1 .insert(l1 , IDw , ⊥); k w2 2 U TO .insert(l2 , IDwk , ⊥);
else 1 2 U TOw1 .insert(wsk , IDw , τw1 k ); U TOw2 .insert(wsk , IDw , τw2 k ); k k return (U TOh1 , U TOh2 , U TOw1 , U TOw2 );
BRASP
15
Server-side update for the keyword–ID index at CS1 . Algorithm 7 shows how CS1 and CS2 collaboratively refresh the keyword–ID index stored at CS1 . CS1 first permutes the stored entries and hides their labels, after which CS2 applies the update tokens to the permuted view. Because CS1 does not know the permuted update positions and CS2 never observes the original index order, the update process preserves forward security. Here ⊕ denotes the homomorphic combination of encrypted bitmap shares supported by the underlying Paillierbased construction. The update procedure for the prefix–ID index is analogous.
Algorithm 7: Update the Keyword–ID Index at CS1 Input: keyword update-token set U TOw1 , encrypted object c, encrypted object set C1 stored on CS1 , authorization key rku→M , encrypted keyword 1 ID , T P F , T U R; index Iw stored on CS1 , permutation function Pk , pkM 1 e e1 ; Output: updated keyword index Iw and updated encrypted object set C 1 1 1 1 Cloud CS1 : Lw ← ∅; foreach (ws, IDw , τw ) ∈ Iw do 1 ID ); 2 p ← Pk (τw1 ); Lw [p] ← T U R.ReEnc(IDw , pkM send Lw to CS2 ; Cloud CS2 : foreach (p, ·) ∈ Lw do 5 if there exists (p, ∆ID, ·) ∈ U TOw1 then 6 Lw [p] ← Lw [p] ⊕ ∆ID; remove (p, ∆ID, ·) from U TOw1 ;
3 4
7 8
else ID ); Lw [p] ← T U R.ReEnc(Lw [p], pkM
send (Lw , U TOw1 ) to CS1 ; 1 1 1 1 10 Cloud CS1 : Iew ← ∅; foreach (ws, IDw , τw ) ∈ Iw do 1 1 1 e 11 p ← Pk (τw ); Iw .insert(ws, Lw [p], τw ); 9
1 foreach (ws, IDw , τw1 ) ∈ U TOw1 do 1 1 13 Rw ← T P F.ReEnc(ws, rku→M ); Iew .insert(Rw , IDw , τw1 );
12
14
6
1 e e1 ← C1 .insert(c); return (Iew C , C1 );
Security Analysis
In this section, we analyze BRASP with respect to four properties: confidentiality, shuffle indistinguishability, query unforgeability, and forward security. For readability, the main text states each notion, theorem, and proof sketch, whereas the full arguments are given in Appendix B, C, D and E. 6.1
Confidentiality
Confidentiality requires that an honest-but-curious cloud server should learn no information about the plaintext objects, queried keywords, or queried ranges
16
J. Zhang et al.
beyond the explicitly allowed leakage. We formalize this property in the standard real-world/ideal-world framework with respect to a leakage function collection L = (LQuery , LUpdate ). Let RealA (ζ) denote the experiment in which a probabilistic polynomialtime adversary A interacts with the real BRASP protocol, and let IdealA,S (ζ) denote the experiment in which A interacts with a simulator S that receives only the leakage specified by L. BRASP is said to be L-confidential against adaptive chosen-keyword attacks if, for every PPT adversary A, there exists a PPT simulator S such that |Pr[RealA (ζ) = 1] − Pr[IdealA,S (ζ) = 1]| ≤ negl(ζ).
(3)
Theorem 1. BRASP is L-confidential against adaptive chosen-keyword attacks if T P F and F are secure pseudorandom functions. Proof. The proof is by a sequence of hybrids that gradually replace the real keyword encodings, prefix encodings, tags, and re-randomized ID fields with simulated values that are consistent with the leakage function collection L. Because the two cloud servers are assumed to be non-colluding, the simulator only needs to reproduce the view of each server separately. Adjacent hybrids are computationally indistinguishable under the pseudorandomness of T P F and F , and the resulting simulated transcript depends only on LQuery and LUpdate . Therefore the real and ideal experiments are indistinguishable up to negligible advantage. The detailed hybrid argument is given in Appendix B.
6.2
Shuffle Indistinguishability
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. Theorem 2. BRASP achieves shuffle indistinguishability if T P F and F are secure pseudorandom functions and the ciphertexts output by T U R.ReEnc are computationally unlinkable to their pre-re-randomization form. Proof. Each shuffle applies three independent hiding steps: the keyword/prefix component is re-encrypted by T P F.ReEnc, the bitmap component is re-randomized by T U R.ReEnc, and the tag is refreshed by F ; the resulting entries are then randomly permuted. Consequently, even if a cloud server knows the shuffled multiset of entries, it does not know which fresh representation corresponds to any particular pre-shuffle entry. Any adversary that links a shuffled entry to its predecessor with non-negligible advantage can be used either to distinguish the outputs of T P F or F from random, or to violate the unlinkability of the re-randomized T U R ciphertexts. The detailed reduction appears in Appendix C.
BRASP
6.3
17
Query Unforgeability
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. Theorem 3. BRASP achieves query unforgeability if the proxy pseudorandom function T P F is collision-resistant. Proof. A valid search token must remain consistent with both the client’s secret key and the current shuffle state after the cloud applies the authorization reencryption step. Hence, for an unseen query, any successful forgery must either induce the same valid T P F image as an honestly generated token for a different input, or produce a fresh valid image that is consistent with an unknown secretkey-dependent input. The former event is exactly a collision in the T P F image space, and the latter would contradict the assumed hardness embodied in the keyed T P F construction. Therefore the success probability of a polynomial-time forger is negligible. The full argument is given in Appendix D. 6.4
Forward Security
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. Theorem 4. BRASP achieves forward security if T P F is collision-resistant and the ciphertexts produced by T U R remain unlinkable under re-randomization. Proof. Update tokens are generated from the current shuffle state and are therefore unlinkable to the tokens observed before the update unless the adversary can correlate two different T P F states. Moreover, the bitmap shares inserted by the update procedure are encrypted under T U R and are further re-randomized by subsequent shuffles, so their ciphertext representations cannot be linked to prior search views. Thus, linking a newly inserted entry to a pre-update query would require either breaking the state-dependent protection of T P F or defeating the unlinkability of re-randomized T U R ciphertexts, both of which occur only with negligible probability. The complete proof is given in Appendix E.
7
Experiment
In our experiments, we use the Yelp business dataset1 as a real-world spatiotextual benchmark. All experiments are implemented in Python 3.12 and conducted on a 64-bit Windows 11 machine with 16 GB RAM and an AMD Ryzen 5 3500U CPU with Radeon Vega Mobile Graphics at 2.10 GHz. We focus on the computation and communication overhead of four representative phases: secure index building, token generation, search, and update. Additional implementation details and workload settings are reported in Appendix F 1
https://business.yelp.com/dataset
18
J. Zhang et al.
(a)
(b)
(c)
(d)
Fig. 7: Performance of Secure Index Building.
(a)
(b)
Fig. 8: Performance of Token Generation.
Secure Index Building. Fig. 7 compares the secure-index-building performance of VPBRQSupL , PPSKS, and BRASP. Fig. 7a and Fig. 7c report the computation overhead as the number of spatial objects and the number of indexed keywords increase, respectively, whereas Fig. 7b and Fig. 7d report the corresponding communication overhead. In all four settings, BRASP achieves lower overhead than VPBRQSupL and PPSKS. This advantage is consistent with
BRASP
19
the design of BRASP: it constructs encrypted prefix–ID and keyword–ID indexes using lightweight TPF/TUR-based processing, while the baseline schemes rely on heavier cryptographic operations during index construction. Token Generation. Fig. 8 reports the token-generation performance of the three schemes. Fig. 8a shows the computation overhead as the number of query keywords increases, and Fig. 8b shows the corresponding communication overhead. BRASP consistently incurs the lowest token-generation overhead. This result is expected because BRASP generates keyword and prefix trapdoors through lightweight pseudorandom encodings, whereas the baselines use more expensive distributed or homomorphic primitives.
(a)
(b)
(c)
(d)
(e)
(f)
Fig. 9: Performance of Search.
Search. Fig. 9 compares the search performance of the three schemes. For VPBRQSupL , the reported search cost includes multi-cloud retrieval together with client-side verification and decryption. For BRASP, the reported cost includes dual-server retrieval and the subsequent index-shuffle procedure used to hide search and access patterns. Fig. 9a and Fig. 9b vary the number of spatial objects, Fig. 9c and Fig. 9d vary the number of indexed keywords, and Fig. 9e and Fig. 9f vary the number of query keywords. Across all three workloads, BRASP achieves substantially lower computation overhead than the baselines. Its communication overhead is moderately higher than that of the baseline schemes in some settings, which is mainly due to the extra inter-server interaction introduced by shuffling and result obfuscation. Overall, the results show that BRASP
20
J. Zhang et al.
(a)
(b)
Fig. 10: Performance of Update.
significantly reduces the dominant computation cost of search while maintaining practical communication overhead.
Update. Fig. 10 reports the update overhead of BRASP under different database sizes and update workloads. In Fig. 10a, the three curves correspond to updating 10, 100, and 1000 objects, respectively, and the computation overhead increases with both the number of spatial objects and the number of updated objects. Fig. 10b reports the total communication overhead between CS1 and CS2 during the update process, which also increases as the database size and the update workload grow. These results are consistent with the cost of refreshing encrypted bitmap shares and maintaining the shuffled encrypted indexes after each update.
8
Conclusion
In this paper, we presented BRASP, 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. 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. The scheme further supports dynamic updates and achieves forward security, making it suitable for outsourced spatial databases whose contents evolve over time. We formalized the security goals of BRASP in terms of confidentiality, shuffle indistinguishability, query unforgeability, and forward security, and provided corresponding analyses. Experimental results on the Yelp dataset show that BRASP achieves practical performance across secure index building, token generation, search, and update operations, while substantially reducing search-side computation overhead.
BRASP
21
References 1. Blaze, M., Bleumer, G., Strauss, M.: Divertible protocols and atomic proxy cryptography. In: International conference on the theory and applications of cryptographic techniques. pp. 127–144. Springer (1998) 2. Chang, Z., Xie, D., Wang, S., Li, F., Shen, Y.: Towards practical oblivious join processing. IEEE Transactions on Knowledge and Data Engineering (2023) 3. 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) 4. 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) 5. 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, Proceedings. pp. 163–178. Springer (2004) 6. Gong, Z., Li, J., Lin, Y., Wei, J., Lancine, C.: Efficient privacy-preserving geographic keyword boolean range query over encrypted spatial data. IEEE Systems Journal 17(1), 455–466 (2022) 7. 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 Computing 21(2), 746–763 (2023) 8. 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 Computing 11(1), 336–348 (2021) 9. 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 Information Forensics and Security (2024) 10. 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 Computing 16(5), 3621–3635 (2023) 11. 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) 12. 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 Engineering 36(1), 122–136 (2023) 13. Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: International conference on the theory and applications of cryptographic techniques. pp. 223–238. Springer (1999) 14. Patranabis, S., Mukhopadhyay, D.: Forward and backward private conjunctive searchable symmetric encryption. Cryptology ePrint Archive (2020) 15. 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 Internet of Things Journal 9(16), 15285–15296 (2022) 16. Shang, Z., Oya, S., Peter, A., Kerschbaum, F.: Obfuscated access and search patterns in searchable encryption. arXiv preprint arXiv:2102.09651 (2021)
22
J. Zhang et al.
17. 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 Journal 9(8), 6184–6198 (2021) 18. Song, Q., Liu, Z., Cao, J., Sun, K., Li, Q., Wang, C.: Sap-sse: Protecting search patterns and access patterns in searchable symmetric encryption. IEEE Transactions on Information Forensics and Security 16, 1795–1809 (2020) 19. Song, X., Dong, C., Yuan, D., Xu, Q., Zhao, M.: Forward private searchable symmetric encryption with optimized i/o efficiency. IEEE Transactions on Dependable and Secure Computing 17(5), 912–927 (2018) 20. Sun, L., Zhang, Y., Zheng, Y., Song, W., Lu, R.: Towards efficient and privacypreserving high-dimensional range query in cloud. IEEE Transactions on Services Computing 16(5), 3766–3781 (2023) 21. Tong, Q., Li, X., Miao, Y., Wang, Y., Liu, X., Deng, R.H.: Beyond result verification: Efficient privacy-preserving spatial keyword query with suppressed leakage. IEEE Transactions on Information Forensics and Security (2024) 22. 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– 2262. IEEE (2020) 23. Wang, Y., Sun, S.F., Wang, J., Liu, J.K., Chen, X.: Achieving searchable encryption scheme with search pattern hidden. IEEE Transactions on Services Computing 15(2), 1012–1025 (2020) 24. Wu, Z., Li, K.: Vbtree: forward secure conjunctive queries over encrypted data for cloud computing. The VLDB journal 28(1), 25–46 (2019) 25. 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) 26. 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 Information Forensics and Security 14(4), 870–885 (2018) 27. Xu, T., Ge, X., Shao, C.: Pmkr: Privacy-preserving multi-keyword top-k reachability query. Computers & Security p. 104525 (2025) 28. Zhang, S., Lu, R., Zhu, H., Zheng, Y., Guan, Y., Wang, F., Shao, J., Li, H.: Performance enhanced secure spatial keyword similarity query with arbitrary spatial ranges. IEEE Transactions on Information Forensics and Security (2024) 29. Zhang, S., Ray, S., Lu, R., Guan, Y., Zheng, Y., Shao, J.: Efficient and privacypreserving spatial keyword similarity query over encrypted data. IEEE Transactions on Dependable and Secure Computing 20(5), 3770–3786 (2022) 30. Zheng, Y., Lu, R., Shao, J., Yin, F., Zhu, H.: Achieving practical symmetric searchable encryption with search pattern privacy over cloud. IEEE Transactions on Services Computing 15(3), 1358–1370 (2020) 31. Zuo, C., Sun, S.F., Liu, J.K., Shao, J., Pieprzyk, J., Wei, G.: Forward and backward private dynamic searchable symmetric encryption for conjunctive queries. Cryptology ePrint Archive (2020)
A
Theoretical Analysis
We evaluate the performance of BRASP both theoretically and experimentally, making comparisons with VPBRQSupL .
BRASP
23
Table 1 COMPARISON OF COMPUTATION AND COMMUNICATION COSTS VPBRQSupL [21] BRASP Comp.costs n(Tf + (s1 + s2 )(nTfx + TH ) + nTFc ) (m + p)(TTPF.Rnd + TTUR.Enc ) Encryted Index Build Comm.costs U (s1 + s2 )(n + 1)ρ 2(m + p)M Comp.costs − 4[(p + m)(TTPFReEnc + TTURReEnc + TF ) + TP ] Index Shuffle Comm.costs − 2(m + p)(M + Mtag ) Comp.costs (N S1 + S2 )TDPF.Gen (mq + h)(Tq + TTPF.Rnd ) Token Generation Comm.costs (N S1 + S2 )b 2(mq + h) ′ ′ Comp.costs kU (N s1 + s2 )TDPF.Eval + U (n + 1)(N + 1)TI 4(mq + h)(TTPFReEnc + TTURPDec + TTURDec + Tfind ) Search Comm.costs U (n + 1)N ρ MCS1 + MCS2 Comp.costs − (wo + p)(TTPF.Rnd + TTURReEnc + TTPFReEnc + 2TP ) Update Comm.costs − 2(wo + p)(M + Mtag ) Costs
Notes: Tf : Time complexity of a single computation of a PRF F ; s1 , s2 : Length of Bloom Filter for storing spatial and textual information respectively; n: Total number of objects in the dataset; TH : Time complexity of one computation of HMAC; TFc : Time complexity of a single computation of the prefix-constrained PRF Fc ; U : Number of Cloud Service Providers; ′ ′ s1 , s2 : Number of segments for query range and query keyword set; ρ: Size of each Bloom Filter; S1 , S2 : Size of the Cuckoo hash table for the query range R and the size of the Cuckoo hash table for the query keyword set W ∗ , respectively; TDPF.Gen : Time complexity of a single execution of the generative algorithm for DMPF; TDPF.Eval : Time complexity of a single execution of the evaluation algorithm of the DPF; N : Number of sub-ranges that the query range R is decomposed into; TI : Time complexity of inner product computation; k: Number of hash functions used in PRP-based Cuckoo Hash; b: Size of a DPF share.
In this section, we present a detailed theoretical analysis of the computation and communication costs associated with our proposed scheme, BRASP, and compare it with the existing scheme VPBRQSupL [21]. The analysis focuses on key operations within the schemes: Encrypted Index Build, Index Shuffle, Token Generation, Search, and Update we will only consider some time-consuming operations TTPF.Rnd , TTUR.Enc , TTPFReEnc , TTURReEnc , TF , TP , Tfind . The comparison is based on the theoretical costs outlined in TABLE 1. Computation costs: In Encrypted Index Build, DO constructs and encrypts two indexes: the Prefix-ID index and the Keyword-ID index. Each index entry is encrypted using T P F and T U R techniques. Given m keywords and p prefix encodings (with p=384 in our scheme), the total computation cost for this phase is (m + p)(TTPF.Rnd + TTUR.Enc ). In Index Shuffle, CS2 runs the algorithms T P F.ReEnc and T U R.ReEnc to re-encrypt the indexes stored on CS1 , and it re-randomizes the tags using a pseudorandom function F . Upon receiving re-encrypted indexes, CS1 re-encrypts these indexes again. The total computation cost for this process, considering both indexes stored on CS1 and CS2 , is 4[(p + m)(TTPFReEnc + TTURReEnc + TF ) + TP ]. In Token Generation, the client generates search tokens for m query keywords and h query prefix encodings, which costs Tq . Then randomizes them using the algorithm T P F.Rnd, the total computation cost for this phase is (mq + h)(Tq + TTPF.Rnd ). In Search, the search operation involves querying the encrypted indexes stored on both CS1 and CS2 . Each CS performs the search independently, and the final search result is obtained by intersecting the results from both servers. The search process includes re-encrypting the query tokens, partially decrypting the ID fields, and
24
J. Zhang et al.
locating the relevant encrypted data. The total computation cost for this phase is 4(mq + h)(TTPFReEnc + TTURPDec + TTURDec + Tfind ). In Update, this phase involves modifying the Keyword-ID and Prefix-ID indexes to reflect changes in the database. This process requires re-encrypting the updated index entries and ensuring forward security. The total computation cost for updating the indexes is (wo + p)(TTPF.Rnd + TTURReEnc + TTPFReEnc + 2TP ). Here, wo represents the number of updated keywords, and p is the number of prefix encodings. The cost includes the re-encryption of updated entries and the additional operations required to maintain forward security. Communication costs: During the Encrypted Index Build phase, the communication cost for this phase is primarily due to the transmission of the encrypted indexes to the CSs, the total communication cost is 2(m+p)M . Here, M represents the size of each encrypted index entry. During the Index Shuffle phase, which involves communication between CS1 and CS2 , the communication cost for this phase is 2(m+p)(M +Mtag ). Here, Mtag represents the size of the shuffle state tags. During the Token Generation phase, the communication cost for this phase is relatively low since the tokens are generated locally by the client and sent to the CSs. The total communication cost is 2(mq + h). During the Search phase, the final search result is obtained by intersecting the results from both CSs. The communication cost for this phase is MCS1 + MCS2 . Here, MCS1 and MCS1 represent the sizes of the search results from CS1 and CS2 , respectively. This cost accounts for the results transmitted between the client and the CSs during the search process. During the Update phase, the client communicates with the CSs to update the indexes. The communication cost for this phase is 2(wo + p)(M + Mtag ). Here, wo represents the number of updated keywords. Compared to the existing scheme VPBRQSupL , our proposed BRASP scheme 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 T P F and T U R. Additionally, the Index Shuffle operation in BRASP is designed to minimize the computational overhead while ensuring robust privacy protection. The Search and Update operations in BRASP also demonstrate improved efficiency, making it a more practical solution for privacypreserving data queries in cloud environments.
B
Proof of Theorem 1
We prove confidentiality by a standard hybrid argument. Let ViewCS1 and ViewCS2 denote the views of CS1 and CS2 , respectively, during the execution of BRASP. Because the two servers are assumed to be noncolluding, it is sufficient to simulate the view of each server separately. Intuitively, CS1 observes the partially recovered search results together with the messages needed for shuffling and updating, whereas CS2 observes encrypted trapdoors, partial decryptions, and shuffle-related messages. We show that both views can be simulated from the leakage function collection L = (LQuery , LUpdate ).
BRASP
25
– Game G0 (Real Execution). This is the real BRASP experiment. Therefore Pr[G0 = 1] = Pr[RealA (ζ) = 1]. – Game G1 (Simulating Encodings and Tags). Replace the outputs of T P F.Rnd, T P F.ReEnc, and the tag-generation function F with uniformly distributed strings of the correct length, while preserving the equality pattern implied by the leakage. Any distinguisher between G1 and G0 yields an adversary against the pseudorandomness of T P F or F . Hence, for some PPT adversary B1 , prf |Pr[G1 = 1] − Pr[G0 = 1]| ≤ Advprf T P F,B1 (ζ) + AdvF,B1 (ζ).
– Game G2 (Simulating Re-randomized ID Fields). Replace the rerandomized ID ciphertexts that appear during shuffling, search, and update with simulated ciphertexts of the correct format that are consistent with the leaked access information. Since the plaintext bitmaps are never exposed to a single cloud server, and only their leakage-consistent behavior matters, the adversary’s view remains computationally indistinguishable from that in G1 . – Game G3 (Simulating Search and Update Tokens). Generate search tokens using only LQuery and update tokens using only LUpdate . Repeated queries and repeated updates are mapped to simulated values that preserve the permitted equality structure, while fresh events are assigned fresh simulated strings and ciphertexts. The resulting transcript is distributed exactly as in the ideal world defined by the simulator S. Combining the above hybrids, for every PPT adversary A there exists a PPT simulator S and PPT adversaries B1 , B2 such that prf |Pr[RealA (ζ) = 1] − Pr[IdealA,S (ζ) = 1]| ≤ Advprf T P F,B1 (ζ) + AdvF,B2 (ζ) + negl(ζ). (4) If T P F and F are secure pseudorandom functions, the right-hand side is negligible in ζ. Therefore BRASP is L-confidential against adaptive chosen-keyword attacks.
C
Proof of Theorem 2
We prove shuffle indistinguishability by analyzing the view of a single honestbut-curious cloud server during one shuffle round; the argument for the other server is identical. Let ei = (xi , IDi , tagi ) be an encrypted index entry before shuffling, where xi denotes either a keyword encoding or a prefix encoding. After one shuffle round, the corresponding entry takes the form e′j = (x′j , IDj′ , tagj′ ),
26
J. Zhang et al.
with
x′j = T P F.ReEnc(T P F.ReEnc(xi , r2 ), r1 ), ID ID IDj′ = T U R.ReEnc(T U R.ReEnc(IDi , pkM ), pkM ),
tagj′ = F (F (tagi , r2 ), r1 ). Consider a challenge experiment in which the adversary is given two preshuffle entries e0 , e1 , a shuffled challenge entry e⋆ , and must decide whether e⋆ originates from e0 or from e1 . The adversary additionally sees the shuffled collection after the final random permutation. Because T P F and F are secure pseudorandom functions, the distributions of x′j and tagj′ are computationally indistinguishable from fresh random strings to any party that does not know the shuffle randomness. Moreover, by the assumed unlinkability of T U R.ReEnc, the ciphertext IDj′ is computationally indistinguishable from a fresh ciphertext of the same bitmap and therefore does not reveal which pre-shuffle entry it came from. Finally, the random permutation removes positional information. Hence any adversary that identifies the predecessor of e⋆ with non-negligible advantage would either distinguish the outputs of T P F or F from random, violate the unlinkability of T U R.ReEnc, or exploit positional information that is eliminated by the permutation. Therefore Pr[b′ = b] ≤
1 + negl(ζ), 2
which proves Theorem 2.
D
Proof of Theorem 3
Assume that there exists a PPT adversary A that outputs a valid search token for a Boolean range query that has never been issued by an honest client. We show that such an adversary can be transformed into an algorithm that breaks the collision resistance of T P F . For a keyword wk and a prefix hk , honest tokens are generated as Tw = T P F.Rnd(ku · (r1 r2 )Uwk , wk ),
Th = T P F.Rnd(ku · (r1 r2 )Uhk , hk ).
After the cloud applies the authorization re-encryption step, these tokens are mapped to the current encrypted index state. Therefore, a forged token is accepted only if it matches the image of some valid token under the corresponding shuffled state. Now consider the first successful forgery output by A. Since the forged query has never been issued before, one of the following must occur: 1. the forged token collides with the image of an honestly generated token derived from a different query component or a different shuffle state; or 2. 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 keyed T P F image space. The second event is precisely the type of event ruled out by the collision-resistant keyed encoding used by T P F , because acceptance requires consistency with an existing encrypted-index entry after the authorization re-encryption step. Consequently, any non-negligible forgery advantage of A yields a non-negligible advantage for an algorithm that violates the collision resistance of T P F . Hence the probability that a PPT adversary forges a valid unseen search token is negligible, and BRASP achieves query unforgeability.
E
Proof of Theorem 4
We consider an adversary controlling one of the two cloud servers and ask whether it can use the transcript observed before an update to determine whether a newly inserted object would have matched any earlier query. For a newly inserted object, the client generates fresh encrypted bitmap shares together with fresh update tokens under the current shuffle state. If a keyword or prefix is new, the corresponding update entry is inserted as a fresh encrypted item. If it already exists, the update token is first mapped through the current tag state and is then merged into the current shuffled index. In either case, the associated bitmap shares are encrypted under T U R. After the update, subsequent shuffle rounds re-randomize those ciphertexts again. Therefore, a cloud server that only saw the pre-update search transcript cannot decide whether a new entry is related to a pre-update query unless it can perform at least one of the following attacks: 1. correlate update tokens across different shuffle states by reversing or colliding the state-dependent T P F derivation; or 2. link a re-randomized T U R ciphertext 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-randomized T U R ciphertexts. Under these assumptions, both events have at most negligible probability. Hence the insertion of a new object does not reveal whether that object would have matched any query issued before the update, and BRASP achieves forward security.
F
Additional Experimental Settings
This appendix provides additional details for the experimental methodology used in Section 7. The goal is to make the evaluation setup more explicit and to clarify how the parameters in Fig. 7–Fig. 10 are instantiated.
28
J. Zhang et al.
Dataset and data preparation. We construct the experimental dataset from the yelp_academic_dataset_business.json subset of the Yelp academic dataset. The resulting benchmark is treated as a spatio-textual database in which each record contains a spatial location together with an associated keyword set. The implementation used to preprocess the dataset, build the encrypted indexes, run the queries, and generate the plots is publicly available at https://github. com/Egbert-Lannister/BRASP. Implementation environment. All experiments are implemented in Python 3.12 and run on a 64-bit Windows 11 machine equipped with 16 GB RAM and an AMD Ryzen 5 3500U CPU with Radeon Vega Mobile Graphics at 2.10 GHz. For each experiment, we report the measured computation overhead and communication overhead produced by the implementation under the specified parameter setting. For each parameter configuration, we repeated the experiment 10 times and report the mean computation and communication overheads. To ensure clarity and visual readability of the figures, we plot only the mean values and omit error bars. Workload parameters. The evaluation varies four main parameters: – n: the number of spatial objects in the outsourced database; – m: the number of indexed keywords; – |Wq |: the number of query keywords in a Boolean range query; – wo : the number of objects inserted during an update workload. The specific parameter ranges follow the settings shown in the figures: – In Fig. 7(a)–(b), Fig. 9a–Fig. 9b, and Fig. 10a–Fig. 10b, the database size varies as n ∈ {2, 4, 6, 8, 10} × 104 . – In Fig. 7(c)–(d) and Fig. 9c–Fig. 9d, the number of indexed keywords varies as m ∈ {100, 200, 300, 400, 500}. – In Fig. 8a–Fig. 8b and Fig. 9e–Fig. 9f, the number of query keywords varies as |Wq |∈ {2, 4, 6, 8, 10}. – In Fig. 10a–Fig. 10b, the update workload size is set to wo ∈ {10, 100, 1000}, corresponding to the three curves (or bar groups) shown in Fig. 10. Experiment-by-experiment setup. The four groups of experiments are configured as follows. – Secure index building: We evaluate the cost of encrypting the prefix–ID and keyword–ID indexes as the database size n or the keyword vocabulary size m increases. – Token generation: We evaluate the cost of generating keyword trapdoors and prefix trapdoors while varying the query-keyword cardinality |Wq |. – Search: We evaluate both computation and communication overhead while varying n, m, and |Wq | separately. For BRASP, the reported search cost includes the dual-server retrieval procedure together with the subsequent index-shuffle step used to hide the search and access patterns.
BRASP
29
– Update: We evaluate the update overhead under different database sizes n and insertion workloads wo . The reported cost includes refreshing the encrypted bitmap shares and maintaining the shuffled encrypted indexes after the update. Metrics. The evaluation reports two metrics. The computation overhead records the measured running time of the corresponding operation, and the communication overhead records the total amount of data transmitted during that operation. The same pair of metrics is used throughout Fig. 7–Fig. 10 to facilitate a consistent comparison across different phases. Reproducibility note. The exact scripts used for preprocessing, workload generation, execution, and figure plotting are included in the public BRASP implementation. Accordingly, the appendix is intended to summarize the workload configuration used in the paper, while the released code serves as the reference source for implementation-level details.