# A Practical Framework for Executing Complex Queries over Encrypted Multimedia Data

Fahad Shaon, Murat Kantarcioglu

► To cite this version:

Fahad Shaon, Murat Kantarcioglu. A Practical Framework for Executing Complex Queries over Encrypted Multimedia Data. 30th IFIP Annual Conference on Data and Applications Security and Privacy (DBSec), Jul 2016, Trento, Italy. pp.179-195, 10.1007/978-3-319-41483-6_14 . hal-01633678

HAL Id: hal-01633678

https://inria.hal.science/hal-01633678

Submitted on 13 Nov 2017

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Practical Framework for Executing Complex Queries over Encrypted Multimedia Data

Fahad Shaon and Murat Kantarcioglu

The University of Texas at Dallas, Richardson, TX 75080, USA
{fahad.shaon,muratk}@utdallas.edu

**Abstract.** Over the last few years, data storage in cloud based services has been very popular due to easy management and monetary advantages of cloud computing. Recent developments showed that such data could be leaked due to various attacks. To address some of these attacks, encrypting sensitive data before sending to cloud emerged as an important protection mechanism. If the data is encrypted with traditional techniques, selective retrieval of encrypted data becomes challenging. To address this challenge, efficient searchable encryption schemes have been developed over the years. Almost all of the existing searchable encryption schemes are developed for keyword searches and require running some code on the cloud servers. However, many of the existing cloud storage services (e.g., Dropbox<fnref n="1" />, Box<fnref n="2" />, Google Drive<fnref n="3" />, etc.) only allow simple data object retrieval and do not provide computational support needed to realize most of the searchable encryption schemes.

In this paper, we address the problem of efficient execution of complex search queries over wide range of encrypted data types (e.g., image files) without requiring customized computational support from the cloud servers. To this end, we provide an extensible framework for supporting complex search queries over encrypted multimedia data. Before any data is uploaded to the cloud, important features are extracted to support different query types (e.g., extracting facial features to support face recognition queries) and complex queries are converted to series of object retrieval tasks for cloud service. Our results show that this framework may support wide range of image retrieval queries on encrypted data with little overhead and without any change to underlying data storage services.

## 1 Introduction

Cloud computing is being adopted by organizations and individuals to address various types of computation needs including file storage, archiving, etc. However, there have been several incidents of data leak in popular cloud storage service providers [1,25]. To ensure the security of the sensitive data and prevent any unauthorized access, users may need to encrypt data before uploading

<footnote n="1">¹ https://www.dropbox.com</footnote>

<footnote n="2">² https://www.box.com/</footnote>

<footnote n="3">³ http://drive.google.com/</footnote>
to cloud. If data uploaded to cloud is encrypted using traditional encryption
techniques, executing search queries on the stored data become infeasible. To
alleviate this situation many searchable encryption techniques have been pro-
posed [9,16,5,13,6,19,20,11,4]. Among those approaches, searchable symmetric
encryption (SSE) [9,16,5,13,6,19,4] emerges as an efficient alternative for cloud
based storage systems due to minimal storage overhead, low performance over-
head, and relatively good security.

However, almost all searchable encryption techniques require executing some
code on the cloud servers to enable efficient processing. On the other hand, pop-
ular commercial personal cloud storage providers¹ ² ³ only support basic file op-
erations like read and write file that makes it infeasible to apply traditional SSE
techniques. Furthermore, complex queries on multimedia data may require run-
ning different and expensive cryptographic operations. These limitations create
a significant problem for wide adoption of SSE techniques. Therefore, developing
SSE schemes that can run on the existing cloud storage systems without requir-
ing the cloud service providers cooperation emerges as an important and urgent
need. To our knowledge, only [19] considered a setup without computational sup-
port from the cloud storage but the proposed solution does not support efficient
complex querying over encrypted data.

Even though, one can wish that an alternative SSE as a service could be
offered in the near future by the cloud service providers, due to network effects,
many of the existing users may not want to switch their cloud service providers.
Therefore, any new “secure” cloud storage with SSE providers may have a hard
time in getting significant traction. So supporting SSE on the existing cloud
storage platforms without requiring any support from the cloud storage service
providers is a critical need.

In addition, adoption of multimedia (e.g., image, music, video, etc.) data for
social communication is increasing day by day. KPCB analyst Mary Meeker’s
2014 annual Internet Trends report<fnref n="4" /> states *1.8 billion* photos shared *each day*.
However, indexing multimedia data is harder compared to text data. A signifi-
cant pre-processing is required to convert raw multimedia data to a searchable
format and queries made on multimedia data are complex as well. So building
efficient cryptographic storage system that can easily handle multimedia content
is a very important problem.

To address these challenges, in this paper, we propose an efficient searchable
encryption scheme framework that can work on existing cloud storage services
and can easily handle multimedia data. Our proposed framework only requires
file storage and retrieval support from cloud storage services. Furthermore, by
leveraging the extensible extract, transform and load operations provided by
our framework, very complex queries can be executed on the encrypted data. As
an example, we show how our framework could be used to run face recognition
queries on encrypted images. To our knowledge, this is the first system that
can support *complex queries* on encrypted multimedia data *without significant
computational support* from the cloud service provider (i.e., without running cus-

<footnote n="4">⁴ http://www.kpcb.com/blog/2014-internet-trends</footnote>
tomized code in the cloud). Main contributions of this work can be summarized
as follows:

