Privacy-aware Character Pattern Matching over Outsourced Encrypted Data

The significant improvements in reliability and total cost of ownership provided by remote data management services have proven on field to be beneficial to a large variety of enterprises. In this context, a company relies on cloud-based services to store a significant amount of its own data in an infrastructure located in a third-party data center, beyond the means of its direct control. While this has significant benefits in termsof the reduction of the efforts to be made for infrastructural maintenance, it comes with confidentiality (secrecy) and privacy concerns acting as stopgaps to the adoption of cloud-based storage solutions.

In this article, we consider the popular cloud computing model composed by three entities: the data owner, the cloud server, and the users authorized to access the remotely stored data. The data owner stores the data on the cloud server and authorizes the users to issue specific queries on the outsourced data. To protect the data, the data owner encrypts the data before outsourcing them and shares the decryption keys with the authorized users only. However, data encryption is a major hindrance to perform queries over the data, such as searching for a given pattern, with practical performance. Therefore, there is a pressing need for effective solutions enabling a set of querying functionalities on encrypted data, possibly by multiple users, preserving the confidentiality of the searched information even against the service (storage) provider itself.

Problem Statement. A data owner outsources a set of documents \(\mathbf {D} = \lbrace D_1, \ldots , D_z\rbrace\), \(z \ge 1\), where each document is a sequence of symbols (string) over an alphabet \(\Sigma\) with length \(\mathtt {len}(D_i)\), encrypted with a cryptographic primitive of choice. In addition, the data owner builds an indexing data structure to enable the search for any substring \(q \in \Sigma ^*\), \(\mathtt {len}(q)\)\(=\)\(m\ge\)1, over \(\mathbf {D}\). A query for a substring \(q\) will yield, for each document \(D_i\), \(1 \le i \le z\), the set of positions, \(S_i\), where an occurrence of \(q\) appears. Along with the collection of documents \(\mathbf {D}\), the data owner stores on the remote storage a privacy-preserving representation of the aforementioned indexing data structure allowing authorized clients to use the substring search functionality with the cooperation of the service provider. The main challenge in this scenario is reducing the information learned by an adversary (including the service provider) to the knowledge of the size of the outsourced document collection, the size of the substring, the one of the indexing data structure, and the total number of occurrences matching the query at hand. We remark that the private retrieval of the matching documents from the remote storage is out of scope in the problem addressed by this article, as this functionality can be achieved by hinging upon existing cryptographic primitives such as Oblivious RAMs (ORAMs) [36] or Private Information Retrieval (PIR) protocols [25].

Adversary and Security Model. In a real-world deployment of a privacy-preserving substring search solution, the notion of semi-honest adversary fits well entities that trustworthily follow the protocol specification, although being curious about any other additional information that may be inferred with a polynomial computation effort about the confidential data as well as the access patterns or the search patterns on the remote data storage. Informally, a search pattern refers to the understanding of how similar distinct queries are (e.g., if they share a common prefix or only some non-consecutive symbols), while access pattern refers to the understanding of the positions of occurrences of the queried substring in \(\mathbf {D}\).

Prior Art Approaches. The seminal work on searching over data in an encrypted state [35] (a.k.a. searchable encryption schemes), as well as many of the subsequent improvements in terms of computational and communication resources [3, 9], relies on pre-registering searchable keywords, without supporting free form searching over the encrypted data. Such a limitation is overcome by substring searchable encryption schemes [6, 11, 18, 23, 38]. These schemes exhibit computation/communication complexities linear or quadratic in the length of the searched substring (hence, independent from the size of the document collection), with different server side storage savings and assumptions on the adversary capabilities. Notably, the protocol described in Reference [11] is the only one that enables querying on patterns including the wildcard symbol \(?\), which acts as a placeholder in matching an arbitrary single character. Furthermore, since the design of this protocol stems from an existing dynamic searchable encryption scheme, it is the only substring searchable encryption scheme that allows to efficiently add new documents to the collection without re-encrypting significant portions of the search index employed for queries. While these solutions cope with the problem of substring search, the works in References [6, 11, 23, 38] do not provide protection of search and access pattern, while the information leakage shown in Reference [18] is not explicitly framed as a search or access pattern one. The importance of protecting both the search and access pattern is demonstrated by References [5, 33], where the authors describe the recovery of either a significant portion of the documents in the collection \(\mathbf {D}\) or the content of the queried substrings by combining search and access pattern leakages with public information related to the application domain itself.

Contributions. Substring searchable encryption schemes [6, 18, 23, 38] employ symmetric-key or order-preserving cryptographic primitives, obtaining practical performance figures in terms of required bandwidth, computational power, and storage demands on both clients and servers. However, they do not take into account the information leakage coming from the observation of both search and access patterns. The higher privacy guarantees resulting from the inclusion of such leakages in the security model come along with the usage of cryptographic primitives with higher computational complexity. We refer to substring search schemes preserving search or access pattern confidentiality as privacy-preserving substring search(PPSS) protocols.

In the following, we describe the first multi-user PPSS protocol secure against semi-honest adversaries preserving both search and access pattern confidentiality and enabling queries for patterns containing wildcard characters. We combine the working principles of the Burrows Wheeler Transform (BWT) [4] (as a method to perform a substring search) with a single server Private Information Retrieval (PIR) protocol; specifically, we choose the PIR proposed by Lipmaa in Reference [25], which is based on the generalized Paillier homomorphic encryption scheme proposed in Reference [10], because of its limited communication cost. This design leads to a PPSS protocol with \(O(m\)\(+\)\(o_q)\) communication rounds and an \(O((m\)\(+\)\(o_q) \log ^2 n)\) communication cost between client and service provider, where \(o_q\) denotes the number of occurrences of the queried string \(q\) (\(m\)\(=\)\(\mathtt {len}(q)\)) over the document collection \(\mathbf {D} = \lbrace D_1, \dots , D_z\rbrace\), \(z \ge 1\), and \(n\)\(=\)\(\sum _{i=1}^z \mathtt {len}(D_i)\). Our PPSS protocol exhibits an \(O((m\)\(+\)\(o_q) \log ^4 n)\) computational cost and requires \(O(\log n)\) memory on the client side, while the computational and storage demands on the service provider side amount to \(O((m\)\(+\)\(o_q) n)\) and \(O(n)\), respectively. An enhanced version of the same protocol allows to retrieve all \(o_q\) occurrences of a queried string \(q\) in a single communication round instead of \(o_q\) ones, making the computational cost at server side also independent from \(o_q\). This version improves all the figures of merit exhibiting an \(O(m\log ^2(n)\)\(+\)\(o_q\log (n))\) communication cost, an \(O(m\log ^4(n)\)\(+\)\(o_q\log ^4(\frac{n}{o_q}))\) computational cost at client side and an \(O(m\)\(\cdot\)\(n)\) computational cost at server side. In a multi-user scenario, our PPSS protocol allows distinct and simultaneous queries on the same document collection, run by multiple clients without any interaction with the data owner and among themselves. Our multi-user approach avoids to replicate the outsourced document collection for each authorized client, limiting the additional memory required by each query to \(O(\log ^2 n)\) cells. Finally, to make our PPSS protocol resilient against accidental or misconfiguration errors, we complement its features with an efficient mechanism that allows the client to verify the correctness of the remotely accessed data.

