Fahad Shaon
email: fahad.shaon@utdallas.edu

Murat Kantarcioglu
email: muratk@utdallas.edu

A Practical Framework for Executing Complex Queries over Encrypted Multimedia Data

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 1 , Box 2 , Google Drive 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.

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 [START_REF] Agarwal | Web vulnerability affecting shared links[END_REF][START_REF] Stadmeyer | Google drive update to protect to shared links[END_REF]. To ensure the security of the sensitive data and prevent any unauthorized access, users may need to encrypt data before uploading 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 proposed [START_REF] Curtmola | Searchable symmetric encryption: improved definitions and efficient constructions[END_REF][START_REF] Van Liesdonk | Computationally efficient searchable symmetric encryption[END_REF][START_REF] Cash | Dynamic searchable encryption in very-large databases: Data structures and implementation[END_REF][START_REF] Kamara | Parallel and dynamic searchable symmetric encryption[END_REF][START_REF] Cash | Highlyscalable searchable symmetric encryption with support for boolean queries[END_REF][START_REF] Naveed | Dynamic searchable encryption via blind storage[END_REF][START_REF] Ostrovsky | Efficient computation on oblivious rams[END_REF][START_REF] Goldreich | Software protection and simulation on oblivious rams[END_REF][START_REF] Bösch | A survey of provably secure searchable encryption[END_REF]. Among those approaches, searchable symmetric encryption (SSE) [START_REF] Curtmola | Searchable symmetric encryption: improved definitions and efficient constructions[END_REF][START_REF] Van Liesdonk | Computationally efficient searchable symmetric encryption[END_REF][START_REF] Cash | Dynamic searchable encryption in very-large databases: Data structures and implementation[END_REF][START_REF] Kamara | Parallel and dynamic searchable symmetric encryption[END_REF][START_REF] Cash | Highlyscalable searchable symmetric encryption with support for boolean queries[END_REF][START_REF] Naveed | Dynamic searchable encryption via blind storage[END_REF][START_REF] Bösch | A survey of provably secure searchable encryption[END_REF] emerges as an efficient alternative for cloud based storage systems due to minimal storage overhead, low performance overhead, 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, popular commercial personal cloud storage providers 1 2 3 only support basic file operations like read and write file that makes it infeasible to apply traditional SSE techniques. Furthermore, complex queries on multimedia data may require running 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 requiring the cloud service providers cooperation emerges as an important and urgent need. To our knowledge, only [START_REF] Naveed | Dynamic searchable encryption via blind storage[END_REF] considered a setup without computational support 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 4 states 1.8 billion photos shared each day. However, indexing multimedia data is harder compared to text data. A significant 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-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.

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 [START_REF] Bösch | A survey of provably secure searchable encryption[END_REF]. Curtmola at el. [START_REF] Curtmola | Searchable symmetric encryption: improved definitions and efficient constructions[END_REF] 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 [START_REF] Van Liesdonk | Computationally efficient searchable symmetric encryption[END_REF][START_REF] Cash | Dynamic searchable encryption in very-large databases: Data structures and implementation[END_REF][START_REF] Kamara | Parallel and dynamic searchable symmetric encryption[END_REF][START_REF] Kamara | Dynamic searchable symmetric encryption[END_REF] 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. [START_REF] Cash | Highlyscalable searchable symmetric encryption with support for boolean queries[END_REF] proposed such a construction, where authors used multiround 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. [START_REF] Kuzu | Efficient similarity search over encrypted data[END_REF] 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. [START_REF] Faber | Computer Security -ESORICS 2015: 20th European Symposium on Research in Computer Security[END_REF], 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. [START_REF] Naveed | Dynamic searchable encryption via blind storage[END_REF] 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) [START_REF] Ostrovsky | Efficient computation on oblivious rams[END_REF][START_REF] Goldreich | Software protection and simulation on oblivious rams[END_REF] that also hides search access pattern and much secure. Despite recent developments [START_REF] Pinkas | Oblivious ram revisited[END_REF], traditional ORAM remains inefficient for practical usage in cloud storage system as described in [START_REF] Bindschaedler | Practicing oblivious access on cloud storage: the gap, the fallacy, and the new way forward[END_REF]. 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. [START_REF] Qin | Towards efficient privacypreserving image feature extraction in cloud computing[END_REF] proposed an efficient privacy preserving cloud based secure image feature extraction and comparison technique. Similar construction for ranked image retrieval is proposed by [START_REF] Xia | A similarity search scheme over encrypted cloud images based on secure transformation[END_REF][START_REF] Lu | Enabling search over encrypted multimedia databases[END_REF][START_REF] Raval | Efficient content similarity search on encrypted data using hierarchical index structures 24[END_REF]. 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-derOak5 , BoxCryptor6 ,Wuala7 , 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.

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, T rpdr, 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. T rpdr 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 [START_REF] Curtmola | Searchable symmetric encryption: improved definitions and efficient constructions[END_REF] for further discussion of SSE. Furthermore, in a typical SSE settings, Gen, Enc, T rpdr, 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.

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 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 form existence of such communication. We also assume that the cloud storage server Z is managed by Bob, who is semi-honest. As such, he follows the protocol as it is define 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.

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.

Extract

In this phase we extract necessary features from a dataset. Let, D = {d 1 , d 2 , ..., d n } be a set of documents, id(d i ) be the identifier of document d i , Θ = {θ 1 , θ 2 , ..., θ m } be a set of m feature extractor functions. Functions in Θ 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 θ j ∈ Θ we compute (f, v) ← θ j (d i ) and store (f, v) in U i . Finally we organize the result in P, such that P[id

(d i )] ← U i . Such an example P is illustrated in Fig- ure 1(c). Here, we have four documents {D 1 , ..D 4 }. D 1 has feature value pairs U 1 ={(f a , v α ),(f b , v β ), (f b , v γ )}, etc.
To clarify further, let us assume that, we want to build an encrypted image storage application that can preform location based query over the encrypted images. In other word, the system is capable of answering queries, such as, find images taken in Italy. To support such a query, we implement a feature extractor function θ l , where θ l extracts location information from image meta data. Output of θ 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.

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 , .., 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 t f,v ← t(f, v) where t ∈ 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] ← 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 α ), (f b , v β ), (f b , v γ ), (f a , v σ ), (f a , v δ ) 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.

