Substring search over encrypted data

Abstract

We propose a general solution to the problem of efficient substring search over encrypted data. The solution enhances existing “keyword” searchable encryption schemes by allowing searching for any part of encrypted keywords without requiring one to store all possible combinations of substrings from a given dictionary. The proposed technique is based on the idea of letter orthogonalization that allows testing of string membership by performing efficient inner products. We first propose SED-1, the base protocol for substring search. We then identify some attacks on SED-1 that demonstrate the complexity of the substring search problem under different threat scenarios. This leads us to propose our second and main protocol SED-2. The protocol is also efficient in that the search complexity is linear in the size of the keyword dictionary. We run several experiments on a sizeable real world dataset to evaluate the performance of our protocol.

Keywords

Encrypted search substring search wildcard search orthonormalization

1. Introduction

Efficiently searching plaintext documents for keywords has been a major research area within the information retrieval community. In its simplest form, the problem involves simple and exact keyword search. Exact keyword search, however, is just a special case of substring search, which allows searching for only a portion of the keyword. Prefix and suffix searches are the most common substring searches. Substring search can also involve finding all words containing a certain string regardless of its position in the word.

For outsourced data, when the server hosting the document corpus is an honest but curious adversary and the confidentiality of the documents needs to be protected, the above problem reduces to searching encrypted data for substrings. The problem of searching encrypted documents for keywords (and not substrings) has been investigated extensively with many constructions proposed in the context of symmetric search [8,10,13,16,19,27] including ones that support boolean expression search involving keywords [9,24,25], and asymmetric search [1,2,4,14] including support for conjunction, range or subset searches [5,26]. In this work, we address substring search over encrypted data in an efficient manner.1

¹
By the time of submission August 2014, we were not aware of any existing dedicated solution for the substring encrypted search problem. Throughout the reviewing process, several constructions with better leakage profiles and efficiency [11,15,23] have been publicly published. We detail these techniques in Section 2.

Exact keyword search over encrypted data can be trivially extended to substring search albeit at the expense of significant storage overhead. Consider a user who associates the following three keywords with a given document: “search”, “symmetric” and “encryption”, and wants to execute the following query: “search the corpus for all keywords containing exactly the substring sear”. By using existing exact keyword symmetric searchable encryption schemes this query can be implemented as follows. The user generates all possible combinations of characters in words, such as, “s”, “se”, “sea”, “ea” … etc., and stores them in an index before performing the query. If we assume that all keywords have the same length m and the dictionary contains z keywords, then the user has to generate $z \cdot 2^{m}$ entries in the index instead of only z keywords, by taking into account the position of the substrings in the keyword. This approach entails significant storage and processing overhead. To give an idea, if we create a simple lookup table that associates each substring to the documents that contain this substring, with $m = 16$ characters, $z = 10^{5}$ and the allocation for each entry in this table to be $10^{3}$ bits, the size of this lookup table will be in the order of terabytes of data.

1.1. Problem statement and contribution

In this work, we investigate the problem of efficient substring search over encrypted data. We assume that the user creates a document corpus, D, comprising of a set of n documents, ${D_{1}, \dots, D_{n}}$ generated from a dictionary, W, of z keywords ${w_{1}, \dots, w_{z}}$ . The user stores this corpus in an encrypted manner on a server. Later, the user submits a query involving some substring of one or more keywords in the dictionary. The server responds by retrieving the set of documents from the corpus that contain the keywords of which the given string is a substring. We develop a simple protocol that implements such substring search over encrypted data with search complexity linear in the size of the dictionary where $z ≪ n$ , without inducing any significant storage overhead, and providing a clear leakage description.

To solve this problem efficiently we re-formulate the problem to ask the following question: Is there a bivariate function f that takes as input an encrypted substring s and a set of encrypted keywords in the dictionary W, and outputs a deterministic boolean result that defines the success or failure of the search? Orthogonalization of vectors appears to provide some solution to the problem. Two vectors of the same subspace $x_{1}$ and $x_{2}$ are orthogonal if their inner product is equal to 0; $x_{1}$ and $x_{2}$ are orthonormal if they are orthogonal and they are unit vectors. Orthogonalization is the process of determining a set of such orthogonal vectors spanning a specific subspace.

We provide an intuition behind our approach. Imagine that two vectors $x_{1}$ and $x_{2}$ represent two letters say from the English alphabet. If $x_{1}$ and $x_{2}$ represent the same letter then they are not orthogonal and their inner product will not be equal to zero; if $x_{1}$ and $x_{2}$ represent different letters then the inner product will be equal to zero. We extend this idea to search for substrings in keywords. Assume that the letters in an alphabet are represented as column vectors such that these vectors are pairwise orthonormal. A keyword in a dictionary can be considered as a concatenation of letters. The keyword then is a matrix where each column corresponds to a letter of the keyword and two columns are adjacent if the corresponding two letters are adjacent in the keyword. Given the fact that a substring is also a concatenation of letters and can similarly be represented by a matrix, a matrix product between the substring and the keyword can provide an “answer” matrix for the substring membership. To be precise, the result will be a matrix with ones in all the diagonal components in case of a substring match. Thus, our bivariate function f can be intuitively viewed as a matrix product operation that takes as an input an orthogonal representation of the substring and orthogonal representation of the keyword. For the actual protocol implementation, the function f takes as the second input a matrix representing all keywords in the dictionary in the transformed format. We call this second input the searchable part in our protocols. Note that our actual construction is more complex and we will discuss this in details later.

At a higher level, the basic protocol works as follows. The user extracts a dictionary of keywords from the document corpus. The user then generates the searchable part corresponding to these keywords in a manner discussed above. The user also creates a lookup table that associates keywords with their respective documents. Finally, the user encrypts the documents and uploads the searchable part, the lookup table and the encrypted documents to the server. Note that the lookup table is encrypted using single-keyword symmetric searchable encryption technique, later generalized as structured encryption for inverted index data structure [10]. A user query generation is similar to the generation of any column of the searchable part. During the document retrieve phase, the server will first output all indexes (keywords) that contain the given substring (query), then uses the encrypted lookup table to retrieve the set of matching encrypted documents with a single interaction with the client.

Note that this technique, although appealing, induces many challenges in term of efficiency, correctness and security. First, characters, in ASCII for instance, do not form an orthogonal family in their binary representation. In order to be orthogonal, they should be linearly independent first, which implies that their binary representations should be at least equal to 128 bits. Consequently, a transformation is required to impart the orthogonality feature. This, in turn, brings up certain challenges in terms of the size of the transformed letter, and a decimal representation that involves computational precision. Second, a matrix product for identifying substring membership tends to be computationally inefficient for large dictionaries. To facilitate inner product computation, a compaction of the query (substring searched for) and the searchable part is mandatory which brings up more challenges for protocol correctness. Third, every keyword is defined by its own letters’ ordering that should be taken into consideration. In fact, this adjacency is critical for the correctness of the scheme especially if one wants to reduce the size of the query as well as the searchable part. Fourth, the search scheme should ideally allow wildcard search similar to the one enabled on plaintext search. Last but not least, substring search tends to leak more information than exact keyword search. To understand why, note that in order to perform efficient encrypted search, a user may send a deterministic trapdoor for a given substring. As a result, the server acquires the knowledge of all matching substrings, which will eventually lead to a worse leakage profile when compared to exact keyword SSE one. Based on this leakage, over time the server can build a knowledge of the substring frequencies which may lead to data and query recovery. It is important to point out that the SED protocol employs orthogonalization process for the sole purpose of fast inner product and leveraging both orthonormal and additive properties, the security of SED nevertheless consists of other cryptographic primitives involved in the construction process of the searchable part that we will detail later.

In this work, we address these challenges and present two progressively refined Substring search over Encrypted Data (SED) schemes. The first scheme, SED-1, is the initial attempt at using orthogonalization techniques for encrypted substring search. We discuss that SED-1 is vulnerable to some forms of inference attacks as well as attacks based on the search history. The SED-2 scheme improves upon SED-1 by reducing information leakage based on characters’ positions and pattern’s construction. The SED-2 scheme is efficient in that the communication complexity is linear in the size of the substring in the search query sent to the server, and the search complexity is in $O (z + opt)$ , where z is the size of the dictionary and $opt$ is the number of matching documents.

Outline. The rest of the paper is organized as follows. We discuss related work in more details in Section 2. Section 3 introduces the threat model and formally defines the concept of adaptive security and information leakage. We present the orthonormalization pre-construction on which the two SED schemes are based in Section 4. The first scheme, SED-1, is presented in Section 5. It then presents a discussion of the two attacks that can be launched on SED-1. Section 6 and Section 8 respectively present SED-2 and its generalization. Security proof of the SED-2 scheme is discussed in Section 7 and postpone the performances’ study to Section 9. We summarize our contributions and conclude in Section 10.

2. Related works

The area of searchable encryption has been an active research area for over a decade. Many original constructions for searchable encryption can be found in the literature both in the symmetric search setting [9,10,13,16,27] as well as the asymmetric one [1,2,4,14]. Symmetric searchable encryption was later generalized by Chase and Kamara [10] to show how to encrypt different types of data structures. Symmetric schemes, in general, are more geared towards cloud storage and archival for a single user. Asymmetric schemes, on the other hand, are more suitable for multiple users in a collaborative environment. Early schemes focused only on exact keyword searches. In the asymmetric setting, several schemes have been proposed with support for conjunction, range or subset searches [5,26] that exploit the mathematical properties (in particular, homomorphism or pairing) inherent in this setting. However, asymmetric schemes remain orders of magnitudes less efficient than symmetric ones and are not suitable for practical deployments.

In the symmetric setting, Curtmola et al. showed that it was possible to support multiple users [13]. Recent works have also studied several extensions of symmetric searchable encryption schemes to support conjunctions in sub-linear time [9] with an extension to the multi-user setting [19], as well as a schemes [24,25] to support arbitrary boolean queries (including conjunctions, disjunctions and negations). Finally, dynamic SSE constructions have been also proposed [21,22].

