June 10, 2017 Written by

Searchable encryption is a helpful tool to search within encrypted data, while preserving privacy and security. After giving you a short introduction into the importance of this primitive, we take a look at one of the most recent approaches of Cash et al. We start by describing the setting of this scheme and how it is realised. Therefore we take apart the construction and analyse the main database structure, namely the TSet. Next, we show how this $TSet$ can be build up, as well as how it can be used with a given keyword to retrieve the indices of the associated files. Finally, we give you an overview of the complete $OXT$ protocol and show you how boolean queries can be applied to achieve conjunctive search results.

Introduction

In this blog post we want to give you an introduction into the interesting world of searchable encryption. This research topic gains importance as nowadays more and more applications are shifted to the cloud including large data sets. Simply think at the popularity of storage systems like dropbox or google drive. But there is one big problem. You have to trust the provider that he doesn't abuse your data. Right? Well, let's think about it. A corrupted provider could simply rifle through your files and look for something interesting. Of course, we can encrypt our data and then upload it to our cloud storage. But what happens if, let's say we have multiple thousands of files stored on the server and we look for a subset, maybe only the files that contain a special keyword? That's a problem because the server can't look into our encrypted files and search for this specific keyword. Obviously the naive retrieve-and-decrypt approach does not scale well. It requires to download the whole storage, such as the total 10 GB dropbox in order to find a 1 KB text file. Searchable encryption (SENC) comes to rescue here. Using such a scheme, the server is able to search for a given keyword in all files but without really knowing what he is actually looking for. That sounds strange, doesn't it? In this post we explain the techniques behind searchable encryption of Cash et al. \cite{Cash:2013} from an undergraduate view, which is considered to be the fastest scheme while offering a rich search query language and being provably secure. For a general introduction to SENC and the importance of search query functionality, provable security and other features we refer to the great work of Seny Kamara \cite{Kamara:Blog}.

Our Setting

So, let's first describe the setting. The server holds some kind of encrypted index (also referred here as database). For every keyword, the index holds a pointer $ind$. The client can now ask the server to deliver him ciphertexts. Each ciphertext encrypts a file associated with a set of search words, which are represented through some kind of tokens, while the server is unable to learn the word the client is looking for. So let's get an intuition how we can realise this setting. There are two important things to do. First, we have to create our encrypted database $EDB$ and prepare it in such a way that, we can perform all of our previously defined functionalities. Next, we have to work out how we can use our search words in order to find something within the database.

The basic database structure

Now, let's take a look at how we can create our database [Figure \ref{fig:edb}]. Since this research topic was first considered in 2000, there were quite some constructions available, always heading the problem of finding a trade-off between security and performance. A recent approach by Kamara \cite{Kamara:2012, Curtmola:2006} relies on linked lists. A bit more precisely, his scheme is build of two data structures. First, a search array that contains equal sized lists for every distinct keyword, while the list nodes are encrypted and permuted in a random order among the whole array. The nodes itself consists of an identifier of a file that contains the keyword as well as the address of the next node within the array forming a linked list. Second, a lookup table that can be used by the server to retrieve the pointer for the first list item for a given search word plus the corresponding key. Within the search process the server then simply follows the chain in order to retrieve all file pointers. The construction of Cash et al. generalises this idea in two ways. First, by using a multi-dimensional array. Second, by randomly shuffling the keyword-index combinations into it. And there we are, our main database structure which we are calling $TSet$ is finished. The improvement in comparison to Kamara's, is the possibility of search parallelism, which is a huge advantage when working with large data sets.

 Fig. 1: EDB structure

TSet in detail

TSet preparations

Before we can start setting up our $TSet$, we have to prepare our data in order to get an array, that contains all the keywords associated with there respective file pointers. This sorted structure helps us to build up the $TSet$. We do so by first create an empty array $T$. Now, for every distinct keyword $w \in W$ we create a list $t$. Into this list we put a tuple containing an encrypted version of the pointer $e \leftarrow Enc(K_e, ind)$ together with some blinding factor $y$, which we require later to enable conjunctive search queries $t \leftarrow (e,y)$. We do this for all the identifiers of the files where the word $w$ is contained. At least we put the list into the array