Load

In this phase we setup our encryption schema, encrypt the inverted index, and upload the encrypted version into a file storage server Z. We initialize a master encryption key K, three random constants C 1 , C 2 , C 3 , a secure pseudo random permutation function ϕ, and a keyed pseudo random function H. Given a key, ϕ encrypts data, ϕ -1 decrypts corresponding result, and H generates authentication code of messages. In addition, we define a small synchronized cache C and an encryption key K C for encrypting the cache. C is always synchronized with storage server 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 C, we store document id list size of all search signatures of I, which is notated C.f req. 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 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 s j and K s j for j th block of document list of I[s]. We use K s j to encrypt block contents Algorithm 1 Load encrypted index for j = 1 → blockss do 6: and T s j as the key for encrypted inverted index 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.f req[s], then encrypt and upload the cache. Algorithm 1 describes the operations necessary for load phase.

T s j ← H(K, s || j || C1), K s j ← H(K, s || j || C2) 7: sub ← I[s].slice((j -1) × b, j × b) 8: E[T s j ] ← ϕ(K s j ,

Query

In previous phases we have created an encrypted inverted index and uploaded into file storage server 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 Q. We use number of document ids per block, stored in C.f req, to compute block counts, which in turn used to compute trapdoors K s j and T s j for each block of search signatures. Using these trapdoors we retrieve and decrypt document ids. Finally, the result is organized into a hash table R such that R[s] = I[s] for all s ∈ Q. Algorithm 2 contains the detail operations of query phase.

for i = 1 → blockss do 6: T s j ← H(K, s || j || C1), K s j ← H(K, s || j || C2) 7: L ← Z.read(T s j ) 8: add ϕ -1 (K s j , L) in R[s] 9:
end for 10: end for 11: return R

Post-process

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

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 α and co-efficient of dynamic cost β. Cost can be in terms of time and size. (α + β × 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 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|γ, x m ) = γx γ m x (γ+1) , where x is the random variable, γ 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

G (b) = β -x γ m βb -γ + (α + βb)x γ m γb -γ-1 -γx γ m b -γ ( α b + β) - γx γ m γ -1 b -γ-1 α
Now we minimize b by setting G (b) = 0 and solving the equation for b. In experimentation we observe that method of moments estimation for x m and γ gives almost correct value.

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 deffer further discussion on dynamic document addition for full version of the paper [24].

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., [START_REF] Curtmola | Searchable symmetric encryption: improved definitions and efficient constructions[END_REF] is widely used in literature. Later it is customized to work under random oracle model in [START_REF] Kamara | Dynamic searchable symmetric encryption[END_REF]. We adapt this definition to prove our security model. In short, we define, history H η , trace λ (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 (H η ) and the real view v R (H η ) of history H η are computationally indistinguishable. Due to space limitation we defer the formal security proof to our full version [24].

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) [START_REF] Chatzichristofis | Fcth: Fuzzy color and texture histogram -a low level feature for accurate image retrieval[END_REF], Eigenface [START_REF] Turk | Eigenfaces for recognition[END_REF], Locality Sensitive Hashing(LSH) [START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF], and range query to exact query conversion mechanism [START_REF] Faber | Computer Security -ESORICS 2015: 20th European Symposium on Research in Computer Security[END_REF].

Fuzzy Color Texture Histogram (FCTH) [START_REF] Chatzichristofis | Fcth: Fuzzy color and texture histogram -a low level feature for accurate image retrieval[END_REF] is an histogram of image that combines texture and color information. It is widely used in content based image retrieval systems (CBIR), e.g. [START_REF] Lux | Lire: Lucene image retrieval: An extensible java cbir library[END_REF][START_REF] Chatzichristofis | Img(rummager): An interactive content based image retrieval system[END_REF]. 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 [START_REF] Turk | Eigenfaces for recognition[END_REF] 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 bellow a pre-determined threshold then those faces are considered a match for associated test face. A detail 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 [START_REF] Andoni | Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions[END_REF]. 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( v.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 [START_REF] Faber | Computer Security -ESORICS 2015: 20th European Symposium on Research in Computer Security[END_REF]. 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 [START_REF] Faber | Computer Security -ESORICS 2015: 20th European Symposium on Research in Computer Security[END_REF], create the corresponding search signatures and perform the query.

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 take, time -when the picture was taken, texture and color -for searching similar pictures, and facesfor 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 feature 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 addition, result of LSH can contain false positives. We need extra post processing to remove those.

Extract. Location and time data are extracted from Exif8 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 9 . We use FCTH for similarity analysis and used a open source implementation of FCTH analyzer [START_REF] Lux | Lire: Lucene image retrieval: An extensible java cbir library[END_REF]. Finally, for face recognition using Eigenface, we extract frontal faces from images using haar cascade [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF] frontal face pattern classifier.

Transform. Now we define appropriate transformations for extracted features. 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 service10 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.

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 rang 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 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.

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 S311 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 it's services. In our implementation, search signatures of encrypted inverted index 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 1 , Box 2 , and Google Drive 3 . 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 [START_REF] Thomee | The new data and new challenges in multimedia research[END_REF], which contains basic in- 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.

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 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].

Conclusion

In this study, we addressed the problem of searchable encryption with simple server that can support complex queries with multimedia data type. We made several contributions including an extensible general framework with security 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 perform very sophisticated queries, such as face recognition, without needing cryptographic computational support from the server. Our implementation shows small overhead for building encrypted search index and performing such complex 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.

Fig. 1 .

 1 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.

1 :

 1 Require: K = Master key, I = Inverted index of search signatures, C = Synchronized cache, KC = encryption key for cache, Z = File storage server. 2: b ← optimize(I) 3: for all signature s in I do 4: blockss ← |I[s]| b 5:

Algorithm 2 1 :

 21 Query Require: K = Master key, q = Query, b = block size, Z = File storage server 2: Q ← Extract and Transform q 3: for all search signatures s in Q do 4: blockss ← C.f req[s] b 5:

  Both linearly depends on block size in our construction. So cost for a b length block is (α + β × b). Let, J (s) is |I[s]| meaning document id list size for search signature s and total cost G(b) for blocking and encrypting given inverted index I for block length b then G(b) = s∈I J (s) b

Fig. 3 .

 3 Fig. 3. Time required in different phases of building and uploading the index for different number of images.

Fig. 2 .

 2 Fig. 2. Index and cache sizes

  (b).

Fig. 4 .

 4 Fig. 4. Time required for different type of queries vs number of files.

https://www.dropbox.com

https://www.box.com/

http://drive.google.com/

http://www.kpcb.com/blog/2014-internet-trends

https://spideroak.com/

https://www.boxcryptor.com/

https://www.wuala.com/

http://www.cipa.jp/std/documents/e/DC-008-2012_E.pdf

https://drewnoakes.com/code/exif

http://wiki.openstreetmap.org/wiki/Nominatim

https://aws.amazon.com/s3/

Acknowledgments. The research reported herein was supported in part by NIH awards 1R0-1LM009989 & 1R01HG006844, NSF CNS-1111529, CNS-1228198, & CICI-1547324.


Ibrahim Lazrig
email: lazrig@cs.colostate.edu

Toan Ong
email: toan.ong@ucdenver.edu

Indrajit Ray
email: indrajit@cs.colostate.edu

Indrakshi Ray
email: iray@cs.colostate.edu

Michael Kahn
email: michael.kahn@ucdenver.edu

Privacy Preserving Probabilistic Record Linkage Using Locality Sensitive Hashes

As part of increased efforts to provide precision medicine to patients, large clinical research networks (CRNs) are building regional and national collections of electronic health records (EHRs) and patientreported outcomes (PROs). To protect patient privacy, each data contributor to the CRN (for example, a health-care provider) uses anonymizing and encryption technology before publishing the data. An important problem in such CRNs involves linking records of the same patient across multiple source databases. Unfortunately, in practice, the records to be matched often contain typographic errors and inconsistencies arising out of formatting and pronunciation incompatibilities, as well as incomplete information. When encryption is applied on these records, similarity search for record linkage is rendered impossible. The central idea behind our work is to create characterizing signatures for the linkage of attributes of each record using minhashes and locality sensitive hash functions before encrypting those attributes. Then, using a privacy preserving record linkage protocol we perform probabilistic matching based on Jaccard similarity measure. We have developed a proof-of-concept for this protocol and we show some experimental results based on synthetic, but realistic, data.

Introduction

The problem of privacy preserving record linkage arises in many data sharing applications that limit the access to certain information on a need-to-know basis. A typical example of this problem is that of record linkage in large clinical research networks. As part of increased efforts to provide precision medicine to patients, large clinical research networks (CRNs) are building regional and national collections of electronic health records (EHRs) and patient-reported outcomes (PROs). To protect patient privacy, each data contributor to the CRN (for example, a health-care provider) uses anonymizing and encryption technology before publishing the data. A medical researcher (data subscriber) on the other hand requests medical data from different data contributors and needs to aggregate the records of different patients. The challenging scenario occurs when many competitor data publishers are willing to anonymously and securely share some information with a subscriber, but do not want to share the encryption keys in order to protect their clients' privacy. The researcher is interested in finding linked (matched) patient records across the datasets and to be able to retrieve updates on some previously queried patients as well. In addition, the subscriber is not only interested in finding deterministically matched records only, but also records that potentially matches with high probability.

If the data is encrypted with a shared (or same) key, the matching process could be performed deterministically [11]. However, in a typical real-world setting, where the data publishers operate independently of each other, there is no guarantee that the same datum is consistent across different publishers. This occurs owing to factors such as, different structures (FName versus First Name), semantics (whooping cough vs. pertussis), typographic and formatting errors (John vs. Jhon), or the way the data is captured, entered and maintained by each entity. As a result, deterministic matching becomes difficult or ineffective. If the data is encrypted with different keys (as would typically be done by independent data publishers that do not trust each other), finding matches between the records are even more challenging. For privacy preserving record matching to be effective under such circumstances, we need to consider as many of the discrepancies in the data as possible that can potentially occur during acquisition (input) such as spelling mistakes, formatting errors, abbreviations, punctuations, pronunciations, users background, or different underlying assumptions about the structure of the data, and attempt to determine how similar the encrypted data are.

In this work, we build upon our previous secure record matching protocol [11], that performs a deterministic record matching using the services of a semitrusted broker, in order to construct a probabilistic record matching protocol. It takes into account the different types of discrepancies mentioned above. Probabilistic in the context of this work means that the matching is performed based on the likelihood of similarity with certain probability. We call the set of attributes used to perform the record matching, the linkage attributes. (Note that in the literature the term "quasi-identifier" is often used for the combination of attributes used for linkage. We do not use the term "quasi-identifier" because it explicitly excludes attributes that are themselves unique identifiers. In our case, the linkage attributes can be key attributes too. ) In order to hide the identities of the matched entities from all of the parties, the matching process is performed on encrypted data under different keys. Any two records of different data sets are said to be matched if they belong to the same individual/entity. In our demonstration, we use personal identification information as the linkage attributes (e.g. names. SSN, email address, DOB, Driving License number, etc.) for finding candidates for record matching. However, our protocol is easily generalizable to any other attributes that are of interest.

Related Work

The record linkage problem is defined as the process of finding records belonging to the same entity, across two or more data sets [START_REF] Fellegi | A Theory for Record Linkage[END_REF]. It has been widely studied in the context of linking records stored on different databases so as to identify duplicate records that appear to be different. Approximate comparison of string values and distance measures allow researchers to deal with data discrepancies and errors that causes such apparent differences in duplicate records [START_REF] Navarro | A Guided Tour to Approximate String Matching[END_REF][START_REF] Porter | Approximate String Comparison and Its Effect on an Advanced Record Linkage System[END_REF][START_REF] Broder | Identifying and Filtering Near-Duplicate Documents[END_REF][START_REF] Leskovec | Mining of Massive Datasets[END_REF]. In this work, we rely on Jaccard similarity measure that is calculated based on the common sub-strings of bi-grams between the strings to be compared. The min-hash technique, which has been proven to be a good approximation to the Jaccard similarity [START_REF] Broder | Identifying and Filtering Near-Duplicate Documents[END_REF][START_REF] Leskovec | Mining of Massive Datasets[END_REF], is used to construct a locality-sensitive hash function that speeds up the calculation of the Jaccard similarity [START_REF] Leskovec | Mining of Massive Datasets[END_REF].

Sharing individual data, such as medical or financial records, among multiple parties is a two edge sword that has its research benefits and privacy concerns for both the parties (who might be competitive) and the subjects (individuals) whose data is to be shared. Because privacy is a big concern, many research has been conducted to address privacy issues in the record linkage of shared data. The research resulted in the development of a number of privacy preserving record linkage protocols. Some of the protocols allow the parties to directly communicate and perform the matching process, and some utilize the service of a third party to accomplish the task of record matching. Our work belongs to the second category, where the third party blindly performs the matching process. Some research developed protocols targeted at private set intersection [START_REF] Cristofaro | Practical Private Set Intersection Protocols with Linear Complexity[END_REF][START_REF] Freedman | Efficient Private Matching and Set Intersection[END_REF][START_REF] Huang | Private Set Intersection: Are Garbled Circuits Better Than Custom Protocols?[END_REF]] and secure multi-party computation (SMC) [START_REF] Hazay | Efficient Protocols for Set Intersection and Pattern Matching with Security against Malicious and Covert Adversaries[END_REF][START_REF] Durham | Quantifying the Correctness, Computational Complexity, and Security of Privacy-Preserving String Comparators for Record Linkage[END_REF][START_REF] Atallah | Secure and Private Sequence Comparisons[END_REF][START_REF] Feigenbaum | Secure Multiparty Computation of Approximations[END_REF] to solve the record linkage problem. However these techniques do not fit directly in our scenario because either they require a shared key or the parties involved learns the result of the computation. Further more, some of these techniques do not scale very well with the number of parties and the size of the data sets, and incur large computation or communication overhead [START_REF] Vatsalan | An Efficient Two-Party Protocol for Approximate Matching in Private Record Linkage[END_REF].