We now briefly revise existing PPSS protocols, comparing their functionalities and performance with our solution and its enhanced version. An overview of such comparison is reported in Table 1. In Reference [40], the authors describe a PPSS protocol to establish if a given substring is present in the outsourced document collection with an \(O(n)\) communication cost and an impractical \(O(n)\) amount of cryptographic pairing computations required at the client side for each query. Shimizu et al. in Reference [34] described how to use the BWT [4] and Paillier’s Additive Homomorphic Encryption (AHE) scheme [31] to effectively retrieve the occurrences of a substring. The main drawback of the scheme lies in the significant communication cost: Each query needs to send \(O((m\)\(+\)\(o_q)\sqrt {n})\) ciphertexts from client to server. Such a cost was reduced by Ishimaki et al. [21] to \(O((m\)\(+\)\(o_q)\log (n))\), at the price of employing a Fully Homomorphic Encryption (FHE) scheme [16], making their solution unpractical. Indeed, FHE schemes generally require ciphertexts bigger than the ones exhibited by Paillier AHE scheme, introducing a significant constant factor in the communication cost. Moreover, the computational cost for the server is \(O((m\)\(+\)\(o_q)n\log (n))\), which also hides a large constant overhead (about \(10^6\)) required to compute on FHE ciphertexts.

A multi-user protocol, preserving only the search pattern confidentiality and with communication cost linear in the size of the searched substring, is described in Reference [12]. The main drawbacks of this solution are the need for the client to interact with both the data owner and the server to perform a query, and the constraint that only substrings of a fixed length, which must be decided when the privacy preserving indexing data structure to be outsourced is built, can be queried, in turn limiting the impact of the solution. This protocol has been recently improved in Reference [32], removing the interaction between the client and the data owner during queries. Remarkably, this is the first substring search protocol that allows multiple users to perform queries over data coming from multiple data owners with an access control mechanism that allows to restrict, for each document, the users authorized to perform queries. Nonetheless, the protocol is still affected by a lack of access pattern privacy; furthermore, the client must perform a distinct query for each document the client is interested in.

The suffix-array-based solutions proposed by Moataz et al. in Reference [30] guarantee the confidentiality of the content of both the substring and the outsourced data, as well as the privacy of the access pattern and the search pattern observed by the server. The access pattern to the outsourced indexing data structures is concealed by employing an ORAM data structure [36]—which is specifically designed to obliviously access a remote data storage without leaking search and access patterns. The asymptotic complexities of the protocol shown in Reference [30] mainly depends on the size of each document being negligible w.r.t. the total number of them (denoted as \(z\)). Indeed, it exhibits \(O(m\log ^3(z))\) communication and computation complexities, assuming that the size of each document is \(O(\log ^2(z))\). If the size of each document is not negligible w.r.t. their total number, then the computational and communication cost of the solution increases proportionally to the size \(n\) of the document collection, by (at least) a factor \(\log ^2(n)\). Each of the \(o_q\) occurrences can be retrieved with \(o_q\) accesses to the ORAM, yielding an additional \(O(o_q\log ^2(n))\) communication cost.

ObSQRE [28] is the first PPSS protocol with optimal communication cost concealing both the search and the access patterns. This goal is achieved by relying on Intel SGX technology [8], which allows to execute an application on an untrusted machine while guaranteeing the confidentiality and the integrity of the application code and data. Nonetheless, since this technology is based on trusted hardware modules provided by Intel, ObSQRE can only be deployed on servers equipped with Intel CPUs where such hardware is available. Furthermore, ObSQRE lacks two important features provided by our PPSS protocol: Indeed, it supports neither simultaneous queries from multiple users, nor queries for patterns containing wildcard characters.

A multi-user PPSS protocol allowing queries with wildcard characters was first proposed in Reference [24]. This solution allows users to identify the documents in the collection that belong to the language specified by a Deterministic Finite Automaton (DFA). Specifically, authorized users can independently send an obfuscated version of the DFA to the server, which computes the set of matched documents, i.e., the ones accepted by the DFA. Therefore, this PPSS protocol enables the matching of any regular pattern in the document collection, making it more expressive than our solution. Nonetheless, although the structure of the DFA is concealed to the server in such a way to prevent search pattern leakage, the server learns which documents are matched, hereby leaking the access pattern. Furthermore, a relevant limitation of this protocol is the need for each user to interact with a trusted authority to build a properly obfuscated search query (relying on a master secret key known only to the trusted authority). The said interaction between a user and the trusted authority has been removed in a further modification of this protocol proposed in Reference [41], which, however, requires the data owner to encrypt the documents employing a pairing-based cryptosystem (specifically designed by the authors) with a per-user public key, hence requiring a distinct per-user encrypted copy of the outsourced document collection. Because of this limitation, we do not classify in Table 1 this solution as a multi-user PPSS protocol.

In the following, we describe the basic algorithms and cryptographic primitives employed in this work, detailing their features and pointing out the properties needed to define our PPSS protocol.

A PPSS protocol allows the server to provide the functionality specified in Definition 4.1 without learning the content of the document collection \(\mathbf {D}\), the value of the substring \(q\) and the positions in \(O_{\mathbf {D},q}\), as well as guaranteeing search and access pattern privacy. To this end, the protocol needs to hide all these data by employing privacy-preserving representations. We will denote the privacy-preserving representation of a datum by enclosing it in square brackets (e.g., \([[\mathbf {D}]]\)).

Relying on the substring search algorithm based on the BWT transformation reported in Algorithm 1 and the Lipmaa’s PIR protocol based on the FLAHE Paillier scheme, we now provide the operational description of the proposed PPSS protocol, reported in Algorithm 5 and Algorithm 6.

The document collection \(\mathbf {D}\) employed for the searching operation is encrypted with a symmetric-key and outsourced to the remote server. Along with the encrypted version of \(\mathbf {D}\), the client computes the indexing structure \([[\mathbf {D}]]\) by employing the \(\mathtt {Setup}\) procedure.