- We propose a generic outsourcing framework that enables secure and efficient querying on any data. Our framework supports complex querying on any encrypted data by allowing queries to be represented as series of simple equality queries using the features extracted from the data. Later on, these extracted features are transformed into encrypted indexes and these indexes are loaded to cloud and leveraged for efficient encrypted query processing.

- We prove that our system satisfies adaptive semantic security for dynamic SSE.

- We show the applicability of our framework by applying it to state-of-the-art image querying algorithms (e.g., face recognition) on encrypted data.

- We implement a prototype of our system and empirically evaluate the efficiency under various query types using real world cloud services. Our results show that our system introduces very little overhead, which makes it remarkably efficient and applicable to real-world problems.

The rest of the paper is organized as follows: Section 2 discusses previous related works, Section 3 provides the general setup and threat model of our system, Section 4 describes internal details of each phases, Section 5 extends our initial framework making it dynamic, in Section 6 we discuss the security of our system, Section 7 shows an application of our proposed framework, Section 8 shows the experimentations, and in Section 9 we conclude our work.

## 2 Related Work

Currently there are few ways to build encrypted cloud storage with content based search. Searchable symmetric encryption (SSE) is one of those, which allows users to encrypt data in a fashion that can be searched later on. Different aspects of SSE has been studied extensively as shown in an extensive survey of provably secure searchable encryption by Bösch at el. in [4]. Curtmola at el. [9] provided simple construction for SSE with practical security definitions, which was then adopted and extended by several others in subsequent work. Few works also looked into dynamic construction of SSE [16,5,13,14] so that new documents can be added after SSE construction.

Another branch of study related to SSE is supporting conjunctive boolean query. Cash at el. [6] proposed such a construction, where authors used multi-round protocol for doing boolean query with reasonable information leakage. In the process they also claimed to build the most efficient SSE in terms of time and storage. Kuzu at el. [15] proposed an efficient SSE construction for similarity search, where they used locality sensitive hashing to convert similarity search to equality search. There are also work towards supporting efficient range query, substring matching query, etc. [10], where a rich query is converted to an exact matching query. However, these constructions require specialized server. Importantly, we can easily adopt such a conversion technique in our framework.
Naveed at el. [19] proposed a dynamic searchable encryption schema with
simple storage server similar to our setup. The system also hides certain level
of access pattern. However, authors did not consider complex query problem in
their work, which is one of the major challenges that we solved in this work.

Another way of querying encrypted database is oblivious RAM (ORAM) [20,11]
that also hides search access pattern and much secure. Despite recent develop-
ments [21], traditional ORAM remains inefficient for practical usage in cloud
storage system as described in [3]. Furthermore, our proposed system converts
complex operations into sequence of key value read and write operations, which
can easily be combined with ORAM technique to hide the access pattern.

Qin at el. [22] proposed an efficient privacy preserving cloud based secure
image feature extraction and comparison technique. Similar construction for
ranked image retrieval is proposed by [29,17,23]. These systems depend on highly
capable cloud server for preforming image similarity query.

Finally, there are few commercial secure cloud storage systems, e.g., Spi-
derOak<fnref n="5" />, BoxCryptor<fnref n="6" />, Wuala<fnref n="7" />, etc. Even though these systems are easy to use
and provide reliable security, these systems provide neither server based search
nor complex query support. All these systems depend on either operating system
or local indices to provide search functionalities. As a result, to provide search
functionalities these systems need to download and decrypt all the data stored
in cloud server, which might not be efficient solution in all circumstances.

3 Background and Threat Model

**Searchable Symmetric Encryption (SSE)** is one of the many mechanisms
to enable search over encrypted data. In a SSE schema, we not only encrypt the
input dataset, but also we create an encrypted inverted index. The index contains
mapping of encrypted version of keywords (called trapdoors) to list of document
ids that contains corresponding plain text keywords. Formally, a SSE schema
is defined as collection of 5 algorithms *SSE* = (*Gen*, *Enc*, *Trpdr*, *Search*, *Dec*)
Given security parameter *Gen* generates a master symmetric key, *Enc* generates
the encrypted inverted index and encrypted data sets from the input dataset.
*Trpdr* algorithm takes keywords as input and outputs the trapdoor, which is used
by *Search* algorithm to find list of documents associated with input keywords.
Finally, the *Dec* algorithm decrypts the encrypted document given the id and
proper key. We refer the reader to [9] for further discussion of SSE. Furthermore,
in a typical SSE settings, *Gen*, *Enc*, *Trpdr*, and *Dec* are performed in a client
device and the *Search* algorithm is performed in a cloud server. For this reason,
we need a server with custom computational support to run a SSE based system.
Here, we focus on building a framework that enables us to build SSE alike schema
with complex query processing capabilities using file storage servers that does
not have custom computation support.

<footnote n="5">⁵ https://spideroak.com/</footnote>

<footnote n="6">⁶ https://www.boxcryptor.com/</footnote>

<footnote n="7">⁷ https://www.wuala.com/</footnote>
**Threat Model.** In this study, we consider a setup, where a user owns a set of documents, which includes multimedia documents. User wants to store these documents into a cloud storage server in encrypted form. User also wants to perform complex search queries over the encrypted data. Most importantly, user wants to utilize existing cloud storage service, which is not capable of executing any custom code provided by user. Formally cloud storage server $\mathcal{Z}$ can only preform *read* and *write* operations. This simple requirement of cloud storage server makes the system easily adoptable in several real world scenario. On the other hand, user have devices with sufficient computation power that can perform modern symmetric cryptography algorithms and are called clients.