Concurrently to our work, researchers got interested on designing symmetric searchable schemes with better expressiveness. Chase and Shen [11] show how to perform substring queries based on suffix trees as their underlying structure. The construction offers a search complexity in $O (λ \cdot m + k)$ , where λ is a security parameter, m the size of the longest string, and k the number of matching files. The proposed solution exhibits the same features as a plaintext suffix tree in the sense that it enjoys the compactness and efficiency of suffix trees. Nevertheless, the solution leaks some non-trivial meta-information such as the intersection between searched for queries that can enable an adversary with adequate auxiliary information to recover the edges’ values. Moreover, the construction by Chase and Shen [11] is static and does not handle updates. Moataz and Blass [23] demonstrate how to perform substring search on an oblivious manner based on suffix trees. Their solution consists of modeling the levels of the suffix tree as smaller ORAMs. They provide new block size encoding technique that reduces the block size, and therefore reduces the overall communication overhead. Note that the construction only enables to check for the existence of a substring and its occurrence on a given corpus. The scheme is not designed to retrieve the associated files of a given substring. However, the scheme can be extended with a single-keyword symmetric searchable encryption for file retrieval, but at the cost of loosing its obliviousness – as SSE has some additional leakage. Faber et al. [15] have recently shown how to extend the OXT construction by Cash et al. [9] to include richer queries such range, substring, wildcard, phrase search that can be embedded into boolean expressions, or extended to a multi-user setting based on Jarecki et al. [19] scheme. Substring search in [15] is based on a tokenization process. At a high level, tokenization fixes a nonnegative integer k and generates for every keyword all k-grams patterns. The k-grams are distributed in the form of s-terms and x-terms similar to the conjunctive OXT scheme.

3. Preliminaries

3.1. Notation

We use the following notation for this discussion. The notation $x \overset{R}{\leftarrow} S$ means uniform sampling at random of the string x from the set S. In this paper, the string x is a binary or real component vector, that is, $x \overset{R}{\leftarrow} {0, 1}^{*}$ or $x \overset{R}{\leftarrow} R_{*}^{+}$ , where $R_{*}^{+}$ denotes the finite set of all nonnegative real numbers that are not zeros and have a fixed precision and an upper bound.2

²
The precision depends on the variable that we have chosen in our experiments. In our case, we have chosen BigDecimal for our implementation.

The size of the string x is denoted by

| x |

x_{i}

denotes the ith component of the string x and

x^{T}

represents the transpose of the string x. If x and y are two strings, then

x ∥ y

is the concatenation of x and y. Let A be a set. We use

A [i]

to denote the value of the ith element of the set.

If $A$ is an algorithm, then $x \leftarrow A (\dots)$ represents the result of applying the algorithm $A$ on the given arguments. The parameter k is used to denote a security parameter in this paper. $δ_{i, j}$ represents the Kronecker delta such that: $if i = j δ_{i, j} = 1 else δ_{i, j} = 0$ .

Let $D = {D_{1}, \dots, D_{n}}$ be the set of documents in the corpus, $W = {w_{1}, \dots, w_{z}}$ be a dictionary of keywords, and $l = {l_{1}, \dots, l_{t}}$ be the set of all unique letters, where $\forall i \in [[1, t]] l_{i} \in {0, 1}^{q}$ . If we are considering ASCII characters as an instance, then $t = 2^{7}$ and $q = 7$ . We denote the set of positive integers smaller than t by $I = [[1, t]]$ . We will denote by $S$ the set of all possible strings. Let $M_{s}$ , an array with elements in I, represent the indexes of letters for a string s. In this case, given a string s with its associated set of letter indexes $M_{s}$ , we represent s as $s = (s^{1}, s^{2}, \dots, s^{| M_{s} |})$ , where each component is a letter such that $s^{j} = l_{M_{s} [j]}$ .

3.2. Structured encryption

Structured encryption introduced by Chase and Kamara [10] is a generalization of symmetric searchable encryption. It is a primitive that shows how to encrypt any data structure while preserving its functionality. For instance, structured encryption can show how to encrypt inverted index, graphs and so on. We borrow the definition of structured encryption in [10]:

Definition 1.
A structured encryption scheme $STE = (KeyGen, Setup, Query, Retrieve)$ consists of four polynomial time algorithms that works as follows3
³
Note also that in the definition above, we can modify the $Setup$ to include the key generation instead of having a separate algorithm for it.

$K \leftarrow KeyGen (1^{k})$ : takes as input the security parameter k and outputs a secret key K.

$EDS \leftarrow Setup (K, DS)$ : is a probabilistic algorithm that takes as inputs a key K, a data structure $DS$ and outputs an encrypted data structure $EDS$ .

$Q \leftarrow Query (K, q)$ : is a (possibly) probabilistic algorithm that takes as inputs the key K, the query q and outputs the token $Q$ .

${⊥, r} \leftarrow Retrieve (EDS, tk)$ : is a (possibly) probabilistic algorithm that takes as inputs the encrypted data structure $EDS$ , the token Q and outputs either ⊥ or r.

Throughout the paper, structured encryption will be mainly used to encrypt an inverted index. There are many efficient instantiations of inverted index (or lookup table) encryption such as the one by Chase and Kamara [10] or Cash et al. [9]. Moreover, we use the words single-keyword SSE and inverted index structured encryption interchangeably. In the following, we slightly adapt STE definition to substring search over encrypted data for which we encrypt both a structure as well as the documents.
3.3. Formal model of SED and correctness criterion

Definition 2.
Substring search over Encrypted Data (SED) over a set of documents D and a dictionary W is a tuple of four polynomial-time algorithms SED = $(KeyGen, Setup, Query, Retrieve)$ such that:
$(K, χ) \leftarrow KeyGen (k)$ : takes as input the security parameter k and outputs a secret key K and a seed χ.

$(K, E_{K} (D), T, V) \leftarrow Setup (K, χ, D, W)$ : a (possibly) probabilistic algorithm that takes as inputs the secret key K, the seed χ, the collection of documents D and the dictionary W. It outputs a secret state κ, the encrypted collection of documents $E_{K} (D) = (E_{K} (D_{1}), \dots, E_{K} (D_{n}))$ , an encrypted lookup table $T$ and the searchable part $V$ .

$Q \leftarrow Query (κ, χ, s)$ : a (possibly) probabilistic algorithm that takes as input a state κ, the seed χ and the string s. It then outputs the query Q.

$(⊥, E_{K} (D^{'})) \leftarrow Retrieve (Q, T, V)$ : a (possibly) probabilistic algorithm that takes as inputs the query Q, the searchable part $V$ and the encrypted lookup table $T$ . The output consists of either ⊥ or a collection of encrypted documents $E_{K} (D^{'}) \subseteq E_{K} (D)$ that match the query Q.

In our discussion, we will use the following notion of correctness for substring search over encrypted data. Definition 3 (Correctness).

Let s be the substring being searched for and $E_{K} (D^{'})$ be the set of encrypted documents that contain keywords matching the substring s. If Q is the result of the probabilistic algorithm, $Query$ , on s, we say that the scheme is correct if: $\begin{matrix} Pr [Retrieve (Q, T, V) = E_{K} (D^{'})] \approx 1 \end{matrix}$

3.4. Threat model

We assume that the server is honest but curious. It executes the protocol correctly and does not deviate from it, but analyses any data sent to it by the client and the corresponding interactions, in order to extract as much additional information as possible about the documents and the keywords. In the rest of the paper, we assume that the server and the adversary are the same entity. We define security for the SED protocols in terms of simulation based experiments: real and ideal experiment [13]. The approach to proving security under this framework is to show that the adversary cannot distinguish between the output of a real experiment and that of the ideal experiment, which is only based on the gathered information (leakage). We will show in the security analysis section that SED is secure under this definition. In the following, we elaborate on the characteristics of the adversary by discussing the types of information that the adversary can gather during the execution of the protocol.

3.4.1. Information leakage

We assume that the adversary has the characteristics of an adaptive adversary as defined by Curtmola et al. [13]. Such an adversary takes into consideration the history of search (that is, queries issued by the user previously as well as the results of those queries) before requesting for a new query. Information that are leaked to an adaptive adversary throughout the process of search are twofold: (1) the search pattern leakage as well as (2) the access pattern leakage. In the case of single-keyword SSE, search pattern leakage implies that the adversary will always know if a query was issued previously by the user. Access pattern leakage embodies a transcript of all accesses made by the user. This transcript consists, of the identifiers of encrypted documents searched for. Acquiring this knowledge, an adversary can build a pattern modeling the user’s accesses, for example, how often the user accesses a given document or what documents were not queried before, and so on. In addition, we are also required to take into consideration the setup leakage consisting of information disclosed by the encrypted data structure itself (before sending any search query). As an instance, for most single-keyword SSE, the encrypted data structures disclose the number and the size of documents stored on the server plus some additional information that we defer the details after the construction instantiation. We refer the reader to [13] for a detailed discussion on search and access pattern leakage. In the following, we denote by ${LK}_{s}$ the setup leakage, and by ${LK}_{a}$ the adaptive leakage.

As a side remark, for the adaptive leakage ${LK}_{a}$ , the search and access pattern may not be completely uncorrelated – search pattern can be partially disclosed via knowledge about the access pattern. To illustrate, let us consider the ideal case where the queries are totally randomized so that the adversary does not have any idea about the occurrence of these search queries but always knows the access pattern associated with the result of these queries. If two randomized queries output the same access pattern then, with a high probability, these queries are for the same keyword and, consequently, the adversary can always infer a statistical behavior of the search habit of the user. To prevent access and search pattern leakage, cryptographic primitives such as Oblivious RAM [17,28] have been proposed in the literature.4

⁴
Note that ORAM can hide the access pattern if and only if the ORAM blocks are padded to a maximum value to hide the number of documents identifiers associated to every keyword. Moreover, the encrypted documents, if stored in the same server, have also to be stored in an ORAM. That is, ORAM solution induces a lot of overhead in general if properly employed.

However, whereas for exact keyword search the knowledge of access pattern partially implies a highly likely knowledge of search pattern, it is not necessarily the case for substring search. This is because, in the latter case, matching keywords could be the same for different substring; this knowledge is not as accurate as the exact keyword search. Consequently, for our simulations, we will take the search and access patterns as two different types information leakages.

Both leakages, ${LK}_{s}$ and ${LK}_{a}$ , as any searchable encryption scheme, depends on the underlying instantiation. That is, every construction has its own leakage that eventually increases with the increase of the scheme expressiveness. The security definition of SSE constructions insures that the construction will not leak anything about the encrypted data except what it is disclosed in the leakage functions. Ideally, the leakage should be reduced to be as small as possible to avoid cryptanalysis attacks where the adversary holds some auxiliary information about the stored data [7]. We formally describe the leakage functions and its security impacts in Section 7.1. At a higher level, we show that SED leaks more than standard single-keyword SSE and this might lead to some non-trivial attacks on the encrypted data structure.

In the following, we formally recall adaptive security definition introduced by Curtmola et al. [13] and generalized by Chase and Kamara [10].

3.4.2. Adaptive security

Definition 4 ( $({LK}_{s}, {LK}_{a})$ -adaptive security).