This procedure (see Algorithm 5) takes as input the \(z\) documents in \(\mathbf {D}\) to compute a single string \(s\) obtained concatenating the documents, interleaved with $ (lines 2–3). The additional input \(\lambda\) is an integer number representing the computational security level employed to instantiate the underlying cryptographic primitives. Subsequently, the procedure computes the \((|\Sigma |\)\(+\)\(1)\)\(\times\)\((n\)\(+\)\(1)\) matrix representation of \(L\)\(=\)\(\mathtt {BWT}(s)\), denoted as \(M\) in Algorithm 1, the corresponding \(1 \times (n+1)\) suffix array, \(SA\), and the \(\mathtt {Rank}\) dictionary with size \(|\Sigma |\)\(+\)1, containing pairs \((c, l)\), where \(l\)\(=\)\(\mathtt {Rank}(c)\), 0\(\le\)\(l\)\(\le\)\(n\)\(+\)1, is the number of characters in \(s\) alphabetically smaller than \(c\). As the rows of \(M\) are indexed by characters in \(\Sigma \cup \lbrace \$\rbrace\), a bijective function \(\mathtt {Order}:\Sigma \cup \lbrace \$\rbrace \mapsto \lbrace 0,1,\ldots ,|\Sigma |\rbrace\) is employed to build a dictionary including pairs \((c, o)\), where \(c\)\(\in\)\(\Sigma\)\(\cup\)\(\lbrace \$\rbrace\) and \(o\)\(=\)\(\mathtt {Order}(c)\) is the unique numerical index corresponding to the character indexing a row of \(M\). At lines 4–7, the integer matrix \(M\) is converted into a \((|\Sigma |\)\(+\)\(1)\)\(\cdot\)\((n\)\(+\)\(1)\) array of integers, \(C\), built as the concatenation of the rows of \(M\) in ascending order of the numerical index obtained via the \(\mathtt {Order}\) function. We note that \(\mathtt {Rank(c)}\) is summed to \(M[c][j]\) at line 7 of Algorithm 5 to save the additions that should be executed later as per lines 5–6 of Algorithm 1.

As the data structures \(C\) and \(SA\) are sufficient to reconstruct \(s\), and thus the document collection \(\mathbf {D}\), they are cell-wise encrypted (lines 9–12) before being outsourced, obtaining arrays \(\langle C \rangle\) and \(\langle SA \rangle\). To this end, any secure cipher \(\mathcal {E}\) can be employed; we choose a symmetric block cipher for efficiency reasons. The algorithms referring to the mentioned cipher are denoted as (\(\mathcal {E}.\mathtt {KeyGen}, \mathcal {E}.\mathtt {Enc}, \mathcal {E}.\mathtt {Dec}\)), where the \(\mathtt {KeyGen}\) procedure yields a pair of public and private keys, i.e.: \(pk_\mathcal {E}\), \(sk_{\mathcal {E}}\) (line 8), where \(pk_\mathcal {E} = sk_\mathcal {E}\) if \(\mathcal {E}\) is a symmetric-key cipher.

At line 13, the secret information kept by the client \(aux_s\) is computed as the dictionary \(\mathtt {Order}\) and the secret key of cipher \(\mathcal {E}\). Finally, the \(\mathtt {Setup}\) procedure in Algorithm 5 returns the secret data to be kept by the client, \(aux_s\)\(=\)\((\mathtt {Order}, sk_\mathcal {E})\), and the privacy-preserving representation \([[\mathbf {D}]]\), given by the pair of encrypted data structures (\(\langle C \rangle\), \(\langle SA \rangle\)), of the indexing structure of the document collection, to be outsourced to the server.

The Query procedure, reported in Algorithm 6, takes as input the \(m\)-character string to be searched \(q\), the secret auxiliary information \(aux_s\)\(=(\mathtt {Order}, sk_\mathcal {E})\), and the privacy-preserving representation \([[\mathbf {D}]] = (\langle C \rangle , \langle SA \rangle)\).

The operations performed during the execution of the Queryprocedure are grouped in two phases. The first phase, labeled as \(\mathtt {Qnum}\) (lines 2–12), corresponds to lines 1–6 in Algorithm 1 and allows to evaluate as \(\beta -\alpha\) the total number of occurrences of \(q\) in the remotely stored documents. In particular, all memory lookups performed on the matrix representation \(M\) of the BWT of the document collection in Algorithm 1 are realized accessing the cells of the array \(\langle C \rangle\). Realizing each access via the primitives of any PIR protocol allows to hide the position of the array cell requested by the client, thus providing search pattern privacy of the retrieved content. Indeed, without the PIR protocol, the adversary, i.e., the server, would be able to infer the similarity between the strings searched in two separate queries due to deterministic access to the same positions of the array \(\langle C \rangle\). In our PPSS protocol, the Lipmaa PIR protocol described in Section 3.2 is adopted due to its efficiency in terms of communication complexity. Finally, as each cell \(\langle C\rangle [h]\) stores an encrypted content, the client needs to further decrypt the material returned by the PIR-retrieve procedure, as shown in line 7 (line 12, respectively).

The second phase, labeled as \(\mathtt {Qocc}\) (lines 13–17), corresponds to lines 7–9 in Algorithm 1, and it allows to compute the set of positions, in the remotely stored documents, where the leading characters of the occurrences of \(q\) are found. Similarly to the previous phase, each memory lookup to the suffix array data structure in Algorithm 1 is realized by accessing privately the cells of the outsourced array \(\langle SA \rangle\).

Informally, the security of our protocol is based on the security of the PIR protocol employed and on the semantic security of the encryption scheme used to encrypt the array \(\langle C \rangle\) and the suffix array \(\langle SA \rangle\), as the server observes only PIR queries on arrays encrypted with a semantically secure encryption scheme. The only information leaked to the server is the size of the array \(\langle C \rangle\) and of the \(\langle SA \rangle\), which are both proportional to the size \(n\) of the document collection, while the length \(m\) of the substring \(q\) and the number of occurrences \(|R_q|\) are leaked by the number of iterations required by the execution of the phases in Algorithm 6 labeled as \(\mathtt {Qnum}\) and \(\mathtt {Qocc}\), respectively. Concerning the computational and communication complexities of the \(\mathtt {Setup}\) and Queryprocedures, we note that the former costs \(O(n)\) bit operations, while storing \([[\mathbf {D}]]\) on the server requires \(O(n)\) space. The cost of the Queryprocedure is split between the client and the server, obtaining \(O((m+|R_q|) \cdot b\log ^3(N) \log _b^4(n))\) and \(O((m+|R_q|) \cdot \frac{n}{b}\log ^3(N))\) complexities, respectively, where \(N\) is the modulus employed in the FLAHE Paillier keypair. The amount of data exchanged between the client and the server amounts to \(O((m + |R_q|) \cdot \log (N) b \log _b^2(n))\).