In our system, the communication between server and client is done over encrypted channel, such as https. So eavesdroppers can not learn any meaning full information about the documents capturing the communication, apart from existence of such communication. We also assume that the cloud storage server $\mathcal{Z}$ is managed by Bob, who is semi-honest. As such, he follows the protocol as it is defined but he may try to infer private information about the document he hosts. Furthermore, the system does not hide search access pattern, meaning Bob can observe the trapdoors in search query. Based on the encrypted file accesses after subsequent search queries Bob also can figure out trapdoor to document ids assignments. However, Bob can not observe the plain text keyword of trapdoors.

# 4 The Proposed System

Our main motivation is to build encrypted cloud storage that can support complex search query with support of simple file storage server. We generalize the required computations into a five phase *Extract, Transform, Load, Query, Post-Process (ETLQP)* framework. These five phases represent chronological order of operations required to create, store encrypted index, and perform complex operations. Figure 1(a) and 1(b) illustrates an overview of different phases in our system.

## 4.1 Extract

In this phase we extract necessary features from a dataset. Let, $\mathcal{D} = \{d_1, d_2, ..., d_n\}$ be a set of documents, $id(d_i)$ be the identifier of document $d_i$, $\Theta = \{\theta_1, \theta_2, ..., \theta_m\}$ be a set of $m$ feature extractor functions. Functions in $\Theta$ can extract set of feature and value pairs $(f, v)$ from documents. We build list $U_i$ with all the feature value pairs extracted from $d_i$. For all the feature extractors $\theta_j \in \Theta$ we compute $(f, v) \leftarrow \theta_j(d_i)$ and store $(f, v)$ in $U_i$. Finally we organize the result in $\mathcal{P}$, such that $\mathcal{P}[id(d_i)] \leftarrow U_i$. Such an example $\mathcal{P}$ is illustrated in Figure 1(c). Here, we have four documents $\{D_1, ..D_4\}$. $D_1$ has feature value pairs $U_1 = \{(f_a, v_\alpha), (f_b, v_\beta), (f_c, v_\gamma)\}$, etc.

To clarify further, let us assume that, we want to build an encrypted image storage application that can perform location based query over the encrypted images. In other word, the system is capable of answering queries, such as, *find*
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Overall workflow of our proposed system and important data structures. (a) Index creation consists of extract, transform and load phases. (b) Search consists of query and post-process phases. (c) *P*, output of extract phase that maps document ids to feature value pairs, (d) Inverted index *I*, that maps search signatures to document ids.</figcaption></figure>

images taken in Italy. To support such a query, we implement a feature extractor function $\theta_l$, where $\theta_l$ extracts location information from image meta data. Output of $\theta_l$ is defined as a feature value pair ("LOCATION", "longitude and latitude of image"). We define as many feature extractor necessary based on application need. However, all feature extractor functions returns values in similar format. In Section 7 we discuss in details how we defined more feature extractors and use those to answer much more complicated queries.

## 4.2 Transform

In this phase we transform the extracted feature values into much simpler form so that complex search operations can be expressed as series of equality searches. We compute search signatures *s* form feature-value pairs and associate corresponding documents with *s*. This association at query stage can be used to infer existence of a feature-value pair in a document. Essentially here we define sets of transform functions $T = \{t_1, \dots, t_p\}$, where each transform function is designed to generate search signatures from a feature value pair $(f, v)$ and $T_f$ defines subset of transformation functions that can be applied to feature *f*.

With these transform functions $T$, we generate an inverted index *I* that is indexed by search signatures and contains list of document ids. For all the feature value pairs in *P*, we generate search signature $s_{f,v} \leftarrow t(f, v)$ where $t \in T_f$. We build document id list $V_s$ for all the unique search signature *s* that contains $id(D_i)$ if and only if there exists a feature value pair $(f, v)$ that is in $U_i$ and at least one transformation function *t* that generates search signature *s*. Finally we fill the inverted index *I* such that $I[s] \leftarrow V_s$. In Figure 1(d) we show such an example *I*, which is created from *P* of Figure 1(c). Here, search signature $s_1, s_2, s_3, s_4, s_5$ are generated from feature value pairs $(f_a, v_\alpha), (f_b, v_\beta), (f_b, v_\gamma), (f_a, v_\delta), (f_a, v_\delta)$ accordingly.
Similarly, in our encrypted image storage application example, we define a transform function $t_l$ that takes geographic location and document id as input, converts the location information to mailing address using reverse address lookup service, takes the country information and document id to construct a search signature using a collision resistant hash function.

Using such extract transform model has several benefits over adhoc model. The proposed model helps us to organize the necessary computation into modules, which intern increase development efficiency. The feature extractor functions can be reused in other project.

## 4.3 Load