In [START_REF] Karakasidis | Secure Blocking+ Secure Matching= Secure Record Linkage[END_REF], a framework for privacy-preserving approximate record linkage is proposed. The framework is based on a combination of secure blocking and secure matching. The secure blocking is based on phonetic algorithms statistically enhanced to improve security, and the secure matching is performed using a private approach of the Levenshtein Distance algorithm. The main advantage of blocking is that it results in a huge decrease of record comparisons.

A three-party protocol, proposed in [START_REF] Schmidlin | Privacy Preserving Probabilistic Record Linkage (P3rl): A Novel Method for Linking Existing Health-Related Data and Maintaining Participant Confidentiality[END_REF], relies on identical encryption at the sources and uses Bloom filters to perform similarity search. The linkage center performs probabilistic record linkage with encrypted personally identifiable information and plain non-sensitive variables. To guarantee similar quality and format of variables and identical encryption procedure at each site, the linkage center generates semi-automated pre-processing and encryption templates based on information obtained via a new method called data masking that hides personal information.

Similarity preserving data transformation approaches like [START_REF] Scannapieco | Privacy Preserving Schema and Data Matching[END_REF][START_REF] Yakout | Efficient Private Record Linkage[END_REF][START_REF] Pang | Privacy-Preserving Fuzzy Matching Using a Public Reference Table[END_REF][START_REF] Schnell | Privacy-Preserving Record Linkage Using Bloom Filters[END_REF] have been also presented. In [START_REF] Scannapieco | Privacy Preserving Schema and Data Matching[END_REF], a protocol that provides privacy at the levels of both data and schema matching was presented. In this protocol, records are mapped into an Euclidean space using a set of pre-defined reference values and distance function, while preserving the distances between record values. Then the semi-trusted (HBC) third party will compare the records in the metric space in order to decide their matching. The secure schema matching requires global schema, provided by the third party, on which the parties map their own local schemas. In [START_REF] Yakout | Efficient Private Record Linkage[END_REF], an approach based on the work in [START_REF] Scannapieco | Privacy Preserving Schema and Data Matching[END_REF], that doesn't need a third party was presented. A complex plain is created then an adjustable width slab is moved within the complex plain to compute likely matched pairs. In [START_REF] Pang | Privacy-Preserving Fuzzy Matching Using a Public Reference Table[END_REF], public reference tables are used to encode names as the distance to all reference points.Then a third party will estimate the distance between pairs based on their encoding.