$T[w] \leftarrow t$
.

Building up the TSet

So, let's see how we can create this database. We start with an empty $TSet$, which is basically only a simple one-dimensional array, of size $B$. Now, into every of these array items, called buckets, we put another array. These inner arrays can hold $S$ items of type $\mathsf{record}$. We will later see, how such an $\mathsf{record}$ looks like. Next, we create a second array, which acts as a helper for building up the first one. It is called $\mathsf{Free}$. This second array is also of size $B$ and every item contains a set of integers $\{1,...,S\}$. After all, we have two arrays where the first can contain $\mathsf{record}$'s and the second one contains integer sets. Don't worry about the dimension of $B$ and $S$. They will be chosen by a formula that depends on the amount of keywords we have in our database.

Filling up the TSet

Now it becomes very interesting. We want to put all the encrypted pointers, denoted as $(e,y)$, from our list $T$ into our $TSet$. Therefore we first create a token out of the first search word $w_1$, called $STag$. This $STag$ token is the exact same one, as we are using later to search within our database. Now, we have to initialise a counter $i$. This counter is important to realise the abstraction of our data list structure because it helps us to get the location of the next item within the chain and therefore we have to increment it for every keyword-index combination. Putting this $STag$ together with the counter into a hash function $H$, giving us a tuple containing the three elements $(b,L,K) \leftarrow H(STag, i)$. We retrieve a label $L$, a bucket index $b$ and some key $K$. Now, we go to the $b$'th item within our $\mathsf{Free}$ array. Remember, this was the array containing integer sets from 1 to $S$. Out of the set from $\mathsf{Free}[b]$, we randomly chose one integer $j \in [1,S]$ and remove it from the set. With the help of $j$ we are now able to determine the position of where we put the encrypted index $(e,y)$, which corresponding to a specific $ind \in db(w_1)$, into our database structure. Its $TSet[b,j]$. We see its the same bucket index $b$ used in the $\mathsf{Free}$ array but $j$ now shows us which of the inner array elements we have to use. Remember, the $TSet$ was an array containing arrays of $\mathsf{record}$'s. Its now time to define how such a $\mathsf{record}$ type looks like. Well its quite easy, a $\mathsf{record}$ simply has the two fields $\mathsf{label}$ and $\mathsf{value}$ where the former is used to recover the correct index within the search process and the latter contains the encrypted index. To the $\mathsf{label}$ field we assign the value $L$, one of the three results out of our hash function. The input of the $\mathsf{value}$ field is not much more complicated. Into this field we put our encrypted index $(e,y)$ together with a bit $\beta$. This bit is only a little helper that determines whether there are more indices that matches for this search word. The whole $\mathsf{value}$ field is at least encrypted using the key $K$. To summarise, we can say that, we found a way to put all of our keyword-index combinations within our $TSet$ and shuffled it in a way that all the items are apportioned into the different bucket locations.

 Fig. 2: TSet construction.

Retrieve indices for a keyword