Let us consider the substring search over encrypted data scheme as composed of four algorithms $SED = (KeyGen, Setup, Query, Retrieve)$ , and k, a security parameter. We present the following game based on two experiences ${Real}_{A}$ and ${Ideal}_{A, S}$ where $A$ is a stateful adversary, $S$ is a stateful simulator, and $({LK}_{s}, {LK}_{a})$ are the leakages outlined earlier. ${Real}_{A} (k)$ :

The challenger (user) runs the $KeyGen (k)$ algorithm and outputs the key K and the seed χ. $A$ sends the tuple $(D, W)$ and receives $(E_{K} (D), T, V) \leftarrow Setup (K, χ, D, W)$ from the challenger. $A$ generates a polynomial in k number of adaptive queries composed of arbitrary strings ${(s_{i})}_{1 ⩽ i ⩽ t}$ and sends them to the challenger. The adversary receives the search queries generated by the challenger such that $Q_{i} \leftarrow Query (χ, s_{i})$ . $A$ returns a bit as an output of the experiment.

{Ideal}_{A, S} (k)

The adversary outputs D. Given the leakage ${LK}_{s}$ , $S$ will generate the lookup table, the searchable part as well as the encrypted documents $(E_{K} (D), T, V)$ , where K is generated randomly, and sends them to the adversary. $A$ makes a polynomial number of adaptive queries ${(s_{i})}_{1 ⩽ i ⩽ t}$ and sends them to the simulator. Given the leakage ${LK}_{a}$ , the simulator sends the appropriate search queries to the adversary. Finally, $A$ returns a bit as an output of the experiment.

We say that SED is

({LK}_{s}, {LK}_{a})

-adaptive secure if for all polynomial time adversaries

A

, there exists a non-uniform polynomial-size simulator

S

such that:

\begin{matrix} | Pr [{Real}_{A} (k) = 1] - Pr [{Ideal}_{A, S} (k) = 1] | ⩽ negl (k) \end{matrix}

4. Substring search over encrypted data – pre-construction

We present two increasingly sophisticated substring search protocols. The first scheme, SED-1, is a toy constructions that shows how we can apply the orthogonalization concept. This first scheme suffers from some serious leakages that we handle in the second construction SED-2, in particular in its generalization. The search and storage complexity also decrease for SED-2. Both schemes provide both a general substring search as well as wildcard search. The general query allows one to search for a substring without fixing the position of the substring pattern within the keyword. The wildcard query allows one to search for a fixed substring at a fixed position in the keywords. The user provides the positional information of substring by utilizing a wildcard (do-not-care) symbol. (We use the “∗” symbol for denoting wildcards.) The wildcard symbol can be at the beginning of the substring such as “ $* * s_{1}$ ”, in the middle of two strings such as “ $s_{1} * * s_{2}$ ”, or may occur at multiple positions such as “ $s_{1} * * * s_{2} * * s_{3}$ ”, where $s_{1}, s_{2}, s_{3}$ are strings themselves.

Both schemes involve a setup phase that creates a single data structure that allows the substring matching for the entire corpus. This encrypted data structure has two parts – an encrypted lookup table that contains the association between keywords and corresponding documents, and a searchable part that allows identifying keywords that match a given query sent by the user. In addition, there is a preliminary pre-construction phase that transforms each keyword in the dictionary into an orthonormal keyword, and that we are detailing in the subsequent section.

4.1. Pre-construction

Let us consider the set of letters $l = {l_{1}, \dots, l_{t}}$ . The first step in the pre-construction is to create an independent family from these letters and then generate the associated orthogonalized vectors. The orthogonalization can be done employing many different algorithms, such as, the Householder Transformation [18], Givens Rotation [3] or the Gram–Schmidt Process [12]. We choose the Gram–Schmidt process because of its ability to terminate once it has arrived at the desired vector while the other techniques need to perform the computation on the entire set of input vectors (see [12] for more explanation).

We begin by generating t linearly independent vectors ${f_{1}, \dots, f_{t}}$ . For this purpose, given a pseudo-random generator G and a seed χ, we select the $t \cdot k$ first bits of $G (χ)$ such that for all $i \in [t]$ , $| f_{i} | = k + t$ bits, and $f_{i} = G {(χ)}_{i} ‖ (δ_{i, 1}, \dots, δ_{i, j}, \dots, δ_{i, t})$ , where $G {(χ)}_{i}$ is a sequence of $i \cdot k$ bits starting at the $(i - 1) \cdot k + 1$ bits of $G (χ)$ . It is clear that ${f_{1}, \dots, f_{t}}$ is a free family.

We finally associate each letter $l_{i}$ to a different vector $f_{i}$ in a one-to-one map. Next, we apply the Gram–Schmidt process for orthonormalization of the letters as follows using the property of Theorem 4.1 from [12].

Theorem 4.1.
If ${(f_{i})}_{1 ⩽ i ⩽ t}$ is a linearly independent family of a pre-Hilbert space, there exists an orthogonal family ${(o_{i})}_{1 ⩽ i ⩽ t}$ such that:
$ϕ (o_{i}, o_{j}) = ϕ (o_{i}, o_{i}) δ_{i, j}$ ,

$Span (f_{1}, \dots, f_{t}) = Span (o_{1}, \dots, o_{t})$ ,

$ϕ (f_{i}, o_{i}) > 0$ , where $ϕ (\cdot, \cdot)$ denotes the inner scalar product.

Definition 5.
The orthogonal projection p onto a vector line spanned by a non-zero u is defined as: $\begin{matrix} p_{u} (v) = \frac{ϕ (v, u)}{ϕ (u, u)} u . \end{matrix}$

Orthonormal Letter Construction: Let us consider ${(f_{i})}_{1 ⩽ i ⩽ t}$ a linearly independent family. According to Theorem 4.1, there is an orthogonal family ${(o_{i})}_{1 ⩽ i ⩽ t}$ . We can construct this family following the Gram–Schmidt process: $\begin{matrix} o_{i} = f_{i} - \sum_{k = 1}^{i - 1} p_{o_{k}} (f_{i}), for 1 ⩽ i ⩽ t . \end{matrix}$ ${(o_{i})}_{1 ⩽ i ⩽ t}$ , forms the new keyword orthogonal family that satisfies: $\begin{matrix} (1) & \forall i, j \in I, ϕ (o_{i}, o_{j}) = ϕ (o_{i}, o_{i}) δ_{i, j} . \end{matrix}$ Next, we normalize the vectors to obtain an orthonormal family: $\begin{matrix} \forall i, \in I u_{i} = \frac{1}{\sqrt{ϕ (o_{i}, o_{i})}} o_{i} . \end{matrix}$ At the end of this pre-construction phase, for each letter $l_{i}$ , we obtain an associated orthonormal value $u_{i}$ such that $| u_{i} | = t + k$ . We note here that the order of the orthogonalization is important to obtain a unique output of the orthogonalization since Gram–Schmidt process takes into consideration the order of the linearly independent vectors. Different order outputs different orthonormal vectors. We denote in the subsequent parts of the paper $Ortho (χ, l)$ , the entire pre-construction process that takes as input the seed χ and the set of pairwise distinct vectors l. In particular, we denote by $Ortho (χ, l_{i})$ , for $l_{i} \in l$ , the ith output of the pre-construction process such that $ϕ (Ortho (χ, l_{i}), Ortho (χ, l_{j})) = δ_{i, j}$ .

We now discuss our first strawman scheme – SED-1 for Substring search over Encrypted Data. SED-1 is discussed in terms of three phases – the Setup phase in which the user prepares the encrypted data structure that allows the server to search later on, the Query phase in which the user poses a search query to the server, and the Retrieve phase in which the server retrieves the encrypted documents that satisfy the query. We assume that the user generates the key K and the seed χ by using the $KeyGen (1^{k})$ algorithm where k is the security parameter.
5. Substring search over encrypted data #1 – SED-1

5.1. Setup phase

Let $D = {D_{1}, \dots, D_{n}}$ be the set of documents, and $W = {w_{1}, \dots, w_{z}}$ be a dictionary of keywords extracted from D. We assume that this dictionary is ordered randomly, e.g. pseudo-random evaluation on the lexicographic order. For each keyword $w_{i}$ in the dictionary W, we associate the set $D (w_{i})$ that contains the entire list of document identifiers, $D_{j}$ containing the keyword $w_{i}$ .

Next, the user creates an encrypted lookup table $T$ using any of the optimal lookup table (inverted index) encryption used in the single keyword SSE constructions such as [9,10,13]. The plaintext lookup table consists of a number of $⟨ key, value ⟩$ pairs, one for each keyword in the dictionary. The entity $key$ is a nonnegative integer equal to the position of the keyword in the dictionary. In other words, the ith $key$ in the lookup table is associated with the keyword $w_{i}$ in W. We would like to emphasize that we do not store any information related to the actual keyword. The $value$ is the set of document identifiers, $D (w_{i})$ , containing the keyword $w_{i}$ . The client finally outputs the encryption of the lookup table $T$ . This encrypted structure can be queried similarly to the existing single keyword SSE, i.e., by constructing tokens, in our case, based on the index position to retrieve documents identifiers. Given the row number, this encrypted lookup table will help the server during the retrieve phase to find the relevant document identifiers in an optimal search time leveraging existing constructions [8–10,13]. Based on one of the most efficient constructions, e.g., Cash et al. [8], the size of this lookup table is in $O (N)$ , where $N = \sum_{w_{i} \in W} D (w_{i})$ .

The third step constructs the searchable part $V$ of the data structure using which the server identifies which keywords contain the given substring. To begin with, we construct $V$ as $V = {v_{1}, \dots, v_{m}}$ . The value m represents the size of the longest keyword in the dictionary W. Each vector5

⁵
The vector $v_{i}$ is a $(t \times | W |)$ matrix, but for sake of clarity we will call it a vector.

v_{i}

is a row vector of a size equal to

| W |

, the number of keywords dictionary. Each vector

v_{i}

contains some value corresponding to the ith letter of each keyword in the dictionary. If the jth entry of the lookup table corresponds to a given keyword

w_{j}

, the jth component of the vector

v_{i}

will correspond to the ith letter of the same keyword. The vector

v_{i}

is generated as follows.