In [START_REF] Schnell | Privacy-Preserving Record Linkage Using Bloom Filters[END_REF], a Bloom filters with a set of cryptographic hash functions are used to encode the attributes of the data records. The encoded records are then compared via a set-based similarity measure.

Most of these protocols where either theoretically or experimentally proven to be efficient. However most of these works do not fit directly into our scenario [START_REF] Cristofaro | Practical Private Set Intersection Protocols with Linear Complexity[END_REF][START_REF] Freedman | Efficient Private Matching and Set Intersection[END_REF][START_REF] Huang | Private Set Intersection: Are Garbled Circuits Better Than Custom Protocols?[END_REF][START_REF] Atallah | Secure and Private Sequence Comparisons[END_REF][START_REF] Vatsalan | An Efficient Two-Party Protocol for Approximate Matching in Private Record Linkage[END_REF] Because The data source parties participate in the matching process will know the matching results, or they work for deterministic match [START_REF] Cristofaro | Practical Private Set Intersection Protocols with Linear Complexity[END_REF][START_REF] Freedman | Efficient Private Matching and Set Intersection[END_REF], require a shared key [START_REF] Schmidlin | Privacy Preserving Probabilistic Record Linkage (P3rl): A Novel Method for Linking Existing Health-Related Data and Maintaining Participant Confidentiality[END_REF], or rely on expensive SMC operations that do not scale very well with the size of the data [START_REF] Hazay | Efficient Protocols for Set Intersection and Pattern Matching with Security against Malicious and Covert Adversaries[END_REF][START_REF] Durham | Quantifying the Correctness, Computational Complexity, and Security of Privacy-Preserving String Comparators for Record Linkage[END_REF][START_REF] Atallah | Secure and Private Sequence Comparisons[END_REF][START_REF] Feigenbaum | Secure Multiparty Computation of Approximations[END_REF].