In this phase we setup our encryption schema, encrypt the inverted index, and upload the encrypted version into a file storage server $\mathcal{Z}$. We initialize a master encryption key $K$, three random constants $C_1, C_2, C_3$, a secure pseudo random permutation function $\varphi$, and a keyed pseudo random function $H$. Given a key, $\varphi$ encrypts data, $\varphi^{-1}$ decrypts corresponding result, and $H$ generates authentication code of messages. In addition, we define a small synchronized cache $\mathcal{C}$ and an encryption key $K_C$ for encrypting the cache. $\mathcal{C}$ is always synchronized with storage server $\mathcal{Z}$. Synchronization is achieved by updating the server's version after any change in client's version and before updating the cache locally most recent version is downloaded from the server first. In $\mathcal{C}$, we store document id list size of all search signatures of $\mathcal{I}$, which is notated by $C freq$. Later, we also use this cache to store information related to individual files to make the query phase easier.

We divide all the document id lists in $\mathcal{I}$ into $b$ length blocks and add padding to last block if needed. The value of $b$ is determined by defining and minimizing a cost function (described in Subsection 4.6). We generate trapdoors $T_j^s$ and $K_j^s$ for $j^{th}$ block of document list of $\mathcal{I}[s]$. We use $K_j^s$ to encrypt block contents

<caption>**Algorithm 1 Load encrypted index**</caption>

1: **Require:** $K$ = Master key, $\mathcal{I}$ = Inverted index of search signatures, $\mathcal{C}$ = Synchronized cache, $K_C$ = encryption key for cache, $\mathcal{Z}$ = File storage server.
2: $b \leftarrow optimize(\mathcal{I})$
3: **for all** signature $s$ in $\mathcal{I}$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;blocks$_s \leftarrow \lceil \frac{|\mathcal{I}[s]|}{b} \rceil$
5: &nbsp;&nbsp;&nbsp;&nbsp;**for** $j = 1 \rightarrow blocks_s$ **do**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$T_j^s \leftarrow H(K, s \parallel j \parallel C_1)$, $K_j^s \leftarrow H(K, s \parallel j \parallel C_2)$
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sub $\leftarrow \mathcal{I}[s].slice((j-1) \times b, j \times b)$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{E}[T_j^s] \leftarrow \varphi(K_j^s, pad(sub))$
9: **end for**
10: $C freq[s] \leftarrow |\mathcal{I}[s]|$
11: **end for**
12: **for all** trapdoor $t$ in $\mathcal{E}$ **do**
13: &nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{Z}.write(t, \mathcal{E}[t])$
14: **end for**
15: $C_{sig} \leftarrow H(K_C \parallel C_3, 1)$
16: $\mathcal{Z}.write(C_{sig}, \varphi(K_C, \mathcal{C}))$
and $T_j^s$ as the key for encrypted inverted index $\mathcal{E}$. To query the inverted index later on, our system will regenerate these two trapdoors and perform inverse operations to build the original document id list. In addition, we store number of documents associated with a signature $s$ in $C.freq[s]$, then encrypt and upload the cache. Algorithm 1 describes the operations necessary for load phase.

## 4.4 Query

In previous phases we have created an encrypted inverted index and uploaded into file storage server $\mathcal{Z}$. Query and post-process phases are dedicated for querying the index and returning proper output to user. First, given a user query $q$, we extract and transform it to a set of search signatures $\mathcal{Q}$. We use number of document ids per block, stored in $C.freq$, to compute block counts, which in turn used to compute trapdoors $K_j^s$ and $T_j^s$ for each block of search signatures. Using these trapdoors we retrieve and decrypt document ids. Finally, the result is organized into a hash table $\mathcal{R}$ such that $\mathcal{R}[s] = \mathcal{I}[s]$ for all $s \in \mathcal{Q}$. Algorithm 2 contains the detail operations of query phase.

<caption>**Algorithm 2 Query**</caption>

1: **Require:** $K$ = Master key, $q$ = Query, $b$ = block size, $\mathcal{Z}$ = File storage server
2: $\mathcal{Q} \leftarrow$ Extract and Transform $q$
3: **for all** search signatures $s$ in $\mathcal{Q}$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;blocks$_s \leftarrow \lceil \frac{C.freq[s]}{b} \rceil$
5: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 1 \rightarrow blocks_s$ **do**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$T_j^s \leftarrow H(K, s \parallel j \parallel C_1)$, $K_j^s \leftarrow H(K, s \parallel j \parallel C_2)$
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$L \leftarrow \mathcal{Z}.read(T_j^s)$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;add $\varphi^{-1}(K_j^s, L)$ in $\mathcal{R}[s]$
9: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
10: **end for**
11: **return** $\mathcal{R}$

## 4.5 Post-process

In this step we further process the result of query phase to remove false positive entries. Given result set $\mathcal{R}$ from query phase for query $q$, we remove id of document that does not match the original query. Therefore, $\mathcal{R}.remove(id(d))$ if $q(d) \neq True$. Query that only contains exact search features, this phase is optional.

## 4.6 Optimal block size analysis