We remark that any PIR protocol can be employed in our PPSS protocol, although the computational and communication costs depend on the PIR at hand. Therefore, improvements in terms of computation or communication in a PIR solution may be immediately applicable in our PPSS protocol. In particular, XPIR [29] and SealPIR [1] are two recently proposed PIR solutions that improve upon the scheme introduced by Stern in Reference [37] showing significant improvements in terms of computation by relying on lattice-based additive homomorphic encryption schemes instead of number-theoretic ones such as the Paillier scheme employed in this work. Furthermore, XPIR and SealPIR rely on the Learning with Error trapdoor, which in turn provides post-quantum security assurances. Nonetheless, their communication cost amounts to \(d \cdot n^\frac{1}{d} + F^d\), where \(F = \Theta (1)\) and \(d\) is a value chosen by the client at each query. We observe that these protocols cannot achieve a polylogarithmic communication cost: Indeed, if \(d = O(1)\), then the communication cost is \(O(n^\frac{1}{O(1)})\); if \(d = \Theta (\log (n))\), then the communication cost becomes \(O(\log (n) + F^{\log (n)}) = O(n)\). Since the main goal of this work is achieving a polylogarithmic communication cost, to make our protocol usable in scenarios with limited bandwidth (e.g., on mobile phones), we decide to employ the Lipmaa’s PIR despite a possibly higher computational cost at server side. In application scenarios where a non-polylogarithmic communication cost is acceptable, replacing the Lipmaa’s PIR protocol with either XPIR or Seal PIR remains a viable solution.

Batched Retrieval of Occurrences. In the Qocc phase of the Query procedure (lines 13–17 in Algorithm 6), the client performs \(o_q = |R_q| = \beta - \alpha\) Lipmaa’s PIR queries, one for each occurrence of the string \(q\). We now introduce an optimization that allows to retrieve all the occurrences in a single communication round, reducing both computational and communication costs.

This optimization is based on enabling the retrieval of multiple entries (i.e., batches) of the outsourced dataset (array) managed by the Lipmaa’s PIR protocol. To this extent, we introduce an additional parameter of the PIR protocol, denoted as \(a\), that specifies the number of entries to be retrieved with a single PIR query; specifically, the dataset \(A\) with \(n\) elements is split in \(\lceil \frac{n}{a} \rceil\) chunks of \(a\) consecutive entries each to allow the \(i\)th chunk, \(i\in \lbrace 0 \dots , \lceil \frac{n}{a} \rceil\)\(-\)\(1\rbrace\), to be retrieved by the client issuing a single PIR query. In particular, the client generates a Lipmaa’s PIR trapdoor to retrieve the \(i\)th entry from a dataset with \(\lceil \frac{n}{a} \rceil\) entries; the server splits the dataset \(A\) in \(a\) arrays, with the \(j\)th one, \(j \in \lbrace 0, \dots , a\)\(-\)\(1\rbrace\), containing all the entries \(A[h]\) such that \(h \bmod a = j\), and employs the trapdoor to retrieve the \(i\)th entry from each of these \(a\) arrays; these \(a\) entries are then sent back to the client. The computational and communication costs for the PIR-Trapdoor procedure are reduced to \(O(b\log ^3(N)\log _b^4(\frac{n}{a}))\) and \(O(b\log (N)\log _b^2(\frac{n}{a}))\), respectively, as a trapdoor for a dataset with \(\lceil \frac{n}{a} \rceil\) entries is generated in place of a trapdoor for a dataset with \(n\) entries; conversely, both these costs increase by a factor \(a\) in the PIR-Retrieve procedure, because \(a\) entries are sent back from the server and then decrypted by the client. Most importantly, the computational cost at the server side is unchanged: Indeed, the server performs \(a\)PIR-Search operations over a dataset with \(\lceil \frac{n}{a} \rceil\) entries, thus yielding a \(O(a\frac{n}{ab}\log (N)) = O(\frac{n}{b}\log (N))\) cost.

In the Queryprocedure of our PPSS protocol, the client can hinge upon this batched retrieval strategy in the Qocc phase to retrieve from the encrypted suffix array \(\langle SA \rangle\) the \(o_q = \beta - \alpha\) elements \(\lbrace \langle SA \rangle [\alpha +1], \dots , \langle SA \rangle [\beta ]\rbrace\) with a single PIR query. Specifically, the client chooses a value \(a \ge o_q\) as the minimum value such that \(\lfloor \frac{\alpha +1}{a} \rfloor = \lfloor \frac{\beta }{a} \rfloor\): this choice guarantees that all the \(o_q\) elements \(\lbrace \langle SA \rangle [\alpha +1], \dots , \langle SA \rangle [\beta ]\rbrace\) are found in the \(\lfloor \frac{\alpha +1}{a} \rfloor\)th chunk among the \(\lceil \frac{n}{a} \rceil\) ones of \(\langle SA \rangle\). This strategy improves both the computational and communication costs of the queries in our PPSS protocol, as reported in Table 2. Remarkably, the computational cost at server side becomes independent from the number of occurrences \(o_q\), as well as a significant improvement is observed in terms of communication cost because of the Qocc phase being performed in a single round instead of \(o_q\) ones.

We now extend our PPSS protocol to enable queries for a string \(q\) containing meta-characters, also called wildcards, that allow to define a language (i.e., a set of strings) over the alphabet instead of a single string. We call a pattern, denoted by from here on, any string containing at least one of these wildcards; the language defined by a pattern is denoted by . Although a pattern is usually employed to filter out strings that do not belong to , in our PPSS protocol, we want to find the positions of the (sub)strings in the document collection \(\mathbf {D}\) that are also in . From now on, these (sub)strings will be referred to as matches or occurrences of the pattern over the document collection; each occurrence is identified by the document where it is located and its starting position in the document at hand:

Coherently with Definition 4.1, our PPSS protocol aims at computing, for a pattern and a document collection \(\mathbf {D}\), the set of positions . To specify a pattern in the queries of our PPSS protocol, we define our own format building upon the well-known glob patterns,¹ which denote a simple syntax in the Command Line Interface (CLI) of Unix-based systems that is largely used to filter out the filenames not belonging to the language defined by the specified pattern.

In the previous sections, we observed how our PPSS protocol ensures the confidentiality of the remotely stored string, of the searched substring, and of the results returned by each search query. Furthermore, it provide indistinguishability of the search-pattern followed by multiple queries as well as the access-pattern privacy of locating the occurrences of a given substring. In the following, adopting the framework introduced by Curtmola in Reference [9], we provide a formal definition of the information leakage coming from a PPSS and we formally specify the adversarial model as well as the security guarantees provided by our PPSS protocol.

The security game stated in Definition 6.2 allows to prove that a semi-honest adversary does not learn anything but the leakage \(\mathcal {L}\). To this end, this definition requires the existence of a simulator \(\mathcal {S}\), taking as inputs only \(\mathcal {L}_{\mathbf {D}}\) and \(\mathcal {L}_q\), which is able to generate a transcript of the PPSS protocol for the adversary that is computationally indistinguishable from the one generated when a legitimate client interacts with the server during a real execution of the protocol.

In the experiments shown in Figure 2, \(\mathbf {D}\) is chosen by the adversarial algorithm \(\mathcal {A}_D\) and the query \(q_i\) is adaptively chosen by the \(i\)th adversarial algorithm \(\mathcal {A}_i\) depending on the transcripts of the protocol in the previous queries. All the adversarial algorithms share a state, denoted as \(\mathtt {st}_{\mathcal {A}}\), which is used to store possible information learned by the adversary throughout the experiment.