Problem Formulation, Definitions and Background

We abstract the problem as that of a group of n ≥ 2 publishers (data sources) {P 1 , • • • , P n } , with n data bases {D 1 , • • • , D n } who would like to share information with another group of m ≥ 1 subscribers (e.g. researchers) {S 1 , • • • , S m } while protecting the privacy of their clients. At the end of the linkage process, we require that 1) the subscriber(s) gets the linked records identified by some random non-real ids, 2) none of the publishers knows the result of the linkage process, or that a certain client's information exists at other party's records , 3) none of the parties, including the party conducting the linkage process, should know the real identity of any client that it did not know a priori. Definition 1 -Linkage Attributes: For a database D i of publisher P i with a schema C = (A 1 , • • • , A w ) that has a set of w attributes, we define the set of linkage fields L ⊆ C as a subset of t ≤ w attributes that uniquely define the personal identity of the database records. We denote the linkage fields set as

L = {L 1 , • • • , L t } and the set of records of D i as R = {R 1 , • • • , R v }. We refer to the value of the linkage field L j of the record R k by R k • L j .
Definition 2 -Linkage Parameters: We associate with the linkage fields L sets of linkage parameters K, St, W , such that for each linkage field L i ∈ L , we define some linkage parameters, K i ∈ K that represents the number of hash functions used for similarity calculations of the values of that field, similarity threshold 0 ≤ St i ≤ 1 which defines the minimum similarity threshold to consider the values of the linkage field as a match, and Linkage Field weight w i ∈ W : 1≤j≤t w j = 1 that represents the importance of that field in the matching decision.

Definition 3 -Field Match Score: Given two values R j •L i , R k •L i of linkage field L i of two records R j , R k ,
similarity function Sim, field similarity threshold St i , and field weight w i , a field match score F M i is defined as:

F M i (R j •L i , R k •L i ) = 0 if Sim(R j • L i , R k • L i ) < St i w i • Sim(R j • L i , R k • L i ) otherwise Definition 4 -Record Match Decision: Given a similarity threshold T R and a set of Field Match scores {F M i : 1 ≤ i ≤ t} of two records R j , R k , the record match decision RM of R j , R k is defined as: RM (R j , R k ) = M atch if 1≤i≤t F M i ≥ T R N on -M atch otherwise 2.

Adversary Model

This work derives from the deterministic matching protocol of our previous work [11] that relies on a semi-trusted broker. Data publishers are considered competitors who do not want to share data with each other. Each publisher tries to determine information about the clients of competitor publisher, or at a minimum, tries to determine if any one of its clients is also a client of its competitor. However, publishers are also honest in the execution of the protocol steps and are willing to share information with subscribers privately, that is, without revealing real identities, and securely, that is, without any leakage of information to other data publishers, and without revealing the publisher's identity to the subscribers.

A data subscriber, on the other hand, needs to determine if any information that came from different publishers belong to the same individual so they could be grouped together as such and treated accordingly. For example, if a researcher is looking for the side effects of a new drug used for skin treatment on patients who has kidney problems, then he has to match patients from the Dermatology and Nephrology departments to find patients under these conditions. We need to allow such grouping at the subscriber side.

Further more, the subscriber is allowed to issue retrospective queries regarding some individual client, for example, update queries regarding the progress of treatment of certain patients. Subscribers (researchers) are considered curious in the sense they will try to determine the real identities of the individuals. Some information about individual identities might be leaked from their non-identification information (i.e. eye color, age, weight, etc.) using statistical inference techniques. This is a separate problem that needs to be addressed with anonymization (i.e. k-anonymity) or other sanitization methods, and is not considered in this work.

The broker is honest in the sense that it will not collude with any of the parties, but is curious and not trusted to keep a secret, secret. The broker will work as a mediator between the data publishers and the subscribers by honestly performing the following tasks:

-Hide the source of information (publishers and clients' identities) from the subscribers. -Blindly determine record linkages among the encrypted publishers' records and assign alternate random identifiers to the linked records before sharing them with the subscribers. The broker will just know the linkages between two encrypted records without knowing the real identifiers.

The Secure Deterministic Matching Protocol

The current work builds on our previous work [11] where we introduced the deterministic matching protocol using a semi-trusted broker. To facilitate understanding of the current protocol we briefly describe the previous work. Our previous protocol has three phases, the setup phase, the encryption of query results phase, and the secure matching phase:

-Setup phase: It is executed only once. In this phase the publishers collaboratively and securely create a set of encryption key converters, one for each publishers, using El-Gamal homomorphic encryption and the broker's public key pk. The inputs to this phase are each publisher's initial temporary encrypted key converter t i→i = Enc pk (r -1 i ), and the publisher's secret key sk i , where r i is an initial random secret of this publisher d i . At the end of this phase, each publisher has its initial key converter value (t i→f inal ) securely processed (using homomorphic operations under the broker's public key) by all other publishers. Then publisher d i sends its final encrypted key converter value to the broker, and saves a copy of it for future updates in case new publishers join the system or to refresh its secret key. Then, For each t i→f inal , the broker extracts the key conversion δ i using its private key sk such that:

δ i = Dec sk (t i→f inal ) = r -1 i N j=1 j =i sk j

-Encryption of query results phase:

Each publisher has the publicly known ElGamal EC parameters, i.e., the curve parameters E (F q ) and the point on the curve P of prime order n. The public/private key pair will be (r i • sk i • P, r i • sk i ) and both of the keys are kept secret. Each publisher encrypts the identification part of its data set id, which in our multiplicative scheme needs to be a scalar. We denote by E(.) the encryption of ElGamal based on EC. The publisher first hashes the identifying part of every record in its data set using a universal hash function H. Then uses its secret key multiplied by the corresponding random value, (r i • sk i ), to encrypt the resulting hash. That is, the encryption of any identifier id will be:

E (ri•sk i ) (H(id)) = H(id) • r i • sk i • P
Finally, the publisher substitutes the real identifying part, id, by