Block size has a direct impact on performance of our proposed system. Larger block size implies waste of space for padding and smaller block size implies many blocks to process. So we need to find an optimal value of block size $b$ that keeps the over all cost to minimal. In our construction for each block we have a fixed cost and a dynamic cost that is related to block length. We define fixed cost as $\alpha$ and co-efficient of dynamic cost $\beta$. Cost can be in terms of time and size. Both linearly depends on block size in our construction. So cost for a $b$ length block is $(\alpha + \beta \times b)$. Let, $\mathcal{J}(s)$ is $|\mathcal{I}[s]|$ meaning document id list size for search signature $s$ and total cost $\mathcal{G}(b)$ for blocking and encrypting given inverted index
I for block length b then $\mathcal{G}(b) = \sum_{s \in I} \left[ \frac{\mathcal{J}(s)}{b} \right] (\alpha + \beta \times b)$. We want to minimize the above function for b. However, if contains a ceiling function, which can not be minimize by taking derivatives and equating to zero. So we approximate the probability distribution of $\mathcal{J}$, i.e., lengths of document id list in $I$. We assumed that, distribution is Pareto distribution, which is defined by probability density function (PDF) $f(x|\gamma, x_m) = \frac{\gamma x_m^{\gamma}}{x^{(\gamma+1)}}$, where x is the random variable, $\gamma$ is distribution parameter, and $x_m$ is minimum value of x. After several algebraic simplification (explained in details in full version [24]), we find the first order derivative

$$ \mathcal{G}'(b) = \beta - x_m^{\gamma}\beta b^{-\gamma} + (\alpha + \beta b)x_m^{\gamma}b^{-\gamma-1} - \gamma x_m^{\gamma}b^{-\gamma}\left(\frac{\alpha}{b} + \beta\right) - \frac{\gamma x_m^{\gamma}}{\gamma-1}b^{-\gamma-1}\alpha $$

Now we minimize b by setting $\mathcal{G}'(b) = 0$ and solving the equation for b. In experimentation we observe that method of moments estimation for $x_m$ and $\gamma$ gives almost correct value.

# 5 Dynamic Document Addition

Here we are going to improve our algorithms to support dynamic addition of documents. Given a new document set for addition we first perform extract and transform to build an inverted index. Next we compute number of blocks and number of empty spaces in last block for each signature the cache $C$. If there exists empty space we fill the empty spaces than create new blocks as needed. On the other hand, if a new signature is observed in new inverted index we perform exact same steps of load. Due to space limitation we defer further discussion on dynamic document addition for full version of the paper [24].

# 6 Security

Over the years, many security definitions have been proposed for searchable encryption for semi-honest model. Among those simulation based adaptive semantic security definition by Curtmola, at el., [9] is widely used in literature. Later it is customized to work under random oracle model in [14]. We adapt this definition to prove our security model. In short, we define, history $\mathcal{H}_\eta$, trace $\lambda$ (the maximum amount of information that a data owner allows its leakage to an adversary) and view $v$ (the information that is accessible to an adversary) of our system and show the existence of polynomial size simulator $S$ such that the simulated view $v_S(\mathcal{H}_\eta)$ and the real view $v_R(\mathcal{H}_\eta)$ of history $\mathcal{H}_\eta$ are computationally indistinguishable. Due to space limitation we defer the formal security proof to our full version [24].

# 7 Application of ETLQP framework

As an application of our ETLQP framework we built an image storage system that saves encrypted images in cloud storage and built an encrypted index to search later on. Before going into further detail of our ETLQP framework implementation we briefly describe Fuzzy Color and Texture Histogram (FCTH) [7], Eigenface [27], Locality Sensitive Hashing(LSH) [12], and range query to exact query conversion mechanism [10].
**Fuzzy Color Texture Histogram (FCTH)** [7] is an histogram of image that combines texture and color information. It is widely used in content based image retrieval systems (CBIR), e.g. [18,8]. FCTH of an image can be considered as a vector with 192 dimensions and distance between FCTH vector of images can be used to determine similarity among images.

**Eigenface** [27] is a very well studied, effective yet simple technique for face recognition using static 2D face image. In summary, face images are considered as a point in a high dimensional space. An eigenspace consisting few significant eigen vectors are computed for approximating faces in a training face dataset. Next, test face images are projected into the computed eigenspace. Distances of test face images and all training faces images are computed. If any distance is below a pre-determined threshold then those faces are considered a match for associated test face. A detailed formal explanation of eigen-face schema is presented in full version [24].

**Locality sensitive hashing** is a technique widely used to reduce dimensions. Core concept of LSH is to define a family of hash functions such that similar items belong to same bucket with high probability. More specifically we utilized LSH in euclidean space and adopted widely accepted projection over random line technique described in [2]. Let, *r* be a random projection vectors, *v* be an input vector, *o* be a random number used as offset, and *w* be bucket length parameter fixed by user. The bucket id is computed by Round($\frac{v \cdot r + o}{w}$) function. Finally, several such projection vectors are used to generate several bucket ids for a single input vector. In this setting, nearby items will share at least a same bucket with very high probability.

**Range query to exact query conversion.** We adopt the range query mechanism described in [10]. Let, *a* be a discrete feature that has value ranging from 0 to $2^{t-1}$, meaning it requires *t* bits to represent in binary. We first create binary tree of *t* depth representing the complete range. Each leaf node (at depth *t*) represent an element in the range and we level all left edge as 0 and right edge as 1. So, the path from the root to a leaf node essentially represent the binary encoding of that leaf. In transform phase, we convert an input value of the range to *t* feature-value tuples, where the feature is concatenation of field name, depth *i* and value is binary encoding of inner node at depth *i*. During the query phase given a range we first find the cover as described in [10], create the corresponding search signatures and perform the query.

## 7.1 ETLQP for image storage