Consider the set of all possible letters $l = {l_{1}, \dots, l_{t}}$ and a special symbol ς that will be used to denote a ‘null’ position for keywords with a size lower than m. We apply the pre-construction $Ortho$ on $l \cup {ς}$ phase in order to generate the orthonormal set of letters. In the position j of the vector $v_{i}$ , we insert the orthonormal letter that exists in the ith position of the jth keyword. The vector $v_{i}$ is then equal to: $\begin{matrix} v_{i} = (u_{i, 1}, u_{i, 2}, \dots, u_{i, | W |}), \end{matrix}$ where $u_{i, j}$ is a column vector of the orthonormal ith letter of the keyword $w_{j}$ such that $u_{i, j} = Ortho (χ, w_{j} [i])$ . If the size of the keyword $w_{j}$ is smaller than m, we put the orthonormal value $Ortho (χ, ς)$ in all the corresponding positions of $v_{i}$ where $| w_{j} | + 1 ⩽ i ⩽ m$ .

We reiterate the same process for all m vectors. At the end, we obtain the following vector set $V = {v_{1}, \dots, v_{m}}$ that represents the searchable part associated with all possible positions of letters in keywords. At the end of the setup phase, the user sends to the server the collection $(E_{K} (D), T, V)$ , where $E_{K} (D)$ represents the encryption of the document collection using a IND-CPA-secure symmetric scheme, $T$ the encryption of the inverted index based on [8] construction, and $V$ the searchable part described above.

Storage overhead. The storage complexity of the SED-1 scheme is $O (| T | + | V | + | E_{K} (D) |)$ , where $| E_{K} (D) |$ is the size of the entire encrypted document corpus, $| T |$ is the size of the lookup table and $| V |$ is the size of searchable part. The size of the lookup table is in $O (N)$ , where $N = \sum_{w_{i} \in W} D (w_{i})$ , refer to Cash et al. [8] construction. Moreover, since m and t can be considered to be a fixed in our scenario ( $m \sim 40$ ), the size of the searchable part is in $O (| W |)$ . Consequently, the total storage complexity, excluding the files, is in $O (N)$ , as $N ≫ | W |$ . The encryption used for encrypting the document can be any IND-CPA secure symmetric encryption scheme such as AES in a counter mode.

5.2. Query phase

SED-1 offers two different types of queries: Wildcard Query and General Query. We first consider the Wildcard Query setting. This construction takes into account that wildcard characters (represented by “∗” symbol) can be at the beginning of a string or between two strings. Since we are dealing with substring matching, wildcards at the end of the query string are meaningless.