E (ri•sk i ) (H(id))
for all records in its data set before being sent to the broker. Publishers can avoid having the broker store the key converter (δ i ) i∈ [N ] . For this purpose, each publisher encrypts the identifiers of the query results with a new random value r i , updates the key converter t i→f inal , then sends these results to the broker accompanied with the new key converter. This solution adds negligible communication overhead, but ensures a zero-key stored on the broker side.

-Secure matching phase:

The broker receives the encrypted identifiers under different keys from different publishers. The broker's job is to merge similar clients' records from different publishers such that they will map to the same newly generated identifier. It uses the δ i values to convert any identifier id encrypted by publisher d i under its secret key (r i • sk i ), to a value encrypted under a different unknown secret key ∆, i.e., E ∆ (H(id)). The key ∆ = N i=1 sk i is resulting from the product of all the secret keys of all publishers, and cannot be computed by the broker who posses only the key converters of publishers. In order to perform the secure record matching, the broker re-encrypts the encrypted identifying parts of the records coming from the publisher d i using the corresponding key converter δ i as:

E δi E (ri•ski) (H(id)) = E ∆ (H(id))
3 The Secure Probabilistic Matching Protocol

In order to allow the parties to perform secure similarity match based on Jaccard measure, we improve our previous deterministic protocol to perform the match probabilistically with a predefined threshold. We improve the string set representation of the matching (linkage) attributes, then create signatures based on Locality Sensitive Hash scheme explained below. To prevent any correlation analysis, the signatures are lexicographically sorted and encrypted using the publishers' secret keys.

Minhash Functions and Similarity

To calculate the similarity of two strings A and B, we use the Jaccard Similarity measure. First the two strings are converted to a set representation S A , S B respectively (e.g. using bi-grams). Then the Jaccard similarity, Sim(A, B), is calculated on S A and S B as:

Sim(A, B) = | S A ∩ S B | | S A ∪ S B | If Sim(A, B
) is close to 1, then A and B are very similar. Let Ω be the set of all possible values of the set representation of the strings (e.g. all possible bigrams of the alphabet), then MinHash (also called min-wise hash) is computed by applying a random permutation π : Ω → Ω on any given set S and selecting the minimum value.

M inHash π (S) = min{π(S)}

It was proven by A. Broder [START_REF] Broder | Identifying and Filtering Near-Duplicate Documents[END_REF] that the probability of the minhashes of any two sets S A and S B being the same is equal to the Jaccard similarity of the two sets; that is:

P r(M inHash π (S A ) = M inHash π (S B )) = | S A ∩ S B | | S A ∪ S B | = Sim(A, B)
Thus, we can estimate the Jacard similarity of the two strings A and B by choosing a set of n (e.g. n = 100) independent random permutations, apply them to each string set representation to get a set of n minhashes (we also use the term signatures) of those strings, and compute how many corresponding minhashes of the two sets are equal. It is possible to simulate the n random permutations by n independent random hash functions (e.g. selecting a hash function and use n different random seeds).

Locality Sensitive Hashing -LSH

Locality sensitive hashing or LSH is a well known technique in the information retrieval community, that is used for determining similar items by hashing them in such a way that their hash values will collide with high probability. Let St 1 , St 2 be a similarity metric (e.g. Jaccard similarity) and P 1 , P 2 be two probabilities, then a family of functions H (e.g. minhashes) is called the (St 1 , St 2 , P 1 , P 2 )sensitive LSH if for every h ∈ H and any x, y :

1. if Sim(x, y) ≥ St 1 , then the probability that h(x) = h(y) is at least P 1 . 2. if Sim(x, y) ≤ St 2 , then the probability that h(x) = h(y) is at most P 2 .
From above, a family of K minhash functions with a similarity threshold St 0 is a (St 0 , 1 -St 0 , St 0 , 1 -St 0 )-sensitive LSH for Jaccard similarity. For a better accuracy of the similarity estimation it is preferred to have St 1 and St 2 as close as possible and P 1 and P 2 as far as possible. We construct a (St 0 , 1 -St 0 , γ, β)sensitive LSH family from a family of K minhash functions by grouping the minhashes (while keeping the order) into b groups of size r each, such that K = b • r, and then hash each group to get b new signatures. Hence, γ = 1 -(1 -St r 0 ) b and β = (1 -St r 0 ) b , where the probability that the new b signatures of x and y agree in at least one signature is γ.

We can further reduce the number of false positives by requiring that the b-signatures of x and y agree on at least m signatures (e.g. m = 2), then the probability of the b signatures to agree in at least m signatures will be:

m i b b i St r•i 0 (1 -St r 0 ) b-i
However, experiments show that m = 1 is sufficient.

Choosing LSH Parameters

For a similarity threshold St 0 , and K minhash functions we set the values of b (number of groups/signatures) and r (number of minhash values in each group) such that for any two strings x,y that have Sim(x, y) ≥ St 0 , the probability of getting at least m out of b of their corresponding signatures to match is greater than 0.5. This is done as follows:

m b • St

String Set Representation

In order to apply the LSH technique to get the signatures of the strings, we first need to convert the strings to sets of Q-grams (e.g. Bi-grams , for Q=2). In our implementation we extend the bi-gram set representation of our strings in such a way that it accounts for missing and flipped character positions. We add bigrams constructed from tri-grams with the middle character being deleted. For example, the the extended set representation of the string abcde is constructed as follows:

create the set of bi-grams B as B = { a, ab, bc, cd, de, e } create the set of Tri-grams T as T = { ab, abc, bcd, cde, de } -From T create the set of extensions X as X = { b, ac, bd, ce, d } -The Extended set E will be E = B ∪ X With this extension the possibility of matching strings with flipped character increases; for example the two strings John and Jhon will be considered a match with .75 Jaccard similarity using this technique. While the same strings without this extension will have .25 Jaccard similarity. We represent dates as strings and append some characters before and after the month, day and year components to make the bi-grams generated form those components look different in case they have the same digits.

Creation of LSH Signatures