The \(\mathbf {Real_{\mathcal {P},\mathcal {A}}}\) experiment represents an actual execution of the protocol, where the client receives the document collection \(\mathbf {D}\) and the \(d\) queries and it behaves as specified in the protocol; conversely, in the \(\mathbf {Ideal_{\mathcal {A},\mathcal {S}}}\) experiment, the client is simulated by \(\mathcal {S}\), which, however, employs only the leakage information \(\mathcal {L} = (\mathcal {L}_D\), \(\mathcal {L}_{q_1}, \dots , \mathcal {L}_{q_d})\). In particular, the simulator \(\mathcal {S}_D\) constructs a privacy-preserving representation \([[\mathbf {D}]]\) by exploiting only the knowledge of \(\mathcal {L}_D\), while each simulator \(\mathcal {S}_{q_i}\) constructs the trapdoor for each round of the \(i\)th query by exploiting only the knowledge of the leakage \(\mathcal {L}_D\), \(\mathcal {L}_{q_j}\), \(j \in \lbrace 1, \dots , i\rbrace\).

We remark that Theorem 6.3 guarantees search and access pattern privacy, as they are not enclosed in the leakage \(\mathcal {L}\).

Theorem 6.3 applies also to the enhanced version of our PPSS protocol with the batched retrieval of occurrences: Indeed, it is possible to build a simulator \(\mathcal {S}^{\prime }\), simulating this enhanced version in the \(\mathbf {Ideal_{\mathcal {A},\mathcal {S}^{\prime }}}\) experiment of Definition 6.2, with a simple modification of the simulator \(\mathcal {S}\) constructed in the proof reported in Appendix A. The leakage \(\mathcal {L}\) does not change in the enhanced version of the protocol: Indeed, the number of elements sent back to the client is close to the actual number of occurrences.

Privacy Guarantees of Queries with Wildcards. To analyze the information leakage of queries containing wildcard characters, we assume the version of our PPSS protocol enhanced with batched retrieval procedure and we distinguish two possible use case scenarios: In the first one, which is more unlikely, the adversary knows that the client is performing a single query (e.g., an application scenario where each user is allowed to perform a single query per day); in the second one, the client may perform an arbitrary number of queries.

In the first scenario, the adversary can infer the number \(k\) of \(*\) wildcards in the queried pattern and, for each of the \(k\)\(+\)1 well-formed star-free patterns \(\alpha _1, \dots , \alpha _{k+1}\) if there is at least a wildcard different from \(*\) and \(&\). The value \(k\) can be inferred by the number of private accesses to the encrypted array \(\langle SA \rangle\) performed during the execution of the query: Indeed, the QueryPatternprocedure (line 4 in Algorithm 9) runs \(k\)\(+\)1 times the StarFreeQueryfunction in Algorithm 8, which in turn accesses the array \(\langle SA \rangle\) only once per run either by performing a batched retrieval when the Queryfunction in Algorithm 6 is run (line 4 in Algorithm 8) or by executing the BatchedRetrievalfunction at line 13 in Algorithm 8. Furthermore, if the client performs a private access to the encrypted array \(\langle s \rangle\) (line 19 in Algorithm 9) after the \(i\)th access to \(\langle SA \rangle\), 1\(\le\)\(i\)\(\le\)\(k\)\(+\)1, then the adversary learns that the \(i\)th well-formed star-free pattern \(\alpha _i\) found in contains a wildcard character different from \(&\). Once the adversary has reconstructed the structure of , for each well-formed star-free pattern with no wildcard character (except for \(&\)) she learns its length and its number of occurrences; otherwise, for each well-formed star-free pattern \(\alpha _i\) with at least a wildcard character, she learns the length of the longest string in \(L_{\alpha _i}\) (from the number of elements retrieved at line 19 in Algorithm 8) and the upper bound \(o_{min}\) (see communication cost of StarFreeQueryprocedure in Section 5) on the number of its occurrences (from the number of elements retrieved at line 13 in Algorithm 8).

Therefore, the adversary cannot learn the actual number of occurrences of a pattern unless it is a well-formed star-free pattern with no wildcards other than \(&\).

In the second scenario, where the client may perform an arbitrary number of queries, the adversary can no longer reconstruct the number of \(*\) wildcards: Indeed, the adversary only observes a set of queries for well-formed star-free patterns, but it cannot determine which of them are portions of the same well-formed pattern. Nonetheless, the adversary can still infer, for each of the observed queries, if the queried well-formed star-free pattern contains at least a wildcard character other than \(*\) or \(&\) by verifying if the client retrieves any element from the encrypted array \(\langle s \rangle\). It is worth noting that this information leakage may be not accurate for the adversary: Indeed, although not specified in our PPSS protocol, in some application scenarios the client, once determined the positions of an occurrence in a document, may need to download the portions of the document corresponding to such an occurrence, hereby privately accessing via PIR queries the encrypted array \(\langle s \rangle ,\) too. Similarly to the previous scenario, in case the adversary determines that the queried well-formed star-free pattern contains at least a wildcard character other than \(*\) or \(&\), she learns the length of the longest string in \(L_{\alpha _i}\) and the upper bound \(o_{min}\) on the number of its occurrences; otherwise, she learns the length of and the number of its occurrences. Nonetheless, since in this scenario the client cannot know if is a portion of a bigger well-formed pattern or not, the adversary can never know with certainty both the length and the number of occurrences of the well-formed pattern.

The leakage of the structure of the well-formed pattern in both scenarios can be prevented with the following two modifications: the first one consists of conceiving the encrypted arrays \(\langle C \rangle\), \(\langle SA \rangle\) and \(\langle s \rangle\) in \([[\mathbf {D}]]\) as a single dataset, thus any PIR query will be performed over all these three arrays; the second modification requires that PIR queries always retrieve elements in batches of constant size (otherwise, the information concerning which array among \(\langle C \rangle\), \(\langle SA \rangle ,\) and \(\langle s \rangle\) has been accessed would be leaked). Nonetheless, these two modifications would introduce a significant performance overhead to the PPSS protocol, as the performance benefits of implementing a batching retrieval are lost and the penalty due to the the PIR access of a much larger dataset must be kept into account. Since we deem the leakage related to the execution of queries with wildcards acceptable in most of the practical use-case scenarios, we recommend the described countermeasure only for specific use cases where the information leakage about the structure of queries with well-formed pattern is actually a sensitive data.