To build an application using ETLQP framework described system section, programmer has to define proper extract and transformation functions. Load, Query and Post-Process phases remain the same. For our image storage software we consider four features *location* - where the picture was taken, *time* - when the picture was taken, *texture and color* - for searching similar pictures, and *faces* - for face recognition. In our implemented system queries of first two features are equality search and later two are similarity search. Similarity searches are difficult to perform since result not only contains exact matches but also contains
results that are similar. So, we need to have a similarity measure for the fea-
ture in question. To accomplish such a similarity queries we utilize LSH, which
essentially helps us to convert the query to sequence of equality search. In addi-
tion, result of LSH can contain false positives. We need extra post processing to
remove those.

**Extract.** Location and time data are extracted from Exif<fnref n="8" /> meta-data. Exif is a very popular standard for attaching image meta-data into image used by all popular camera manufacturers. Camera with Global Positioning System (GPS) module can store longitude and latitude of a picture taken into Exif data, which can be extracted easily using available libraries<fnref n="9" />. We use FCTH for similarity analysis and used a open source implementation of FCTH analyzer [18]. Finally, for face recognition using Eigenface, we extract frontal faces from images using haar cascade [28] frontal face pattern classifier.

**Transform.** Now we define appropriate transformations for extracted fea-
tures. Main idea behind the definition of transformation functions is to make the
query easier later on. So definition of transformation functions is mainly guided
by the query demand.

- **Location.** Location information in terms of longitude and latitude is difficult to use in practice. We use OpenStreetMap's reverse geolocation service<fnref n="10" /> to determine address of latitude and longitude associated with the image. To make query easier later, we generate search signatures of six sub-features of the address - full address, city, county, country, state, and zip.

- **Time.** Similarly we break created date of an image into five sub-features - complete date, year, month, day of month, and day of week. We generate search signatures based on these sub-features. In addition, to support range query based on date we convert the time into unix time stamp that essentially represents seconds passed from 1 *January 1970* without considering the leap second. Then we divide the time stamp by number of seconds in a day (86400), that gives us the number of days passed from epoch. Finally, we build the range query binary tree with depth 20, which essentially is capable of covering dates till year 4840. Then we create the feature value list as described earlier.

- **Texture and Color.** In the extract phase we extracted FCTH of provided image, which is a 192 dimensional vector. We can treat each dimension as different sub features but that will make it difficult to perform similarity search later on. Instead we define an euclidean LSH schema that put near elements into same bucket and use the bucket ids to generate search signatures.

- **Face.** We built an eigenface schema with extracted face images. Again to preserve similarity we built an euclidean LSH schema with weight vectors of faces and store the eigenspace related information into synchronized cache *C*. In particular we store the average face, selected top eigenfaces, and weights of all faces. Storing such information is the major reason of defining the cache *C*.

<footnote n="8">⁸ http://www.cipa.jp/std/documents/e/DC-008-2012_E.pdf</footnote>

<footnote n="9">⁹ https://drewnoakes.com/code/exif</footnote>

<footnote n="10">¹⁰ http://wiki.openstreetmap.org/wiki/Nominatim</footnote>
**Query and Post-Process.** With previously defined extract and transform functions client can perform *time queries*, such as find images that are taken on specific year, month, day of week, day of moth, or in a range of dates, etc. Client can also perform *location queries*, such as find pictures taken in a country, state, city, etc. In both of these cases, we transform a query into encrypted search signatures and retrieve associated encrypted document ids from the cloud storage server. Finally we decrypt and display the result directly to the user. On the other hand, for face recognition and image-similarity query, we extract appropriate feature values from a query image and transform these values into LSH bucket ids of previously defined LSH schema. We generate encrypted search signature, retrieve encrypted document ids, and decrypt the result like date and time queries. However, before showing results to user we remove false positive results introduced by the LSH schema.

# 8 Experimental Evaluation

**Setup.** In our proposed design we have two components client and server. Client processes images, performs cryptographic operations, and produces encrypted inverted index that is stored in server. In query phase client retrieves partial index from the server based on user-query.

**ETQLP client** is written in Java using several other libraries for image feature extraction. Cryptographic operations are performed using Java Cryptographic Extension (JCE) implementation. During our experimentation, we execute the client program in a computer with *Intel(R) Core(TM) i7-4770 3.40GHz* CPU, *16GB* RAM running *Ubuntu 14.04.4 LTS*. Our implemented client can store encrypted inverted index into different types of servers.

- **File storage server in local network.** We developed a very simple web based storage service that has two end points file read and file write. Our server is written in Python (v2.7.6) using Flask (v0.10.1) microframework and files are stored in a MongoDB (v3.2.0). We deployed our local storage server in a machine with *Intel(R) Xeon(R) CPU E5420 2.50GHz* CPU, *30GB* of RAM running *CentOS 6.4*. In addition, our client computer is also in the same network.

- **Amazon S3**<fnref n="11" /> is very popular commercial object and file storage system, which provides easy to use representational state transfer (REST) application program interface (API) for storing, retrieving and managing arbitrary binary data or file. Amazon also provides very extensive software development kit (SDK) for building applications to utilize its services. In our implementation, search signatures of encrypted inverted index $\mathcal{E}$ are keys of S3 objects and content of the objects are associated encrypted document id list.

- **Personal file storage services.** In our implementation the client is capable to use popular commercial file storage services, for example - Dropbox¹, Box², and Google Drive³. However, due to rate limitation of these services we *could not perform extensive analysis*. Details are presented in full version [24].