During the setup phase, all data sources (publishers) agree on the set of size t linkage fields L = {L 1 , • • • , L t } and their corresponding similarity computation parameters, which are K i hash functions (or,it could be one hash function with K i different seeds), and similarity threshold St i for each linkage field L i ∈ L. We would like to emphasize here that those linkage fields not necessarily a single database attribute, they might be concatenations of certain attributes, as it is the case in many record matching works. Then each party calculates b i (number of groups/signatures) and r i (number of minhash values in each group) for each record linkage field L i as discussed in section 3.3 above. The steps for signature creation are as follows: We denote by Sig (i) j the set of signatures of the column i of record j, and ESig (i) j is its corresponding encrypted signatures. Each party

A with records set R A = {R 1 , • • • , R n } having linkage fields L = {L 1 , • • • , L t },
creates the linkage field signatures for each record R j ∈ R A , 1 ≤ j ≤ n as follows:

-For each linkage field value R j .L i ∈ R j create its corresponding Encrypted signature ESig (i) j as follows: 1. Convert the value R j .L i ∈ R j to an extended bi-grams set E 2. Apply K i hash functions to the set E and get the

K i minhash values minh = {min(h f (E)) : 1 ≤ f ≤ K i } 3.
Group the set minh into b i groups of r i items each, and without changing their order, i.e.

G x = {minh[(x-1) * r i +1] • • • minh[x * r i ]}, 1 ≤ x ≤ b i .
Then, using a universal hash function H, hash each group into one value getting the set of b i signatures of the value R j .L i as:

Sig (i) j = {H(G g ) : 1 ≤ g ≤ b i } 4.
The encrypted signatures of the value R j .L i will be:

ESig (i) j = {E sk A,L i (Sig (i) j [g]||g||L i ) : 1 ≤ g ≤ b i }
, where sk A,Li is the secret key of party A for linkage attribute L i . This secret key could be the same for all attributes.

sort ESig (i) j values in lexicographical order and append them as new field to the record.

Record Matching Phase

Each data source (publisher) will send the encrypted signatures of the linkage fields (columns) (as separate or combined) table(s) along with random record identifiers of its data set to the broker. To determine if record A.R k matches the record B.R j , the broker executes the following steps:

-For each set of encrypted signatures of each linkage column (L i ∈ L) of both records i.e. A.R k .ESig k ) for every linkage field L i . The key ∆ = N p=1 sk p is resulting from the product of all the secret keys of all parties (publishers). That is,

E δ A ESig (i) k = E δ A E sk A (Sig (i) k ) = E ∆ (Sig (i) k )
The same applies to B, that is,

E δ B ESig (i) j = E δ B E sk B (Sig (i) j ) = E ∆ (Sig (i) j )
-Compare the resulting signature sets encrypted under the same key ∆, B.E ∆ (Sig

(i) j ) and A.E ∆ (Sig (i)
k ) to find the number of equal signatures es i and update the results table for this linkage field L i . If the number of equal signatures is zero (0), then the similarity between these two values of this linkage field is less than the pre-set similarity threshold St i , and hence the field match score F M i (R j • L i , R k • L i ) will be zero. Otherwise, calculate the Estimated similarity of the two records for this linkage field L i as S i (es i /b i ) 1/ri , then calculate the field match score based on its weight w i using the equation 3 shown in section 2.

F M i (R j • L i , R k • L i ) = w i • S i
-To make a record match decision RM (R j , R k ) and declare the records R j and R k as a match or not, first compute the overall record match score using the field match scores computed in the previous step.

RecScore = 1≤i≤t F M i
Then compare the record match score with the pre-set record match threshold T R as shown in equation 4 in section 2. If a match is found, save the matched record identifiers as a matched pair in the results table.

At the end, the broker will have an association (mapping) between the record random identifiers of the publishers based on the scores computed from the matched signatures of the corresponding fields. For example, suppose we have two publishers A, and B that send the encrypted signatures of their records as tables with the following schema: Then the Broker will find the matched records and create the mappings between A's record Ids and B's record Ids and save them as new table with a schema similar to this: matchingResultT able(ARecId, BRecid, Score).

Publisher A: A.col 1 SigT able(ARecId, Col 1 Sigs), A.col 2 SigT able(ARecId, Col 2 Sigs), • • • , A.col t SigT
To evaluate the performance and the accuracy of this protocol, we implemented it and tested it against some data sets of different sizes and using combinations of different linkage fields. We adopted the following two approaches, 1) using each single attribute as a linkage field, and 2) using concatenation of some attributes as a linkage field. We evaluated the accuracy and performance based on these two approaches.

We define accuracy in terms of precision and recall based on true positive (TP), false positive (FP), true negative (TN) and false negative(FN). TP (True Positive) is the number of originally-matching records that are correctly identified as match. FP (False Positivse) is the number of originally-non-matching records that are falsely identified as match. TN (True Negative) is the number of originally-non-matched records correctly identified as a non-match. Finally, FN (False Negative) is the number of originally-matched records falsely identified as a non-match. Based on these values, we compute the following: (TPR), calculated as F 1 score = 2 × (P P V ×T P R) (P P V +T P R) .

Results of Using Realistic Synthetic Dataset