We validated our PPSS protocol implementing a client-server architecture and running it on a dual Intel Xeon CPU E5-2620 clocked at 3 GHz, endowed with 128 GiB DDR4-2133, and 64-bit Gentoo Linux17.0 OS. Our implementation provides a cryptographic security level of at least \(\lambda =80\) bits, relying on the multi-precision integer arithmetic GMP library [17] and a proper parametrization of the generalized Paillier algorithms provided by the libhcs library [39], to implement the PIR-related cryptographic operations. We relied on the OpenSSL ver. 1.0.2r [22] for all the symmetric cryptographic operations: the AES-128 CounTeR (CTR) mode primitive for the cell-wise encryption/decryption of \([[\mathbf {D}]]\)\(=\)\((\langle C \rangle , \langle SA \rangle)\); the CMAC primitive based on the AES-128 Cipher Block Chaining (CBC) mode of operation to compute the Message Authentication Code (MAC) associated with each entry in \([[\mathbf {D}]]\); the AES-128 primitive with the Electronic Code Book (ECB) mode of operation to implement a PRF yielding an entry-specific secret key employed for the MAC computation when fed with a master secret key and the position of entry at hand. The implementation of our PPSS protocol (except for the batched retrieval optimization and the queries with wildcard characters) is publicly available online [26], together with detailed instructions on how to reproduce the experimental campaign described in the following, as well as the data files employed for assessing functionalities and performance of the provided implementation.

We chose as our case study a genomic dataset in the widely employed FASTA format [7], which employs an alphabet of five characters to represent a DNA sequence, i.e.: \(\Sigma =\lbrace C,G,A,T, N\rbrace\). Specifically, we considered a document containing approximately \(40 \cdot 10^6\) nucleotides (characters) belonging to the 21st human chromosome selected from the Ensembl publicly available data [15].

In the experiments, we considered documents with variable sizes replicating and truncating the mentioned dataset appropriately. We considered substring searches with a substring \(q\) having \(m=6\) characters, as it is the size of many restriction enzyme sites (transcribed as \(m\)-character strings), that are commonly employed in DNA-based paternity tests. Indeed, the test employs the distances between the occurrences of one of the mentioned substrings in the DNA fragments of two hosts to identify if the hosts are related [2].