**Dataset.** We randomly selected 20109 images from Yahoo Flickr Creative Commons 100 Million Dataset (YFCC100M) in [26], which contains basic in-

<footnote n="11">¹¹ https://aws.amazon.com/s3/</footnote>
<figure><img src="image_3.png" /><figcaption>**Fig. 3.** Time required in different phases of building and uploading the index for different number of images.</figcaption></figure>

formation of 100 million media objects. Size of this random dataset is 42.3GB, average file size is 2.15MB, number of faces detected 7027, and 4102 images have latitude and longitude embedded in EXIF data.

**Experiments.** We measure performance of different phases of our framework for varying number of randomly selected images from above dataset. Horizontal axis of most of the reported graphs is number of randomly selected images used to build the index and vertical axis is the observation. We repeat each experiment for at least 3 times and report the average observation value. We extracted four features of the images as discussed in Section 7. Figure 2 illustrates size growth of unencrypted inverted

index, encrypted inverted index, and synchronized cache. The growth is linear, which implies index size increment is proportional to the number of files added. Moreover, in our experiment we observed that for 20000 images encrypted inverted index size is only 7.05MB, which is about four average size images in our dataset. So size over head of our proposed system is very low.

<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Index and cache sizes</figcaption></figure>

We also observe that feature extraction is the most time consuming phase of our system. Figure 3(a) illustrates required time for extracting features. We observe that face detection and extraction time is the dominating factor in this phase. It requires 464.54 minutes to detect and extract faces from 20000 images in sequential manner, averaging about 1.39 seconds per image. In addition, other three features takes 85.87 minutes for 20000 images, averaging 0.26 seconds per images. Even though it looks like a long time for a lot of images but time required for individual image is very little. Furthermore, these experiments are done in sequential manner. A multi-threaded implementation will certainly reduce the over all time. In addition, in this prototype we implemented a separate program to call native OpenCV API to detect faces and communicate the results back to the main process, which added extra overhead. In contrast, transform phase is one of the fastest phase in our implementation. Here, extracted feature values are transformed into inverted index of search signatures and document ids. We observed that the growth is almost linear and for 20000 images it only requires 696 milliseconds, shown in Figure 3(b).
<figure><img src="image_5.png" /><figcaption>Fig. 4. Time required for different type of queries vs number of files.</figcaption></figure>

Next we encrypt and load the inverted index into a cloud storage server. In our experiments, we load the encrypted index into (1) Local server and (2) Amazon S3. Figure 3(c) shows the time required for encrypting and loading inverted index into local and Amazon S3 server. For 20000 images it requires 20.52 seconds to encrypt and load the entire inverted index split into 1MB blocks into local storage server and 5.65 minutes to complete in Amazon S3 server. Furthermore, the time growth is linear due to the linear growth of index size.

Once encrypted inverted index are uploaded in storage server, we perform queries with different extracted features. In each of the cases we randomly select five value of the respected feature and perform the query and report the average. Figure 4 illustrates performance of the location, date, FCTH, and face queries. Among the location queries we observe that query by full address is fastest Query by state takes longest to finish and query by city performs in between. This is because time require to finish a query is proportional to the number to blocks fetched and processed. Very few images are like to have same full address however more images likely to have common state or city. Among the date queries range query and query by year-month-date (YMD) combination is the fastest for similar reason. Finally, FCTH and face query requires longest time due to long extract, transform, and post-processing step. We had to keep our discussion short here because of space limitation. Detail analysis of these results and few more experiment results are presented in the full version [24].

9 Conclusion

In this study, we addressed the problem of searchable encryption with sim-
ple server that can support complex queries with multimedia data type. We
made several contributions including an extensible general framework with se-
curity proof and its implementation. Our defined extract, transform, load, query
and post-process (ETLQP) framework can build efficient searchable encryption
scheme for complex data types (e.g, images). With this framework we can per-
form very sophisticated queries, such as face recognition, without needing cryp-
tographic computational support from the server. Our implementation shows
small overhead for building encrypted search index and performing such com-
plex queries. In addition, we also show that overhead of general cryptographic
operations is negligible compared to other necessary operations of a cloud based
file storage system.
**Acknowledgments.** The research reported herein was supported in part by NIH awards 1R0-1LM009989 & 1R01HG006844, NSF CNS-1111529, CNS-1228198, & CICI-1547324.

References

1. Agarwal, A.: Web vulnerability affecting shared links. https://blogs.dropbox.com/dropbox/2014/05/web-vulnerability-affecting-shared-links/

2. Andoni, A., Indyk, P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1), 117–122 (Jan 2008), http://doi.acm.org/10.1145/1327452.1327494

3. Bindschaedler, V., Naveed, M., Pan, X., Wang, X., Huang, Y.: Practicing oblivious access on cloud storage: the gap, the fallacy, and the new way forward. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. pp. 837–849. ACM (2015)

4. Bösch, C., Hartel, P., Jonker, W., Peter, A.: A survey of provably secure searchable encryption. ACM Computing Surveys (CSUR) 47(2), 18 (2015)

5. Cash, D., Jaeger, J., Jarecki, S., Jutla, C., Krawczyk, H., Rosu, M., Steiner, M.: Dynamic searchable encryption in very-large databases: Data structures and implementation. In: Network and Distributed System Security Symposium, NDSS. vol. 14 (2014)