We use two datasets generated by the Mocaroo realistic data generator (http: //www.Mocaroo.com) and consisting of 10K records each, and 6K of the records are true matches. The record attributes (fields) used in this data were (ID, SSN, FirstName, LastName, email, DOB, Gender, ZipCode). We used two versions of the datasets, one is more corrupted than the other. We opt to use realistic synthetic datasets for many reasons, like known linkage results, shareable dataset for reproducibility (i.e., synthetic data don't require IRB approval), and controlled error/missing values rate. The data contains randomly generated real names, SSNs , addresses, and so other attributes. The corruption percentage is based on the number of modified (removed/inserted/swapped) characters to simulate errors occurred when acquiring the data (input into the database). The greater the data corrupted the more errors it contains. We ran an extensive set of experiments with different configurations on both versions of the datasets (less corrupted and highly corrupted), and for convenience we will discuss only some of them here. After some experiments using signatures for single attributes, we picked similarity threshold for each attribute (low threshold to allow more permissiveness, and high threshold for strictness in the matching criteria).

1. Using the Less corrupted Vs. the highly corrupted Datasets:

The more corrupted the data the lower the similarity between the records will be. So the similarity threshold of each linkage field that effect the its signatures creation will effect the matching results as well. For more permissiveness the threshold should be low, and vice versa. However the lower threshold will effect the False positive rate, so it is better to keep false positive as low as possible. Using logical expressions constructed from combinations of single attributes gives more flexibility to form matching criteria, and allows fine tuning of the matching threshold of each attribute separately. However it incurs more computation and storage overhead and make the signatures more susceptible to frequency attacks on some attributes. On the other hand, using the concatenated values of certain attributes before creating the signatures will limit the matching criteria to the combinations of these concatenations and reduce the flexibility of matching conditions. However such concatenated attributes, if properly constructed, will reduce the computations required in both signature creation and matching process, and limit the frequency attacks.

In our experiments we used the first technique to evaluate the accuracy of the protocol, and since the signatures are encrypted from the source with different keys, the frequency analysis is only possible if conducted by the broker. If the publishers use new random with each signature, update their key-converter δ and include it with the signatures, they can limit the broker frequency attack to those matched attributes, though will add communication overhead.

Table 1 shows the results of using four different combinations of the set of attributes. The top part of the table for the combinations using single attributes signatures, each has its similarity threshold, the bottom part of the table for the concatenated attributes and the similarity threshold is set for the whole concatenated attributes of each combination. The combinations are as follows:

-comb1: First Name, Last Name, Date of birth -comb2: Date of birth, SSN -comb3: Last name, SSN -comb4: Three Letters First Name, Three Letters Last Name, Soundex(First Name), Soundex (Last Name), Date of birth, SSN Any two records matched by any of the above combinations is considered a match. From the results in table 1, we were able to fine tune the threshold similarity of each attribute, using the single attribute technique, to control the true positives and false positive and get better results. It is much harder to do that in the second technique. The combination (Comb4) where constructed by creating a new attribute (we named "Special1") that consists of the concatenations of the first four parts of comb4 above (i.e. "Three Letters First Name" + "Three Letters Last Name" + "Soundex (First Name)" + "Soundex (Last Name)" ), then create the signatures for it. Finally, table 1 also shows the time used in the matching process using both techniques. It is evident how the second technique out performed the first, for the reasons mentioned above. In conclusion, our system achieved good matching quality results with good performance.

Conclusion

In this paper, we addressed the problem of privacy preserving probabilistic record linkage across multiple encrypted datasets when the records to be matched contain typographic errors and inconsistencies arising out of formatting and pronunciation incompatibilities, as well as incomplete information. We create characterizing signatures for the linkage of attributes of each record using minhashes and locality sensitive hash functions before encrypting those attributes. Then, using a privacy preserving record linkage protocol we perform probabilistic matching based on Jaccard similarity measure. We show some experimental results based on synthetic, but realistic, data. The results show that our matching protocol is flexible and achieved good matching quality without too much computation or communication overhead. Our future work will focus on improving the matching quality results by incorporating automation methods for selecting the best matching criteria and properly adjusting the similarity thresholds and weights of the attributes. In terms of security we will work on making the secure matching protocol resilient to collusion by making the broker collude with at least k out of n parties in order to get the encryption key.

  r 0 and b = K/r so r = K • St r 0 /m or r = ln(r • m/K)/ln(St 0 ), solve for r then use b = K/r to calculate b. All the values K,b, and r must be integers. The similarity threshold could also be approximated based on r and b as St 0 (1/b) 1/r

k

  , and B.R j .ESig

j

  , apply the key-conversion as follows: Use the key converter of A (δ A values) to convert the signatures of linkage fields A.R k .ESig

k

  of the record A.R k encrypted by publisher A under its secret key sk A , to signatures encrypted under a different secret key ∆, i.e., E ∆ (Sig (i)

1 .T P +F N 2 .T N +F P 3 .T P +F P 4 .

 1234 TPR (True Positive Rate) Or Sensitivity/recall: Fraction of originally matched records that are correctly declared as match: T P R = T P TNR (True Negative Rate) Or Specificity: Fraction of originally non-matched records that are correctly declared as non-match: T N R = T N PPV ( Positive Predictive Value) Or Precision: Fraction of correctly matched records from all records declared as a match: P P V = T P ACC (Accuracy ): Fraction of records correctly declared as a match and correctly declared as non-match: ACC = T P +T N T P +T N +F P +F N 5. F 1 score ( F-Measure) is the harmonic mean of precision (PPV) and recall

7 [Fig. 1 : 2 .

 712 Fig. 1: F1 score using low (Exp1) and high (Exp2) Similarity thresholds for single attributes, and different combinations

  able(ARecId, Col t Sigs) Publisher B: B.col 1 SigT able(BRecId, Col 2 Sigs), B.col 2 SigT able(BRecId, Col 2 Sigs), • • • , B.col t SigT able(BRecId, Col t Sigs)

Table 1 :

 1 Using Signatures of Single attributes Sim. Threshold for (SSN,First,Last,DOB,Special1) TP FP PPV ACC F1 Time (ms) Matching quality results of using single and concatenated combinations of attributes with different similarity thresholds settings

	(0.85, 0.85, 0.85, 0.85, 0.85)	5161 14 0.997 0.915 0.924 384589
	(0.85, 0.85, 0.85, 0.95, 0.85)	4916 2	1 0.891 0.901 261302
	(0.85, 0.75, 0.75, 0.98, 0.85)	5022 0	1 0.902 0.911 498038
	Using Signatures of Concatenated attributes
	Sim. Threshold for (comb1, comb2, comb3, comb4) TP FP PPV ACC F1 Time (ms)
	(0.95, 0.95, 0.95, 0.95)	5140 9 0.998 0.913 0.922	3895
	(0.98, 0.988, 0.99, 0.99)	4710 0	1 0.871 0.880	2009
	(0.98, 0.98, 0.98, 0.95)	4848 0	1 0.885 0.894	2364

This work was partially supported by a grant from Colorado State University, by NIST under contract 70NANB158264, and by NSF under grants IIP1540041 and CNS1619641. Any opinions, findings, recommendations, or conclusions reported in this work are those of the author(s) and do not necessarily reflect the views of the NIST or the NSF.