The query is constructed as follows. Let $s \in l \cup {*}$ be the string being searched for that includes letters and “∗”. The string s is associated with the set of letter indexes $M_{s}$ (see Section 3.1). For instance, if the user searches for all documents containing the following sequence “ $* * * l^{1} * * * l^{2} * * l^{3} * *$ ”, the string s is simplified to $l^{1} * * * l^{2} * * l^{3}$ where $l^{i} \in l$ and $p = 3$ , where p is the number of wildcard symbols at the front of the substring. The string s can have a size at most equal to m (which is a direct consequence of storing the longest keyword with a size equal to m). The string is then written as sequence of letters and “∗”s such that: $s = (s^{1}, s^{2}, \dots, s^{| M_{s} |})$ where: $\begin{matrix} s^{j} = \{\begin{matrix} l_{M_{s} [j]} & if s^{j} \in l \\ * & otherwise. \end{matrix} \end{matrix}$ The first step consists of computing the orthonormal value for each letter. We can precompute and store all the orthonormal letters at the client side lookup table to avoid computing the orthonormal value each time the user wants to search for a string. The storage or the computation of all possible letters is a small task since the size of all possible letters is mostly small, as in the case of ASCII code for example. At the end of this stage, the string will be $s = (u^{1}, \dots, u^{| M_{s} |})$ , where $u^{j}$ is equal to: $\begin{matrix} u^{j} = \{\begin{matrix} Ortho (χ, l_{M_{s} [j]}) & if s^{j} = l_{M_{s} [j]} \\ \sum_{i = 1}^{t} Ortho (χ, l_{i}) & otherwise, \end{matrix} \end{matrix}$ where $Ortho (χ, l_{i})$ is the orthonormal letter corresponding to the letter $l_{i} \in l$ as generated by the pre-construction (see Section 4.1).

The last step is to adjust the orthonormal string s by making the location of first wildcard characters meaningful for the server. Indeed, we will see in the next section that the retrieve phase is based on an inner product computation between each orthonormal letter in the query and the corresponding searchable part position. We could have processed the first wildcards much in the same way as the other letters or wildcards; however this processing is not meaningful – the server will easily figure out that these first letters are wildcards since they will match the entire searchable part position. Moreover, in this case it will also cost more because of redundant inner product computations.

In the Wildcard Query setting, the main idea is to specify the number, p, of wildcards in the beginning of the query. We can then send to the server the position of the first letter of the string s in the keyword as $(s, p)$ , p defining the position at which the server will start the search. In the General Query setting the user wants to search for a string pattern regardless of its position. This case is a generalization of the Wildcard Query where p can have any value in the range $(1, \dots, m - | s |)$ . In this case, the user has only to send the string s to search for and the server will make a loop to search for all possible matching keywords.

5.3. Retrieve phase

The retrieve phase is based on an inner product computation between each element of s and the corresponding searchable part. A keyword $w_{j}$ matches the substring in the query iff in all positions of the resulting inner products, the values are different from zero. In the following, we detail step by step how the document retrieval is performed in the server side for both kind of queries.

If the server receives the query $(s, p)$ , the server assumes that the user has posed a Wildcard Query. Given that the position of the first relevant letter is $p + 1$ , the server first computes an inner product between the first component of s and the corresponding vector $v_{p + 1}$ that represents the searchable part stored in the server associated with the position $p + 1$ such that $α_{1} = {s_{1}}^{T} \cdot v_{p + 1}$ with $α_{1}$ being a vector of size equal to $| W |$ . If $α_{1, j} = 0$ , where $1 ⩽ j ⩽ | W |$ , the keyword $w_{j}$ does not match the query; otherwise, if $α_{i, j} \neq 0$ it implies that the keyword $w_{j}$ contains the letter $s_{1}$ at position $p + 1$ . Indeed, due to the orthogonality of the vectors associated with the letters, when there is a zero value in a given position in $α_{1}$ , it means that the letter searched for and the letter existing at this position are different.

A naïve approach to test for this is to compute $α_{i}$ for $1 ⩽ i ⩽ | M_{s} |$ and verify at the end if there are positions for all these vectors where the values are all different from zero. This method induces many unnecessary inner products since we are computing the inner product even for keywords that we know will not be matching the query. Indeed, if there is a position in $α_{1}$ which is equal to zero, we know that from the first verification we can filter keywords that do not match the query. Instead, we instantiate a set $P_{0}$ equal to $(1, \dots, | W |)$ . While computing the inner product $α_{1}$ , we delete from $P_{0}$ all positions where $α_{1}$ is equal to zero and output the new value of positions $P_{1}$ . Restricted only to the positions $P_{1}$ , we compute the inner product between $s_{2}$ and $v_{p + 2}$ so the output of the second search will be a set of positions $P_{2}$ which is a subset of $P_{1}$ . For $α_{3}$ we use $P_{2}$ and so on and so forth. We reiterate the same $| M_{s} |$ operations and the final output will be a set of positions $P_{| M_{s} |}$ .

This resulting set contains the positions of keywords matching the query. The server sends back this set to the client. The client generates a token for every position in the set using the encrypted searchable encryption employed to construct $T$ (recall that we are using Cash et al. [8] construction). For every token, the server queries the structure $T$ and sends the results to the client. We should underline the fact that the client can find in the final result redundant documents’ identifiers. This holds as different keywords can be associated to the same document’s identifier in $T$ . To avoid this repetition, a disjunctive SSE construction has to be used instead of the one by Cash et al. [8], we leave constructing a disjunctive scheme for future work.

Our second case consists of receiving the string s from the user and the server performing a general substring matching. In order to perform this task, the server executes the same operation as if it receives a string with a position information, $(s, i)$ , where $1 ⩽ i ⩽ m - | s |$ . The complexity of our scheme will increase with a multiplicative coefficient equal to $m - | s |$ where m is the size of the longest keyword.

The search computation is not dependent on the size of the database (number of files stored). Rather the search is based on the inner product operations that are in $O (| W |)$ i.e. linear in the size of the dictionary. Note that since $| W | ≪ n$ , one can consider the search complexity of SED-1 sublinear in the size of dataset.

The storage complexity is equal to the size of the encrypted lookup table which is dependent on the distribution of keywords per document, to which we add the searchable part which is in $O (| W |)$ . The search does not require any exponentiation and the efficiency of the inner product makes the scheme practical for small to moderate size databases. However this scheme suffers from many statistical leakage that can end up with the disclosure of the keywords’ contents. This disclosure is due to the detailed construction of searchable part $V$ , these vectors, even if they are constructed using a pseudo random generator that hides the content, the orthogonalization feature leaks more information about the relation between the randomized orthonormal letters within these vectors. In the next section, we discuss some attacks on our first scheme that will lead us to construct a less-leaky scheme – SED-2.

5.4. Problems with SED-1

SED-1 has some vulnerabilities that make it unsuitable for a real-world deployment and which is why we refine SED-1 into SED-2. SED-1 is based on the searchable part $V = (v_{1}, \dots, v_{m})$ where the vector $v_{i}$ contains all letters in the ith position; this searchable part can disclose many information about the distribution of letters in these vectors due to the orthogonal feature of their components. These attacks are analogous to attacks on substitution ciphers using the frequency analysis technique. We discuss two off-line attacks, where the attacks rely only on the knowledge of the searchable part.

5.4.1. Letter frequency attack with known dictionary

We assume that the adversary knows the dictionary W, and the adversary has access to the searchable part $V$ . The goal of the adversary is to find the keywords based on the distribution of letters in the given dictionary. For illustration purposes, we assume that we work with the British Oxford English dictionary. The adversary will launch the attack shown in Algorithm 1 on $V$ .

Algorithm 1:

Letter frequency attack with known dictionary

The algorithm first computes the number of characters stored in the searchable part (lines 3–10). The set $G_{1}$ contains the occurrence of the first character, $G_{2}$ the second, etc. Then line 11 determines the set $G_{z}$ containing the don’t care component; this can be determined by computing the set that contains the maximum number of tuples $(i, j)$ for a given position, where i is the position of the keyword and j is the character in that position. Lines 12–14 compute the frequency of resulting characters by calculating first the total number of characters (excluding those in $G_{z}$ ) and then by dividing every set size $| G_{i} |$ by the total size. Lines 15–23 replace the initial values of the searchable part by the corresponding characters based on comparing a known frequency as the one from British Oxford English and the computed ones. Finally, the algorithm outputs $V$ .

The attack is a direct consequence of the detailed searchable part construction that gives away different information about the frequency of keyword letters. Based on $V$ , the attack first determines positions that contain the same letter. Next, the adversary determines the set $G_{z}$ that contains the ς value that we have used as padding in case of short keywords. This can be done by taking into account the distribution of the keywords’ lengths in the dictionary (see Fig. 1). Thus, based on the frequency of the characters in the dictionary W (see Fig. 2), the adversary can associate the character $c_{i}$ with its corresponding position.

Fig. 1.

Length Frequency.

Fig. 2.

Letter Frequency.

Note that, in this attack, we have made a strong assumption that the adversary has an accurate prior knowledge of the dictionary used by the user. In the next attack, we will assume that the adversary proceeds with the attack without any prior information about the dictionary.

5.4.2. Letter frequency attack with unknown dictionary

The adversary may not know the exact dictionary but can easily know the distribution of characters in the searchable part $V$ by performing multiple inner products between the different components of these vectors (see Section 5.4.1). The adversary can then have a finite size of possible characters, which we denote by q. By looking for all possible combinations of letters, the adversary performs $q!$ combinations to determine if for each combination all keywords belong to some language. The brute force can be expensive. For example, if the number of characters $q = 26$ (which is the size of the English alphabet), the possible solutions are approximately equal to $2^{88}$ (26!). However, the adversary can make the search cheaper without the dictionary.

The attacker can try to use certain types of information to refine the data distribution model. These can be, for example, the geographic localization of the user, the field of interest, etc. However, we assume these to be well hidden from the adversary. Moreover, knowing the exact distribution of characters for each keyword in $V$ , the adversary can generate therefore the frequency of letters in the whole dataset. In the state of the art, there are many frequency studies about the distribution of letters that differs depending on the field such as Scientific, Religious, Financial field etc. Moreover, the adversary can go further by computing the frequency of letters at the beginning of the word, the end of the word, length distribution, frequency of bigrams, trigrams etc., that give more accurate idea of the language used and consequently approach the adversary from the exact letters.

6. Substring search over encrypted data #2 – SED-2

We have seen that the first scheme SED-1 is insecure and can leak the keywords in the case of a known dictionary. We should point out that it is a real challenge to perform substring matching and at the same time hide the distribution of letters within the dictionary from the server. In this section, we present the second and main construction, SED-2, that partially6

⁶
Refer to Section 7.1 for exact description of SED-2 leakage.

hides the letter-distribution of keywords.

The main challenge for SED-2 is to maintain the order of letters within a given keyword. Indeed, only summing up orthonormal letters does not save any pattern with a size bigger than that of the keyword. SED-2 addresses this issue by creating a sort of chain of letters, intelligible to the user with an a-prior stored state, that allows one to search for any pattern. Add to that, this new feature SED-2 also consists of linking every character to its position. That is, two equal characters at different positions will be treated in the setup phase as two totally different characters. This feature enables to hide a great part of the information leakage in SED-1. We will also see that this position based construction can be further generalized with a pattern construction to even hide more about characters’ frequency, refer to Section 8. SED-2 is more efficient and induces less storage complexity than SED-1. In the following, we give a step-by step explanation of both the setup and the search phases (the key generation is still the same as SED-1). We give an algorithmic description of SED-2 in Figure 3.

6.1. Setup phase

In SED-2, the construction of the encrypted lookup table $T$ is similar to SED-1. SED-2 introduces a more compact searchable part composed of only of one vector $V$ . In the following, we discuss the construction of the vector $V$ .

The size of the vector $V$ is equal to the size of the dictionary W. Each component of $V$ corresponds to one keyword in W. Let us consider the set of letters $l = {l_{1}, \dots, l_{t}}$ . We generate m different letter sets (see Fig. 4), each set contains letters for a given position. We denote by $l^{i} = {l_{1}^{i}, \dots, l_{t}^{i}}$ the set of letters at the ith position, where $l_{j}^{i} = l_{j} ‖ i$ . The new set of letters is the concatenation of all possible letters such that $L = (l^{1}, \dots, l^{m})$ .

Fig. 3.

Substring search over encrypted data SED-2 for the Wildcard search case.

Fig. 4.

Example of letters set expansion.

We apply the pre-construction (see Section 4.1) on the entire set of vectors in $L$ in order to generate the orthonormal letters that we denote by $L_{n} = {u_{1}^{1}, \dots, u_{t}^{1}, u_{1}^{2}, \dots, u_{t}^{m}}$ such that $L_{n} \leftarrow Ortho (χ, L)$ . Let us consider each keyword $w_{j}$ in the dictionary as a vector of letters in $L$ associated with an index set $M_{j}$ , such that $w_{j} = (l_{M_{j} [1]}^{1}, \dots, l_{M_{j} [| w_{j} |]}^{| w_{j} |})$ . The corresponding orthonormal keyword is then equal to $w_{j} = (u_{M [1]}^{1}, \dots, u_{M [| w_{j} |]}^{| w_{j} |})$ . The user now uniformly samples m random real nonnegative values, such that $(a_{1}, \dots, a_{m}) \overset{R}{\leftarrow} R_{+, *}^{m}$ , where $\forall i, k a_{i} \neq a_{k}$ . The user then computes the value $V_{j} = \sum_{i = 1}^{| w_{j} |} a_{i} \cdot u_{M_{j} [i]}^{i}$ . The user repeats the same computation for all keywords in the dictionary and outputs the following value: $\begin{matrix} V = (\sum_{i = 1}^{| w_{1} |} a_{i} \cdot u_{M_{1} [i]}^{i}, \dots, \sum_{i = 1}^{| w_{| w |} |} a_{i} \cdot u_{M_{| w |} [i]}^{i}) \end{matrix}$ The user should save locally the values $κ = (a_{1}, \dots, a_{m})$ as a private state. These values captures the adjacency information between the same keyword letters and will be used during the Retrieve phase.

At the end of the Setup phase, the user sends to the server the collection $(E_{K} (D), T, V)$ where $E_{K} (D)$ represents the encryption of the document collection using an IND-CPA-secure symmetric scheme. We would like to point out that the storage complexity of the searchable part is a factor of m less than the one introduced in SED-1.

6.2. Query phase

To discuss the Query phase, we again differentiate between the Wildcard Query and the General Query. Let us first consider that the user wants to search for a specific pattern in a fixed position. The user wants to search for the string s which can be any combination of wildcards and letters (no wildcard can be after the last letter). We denote by $M_{s}$ the position of letters in s. For instance if s is equal to “ $* l^{1} * * * l^{2} * * *$ ”, $M_{s}$ is equal to ${2, 6}$ . The user generates the orthonormal letters $L_{n} = {u_{1}^{1}, \dots, u_{t}^{1}, u_{1}^{2}, \dots, u_{t}^{m}} \leftarrow Ortho (χ, L)$ based on the pre-construction on $L = {l^{1}, \dots, l^{m}}$ , where m is the size of the longest keywords.

The user then computes the following value for the search query and sends the query Q to the server. $\begin{matrix} (2) & Q = \frac{1}{\sum_{i = 1}^{| M_{s} |} a_{M_{s} [i]}} \sum_{i = 1}^{| M_{s} |} u_{M_{s} [i]}^{i} . \end{matrix}$ For the second case, where the user wants to search for the string s at any position in any keyword, the user generates multiple queries instead of one query Q. Each of these queries is intended to search for a specific position. The number of queries in this case is equal to $m - | s |$ where the string s does not contain any wildcards at the beginning or at the end, where m is the size of the longest keyword. Let $M_{s_{1}}, M_{s_{2}}, \dots, M_{s_{m - | s |}}$ be the positions of letters within $s, * s, \dots, \underset{m - | s |}{\underset{︸}{* * \dots *}} s$ . For example, if s is equal to “ $l^{1} * * * l^{2}$ ” then $M_{s_{1}} = {1, 4}$ , $M_{s_{2}} = {2, 5}$ and so on. The user then sends the following query to the server. $\begin{matrix} Q = (Q_{1}, \dots, Q_{m - | s |}) \end{matrix}$ where $\begin{matrix} Q_{j} = \frac{1}{\sum_{i = 1}^{| M_{s_{j}} |} a_{M_{s_{j}} [i]}} \sum_{i = 1}^{| M_{s_{j}} |} u_{M_{s_{j}} [i]}^{i} . \end{matrix}$

6.3. Retrieve phase

The Wildcard Query is a special case of the General Query. We first discuss the case for the Wildcard Query. If the server receives one query, it assumes that the user seeks a Wildcard search. The server performs the following steps for each $j \in (1, \dots, | W |)$ . We will say that the keyword $w_{j}$ matches the query if and only if $Q^{T} \cdot V_{j} = 1$ .

Based on the encrypted lookup table $T$ and the resulting positions for which the result equals one, the client generates the required token to the server who fetches the encrypted documents’ identifiers from $T$ . The server finally sends to the user all the encrypted matching documents.

If, on the other hand, the server receives multiple sub-queries, it considers that the user has provided a General query. Note that, if there is a keyword that matches a given sub-query, there is no need to compute again its inner product value. This is because it already belongs to the matching positions. So to search efficiently, we first create a set P equal to $(1, \dots, | W |)$ . For the first query $Q_{1}$ , the server computes for each $j \in P$ the value ${Q_{1}}^{T} \cdot V_{j}$ , and delete from P all indexes j where the result is equal to one. The server outputs the new value $P_{1}$ . The server computes again the inner product for the second query as ${Q_{2}}^{T} \cdot V_{j}$ , where $j \in P_{1}$ and outputs the new set $P_{2}$ . The server continues this process and finally outputs the set $P_{m - | s |}$ . The server ultimately sends the corresponding encrypted documents from the lookup table.

6.4. Correctness of SED-2

The correctness of the scheme can be easily verified. The query will contain orthonormal letters depending on the position in the string searched for. While the server receives the query, the inner product of the query and the component $V_{i}$ will be equal to one if and only if all letters of the query exist in the same position in the encoded component $V_{i}$ . If this is the case the inner product of each equal orthonormal letters will be $\sum_{i = 1}^{| M_{s} |} a_{M_{s} [i]}$ where s is the substring searched for, which is equal to the denominator of the query. If this product is equal to one, the server will send the exact corresponding documents that match the substring from the lookup table.

7. Security proof for SED-2

7.1. Leakage description of SED-2

SED-2 construction, as any symmetric searchable encryption construction, has some leakage. This leakage is divided in two types. A setup leakage that the server (adversary) can undercover by just looking to the encrypted data structures, and, an adaptive leakage that the adversary can learn during the search phase. SED-2, if compared to single keyword SSE constructions, leaks more at the price of offering better expressiveness. In the following, we details both of these leakages.

Setup leakage ${LK}_{s}$ . SED-2 setup phase outputs an encrypted lookup-table $T$ , along with the searchable part $V$ . The first encrypted data structure leaks ${LK}_{s}^{II} (D, W)$ . Based on the specific instantiation chosen for our algorithm, this leakage might be slightly different from a construction to another. If we choose the construction by Cash et al. [8], then the encrypted inverted index only leaks N, the number of keyword-document identifier such that $N = \sum_{w \in W} D (w)$ . Contrary, to previous SSE, $V$ can leak more than $| W |$ , it leaks the number of characters and therefore the size of the alphabet used for the construction t. Moreover, the server can learn whether two keywords $w_{i}$ and $w_{j}$ have the same character at the same position by performing simple inner product between the coordinates of $V$ . We formalize this leakage in the following: $\begin{matrix} {LK}_{s}^{SED} (D, W) = {{LK}_{s}^{1} (D, W), {LK}_{s}^{2} (D, W)}, \end{matrix}$ where ${LK}_{s}^{1} (D, W) = ({LK}_{s}^{II} (D, W), m, | W |, t)$ and ${LK}_{s}^{2} (D, W) = {k ∣ \forall k \in [m], v_{k} = w_{k}}_{v, w \in W}$ .

Adaptive leakage ${LK}_{a}$ . During search operations, SED-2 like most of SSE constructions, leak the search pattern and access pattern, given τ queries ${(q_{i})}_{i \in [τ]}$ . However, as previously illustrated, due to the additional expressiveness, SED-2 can leak more than traditional exact keyword SSEs, ${LK}_{a}^{II} (D, {(q_{i})}_{i \in [τ]})$ . In SED-2, for the Wildcard search, the server learns whether two queries have the same character at the same position. This leakage, dubbed as query composition leakage, can give the adversary an additional knowledge about the searched for queries. It is clear that the query composition leakage implicitly encapsulates the query occurrences which is the traditional search pattern leakage of SSE constructions. The second component of the adaptive leakage is the one capturing the association between the query and the keywords in $V$ . Every searched for keyword will be associated to some specific keywords in $V$ , we refer to this leakage as keywords pattern leakage. Finally, the server has to retrieve the identifiers of documents that match a specific query. That is, the server will learn the association between every query and the documents’ identifiers, which is known in SSE’s literature as the access pattern. We formalize the adaptive leakage in the following: $\begin{matrix} {LK}_{a}^{SED} (D, {(q_{i})}_{i \in [τ]}) = {{LK}_{a}^{II} (D, {(q_{i})}_{i \in [τ]}), QC (D, {(q_{i})}_{i \in [τ]}), KP (D, {(q_{i})}_{i \in [τ]}), AP (D, {(q_{i})}_{i \in [τ]})}, \end{matrix}$ where $\begin{matrix} QC (D, {(q_{i})}_{i \in [τ]}) = {A ∣ \forall i, j \in [τ], \forall k \in [m], A [i, j, k] = 1 if q_{i, k} = q_{j, k}}, \end{matrix}$ and, $\begin{matrix} KP (D, {(q_{i})}_{i \in [τ]}) = {A ∣ \forall i \in [τ], A [i] = (i_{1}, \dots, i_{h}), where \forall j \in [h], \forall k \in [| q_{i} |], q_{i, k} = w_{i_{j}, k}}, \end{matrix}$ and, $\begin{matrix} AP (D, {(q_{i})}_{i \in [τ]}) = {A ∣ \forall i \in [τ], A [i] = (D (w_{i_{1}}), \dots, D (w_{i_{h}})), where (i_{1}, \dots, i_{h}) = KP (D, q_{i})} \end{matrix}$

This setup and adaptive leakage described above is the only leakage that SED-2 leaks to the adversary when a search is performed. We will show in the next section that SED-2 is $({LK}_{s}^{SED}, {LK}_{a}^{SED})$ -semantically secure as in Definition 4, i.e., that SED-2 does not leak any information to the server besides the stateful captured leakage ${LK}_{s}^{SED}$ and ${LK}_{a}^{SED}$ . Note that the leakage in some scenarios might help the adversary to infer additional information about the encrypted data structure, especially when the adversary holds adequate auxiliary information.

7.2. Security proof of SED-2

The SED-2 protocol is $({LK}_{s}^{SED}, {LK}_{a}^{SED})$ -semantically secure in the honest but curious model. We now provide a simulation based proof in support of our security claim. We restrict our proof to the Wildcard search model.

Theorem 7.1.
If $E$ is a private-key IND-CPA-secure encryption scheme, G is a pseudo-random generator, ${STE}_{II}$ a ${({LK}_{s}^{II}, {LK}_{a})}^{II}$ -semantically secure inverted index encryption, then SED-2 is $({LK}_{s}^{SED}, {LK}_{a}^{SED})$ -semantically secure.
Proof.
Let $S_{II}$ be the simulator guaranteed to exist by the semantic security of ${STE}_{II}$ . Let us consider the simulator $S$ of SED that works as follows.

Given ${LK}_{s} (D, W)$ , $S$ simulates the output of the $Setup$ as follows:
set $T \leftarrow S_{II} ({LK}_{s}^{II} (D, W))$

based on ${LK}_{s}^{SED}$ , the simulator $S$ extracts $| W |$ , t and m. $S$ generates $χ \overset{R}{\leftarrow} {0, 1}^{k}$ . The simulator computes $(g_{1}, \dots, g_{t \cdot m}) \leftarrow G (χ)$ , where $| g_{i} | = t \cdot m + k$ , where k is the security parameter. For every $i \in [| W |]$ , the simulator, based on ${LK}_{s}^{2}$ , computes $V_{i} = {(g_{j})}_{j \in A_{i}}$ , where $A_{i} = {LK}_{s}^{2} [i]$ .

the simulator $S$ generates a key at random $K_{2} \overset{R}{\leftarrow} {0, 1}^{k}$ and sets $\begin{matrix} E_{K_{2}} (D) = (E_{K_{2}} (0^{| D_{1} |}), \dots, E_{K_{2}} (0^{| D_{n} |})) \end{matrix}$

The simulator outputs $(E_{K_{2}} (D), V, T)$ .

The simulator now simulates the query Q for the Wildcard search as follows. $S$ has as input ${LK}_{a}^{SED}$ . Given the queries ${(s_{i})}_{i \in [τ]}$ , the simulator generates for every $i \in [τ]$ , $Q_{i}$ such that for all $j \in [| s_{i} |]$ , if $\exists z < i$ such that $QC [z, i, j] = 1$ , then $Q_{i, j} = g$ , where g is the previously generated value, otherwise if $QC [z, i, j] = 0$ , the simulator sets $Q_{i, j} = g$ , where g is sub-vector of $G (χ)$ that verifies $g \in V_{j_{1}} \cap \dots \cap V_{j_{h}}$ , where $(j_{1}, \dots, j_{h}) \in {LK}_{s}^{2} (D, W)$ .

The simulator $S$ generates the tokens for $T$ such that for each $i \in [τ]$ , for all $j \in KP [i]$ , set ${tk}_{i, j} \leftarrow S_{II} ({LK}_{a}^{II} (D, i))$ .

It remains to show that for all probabilistic polynomial-time adversaries $A$ , the probability that ${Real}_{SED, A} (k)$ and the probability that ${Ideal}_{SED, A, S} (k)$ output 1 is negligibly close. We show this by the sequence of these hybrid games:
$Gam e_{0}$ is the same as ${Real}_{SED, A} (k)$ experiment. Create an empty dictionary $T$ .

$Gam e_{1}$ is the same as $Gam e_{0}$ except that every component of $V$ is replaced with the original (non-orthogonal vectors) PRG evaluations. Every component $V_{i}$ in $V$ is replaced with a vector of the corresponding PRG evaluations of characters composing $V_{i}$ , for all $i \in [| W |]$ . Also, for all $i \in [τ]$ , $Q_{i}$ is replaced with the vector of PRG evaluation of the characters searched for.

$Gam e_{2}$ is the same as $Gam e_{1}$ except that the values of PRG evaluation are replaced with random values as follows: for all $i \in [| W |]$ , for all $v \in V_{i}$ , if $T [v]$ is not empty, then set v to $T [v]$ , otherwise, set $T [v] \overset{R}{\leftarrow} {0, 1}^{k}$ , then set v to $T [v]$ , and update $V_{i}$ accordingly. The queries $Q_{i}$ , for all $i \in [τ]$ , are replaced with random values as follows: for all $i \in [τ]$ , for all $v \in Q_{i}$ , $T [v]$ is not empty, then set v to $T [v]$ , otherwise, set $T [v] \overset{R}{\leftarrow} {0, 1}^{k}$ , then set v to $T [v]$ , and update $Q_{i}$ accordingly.

$Gam e_{3}$ is the same as $Gam e_{2}$ except that the encryption of documents is replaced with $E_{K_{2}} (0^{| D |})$ , for all $D \in D$ .

$Gam e_{4}$ is the same as $Gam e_{3}$ except that $T$ is replaced with $S_{II} ({LK}_{s}^{II} (D, W))$ and for all $i \in τ$ , for all $j \in KP [i]$ , replace all tokens by ${tk}_{i, j} \leftarrow S_{II} ({LK}_{a}^{II} (D, i))$ .

Note that $Gam e_{4}$ is the ideal experiment.

Claim. For all PPT $A$ , $\begin{matrix} Pr [Gam e_{1} = 1] = Pr [Gam e_{0} = 1] . \end{matrix}$

This transition just replaces the orthogonal values in every $V_{i}$ in $V$ and $Q_{j}$ , for $j \in [τ]$ , by the non-orthogonal values, and represents them as a vector of a PRG evaluation. Recall that this trivially stems from the fact that we assume that the orthogonalization is just a tool to speed-up the verification and there exists a polynomial time algorithm that can perform this basis’ transformation.7
⁷
This game shows that our SED security is not based on the linear transformation but on the prior PRG evaluation.

That is the view of an PPT adversary $A$ in $Gam e_{0}$ and $Gam e_{1}$ is the same.

Claim. For all PPT $A$ , $\begin{matrix} Pr [Gam e_{2} = 1] - Pr [Gam e_{1} = 1] ⩽ negl (k) . \end{matrix}$

We show that if there exists an adversary $A$ that breaks the claim, then there exists an adversary $B$ that can distinguish between the output of pseudo-random generator and a random value with respect to a simulator $S^{'}$ . $B$ emulates $A$ . When receiving, D from $A$ , $B$ , generates all characters in D, $(l_{1}, \dots, l_{t})$ , computes as in Step 1 in the $Setup$ phase in Algorithm 3, $L$ . $B$ generates an inverted index that associates every keyword w to its documents identifiers. $B$ outputs $L$ . Upon receiving $L^{}$ , from either ${Read}_{PRG, B} (k)$ , or ${Ideal}_{PRG, B, S^{'}}$ , $B$ outputs to $A$ : $(E_{K} (D), V, T)$ , such that:

$K_{1}, K_{2} \overset{R}{\leftarrow} {0, 1}^{k}$ , $T \leftarrow SKE . Setup (1^{k}, D)$ and for all $i \in | W |$ , for all $v \in V_{i}$ , if $T [v]$ is not empty, then set v to $T [v]$ , otherwise, set $T [v]$ to the next k bits in $L^{}$ , then set v to $T [v]$ , and update $V_{i}$ accordingly.

If $A$ outputs a substring $s_{i}$ for all $i \in [τ]$ , $B$ outputs $Q_{i}^{}$ such that: for all $v \in Q_{i}$ , if $T [v]$ is not empty, then set v to $T [v]$ , otherwise, set $T [v]$ to the next k bits in $L^{}$ , then set v to $T [v]$ , and update $Q_{i}$ accordingly.

$B$ sends the following to $A$ : $(Q_{i}, {tk}_{i, 1}, \dots, {tk}_{i, | Result |})$ , where $Result$ are all indices j of $V$ where characters of $Q_{i} \subseteq V_{j}$ .

After answering all $A$ ’s queries, $A$ outputs a bit that $B$ returns as its own output. We want to emphasize that if $B$ has been executed in a ${Real}_{PRG, B} (k)$ , than the view of $A$ is exactly the one in $Gam e_{1}$ , otherwise then the view of $A$ is the one of $Gam e_{2}$ . It follows by our assumption of $A$ contradicts the claim that: $\begin{matrix} Pr [{Real}_{PRG, B}] - Pr [{Ideal}_{PRG, B, S^{'}}] \end{matrix}$ is non-negligible in k which is a contradiction.

Claim. For all PPT adversary $A$ , $\begin{matrix} Pr [Gam e_{3} = 1] - Pr [Gam e_{2} = 1] ⩽ negl (k) . \end{matrix}$ This claim clearly holds under the IND-CPA security assumption.

Claim. For all PPT adversary $A$ , $\begin{matrix} Pr [Gam e_{4} = 1] - Pr [Gam e_{3} = 1] ⩽ negl (k) . \end{matrix}$ We show that if there exists an adversary $A$ that breaks the claim, then there exists an adversary $B$ that can can break the semantic security of the inverted index encryption ${STE}_{II}$ with respect to an arbitrary PPT simulator $S^{'}$ . $B$ start running $A$ . When receiving, D from $A$ , $B$ , generates all characters in D, $(l_{1}, \dots, l_{t})$ , computes $L$ . $B$ generates an inverted index $DB = {(w_{i}, D (w_{i}))}_{i \in | W |}$ that associates every keyword w to its documents identifiers $D (w_{i})$ . $B$ outputs $DB$ . Upon receiving $T^{}$ , from either ${Read}_{{SET}_{II}, B} (k)$ , or ${Ideal}_{{SET}_{II}, B, S^{'}}$ , $B$ outputs to $A$ : $(E_{K} (D), V, T^{})$ , such that:

$K_{1}, K_{2} \overset{R}{\leftarrow} {0, 1}^{k}$ , for all $i \in | W |$ , for all $v \in V_{i}$ , set v to $T [v]$ .

If $A$ outputs a substring $s_{i}$ for all $i \in [τ]$ , $B$ outputs $Q_{i}$ such that for all $v \in Q_{i}$ , v to $T [v]$ and outputs $Result$ as its own answer to $T^{}$ and receives $({tk}_{i, 1}^{}, \dots, {tk}_{i, | Result |}^{})$ , where $Result$ are all indices j of $V$ where characters of $Q_{i} \subseteq V_{j}$ .

$B$ sends the following to $A$ : $(Q_{i}, {tk}_{i, 1}^{}, \dots, {tk}_{i, | Result |}^{*})$ .

After answering all $A$ ’s queries, $A$ outputs a bit that $B$ returns as its own output. We want to emphasize that if $B$ has been executed in a ${Real}_{{STE}_{II}, B} (k)$ , than the view of $A$ is exactly the one in $Gam e_{3}$ , otherwise if $B$ has been executed in ${Ideal}_{{STE}_{II}, B, S^{'}} (k)$ , then the view of $A$ is the one of $Gam e_{4}$ . It follows by our assumption that: $\begin{matrix} Pr [{Real}_{{STE}_{II}, B}] - Pr [{Ideal}_{{STE}_{II}, B, S^{'}}] \end{matrix}$ is non-negligible in k which is a contradiction. This ends our proof. □

8. SED-2 generalization

SED-2 hides information related to characters that exist at different positions while not impacting the scheme’s correctness. However, we have described in Section 7.1 SED-2 leakage, and we have shown that an adversary can recover non-trivial information about the encrypted data structure even in the setup phase. With adequate auxiliary information, an adversary can run many attacks based on characters frequency. This unfortunately can lead to the disclosure of all part of keywords dictionary. Fortunately, we can generalize SED-2 construction that leaks much lesser with a new pattern’s construction. The ultimate goal of the generalized SED-2 construction is to decrease the setup leakage to be as insignificant as possible.

8.1. Overview

The setup phase is based on a new parameter, pattern length γ, that determines the length of the pattern that is going to be orthogonalized. Every pattern is now determined by its position but also by its length. For every character in $l = {l_{1}, \dots, l_{t}}$ , for all $i \in [m]$ , add $\begin{matrix} \underset{γ characters}{\underset{︸}{c_{1} ‖ (i - γ), \dots, c_{γ} ‖ (i - 1)}}, l ‖ i, \underset{γ characters}{\underset{︸}{c_{γ + 1} ‖ (i + 1), \dots, c_{2 γ} ‖ (i + γ)}} \end{matrix}$ to $L$ , for all $c_{1}, \dots, c_{2 γ} \in l$ and $γ \in [m]$ . Note that SED-2 is a special case of our generalization when $γ = 0$ .

The next step is to apply the orthogonalization process $Ortho$ that outputs orthonormal vectors as described in the pre-construction Section 4.1.

The way we construct the searchable part $V$ is similar to the one in SED-2. For all $w \in W$ , we first determine all patterns in w, and sums up all the corresponding orthonormal characters while using the chaining between patterns as in SED-2. This pattern enables to search for all substrings that have a γ-length pattern at least. The search is very similar to SED-2.

This generalization introduces a new balance between search expressiveness and leakage. In SED-2, the leakage can be greatly reduced when increasing γ. We notice that starting from $γ = 1$ , the setup leakage dramatically reduces. However, note that this comes also at the expense of a slightly larger components of the searchable part $V$ .

The setup leakage as well as the adaptive leakage is now limited to the following. The encrypted searchable part now leaks only the information that two keywords have the same pattern if they are also at the same position. For example, the keywords arbitrary and binary both contain the pattern $ary$ , but at two different positions. This will translate in two different orthonormal values that are not going to be disclosed in the setup phase. Another example reduced leakage is the following. Consider the keywords art and arc, they both contain two characters at the same positions. SED-2 would have disclosed this information in the setup phase while in the generalization this information is hidden. Recall that SED-2 is a special case where the length of the pattern equals 0. In the following, we formalize the leakage of the generalized construction of SED-2.

8.2. Leakage

As illustrated in the previous section, the generalization offers better security guarantees at the cost of slightly reduced expressiveness. We provide in the following a formal description of setup leakage. The adaptive leakage is similar to the one described for SED-2.

Setup leakage ${LK}_{s}^{SED}$ . $\begin{matrix} {LK}_{s} (D, W) = {{LK}_{s}^{1} (D, W), {LK}_{s}^{2} (D, W)}, \end{matrix}$ where ${LK}_{s}^{1} (D, W) = ({LK}_{s}^{II} (D, W), m, | W |, q, {(| D_{i} |)}_{i \in [n]})$ , and $\begin{matrix} {LK}_{s}^{2} (D, W) = {j ∣ \forall j \in [m], \forall i \in [k], v_{j + i} = w_{j + i} and v_{j - i} = w_{j - i}}_{v, w \in W} . \end{matrix}$ Note that ${LK}_{s}^{2} (D, W)$ is a subset of the one of SED-2. This underlines the fact that the generalized version of SED-2 leaks much lesser when compared to SED-2. Note that the security proof of our proposed construction is very similar to the one detailed for SED-2 and therefore omitted from the paper.

9. Performance analysis

We have evaluated the performance of SED-2. For this purpose, we developed a proof-of-concept using Java. We use the Enron document corpus that has over 500,000 emails and is about 1.5 Gbytes in size. Our experiments demonstrate the efficiency of the SED-2 protocol for a moderate size corpus. We discuss the experiments and results in more details below.

9.1. Experiment setup

We executed a number of experiments to validate not only the correctness of the theoretical complexities, but also study the deployability of SED-2 in a realistic setting. Our analyses include a quantification in terms of execution time and storage for the complete SED-2 protocol. In addition to the construction of the lookup table and the searchable part, we study the overhead related to the initial stages of the protocol, namely, determining unique keywords for every document as well as creating a dictionary that is associated with this set of documents. Any encrypted search scheme will involve these steps and execution time for this phase is far from negligible.

We chose the Enron corpus [6] for our performance studies. The corpus contains more than 500,000 emails from about 150 users. The total size of the document corpus is nearly equal to 1.5 Gbytes. The high number of unique keywords in the corpus was the main reason behind our choice of the Enron corpus since the search complexity of SED-2 is dependent on the size of the dictionary and not on the number of the outsourced files. We do not consider the overhead due to the encryption of files in our performance analysis.

The SED-2 scheme is implemented in Java using the JSci library [20] for keywords orthogonalization. Since the components of the searchable part are decimal numbers, we use Java’s BigDecimal class for accurate precision. (For example, if the output is equal to one plus or minus $10^{- 10}$ we assume that there is a match.) We also use Java’s SecureRandom class to generate random numbers in the query and searchable part construction. The experiments have been executed on a 8-core Intel Core i7-3630QM CPU 2.40 GHz with 8 Gbytes of RAM. For execution time, the values displayed in the graph are the sample mean values over several independent executions.

9.2. Results

We first show in Fig. 5 the execution time needed to determine for every file, the number of unique keywords and then constructing the entire dictionary of all these files (graph labeled as “keywords indexation”). Based on unique keywords associated with each file, we construct the lookup table that links each keyword to all documents that contain the keyword. These phases can be merged to gain time, however they are still linear in the number of files (multiplied by the number of keywords in the case of textual files, which was our case in the Enron emails).

Fig. 5.

Time of inverted index encryption.

Fig. 6.

Number of unique keywords.

SED-2 complexity is dependent on the size of the dictionary, we show in Fig. 6 that the number of unique keywords associated with a number of Enron emails. We notice that for 90,000 emails, the number of unique keywords is greater than the size of the Enable (172,820 keywords) or the British Oxford (127,238 keywords) dictionaries. This is due to the additional scientific or organizational notations, proper names etc., in the ENRON corpus and also due to the fact that the other dictionaries contains only the base words and not their variants like the plurals or so.

The setup phase of SED-2 pre-construction is based on the creation of a set of letters with a size equal to the initial set of letters, times the number of possible positions. The number of possible positions is equal to the size of longest keyword. We have assumed a maximum size equal to 40, and the set of initial letters equal to the ASCII representation. The final size of the orthonormal letters is equal to 9.2 MBytes constructed in 2.4 seconds. Once the orthonormal letters are created, they are stored in the client side for more efficiency during the search phase.

Figure 7 shows the time to construct the searchable part as a function of the number of unique keywords based on the dictionary. The study clearly demonstrates the linearity of the searchable part of the construction. As indicated earlier, the searchable part construction is independent of the number of files in the corpus. In Fig. 8 we show the size of the lookup table and the searchable part that the server should store dependent on the number of unique keywords indexed.

Fig. 7.

Searchable part construction.

Fig. 8.

Size of the encrypted data structure.

Fig. 9.

Search phase time.

During the search phase, the user a-priori loads the orthonormal letters in memory to avoid I/O overhead. The time to generate the search query construction is equal to 78 micro seconds. The test phase takes as an input the searchable part, the lookup table and outputs the corresponding set of documents, Fig. 9 shows the time of search in one thread by process and parallelized multiple threads in one process.

The server does not have to wait until the end of the search phase to send the matching encrypted documents, since the searchable part is linear. Once the server finds a matching it sends the positions to generate the token and therefore directly fetch the corresponding encrypted documents. Based on the graph, the mean search time per keyword is equal to 0.85 micro seconds for parallel search and 1.3 micro seconds for one thread process. Note that the client and server co-exists in the same machine and therefore communication cost is negligible in this case.

10. Conclusion

We presented in this paper SED, a substring SSE construction that has an overhead sub-linear in the size of the data set when considering that $| W | ≪ n$ . We have proposed two incremental constructions with a very well described leakage. We believe that the generalized version of SED-2 is the most suitable for substring search scenarios as it has a better balance between security, expressiveness and efficiency. We want, however, to point out that the recent work by Chase and Shen [11] has better leakage with logarithmic search efficiency. The work by Faber et al. [15] is similar to our SED-2 generalization but with a better leakage profile. Moataz and Blass [23] proposed recently an oblivious substring search that provides the best security guarantees for substring search but at the cost of poly-logarithmic blowup for the search overhead. Nevertheless, we want to point out that it would be very interesting to investigate the leakage of substring SSE constructions for a better understanding. At this point, we are unaware of the right balance between leakage disclosure, efficiency and expressiveness. We believe that an interesting open problem in SSE would be to investigate this balance and its impact on SSE constructions. Finally, we would recommend practitioners to not use this construction unless they are very aware of the SED leakage impact.

References

Abdalla,

Bellare,

Catalano,

Kiltz,

Kohno,

Lange,

Malone-Lee,

Neven,

Paillier and

Shi, Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions, Journal of Cryptology 21(3) (2008), 350–391. doi:10.1007/s00145-007-9006-6.

Bellare,

Boldyreva and

O’Neill, Deterministic and efficiently searchable encryption, in: Proceedings of the 27th Annual International Cryptology Conference, Santa Barbara, California, USA, 2007.

Bindel,

Demmel,

Kahan and

Marques, On computing givens rotations reliably and efficiently, ACM Transactions on Mathematical Software (TOMS) 28(2) (2002), 206–238. doi:10.1145/567806.567809.

Boneh,

Di Crescenzo,

Ostrovsky and

Persiano, Public key encryption with keyword search, in: Proceedings of the 24th International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, 2004.

Boneh and

Waters, Conjunctive, subset, and range queries on encrypted data, in: Proceedings of the 4th Theory of Cryptography Conference, Amsterdam, The Netherlands, 2007.

CALO Project, Enron Email Dataset, Available at http://www.cs.cmu.edu/~enron/, Last accessed 11/11/2013.

Cash,

Grubbs,

Perry and

Ristenpart, Leakage-abuse attacks against searchable encryption, in: Proceeding of the 22th ACM Conference on Computer and Communications Security, Denver, CO, USA, 2015.

Cash,

Jaeger,

Jarecki,

Jutla,

Krawczyk,

Rosu and

Steiner, Dynamic searchable encryption in very-large databases: Data structures and implementation, in: Network and Distributed System Security Symposium (NDSS’14), 2014.

Cash,

Jarecki,

Jutla,

Krawczyk,

Rosu and

Steiner, Highly-scalable searchable symmetric encryption with support for Boolean queries, in: Advances in Cryptology – CRYPTO’13, Springer, 2013.

10.

Chase and

Kamara, Structured encryption and controlled disclosure, in: Advances in Cryptology – ASIACRYPT’10, Lecture Notes in Computer Science, Vol. 6477, Springer, 2010, pp. 577–594.

11.

Chase and

Shen, Substring-searchable symmetric encryption, PoPETs 2015(2) (2015), 263–281.

12.

Cheney and

D.R.

Kincaid, Linear Algebra: Theory and Applications, Jones and Bartlett, 2009.

13.

Curtmola,

J.A.

Garay,

Kamara and

Ostrovsky, Searchable symmetric encryption: Improved definitions and efficient constructions, in: Proceedings of the 13th ACM Conference on Computer and Communications Security, Alexandria, Virginia, USA, 2006.

14.

Di Crescenzo and

Saraswat, Public key encryption with searchable keywords based on Jacobi symbols, in: Proceedings of the 8th International Conference on Cryptology in India, Chennai, India, 2007.

15.

Faber,

Jarecki,

Krawczyk,

Nguyen,

Rosu and

Steiner, Rich queries on encrypted data: Beyond exact matches, in: 20th European Symposium on Research in Computer Security ESORICS’15, Vienna, Austria, 2015, pp. 21–25.

16.

E.-J.

Goh, Secure indexes, IACR Cryptology ePrint Archive 2003 (2003), 216.

17.

Goldreich and

Ostrovsky, Software protection and simulation on oblivious RAMs, J. ACM 1996.

18.

A.S.

Householder, Unitary triangularization of a nonsymmetric matrix, Journal of the ACM (JACM) 5(4) (1958), 339–342. doi:10.1145/320941.320947.

19.

Jarecki,

Jutla,

Krawczyk,

Rosu and

Steiner, Outsourced symmetric private information retrieval, in: Proceeding of the 20th ACM Conference on Computer and Communications Security, Berlin, Germany, 2013.

20.

JSci – A Science API for Java, Available at http://jsci.sourceforge.net/, Last accessed 12/11/2013.

21.

Kamara and

Papamanthou, Parallel and dynamic searchable symmetric encryption, in: Proceedings of the 17th International Conference Financial Cryptography and Data Security, Okinawa, Japan, 2013.

22.

Kamara,

Papamanthou and

Roeder, Dynamic searchable symmetric encryption, in: Proceedings of the ACM Conference on Computer and Communications Security, Raleigh, NC, USA, 2012.

23.

Moataz and

Blass, Oblivious substring search with updates, IACR Cryptology ePrint Archive 2015 (2015), 722.

24.

Moataz and

Shikfa, Boolean symmetric searchable encryption, in: Proceedings of the 8th ACM Symposium on Information, Computer and Communications Security, Hangzhou, China, 2013.

25.

Pappas,

Vo,

Krell,

S.A.

Choi,

Kolesnikov,

Keromytis and

Malkin, Blind Seer: A Scalable Private DBMS, Manuscript, 2013.

26.

Shi,

Bethencourt,

H.T.H.

Chan,

D.X.

Song and

Perrig, Multi-dimensional range query over encrypted data, in: Proceedings of the 28th IEEE Symposium on Security and Privacy, Berkley, California, USA, 2007, pp. 350–364.

27.

D.X.

Song,

Wagner and

Perrig, Practical techniques for searches on encrypted data, in: Proceedings of the 21st IEEE Symposium on Security and Privacy, Berkeley, California, USA, 2000.

28.

Stefanov,

van Dijk,

Shi,

C.W.

Fletcher,

Ren,

Yu and

Devadas, Path ORAM: An extremely simple oblivious RAM protocol, in: Proceeding of the 20th ACM Conference on Computer and Communications Security, November, Berlin, Germany, 2013.

Substring search over encrypted data

Abstract

Keywords

1. Introduction

2. Related works

3. Preliminaries

3.1. Notation

2 The precision depends on the variable that we have chosen in our experiments. In our case, we have chosen BigDecimal for our implementation.

3.4. Threat model

3.4.1. Information leakage

Definition 4 ( ( LK s , LK a ) -adaptive security).

4. Substring search over encrypted data – pre-construction

4.1. Pre-construction

5.1. Setup phase

5 The vector v i is a ( t × | W | ) matrix, but for sake of clarity we will call it a vector.

5.3. Retrieve phase

5.4. Problems with SED-1

5.4.1. Letter frequency attack with known dictionary

6. Substring search over encrypted data #2 – SED-2

6 Refer to Section 7.1 for exact description of SED-2 leakage.

6.3. Retrieve phase

6.4. Correctness of SED-2

7. Security proof for SED-2

7.1. Leakage description of SED-2

7.2. Security proof of SED-2

8.1. Overview

8.2. Leakage

9. Performance analysis

9.1. Experiment setup

9.2. Results

References

²
The precision depends on the variable that we have chosen in our experiments. In our case, we have chosen BigDecimal for our implementation.

Definition 4 ( $({LK}_{s}, {LK}_{a})$ -adaptive security).

⁵
The vector $v_{i}$ is a $(t \times | W |)$ matrix, but for sake of clarity we will call it a vector.

⁶
Refer to Section 7.1 for exact description of SED-2 leakage.