In the actual implementation employed for the experimental campaign, we introduced some optimizations that allowed us to reduce the number of entries in the arrays \(\langle C \rangle\) and \(\langle SA \rangle\). First, we recall that \(\langle C \rangle\) is the cell-wise encryption of the array \(C\), which is obtained, as described in lines 4–7 of Algorithm 5, from the matrix representation, \(M\), of the BWT, \(L\), of the document. Specifically, as any entry \(M[c][i]\), with \(c \in \Sigma \cup \lbrace \$\rbrace , i \in \lbrace 1,\dots ,n+1\rbrace\) stores the number of occurrences of character \(c\) in the subarray (\(L[1],\dots ,L[i]\)), the array \(C\) has \((|\Sigma |+1) \cdot (n + 1)\) entries storing \(O(\log n)\) bits each. To reduce the memory footprint of this array, we derived an hybrid representation between \(M\) and the BWT \(L\): Given a parameter \(R\), referred to as sample period, we constructed an array \(C_R\) with \(\lceil \frac{n+1}{R}\rceil\) entries, where \(C_R[j]\) is a tuple with two elements, the first one being \(M[:][j \cdot R]\), that is, the \(j \cdot R\)th column of \(M\), and the second one being the substring of the BWT \(L\) corresponding to characters at positions \(\lbrace j \cdot R, \dots , j \cdot R + R - 1\rbrace\) (i.e., \(L[j \cdot R, \dots , j \cdot R + R -1]\)). In this way, the array \(C_R\) has \(\lceil \frac{n+1}{R}\rceil\) entries requiring (only) \(O(|\Sigma | \cdot \log (n) + R \cdot \log (|\Sigma |)\) bits. The substring search procedure outlined in Algorithm 1 was modified accordingly to make use of \(C_R\) in place of \(M\). Specifically, each access to \(M[c][i], c \in \Sigma \cup \lbrace \$\rbrace , i \in \lbrace 1,\dots ,n+1\rbrace\), is replaced by retrieving \(M[c][\lfloor \frac{i}{R} \rfloor \cdot R]\) from the \(\lfloor \frac{i}{R} \rfloor\)-th entry of \(C_R\) and adding it to the number of occurrences of \(c\) among the first \(i \bmod R\) characters of the substring of the BWT \(L\) found in the \(\lfloor \frac{i}{R} \rfloor\)-th entry of \(C_R\). We chose a sample period \(R\) that allows to encrypt each entry of \(C_R\) to an AES-128 CTR ciphertext within approximately \(\log (N)\) bits, where \(N\) is the modulus employed in the LFAHE Paillier scheme. Furthermore, to reduce the number of entries of the array \(\langle SA \rangle\), we encrypted in a single AES-128 CTR ciphertext of approximately \(\log (N)\) bits as many entries as possible from the array \(SA\). In this way, we reduced the original number of entries of the encrypted arrays \(\langle C \rangle\) and \(\langle SA \rangle\) by significant constant factors (respectively, 1,200 and 28), obtaining a comparable speedup in the Search procedure.

In the first bunch of tests, we profiled the performance of the Query procedure. We evaluated separately the two phases of the Query procedure, labeled as Qnum and Qocc in Algorithm 6, that compute the number of occurrences and the set of positions of the leading character of the occurrences of the substring, respectively. The performance figures related to the second phase refers to the retrieval of a single occurrence, as the costs of retrieving all of them are proportional to their number. We remark that the communication costs reported in our results refer to a single round of communication. In Figure 3, a remotely stored string with length equal to \(500\cdot 10^3\) characters is considered, and the client, server, and communication costs are shown as a function of the radix \(b\) employed in the Lipmaa’s PIR algorithm. As expected, increasing values of \(b\) allows to significantly decrease the computational cost on server side; conversely, the client and communication costs, which include a factor \(O(b\log _b^2(n))\) (see Section 3.3), increase with the values of \(b\), save for small values of \(b\). The results suggest that the optimal value of \(b\) must be found considering the overall response time of a query, and should be differentiated between the phases Qnum and Qocc of the Query procedure as \(b_{n}\) and \(b_{o}\), respectively.

In the next batch of tests, we considered a single-core implementation where we employed the same value \(b=20\) for genomes of increasing size to observe how the performances are affected only by the size of the document collection. In addition, we consider also a multi-core implementation of the PIR-Searchprocedure of the Lipmaa’s PIR protocol. Specifically, we adopted a simple parallelization strategy that employs \(b\) cores to simultaneously compute all the \(b\) recursive calls of Algorithm 7. For these tests, we employed the optimal values \(b_{n}\) and \(b_{o}\) for each document size. The results of these tests are shown in Figure 4. Regarding the server cost, we observe a linear trend in both the single-core (continuous lines in Figure 4) and the multi-core implementations (dashed lines in Figure 4); nevertheless, the multi-core implementation is at least one order of magnitude faster than the single-core, achieving much more practical performances (i.e., approximately five minutes to search for the substring \(q = CTGCAG\) in a \(40\cdot 10^6\) characters document containing the whole chromosome).

The client and communication costs show the expected poly-logarithmic trend that allows to exchange kilobytes of data to search for the occurrences of \(q=CTGCAG\) in the whole chromosome. Furthermore, in Figure 4 the dashed lines on plots reporting the client and communication costs show the benefits of employing specific values \(b_{n}\) and \(b_{o}\) tailored for the size of the document. Concerning the client computational cost, during our experiments, we also measured the time required by the client to verify the integrity of the entries retrieved from the outsourced arrays. As the size of each of the said entries is always \(O(\log (N))\) bits, the computational effort to compute the MAC tag associated with a single entry is always the same regardless of which one among the three outsourced arrays composing the full-text index at server side is accessed. Our experiments revealed that such an effort is negligible w.r.t. the execution time of the PIR-Retrieveperation. Indeed, at client side, the computational cost of the entire process of verifying the integrity of an entry retrieved from the server amounts to 3 \(\mu\)s, while the one of a single run of the PIR-Retrieverocedure fetching such an entry from the server takes \(930\, {\rm ms}\). We remark that the latter cost is averaged over dataset sizes ranging from 0.5 KiB to 40 MiB, as it is dependent from the size of the accessed array.

We also evaluated our enhanced protocol with the batched retrieval method, which is able to fetch all the occurrences in a single round of communication. To fairly compare this approach with the non-batched one, we report in Figure 4 the amortized client, server, and communication costs, i.e., the costs referring to the batched retrieval solution are divided by the total number of occurrences \(o_q\). The results clearly outline the benefits of the batched approach, as all costs in the non-batched version are lowered by a factor roughly proportional to the number of occurrences. Although this result is expected at server side, as its computational cost with the batched approach is independent from \(o_q\), the computational and bandwidth-savings for the client and communication costs, respectively, are definitely more interesting. Indeed, it is worth noting that in our non-batched protocol the number of PIR trapdoors computed and sent by the client and the number of PIR replies received and decrypted by the client are both proportional to \(o_q\), while in our enhanced protocol the size of the single PIR reply is the only component depending from \(o_q\). Thus, considering that both the size of the PIR trapdoor and the client cost to compute it are asymptotically higher than the ones referring to the PIR reply, the reasons for the observed performance benefits become clear. We remark that, for the client cost, the non-amortized cost to retrieve all the \(o_q\) occurrences is even smaller than the cost to retrieve one occurrence in the non-batched method, because the client builds a PIR trapdoor for a dataset with \(\frac{n}{o_q}\) elements instead of \(n\). Finally, since the client can retrieve in a single round all the \(o_q\) occurrences found in the Qnum phase of the Queryalgorithm, the performance benefits exhibited by the Qocc phase of the enhanced protocol increases proportionally to \(o_q\). Indeed, in Figure 4, the trend of the amortized costs is roughly constant or slightly decreasing as \(o_q\) increases depending from the document size.

Willing to compare the execution time of our protocol with the one of the BWT-based substring-search procedure outlined in Algorithm 1 (that features no security guarantees), we focused on querying a single occurrence of the substring \(q=CTGCAG\) in the outsourced document. The experiment showed an execution time for Algorithm 1 equal to a few microseconds. We remark that querying for a single occurrence of \(q\) makes the computational complexity of Algorithm 1 unrelated to the size of the outsourced document, while the PIR-based Query procedure outlined in Algorithm 6 has a computational complexity depending linearly on the size of the outsourced document.

In Figure 5, we also report the execution time for genomes of increasing size of the Setup procedure in Algorithm 5, which builds the privacy-preserving representation \([[\mathbf {D}]]\) of the dataset. In this test, we considered also the genomic data corresponding to the 1st human chromosome, which is much bigger than the 21st one employed in all other tests. The experimental results confirm the expected linear trend and they show practical performance for the Setup procedure: Indeed, building the privacy-preserving representation of the 1st human chromosome, which is as big as 238 MB, requires only 103 seconds.

Last, willing to verify the limited memory consumption when multiple-queries are simultaneously performed, we run each query in a separate thread, measuring the memory consumption of the process, as exposed by the process record in Linux’s proc virtual file system. Figure 6 shows that as the number of simultaneous queries is increased, the memory consumption increases keeping (roughly) the same rate for the four dataset sizes considered. These results agree with the asymptotic spatial evaluations reported at the end of Section 4, where substantial storage savings w.r.t. replicating the whole data structure per-query are discussed.

We presented the first privacy-preserving substring search protocol with proven guarantees of search and access pattern privacy that enables the simultaneous execution of queries from multiple users without the need of the data owner being online and exhibiting a sub-linear (poly-logarithmic) communication cost per user. We further extended the proposed PPSS protocol with the capability of querying strings containing wildcard characters. Our experimental validation with a case study on genomic data shows practical execution times and communication costs, and highlights the possibility of achieving significant benefits from the proposed batched retrieval approach.

Theorem 6.3 is proven by showing the existence of a simulator \(\mathcal {S}\) that interacts with any semi-honest adversary \(\mathcal {A}\), according to the \(\mathbf {Ideal_{\mathcal {A},\mathcal {S}}}\) experiment of Definition 6.2, to produce transcript for this experiment that is computationally indistinguishable from the transcript of the \(\mathbf {Real_{\mathcal {P},\mathcal {A}}}\) experiment, where \(\mathcal {A}\) interacts with a client through our PPSS protocol. As the simulator \(\mathcal {S}\) knows only the leakage \(\mathcal {L}\) as defined in Theorem 6.3, the transcript of the \(\mathbf {Ideal_{\mathcal {A},\mathcal {S}}}\) experiment necessarily depends only on the leakage; thus, if this transcript is computationally indistinguishable from the one of the \(\mathbf {Real_{\mathcal {P},\mathcal {A}}}\) experiment, then it necessarily means that no other information than \(\mathcal {L}\) can be inferred from the latter transcript, as otherwise this additional information could be exploited by the adversary to distinguish between the two experiments. Since the transcript of the \(\mathbf {Real_{\mathcal {P},\mathcal {A}}}\) experiment corresponds to the information observed and derived by the adversary in our PPSS protocol, then no other information than \(\mathcal {L}\) can be inferred from the adversary in our PPSS protocol, in turn proving that the protocol leaks no more information than \(\mathcal {L}\) to the adversary. For the sake of clarity, in the following, we denote all the variables involved in the \(\mathbf {Ideal_{\mathcal {A},\mathcal {S}}}\) experiment with a superscript \(Id\) (e.g., \([[\mathbf {D}]]^{Id}\) is the privacy-preserving representation \([[\mathbf {D}]]\) computed by the simulator \(\mathcal {S}_D\)).

Simulator Construction. We now show how to construct the simulator \(\mathcal {S}\). Specifically, for a document collection \(\mathbf {D}\) of \(z\) documents \(D_1, \dots , D_z\) and a string \(q\), \(\mathcal {S}\) is realized by constructing two simulators \(\mathcal {S}_D\) and \(\mathcal {S}_q\). The former employs the leakage \(\mathcal {L}_D\) to build a privacy-preserving representation \([[\mathbf {D}]]^{Id}\) that is computationally indistinguishable from the privacy-preserving representation \([[\mathbf {D}]]\) computed by the client in our PPSS protocol. The latter simulator employs both the leakage \(\mathcal {L}_D\) and \(\mathcal {L}_q\) to build a trapdoor \([[q]]_j^{Id}\), \(j=1,\dots , w\) for each of the \(w\) rounds of the \(\mathtt {Query}\) procedure for the string \(q\); all these trapdoors must be computationally indistinguishable from the trapdoors constructed by the client in the \(w\) rounds of our PPSS protocol.

We now prove that, for any probabilistic polynomial time adversary \(\mathcal {A}\), the output of the \(\mathbf {Real_{\mathcal {P},\mathcal {A}}}\) experiment is computationally indistinguishable from the output of the \(\mathbf {Ideal_{\mathcal {A},\mathcal {S}}}\) experiment when the simulator \(\mathcal {S}\) we have just constructed is employed. Specifically, we analyze each step of the two experiments and we show that the adversary cannot distinguish the simulator from a legitimate client of our PPSS protocol. In both the experiments, the adversary initially chooses a document collection \(\mathbf {D}\) of \(z\) documents over a publicly known alphabet \(\Sigma\). In the \(\mathbf {Real_{\mathcal {P},\mathcal {A}}}\) experiment, \(\mathbf {D}\) is sent to the client, which constructs a privacy-preserving representation \([[\mathbf {D}]]\) by running the Setup procedure of our PPSS protocol; specifically, \([[\mathbf {D}]]\) is composed by two cell-wise encrypted arrays \(\langle C \rangle\) and \(\langle SA \rangle\) with, respectively, \((n+1) \cdot (|\Sigma |+1)\) and \(n+1\) elements. Conversely, in the \(\mathbf {Ideal_{\mathcal {A},\mathcal {S}}}\) experiment, the simulator \(\mathcal {S}_D\) obtains the leakage \(\mathcal {L}_D\) and constructs the privacy-preserving representation \([[\mathbf {D}]]^{Id}\) as two arrays \(C^{Id}, SA^{Id}\) whose size is the same as \(\langle C \rangle\), \(\langle SA \rangle\), respectively. The semantic security of the scheme \(\mathcal {E}\) employed to encrypt \(\langle C \rangle\) and \(\langle SA \rangle\) in our PPSS protocol guarantees that a ciphertext of \(\omega\) bits computed by \(\mathcal {E}.\mathtt {Enc}\) is computationally indistinguishable from a random bit string of size \(\omega\), which implies that the two privacy-preserving representations \([[\mathbf {D}]]\) and \([[\mathbf {D}]]^{Id}\) are computationally indistinguishable too.

After receiving the privacy-preserving representations \([[\mathbf {D}]]\) and \([[\mathbf {D}]]^{Id}\), the adversary chooses a string \(q_1\). In the \(\mathbf {Real_{\mathcal {P},\mathcal {A}}}\) experiment, the string \(q_1\) is sent to the client, which employs the Query procedure of our PPSS protocol to find all the positions of the occurrences of \(q_1\) in \(\mathbf {D}\). In each of the \(w\) rounds of the Query procedure, the client employs the Trapdoor procedure to generate a trapdoor \([[q_1]]_j, \ j=1, \dots , w\), which corresponds to a trapdoor in the Lipmaa’s PIR protocol. In the \(\mathbf {Ideal_{\mathcal {A},\mathcal {S}}}\) experiment, the simulator \(\mathcal {S}_{q_1}\) receives the leakage \(\mathcal {L}_{q_1}\), which is employed to build a trapdoor \([[q_1]]_j^{Id}, \ j=1,\dots , w\) for each of the \(w\) rounds. The semantic security of the FLAHE Paillier scheme guarantees that a ciphertext computed by the encryption procedure with length \(l\) (i.e., \(\mathtt {FLAHE}.\mathtt {E}_{pk}^l\)) is computationally indistinguishable from a random integer in , which means that the set of trapdoors \([[q_1]]_j\) are computationally indistinguishable from the set of trapdoors \([[q_1]]_j^{Id}\).

Subsequently, in the \(\mathbf {Real_{\mathcal {P},\mathcal {A}}}\) (respectively, \(\mathbf {Ideal_{\mathcal {A},\mathcal {S}}}\)) experiment, the trapdoor \([[q_1]]_j\) (respectively, \([[q_1]]_j^{Id}\)) generated by the client (respectively, \(\mathcal {S}_{q_1}\)) in each of the \(w\) rounds is received by the adversary that employs the Search procedure of Lipmaa’s PIR protocol to compute a ciphertext \([[res_j]]\) (respectively, \([[res_j]]^{Id}\)). The semantic security of the FLAHE Paillier scheme guarantees that all the intermediate values computed by each homomorphic operation of the Search procedure in the \(\mathbf {Real_{\mathcal {P},\mathcal {A}}}\) experiment are computationally indistinguishable from the corresponding intermediate values in the \(\mathbf {Ideal_{\mathcal {A},\mathcal {S}}}\) experiment. Indeed, in the former experiment, given two ciphertexts \(c_1\) and \(c_2\) in for the FLAHE Paillier scheme, each homomorphic addition computes \(c_{add} = c_1 \cdot c_2 \bmod N^{l}\), with \(c_{add}\) being a ciphertext in ; in the latter experiment, the homomorphic addition multiplies two random integers in , obtaining a new random integer in that is computationally indistinguishable from \(c_{add}\). Similarly, in the \(\mathbf {Real_{\mathcal {P},\mathcal {A}}}\) experiment, given a ciphertext and a ciphertext , each hybrid homomorphic multiplication computes \(c_{hmul} = c_2^{c_1} \bmod N^{l+1}\), with \(c_{hmul}\) being a ciphertext in : In the \(\mathbf {Ideal_{\mathcal {A},\mathcal {S}}}\) experiment, each hybrid homomorphic multiplication computes the exponentiation between a random integer in and a random integer in , obtaining a new random integer in that is computationally indistinguishable from \(c_{hmul}\). Therefore, as the Search procedure of Lipmaa’s PIR performs only homomorphic operations, we conclude that all values (including the outcomes \([[res_j]]\) and \([[res_j]]^{Id}\)) observed by the adversary throughout this computation in the \(\mathbf {Real_{\mathcal {P},\mathcal {A}}}\) and \(\mathbf {Ideal_{\mathcal {A},\mathcal {S}}}\) experiments are computationally indistinguishable. In conclusion, the adversary cannot distinguish an interaction with a legitimate client in our PPSS protocol from an interaction with the simulator \(\mathcal {S}_{q_1}\) for the first query \(q_1\).

We note that the same reasoning allows to prove that all the trapdoors and the intermediate values observed by the adversary in the subsequent \(d-1\) queries in the two experiments are computationally indistinguishable. Indeed, in each query, the simulator simply needs to construct trapdoors that looks like generic FLAHE Paillier ciphertexts as computed by the legitimate client in our PPSS protocol independently from their corresponding plaintext value, as the semantic security of the scheme hides any information about the encrypted information stored in these trapdoors.