Now, we have to look the other way around. Meaning that we want to recover the indices for a given search word $w$. To do so we have to look what the server does and what the client does. The clients part is very easy, he simply generates a search token $STag$ from $w_1$. We already saw in the $TSet$ build up, how this can be done. Now, the client sends this $STag$ to the server while the server, like last time, uses the hash function $H$ to retrieve the tuple $(b,L,K)$. So he has already determined the bucked for the first index. But remember, within the bucket are $S$ possible indices (within the $\mathsf{record}$'s). The server finds the matching label by use of a bloom filter. To retrieve the encrypted index $(e,y)$ back out of the $\mathsf{value}$ field we can use the key $K$ for decryption. But the job is not done, there could be more indices for this keyword. Do you remember the little trick we used at the $TSet$ generation to flag whether there are more indices following? The first bit $\beta$ from the $\mathsf{value}$ determines upcoming indices. If it's 0 then we are at least finished the search process and can send all the indices back to the client. Else we restart this process again for the next index.

Oblivious Cross-Tags Protocol (OXT)

In first designs of SSE, it was only possible to search for files that contained a specific keyword. The design of the OXT protocol allows for conjunctive and boolean queries of the form $w_1 \wedge \varphi(w_2,..,w_n)$, where $\varphi$ is an arbitrary boolean formula. This limits the search result to be subset of $w_1$, see [Figure \ref{fig:query}]

 Fig. 3: Search set: The blue intersection set represents the serach result.

Before describing the protocol, some basic definitions have to be in place. Let: $W$ be the set of all possible keywords $w$. Further, let $db(w)$ denote the set of files in the database containing the keyword $w$. A $ind$ denotes a pointer to a specific file. We will not describe how the database is constructed at this point, but describe its basic structure.\\

The encrypted database $EDB$ contains two data structures a $TSet$ and a $XSet$ see also \ref{fig:edb}. The $XSet$ is basically a set of nodes, called $XTag$'s, created from an $ind$ and a keyword, indicating that the word is present in the corresponding file. The second data structure, the $TSet$, returns an array of tuple $(e,y)$ for a valid $STag$, which corresponds to a specific keyword. The value $e$ is the encryption of an $ind$, while $y$ is the half of a $XTag$, associated to the $ind$ in $e$ and obfuscated with a blinding factor.

Lets dive in to the protocol, with a simple example. A client wants to get the $ind$'s for all files, containing the words $w_1$ and $w_2$. To do so, he begins by generating a $STag$ for the word $w_1$ and $XToken$ arrays, one for each index $ind$ in $db(w_1)$. The Arrays contain one $XToken$ for each word in the boolean formula. A $XToken$, is the half of a $XTag$, associated with a keyword, in this case $w_2$. The client starts the communication by sending the $STag$ followed by a stream of $XToken$ arrays to the server. The client stops sending arrays when the server sends a stop signal. Note, that the server does not know $|db(w_1)|$, so the server has to decide, when to stop with the production of $XToken$ arrays.

 Fig. 4: OXT Protocol.

The server on the other side, receives first the $STag$ and uses it, to get the array of tuple $(e,y)$ from the $TSet$. While, the stream of $XToken$'s starts to come in. The Client takes each $y$ and combines it with the received $XToken$. If the created value is a valid $XTag$ in the $XSet$, it indicates that the corresponding $ind$ in $e$ is the index of a file containing $w_2$ and based on the initial formula $w_1 \wedge w_2$, it is send to the Client.

The Protocol is executed in parallel. The Client is generating the $XToken$'s and sending them, while the Server is processing the previously send $XToken$.

References

1. D. Cash, S. Jarecki, C. S. Jutla, H. Krawczyk, M. Rosu, and M. Steiner, Highly-scalable searchable symmetric encryption with support for boolean queries, in Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Babara, CA, USA, August 18-22, 2013. Proceedings, Part 1, R. Canetti and J. A. Garay, eds, vol. 8042 of Lecture Notes in Computer Science, Springer, 2013, pp. 353-373.
2. R.Curtmola, J. A. Garay, S. Kamara, and Ostrovsky, Searchable symmetric encryption: Improved definition and efficent constructions in Proceedings of the 13th ACM Conference on Computer and Communications Secuity, CCS 2006, Alexandria, VA. USA, Ioetober 30 - November 3, 2006, A. Jules. R. N. Wright, and S. D. C. di Vimereati, eds, ACM, 2006, pp. 79-88
3. S. Kamara, How to serach on encrypted data Introduction (part 1). http://outsourcebits.org/2013/10/06/how-to-serach-on-encrypted-data-introduction-part-1/. 2013. Accessed: 2017-01-31.
4. S. Kamara, C. Papamanthou, and T. Roeder, Dynamic searchable symmetric encryption, in the ACM Conference on Computer and Communications Security, CCS'12, Raleigh, NC, USA, October 16-18, 2012, T. Yu, G, Danezis, and V. D. Gligor, eds,, ACM, 2012, pp. 965-976.