6. Cash, D., Jarecki, S., Jutla, C., Krawczyk, H., Rosu, M., Steiner, M.: Highly-scalable searchable symmetric encryption with support for boolean queries. Cryptology ePrint Archive, Report 2013/169 (2013), http://eprint.iacr.org/

7. Chatzichristofis, S., Boutalis, Y.: Fcth: Fuzzy color and texture histogram - a low level feature for accurate image retrieval. In: Image Analysis for Multimedia Interactive Services, 2008. WIAMIS '08. Ninth International Workshop on. pp. 191–196 (May 2008)

8. Chatzichristofis, S., Boutalis, Y., Lux, M.: Img(rummager): An interactive content based image retrieval system. In: Similarity Search and Applications, 2009. SISAP '09. Second International Workshop on. pp. 151–153 (Aug 2009)

9. Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: Proceedings of the 13th ACM conference on Computer and communications security. pp. 79–88. ACM (2006)

10. Faber, S., Jarecki, S., Krawczyk, H., Nguyen, Q., Rosu, M., Steiner, M.: Computer Security – ESORICS 2015: 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part II, chap. Rich Queries on Encrypted Data: Beyond Exact Matches, pp. 123–145. Springer International Publishing, Cham (2015), http://dx.doi.org/10.1007/978-3-319-24177-7_7

11. Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious rams. J. ACM 43(3), 431–473 (May 1996), http://doi.acm.org/10.1145/233551.233553

12. Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. pp. 604–613. STOC '98, ACM, New York, NY, USA (1998), http://doi.acm.org/10.1145/276698.276876

13. Kamara, S., Papamanthou, C.: Parallel and dynamic searchable symmetric encryption. In: Financial Cryptography and Data Security, pp. 258–274. Springer (2013)
14. Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security. pp. 965–976. CCS ’12, ACM, New York, NY, USA (2012), http://doi.acm.org/10.1145/2382196.2382298

15. Kuzu, M., Islam, M.S., Kantarcioglu, M.: Efficient similarity search over encrypted data. In: Data Engineering (ICDE), 2012 IEEE 28th International Conference on. pp. 1156–1167. IEEE (2012)

16. van Liesdonk, P., Sedghi, S., Doumen, J., Hartel, P., Jonker, W.: Computationally efficient searchable symmetric encryption. In: Jonker, W., Petkovi, M. (eds.) Secure Data Management, Lecture Notes in Computer Science, vol. 6358, pp. 87–100. Springer Berlin Heidelberg (2010), http://dx.doi.org/10.1007/978-3-642-15546-8_7

17. Lu, W., Swaminathan, A., Varna, A.L., Wu, M.: Enabling search over encrypted multimedia databases. In: IS&T/SPIE Electronic Imaging. pp. 725418–725418. International Society for Optics and Photonics (2009)

18. Lux, M., Chatzichristofis, S.A.: Lire: Lucene image retrieval: An extensible java chir library. In: Proceedings of the 16th ACM International Conference on Multimedia. pp. 1085–1088. MM ’08, ACM, New York, NY, USA (2008), http://doi.acm.org/10.1145/1459359.1459577

19. Naveed, M., Prabhakaran, M., Gunter, C.A.: Dynamic searchable encryption via blind storage. In: Security and Privacy (SP), 2014 IEEE Symposium on. pp. 639–654. IEEE (2014)

20. Ostrovsky, R.: Efficient computation on oblivious rams. In: Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing. pp. 514–523. STOC ’90, ACM, New York, NY, USA (1990), http://doi.acm.org/10.1145/100216.100289

21. Pinkas, B., Reinman, T.: Oblivious ram revisited. In: Advances in Cryptology–CRYPTO 2010, pp. 502–519. Springer (2010)

22. Qin, Z., Yan, J., Ren, K., Chen, C.W., Wang, C.: Towards efficient privacy-preserving image feature extraction in cloud computing. In: Proceedings of the ACM International Conference on Multimedia. pp. 497–506. ACM (2014)

23. Raval, N., Pillutla, M.R., Bansal, P., Srinathan, K., Jawahar, C.: Efficient content similarity search on encrypted data using hierarchical index structures

24. Shaon, F., Kantarcioglu, M.: A Practical Framework for Executing Complex Queries over Encrypted Multimedia Data. https://eprint.iacr.org/2016/426

25. Stadmeyer, K.: Google drive update to protect to shared links. https://security.googleblog.com/2014/06/google-drive-update-to-protect-to.html (2014)

26. Thomee, B., Shamma, D.A., Friedland, G., Elizalde, B., Ni, K., Poland, D., Borth, D., Li, L.J.: The new data and new challenges in multimedia research. arXiv preprint arXiv:1503.01817 (2015)

27. Turk, M., Pentland, A.: Eigenfaces for recognition. Cognitive Neuroscience, Journal of 3(1), 71–86 (Jan 1991)

28. Viola, P., Jones, M.: Rapid object detection using a boosted cascade of simple features. In: Computer Vision and Pattern Recognition, 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on. vol. 1, pp. I–511. IEEE (2001)

29. Xia, Z., Zhu, Y., Sun, X., Wang, J.: A similarity search scheme over encrypted cloud images based on secure transformation. International Journal of Future Generation Communication and Networking 6(6), 71–80 (2013)