Tahmineh Sanamrad
email: sanamrat@inf.ethz.ch

Lucas Braun
email: braunl@inf.ethz.ch

Donald Kossmann
email: donaldk@inf.ethz.ch

Ramarathnam Venkatesan

Randomly Partitioned Encryption for Cloud Databases

Keywords: Database Encryption, Efficient Query Processing, Domain Attack, Frequency Attack, Query Log Attack, Randomly Partitioned Encryption

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Believing the trade press, cloud computing is the next big thing. Cloud computing promises reduced cost, flexibility, improved time to market, higher availability, and more focus on the core business of an organization. Virtually all players of the IT industry are jumping on the cloud computing band wagon. The only issue that seems to be able to stop cloud computing are security concerns [START_REF] Chow | Controlling data in the cloud: outsourcing computation without outsourcing control[END_REF]. The events that motivated this work were privacy violations in a private cloud by honest-but-curious adversaries. 1Encryption is a possible way to protect data against such attackers. The spectrum of available encryption schemes ranges from strong semantically secure (but typically inefficient) encryption schemes to weak (but efficient) encryption schemes. The problem that Randomly Partitioned Encryption tries to solve is to combine the advantages of lowsecurity/high-performance schemes like OPE [START_REF] Venkatesan | Order preserving encryption for numeric data[END_REF] with high-security/low-performance schemes like Probabilistic AES (AES in CBC mode [START_REF] Katz | Introduction to modern cryptography: principles and protocols[END_REF]), in order to achieve good security and reasonable performance. Performance refers to the average query response times of the TPC-H benchmark, while security, in this paper, is the ability to resist the following attacks (thoroughly defined in section 3):

• Domain Attack: The Adversary has knowledge of the plaintext domain.

• Frequency Attack: The Adversary has knowledge of the plaintext domain and its frequency distribution. • Query Log Attack: The Adversary has knowledge of the plaintext domain and has access to the database query logs.

Background and State of the Art

The main idea of RPE is to randomly partition the domain and apply an order preserving encryption scheme to each partition. This makes RPE a partially order-preserving encryption as each partition is ordered, but the total order is hidden. In the following, we try to summarize the state of the art in the context of existing OPE schemes and argue why they cannot withstand Domain, Frequency and Query Log Attack. A more detailed overview of related work can be found in section 9.

Order-Preserving Encryption (OPE). An order-preserving symmetric encryption (OPE) scheme is a deterministic symmetric encryption scheme whose encryption algorithm produces ciphertexts that preserve numerical ordering of the plaintexts. This property makes OPE very attractive for database applications, since it allows efficient range and rank query processing on encrypted data. However, the order relationship between plaintext and ciphertext remains intact after encryption, making it an easy target for a Domain Attack. Moreover, being deterministic, makes OPE particularly vulnerable against Frequency Attacks. OPE was first proposed in the database community by Agrawal et al. [START_REF] Venkatesan | Order preserving encryption for numeric data[END_REF], and treated cryptographically for the first time by Boldyreva et al. in [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF], followed by [START_REF] Boldyreva | Order-preserving encryption revisited: Improved security analysis and alternative solutions[END_REF], [START_REF] Malkin | Order-Preserving Encryption Secure Beyond One-Wayness[END_REF], [START_REF] Popa | An ideal-security protocol for order-preserving encoding[END_REF], [START_REF] Wozniak | Beyond the ideal object: towards disclosure-resilient order-preserving encryption schemes[END_REF] in search for an "ideal object". However, the problem of dealing with Domain and Frequency Attacks remains.

Probabilistic Order-Preserving Encryption (Prob-OPE). A probabilistic orderpreserving encryption scheme is a probabilistic symmetric encryption scheme whose algorithm not only produces ciphertexts that preserve numerical ordering of the plaintexts, but also generates different ciphertexts for the same plaintext. This property flattens out the original frequency distribution of the plaintext values, therefore resisting any statistical analysis. Examples are [START_REF] Elovici | A structure preserving database encryption scheme[END_REF], [START_REF] Kadhem | MV-OPES: Multivalued-order preserving encryption scheme: A novel scheme for encrypting integer value to many different values[END_REF], [START_REF] Wang | Efficient secure query evaluation over encrypted XML databases[END_REF], [START_REF] Yang | Privacy-preserving queries on encrypted data[END_REF]. However, probabilistic schemes still leak total order and are exposed to Domain Attacks.

Partially Order Preserving Encryption (POP). A partially order-preserving encryption scheme is a symmetric encryption scheme whose algorithm partitions the domain. Within each partition the order is preserved but across the partitions the order is distorted. There are several ways how to partition the domain: [START_REF] Kadhem | A Secure and Efficient Order Preserving Encryption Scheme for Relational Databases[END_REF], [START_REF] Seungmin | Chaotic order preserving encryption for efficient and secure queries on databases[END_REF] partition the domain into several bins. These solutions are secure against Domain Attacks, but vulnerable against Frequency and Query Log Attacks because the queries leak the bin boundaries. RPE on the other hand, partitions the data in a fine-grained manner and proposes a security-tunable method to rewrite queries.

Contributions and Main Results

To the best of our knowledge, this paper is the first that formally defines Domain Attack, Frequency Attack and Query Log Attack. Moreover, we introduce three novel encryption methods and analyze their security under these attacks. We start with a scheme that protects against the Domain Attack which we call Deterministic Randomly Partitioned Encryption (Det-RPE). We then make this scheme probabilistic (Prob-RPE) in order to address the Frequency Attack and finally introduce a new query-rewrite mechanism called Fixed-Range Query Rewrite (FR) to additionally protect RPE from Query Log Attacks. FR can be applied to both, Det-RPE and Prob-RPE, yielding two additional encryption schemes called Det-RPE-FR, resp. Prob-RPE-FR.

What is more, we assess the security and performance of these three encryption methods and compare them to relevant related work. Table 1 shows a summary of this assessment. The first three columns depict security and have a tick if a method is secure against a certain attack (a tick in brackets means that the security depends on a tuning parameter). The last column shows a very rough performance measure that states whether or not range queries can be answered within 30 minutes in the 10-GB TPC-H dataset. As we can see, the three RPE variants are Pareto-optimal as they have unique privacy/performance characteristics that differentiate them from existing solutions. [START_REF] Venkatesan | Order preserving encryption for numeric data[END_REF], [START_REF] Boldyreva | Order-preserving encryption revisited: Improved security analysis and alternative solutions[END_REF], [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF], [START_REF] Malkin | Order-Preserving Encryption Secure Beyond One-Wayness[END_REF], [START_REF] Popa | An ideal-security protocol for order-preserving encoding[END_REF], [START_REF] Wozniak | Beyond the ideal object: towards disclosure-resilient order-preserving encryption schemes[END_REF], [START_REF] Xiao | A Note for the Ideal Order-Preserving Encryption Object and Generalized Order-Preserving Encryption[END_REF] Modular OPE [START_REF] Boldyreva | Order-preserving encryption revisited: Improved security analysis and alternative solutions[END_REF] Probabilistic OPE [START_REF] Elovici | A structure preserving database encryption scheme[END_REF], [START_REF] Kadhem | MV-OPES: Multivalued-order preserving encryption scheme: A novel scheme for encrypting integer value to many different values[END_REF], [START_REF] Yang | Privacy-preserving queries on encrypted data[END_REF] Partially OPE [START_REF] Kadhem | A Secure and Efficient Order Preserving Encryption Scheme for Relational Databases[END_REF], [START_REF] Seungmin | Chaotic order preserving encryption for efficient and secure queries on databases[END_REF] [] AES-CBC [START_REF] Katz | Introduction to modern cryptography: principles and protocols[END_REF]

] Det-RPE Prob-RPE Det-RPE-FR [] Prob-RPE-FR []
One important feature of our methods is their composability. RPE schemes can be composed with any order-preserving encryption scheme approved by the security community, thereby inheriting their latest breakthroughs. Additionally, by adding a layer of randomness on top of a chosen underlying OPE scheme, RPE schemes amend the weaknesses of OPE schemes.

Overview

The remainder of this paper is organized as follows: Section 2 presents our assumed client-server architecture. Section 3 formally defines the newly introduced adversary models. Section 4 starts with describing the basic idea of Randomly Partitioned Encryption, then formally defines Det-RPE and analyses the security of Det-RPE and other OPE schemes under Domain Attack. Section 5 formally defines Probabilistic RPE and analyses its security under Frequency Attack. In Section 6, the Fixed Range Query Rewrite mechanism is explained and its security is analyzed under Query Log Attack. Section 7 and 8 describe implementation details and how they influence performance of the TPCH benchmark. Section 9 discusses related work in detail and section 10 briefly concludes.

Client-Server Architecture

Figure 1a shows the traditional client-server architecture of running applications on top of a database system. The application or end user issues SQL statements to the database server. The database server executes these SQL statements and returns the results. Figure 1b shows the extended architecture assumed in this paper. This architecture has also been assumed by all related work on client-side database security; e.g. in [START_REF] Arasu | Orthogonal Security with Cipherbase[END_REF], [START_REF] Damiani | Balancing confidentiality and efficiency in untrusted relational DBMSs[END_REF], [START_REF] Popa | Cryptdb: protecting confidentiality with encrypted query processing[END_REF], [START_REF] Sion | Secure data outsourcing[END_REF]. In this architecture, the application remains unchanged and issues the same (unencrypted) SQL statements as in the traditional system of Figure 1a. The confidentiality is implemented as part of an Encryption Layer. The Encryption Layer has two significant methods: First, rewriting the queries and updates that are to be submitted to the encrypted database. Second, decrypting and post-processing the query results returned from the encrypted database. Thus, the Encryption Layer encapsulates encryption/decryption and makes security issues transparent to the application developer and end user.

The Encryption Layer is assumed to be thin and trusted. Thin means that not much computational power is needed to implement the Encryption Layer; the heavy weightlifting of executing joins, aggregates, etc. is expected to be carried out in the database. It should be possible to deploy the Encryption Layer on a smart phone or laptop. The goal is to omit any administration requirements for the Encryption Layer.

Adversary Models

A couple of concrete usecases from the financial industry have given birth to new adversary models for cloud databases. These models have not been cryptographically treated so far. In this section we formally introduce the new adversary models and security metrics.

Notation. Let X be the set of plaintext values in a domain, and Y be the set of ciphertext values. The size of X is denoted as X = |X |; the same applies for the size of Y, Y = |Y|. Plaintext elements are denoted as x and ciphertext elements as y. Additionally, we define the Key space to be Keys and K is denoted as an element from the key space. K is a function that randomly selects an element from Keys, denoted as K $ ← Keys. The $ sign on top of the ← shows that the selection was random. Let Enc be the encryption function having a key, K, and a plaintext value, x, as its input parameters; thus, we have: y = Enc(K, x). Symmetrically, Dec will be the decryption function, taking y and K as input, yielding: x = Dec(K, y). Let Rank x be the rank of x in X . Symmetrically, we have Rank y which denotes the rank of y in Y. Let rank be the function that returns the rank of an element in its corresponding space. The frequency distribution of X and Y is denoted as F X and F Y respectively. Let f req be the function that returns the frequency of an element in its corresponding space.

Domain Attack

Domain Attack is launched by an adversary, A D that has a-priori knowledge of the plaintext domain. In our motivating usecase from the financial industry, the database administrator had a list of all customers and needed to retrieve other relevant account information for selected customers.

Rank One-Wayness In order to measure the success probability of A D , in breaking an encryption scheme, ES, we introduce a new notion called Rank One-Wayness (ROW). The ROW advantage is defined to be the probability of Experiment 1 returning 1.

Adv ROW ES (A D ) = P r[Exp ROW ES (A D ) = 1)] (1)
Experiment 1 :

Exp ROW ES (A D ) 1: K $ ← Keys; x $ ← X 2: y ← Enc(K, x) 3: Ranky ← rank(y) 4: x $ ← A D (X , Ranky) 5: if x = x then return 1 6: else return 0
To further clarify Experiment 1, let us consider the following example. Let X = { Beatles , M etallica , U 2 } and ES = OP E. Assume the ciphertext space to be Y = {143, 465, 706}. We start the experiment by choosing a random element from X , for instance M etallica and encrypt it. We provide A D with X and Rank 465 = 2. A D has to return an element from X which he thinks corresponds to the second element of Y. The probability that A D guesses M etallica correctly is called the ROW advantage.

Frequency Attack

A Frequency Attack is an attack that is launched by an adversary, A DF that has a-priori knowledge of the plaintext values as well as their frequency distribution.

Frequency One-Wayness In order to measure the success probability of A DF in breaking an encryption scheme, ES, we introduce a new notion called Frequency One-Wayness (FOW). The FOW advantage is defined to be the probability of Experiment 2 returning 1.

Adv FOW ES (A DF ) = P r[Exp FOW ES (A DF ) = 1] (2)
Again we illustrate this with an example. Let X = { Beatles , Beatles , U 2 } and ES = OP E. The ciphertext space will be Y = {143, 143, 706}. We start the experiment by choosing a random element from X , for instance Beatles and encrypt it. We give A DF , X , F X = {2, 1} and f req 143 = 2. A DF has to return an element from X which he thinks corresponds to the element of Y that appears twice. The probability that A DF guesses correctly is called the FOW advantage.

Experiment 2 : Exp FOW ES (A DF ) 1: K $ ← Keys; x $ ← X 2: y ← Enc(K, x) 3: F reqy ← f req(y) 4: x $ ← A DF (X , Fx, F reqy) 5: if x = x then return 1 6: else return 0

Query Log Attack

A Query Log Attack is launched by an adversary, A Q , that in addition to domain knowledge, has access to the database query logs, Q DB . In our concrete usecase, since the adversary is the database administrator, access to query logs is granted to him. Depending on the encryption scheme, the query logs may reveal more information about the underlying data than what the encryption scheme was initially intended to leak. Thus, it is crucial to add query log analysis to the list of possible cryptanalysis on database encryption schemes. In general, the query logs leak (1) content, ( 2) origin (e.g. an IP address of the client submitting the query), (3) frequencies, and (4) time stamp of the query. In this paper we will focus on the Query Content. How to perform query analysis and what an adversary can obtain from it, depends on the underlying encryption scheme.

We define the success probability of A Q as his advantage to break the Rank One-Wayness of the underlying encryption scheme, ES. Similar to Experiment 1, the adversary, A Q , is given the plaintext domain, X , a ciphertext rank, Rank y , and additionally the database query logs, Q DB . In the end, A Q is asked to return the underlying plaintext, x. The ROW advantage of A Q is formulated as:

Adv ROW ES (A Q ) = P r[Exp QLA ES (A Q ) = 1] (3)
Experiment 3 : Exp ROW ES (A Q ) 1: K $ ← Keys; x $ ← X 2: y ← Enc(K, x) 3: Ranky ← rank(y) 4: x $ ← A Q (X , Ranky, QDB)
note the additional argument QDB 5: if x = x then return 1 6: else return 0 4 Deterministic RPE This section presents the deterministic Randomly Partitioned Encryption scheme (Det-RPE). The key idea of RPE is to take an existing weak encryption method such as OPE as in [START_REF] Venkatesan | Order preserving encryption for numeric data[END_REF], [START_REF] Boldyreva | Order-preserving encryption revisited: Improved security analysis and alternative solutions[END_REF], [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF], [START_REF] Malkin | Order-Preserving Encryption Secure Beyond One-Wayness[END_REF], [START_REF] Xiao | A Note for the Ideal Order-Preserving Encryption Object and Generalized Order-Preserving Encryption[END_REF] as a building block and to enhance its security by applying it separately on different random partitions of the data called Runs. In contrast to other partially order preserving encryption schemes, such as [START_REF] Seungmin | Chaotic order preserving encryption for efficient and secure queries on databases[END_REF], [START_REF] Kadhem | A Secure and Efficient Order Preserving Encryption Scheme for Relational Databases[END_REF] where they bin the plaintext domain in random-length (or fixed ranged) partitions, RPE creates partially ordered partitions called Runs by randomly assigning each domain value to a Run; thereby creating more uncertainty. Figure 2a shows the workings of a traditional OPE encryption function. It receives a plaintext, x, and produces a ciphertext, y, and τ is the set of input parameters that Enc takes (e.g. a secret key). Figure 2b shows how RPE composes this traditional scheme to become more secure and have a number of additional operational advantages (e.g., support for updates). Instead of a single Enc function per domain, RPE makes use of U encryption functions per domain, Enc 1 , Enc 2 , . . . , Enc U , where U is the number of Runs. These U functions possibly all have the same structure (e.g. order-preserving using MOPE [START_REF] Boldyreva | Order-preserving encryption revisited: Improved security analysis and alternative solutions[END_REF]) and just differ in the secret key they use. Given a plaintext, x, ChooseRun generates a number between 1 and U and encrypts x using the corresponding Enc function, i.e. y = Enc ChooseRun(x) (x).

Depending on the ChooseRun function and the structure of the Enc function, the composed encryption scheme of Figure 2b can have different properties. The performance overhead of RPE (as compared to no encryption) depends on the number of runs, U ; In the extreme case of U = 1, RPE is the same as Enc which is typically a weak, yet high performance encryption scheme. In the other extreme, U = ∞, RPE is the same as random which corresponds to a strong yet low performance encryption scheme. Deterministic RPE (abbreviated as Det-RPE) is a deterministic encryption scheme because a deterministic ChooseRun and a deterministic Enc function are used. Determinism of the ChooseRun function can be achieved by making its output depend on the plaintext, x, i.e. by using a pseudo-random function. Our Det-RPE construction has to generate two sets of keys, one set for the runs and the other for the ChooseRun function. The encryption function of Det-RPE then composes the ChooseRun function with the encryption function of a typical OPE scheme. Det-RPE can be composed with any OPE scheme from [START_REF] Venkatesan | Order preserving encryption for numeric data[END_REF][START_REF] Boldyreva | Order-preserving encryption revisited: Improved security analysis and alternative solutions[END_REF][START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF][START_REF] Malkin | Order-Preserving Encryption Secure Beyond One-Wayness[END_REF][START_REF] Wozniak | Beyond the ideal object: towards disclosure-resilient order-preserving encryption schemes[END_REF][START_REF] Xiao | A Note for the Ideal Order-Preserving Encryption Object and Generalized Order-Preserving Encryption[END_REF].

Construction 1 Let OPE = (K, Enc, Dec) be a deterministic order-preserving encryption scheme. We define a deterministic RPE scheme, Det-RPE(K dRP E , Enc dRP E , Dec dRP E ), as follows:

• K dRP E runs K independently for each run and returns U keys, namely (K 1 , ..., K U ).

Also, it runs K independently to generate K map for the ChooseRun function.

• Enc dRP E takes K u and x, as input where u = ChooseRun(K map , x). Then it returns u and y = Enc(K u , x), i.e. (u, y). • Dec dRP E takes (u, y) as input and returns x = Dec(K u , y). Table 2 gives an example of a set of customer names encrypted with Det-RPE with U = 2 using an OPE scheme where U denotes the set of runs and |U| = U .

Analysis of Domain Attack

An ordinary OPE scheme such as in [START_REF] Venkatesan | Order preserving encryption for numeric data[END_REF], [START_REF] Boldyreva | Order-preserving encryption revisited: Improved security analysis and alternative solutions[END_REF], [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF], [START_REF] Malkin | Order-Preserving Encryption Secure Beyond One-Wayness[END_REF], [START_REF] Popa | An ideal-security protocol for order-preserving encoding[END_REF], [START_REF] Wozniak | Beyond the ideal object: towards disclosure-resilient order-preserving encryption schemes[END_REF], [START_REF] Xiao | A Note for the Ideal Order-Preserving Encryption Object and Generalized Order-Preserving Encryption[END_REF] allows the domain adversary, A D , to efficiently break the encryption by solely using sorting. In other words:

Adv ROW OPE (A D ) = 1.
On the other hand, a Modular OPE scheme, as proposed in [START_REF] Boldyreva | Order-preserving encryption revisited: Improved security analysis and alternative solutions[END_REF], is resilient against a Domain Attack as shown in Lemma 1.

Lemma 1 ROW-advantage of A D on Modular OPE is:

Adv ROW MOPE (A D ) = P r[Exp ROW MOPE (A) = 1] = 1 X (4)
Proof. In order to win Experiment 1 on MOPE, the adversary needs to know the modular offset. Since offset is chosen randomly from X , the adversary will win the game with a probability of 1 X .

Nevertheless, MOPE is vulnerable to the Known Plaintext Attacks, where the adversary additionally has one or more plaintext-ciphertext pairs. In that case, MOPE collapses into OPE.

The Probabilistic OPE schemes such as in [START_REF] Elovici | A structure preserving database encryption scheme[END_REF], [START_REF] Kadhem | MV-OPES: Multivalued-order preserving encryption scheme: A novel scheme for encrypting integer value to many different values[END_REF], [START_REF] Yang | Privacy-preserving queries on encrypted data[END_REF] have the following ROW advantage against a Domain Attack: Lemma 2 (proof in [START_REF] Sanamrad | POP: a new encryption scheme for dynamic databases[END_REF]) ROW-advantage of A D on Prob-OPE is:

Adv ROW Prob-OPE (A D ) = P r[Exp ROW Prob-OPE (A D ) = 1] = Ranky-1 Rankx-1 Y -Ranky X-Rankx Y -1 X-1 (5)
RPE amends all variants of OPE schemes to a great extent by randomly partitioning the domain into Runs, thereby breaking the total order into U partial orders. According to [START_REF] Berger | Approximation alogorithms for the maximum acyclic subgraph problem[END_REF][START_REF] Guruswami | Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph[END_REF], the problem of finding the right total order out of U partial orders is classified as inapproximable.

Lemma 3 (proof in [START_REF] Sanamrad | POP: a new encryption scheme for dynamic databases[END_REF]) ROW-advantage of A D on Det-RPE is defined as:

Adv ROW Det-RPE (A D ) = P r[Exp ROW Det-RPE (A D ) = 1] = Rankx-1 Rank (y,r) -1 X-Rankx X U -Rank (y,r) X X U (6)
The probability distribution conforms to a negative hypergeometric probability distribution which applies to sampling without replacement from a finite population, in our case the domain, X . As random selections are made from the population, each subsequent draw decreases the population causing the probability of success to change with each draw. The detailed proofs of Lemma 2 and 3 are quite involved and can be found in our technical report [START_REF] Sanamrad | POP: a new encryption scheme for dynamic databases[END_REF].

An important observation to make from Equations 5 and 6 is that the ROW advantage not only depends on the domain size but also on the rank of the plaintext in the domain. Consequently, extreme values of the domain (e.g. "AAA" or "ZZZ") are breaking the uniformity of the probability distribution. In order to fix this problem, Det-RPE can be composed with Modular OPE [START_REF] Boldyreva | Order-preserving encryption revisited: Improved security analysis and alternative solutions[END_REF] to form a ring structure to hide these extreme values.

In Figure 3 the ROW advantage is plotted for each encryption scheme. As a baseline we plot the advantage of an adversary that outputs a random x regardless of the domain. This is considered to be "ideal" and is exactly what Modular OPE [START_REF] Boldyreva | Order-preserving encryption revisited: Improved security analysis and alternative solutions[END_REF] achieves. We see that Det-RPE helps an OPE scheme (in that case ROPE from [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF]) with high ROW advantage to get close to the "ideal" threshold by increasing the number of runs.

The equations presented in this section can be tuned to meet the user's negligibility requirement. For example, in Equation 6, depending on the domain size, the number of runs can be tuned to meet the security/performance requirements of the system. The higher the number of runs, the closer one gets to the "ideal" threshold, but also the bigger is the performance overhead.

Probabilistic RPE

In this section we present the probabilistic variant of Randomly Partitioned Encryption (Prob-RPE). RPE is made probabilistic in two ways: (a) by using a probabilistic order preserving encryption scheme within each run, such as proposed in [START_REF] Yang | Privacy-preserving queries on encrypted data[END_REF] and (b) by assigning the same plaintext value to different runs to guarantee database dynamism and improve security.

In Probabilistic RPE, ChooseRun is defined as a random function. For each plaintext element, x, ChooseRun randomly selects a run, u. Afterwards, x is to be encrypted in u. Table 3 gives an example of such a Prob-RPE encryption scheme where the same value can even have multiple codes within a single run. For instance, Beatles has two codes in Run 2 and one code in Run 1, in other words Beatles = { 2, 1 , 2, 2 , 1, 1 }.

We formally construct Prob-RPE as follows:

Construction 2 Let Prob-OPE(K p , Enc p , Dec p ) be a probabilistic order-preserving encryption scheme from [START_REF] Yang | Privacy-preserving queries on encrypted data[END_REF]. We define a probabilistic RPE scheme, Prob-RPE(K pRP E , Enc pRP E , Dec pRP E ), as follows:

• K pRP E runs K p independently for each run and returns U keys, namely (K 1 , ..., K U ).

• Enc pRP E takes K u and x, as input where u = ChooseRun(). Then it returns u and y = Enc p (K u , x), i.e. (u, y). • Dec pRP E takes (u, y) as input and returns x = Dec p (K u , y).

The query rewrite mechanisms for RPE have been thoroughly explained in [START_REF] Sanamrad | POP: a new encryption scheme for dynamic databases[END_REF]. To give an intuition on how queries are rewritten using RPE, consider a query that asks for all customers with name LIKE ''M%'' in the example of Table 3 for Prob-RPE. This query must be rewritten to:

SELECT * FROM Customer WHERE (run = 1 AND ( 1 < y < 4)) OR (run = 2 AND ( 3 < y < 5))

Analysis of Frequency Attack

A known weakness of a deterministic encryption scheme is its inability to hide the original frequency distribution of the plaintext domain, specially if the plaintext domain has a skewed frequency distribution. Since OPE, Modular OPE and Det-RPE are all deterministic encryption schemes, the FOW-advantage introduced in Section 3.2 of A DF depends on the plaintext frequency distribution, namely F X . In other words, if the original frequency distribution is uniform then the adversary's advantage is also uniform, i.e. best security. Nevertheless, if the original frequency distribution is skewed, then the adversary's advantage is different and depends on the number of elements having the same frequency.

Corollary 1 Let y = Enc(K, x) and G = {w|w ∈ X ∧ f req X (w) = f req Y (y)} be the set of distinct plaintext values having the same frequency as y. Then, the FOWadvantage of the A DF adversary on a deterministic encryption scheme is defined as his winning probability in Experiment 2:

Adv FOW DET (A DF ) = P r[Exp FOW DET (A) = 1] = 1 |G| (7)
Remark 1 A deterministic encryption scheme is optimally safe against a Frequency Attack if and only if F X is uniform. A uniform F X implies a maximum |G| where |G| = X, i.e. |G| equals the domain size.

Remark 2 Probabilistic OPE and Prob-RPE as described in this section, take care of a skewed probability distribution by each time creating a new ciphertext for a plaintext value. This way the skewed frequency distribution of the plaintext domain is mapped to a uniform frequency distribution in the ciphertext space i.e. the FOW advantage under frequency attack is optimal which is 1 X .

Fixed Range Query Rewrite

In Section 3.3, we have introduced an attack that is based on the information that an attacker can extract from the query logs. The query logs are said to be dangerous, when they carry more information about the underlying encryption scheme than the encrypted data in the database.

To see what type of queries can be dangerous for each of the encryption schemes presented in this paper, we introduce the concept of a Query Simulator. A Query Simulator generates queries by looking at the encrypted data. Thus, if we are dealing with a query which can be simulated just by looking at the encrypted data, that query is called simulatable. Otherwise, the query is dangerous and can be exploited to break the guarantees of the underlying encryption scheme. Typically, in both, probabilistic and partially order preserving schemes, such as in [START_REF] Kadhem | A Secure and Efficient Order Preserving Encryption Scheme for Relational Databases[END_REF], [START_REF] Seungmin | Chaotic order preserving encryption for efficient and secure queries on databases[END_REF], [START_REF] Yang | Privacy-preserving queries on encrypted data[END_REF] to support efficient query processing, the queries reveal essential information about the certain initial values. Therefore, RPE conceals the total order which can be reconstructed by query log analysis. Table 4 presents a summary of the simulatable SQL operators in combination with the encryption schemes presented in this paper. 4 shows that all SQL Operators are simulatable for OPE. Nevertheless, OPE is not safe against Query Log Attack because the adversary has domain knowledge and can therefore launch a Domain Attack. Probabilistic OPE and Partially OPE schemes seem at first sight to be more secure, but on the other hand queries are not simulatable in those schemes, i.e. query log attack breaks them.

Our approach, RPE, is most of the time simulatable except for range queries. Thus, there are two solutions to this problem: (1) Suppress the range queries, (2) Using Fixed Range Query Rewrite mechanisms. In this section we will elaborate the second option. The idea of Fixed Range Query Rewrite is to divide the ciphertext space, Y into k disjoint fixed-sized sub-ranges of size r, f r i where i = 1, ..., k and |f r i | = r. Whenever a range query is asked, the smallest units that are returned are those fixed ranges that contain the user's results.

As an example, consider Table 5 where deterministic RPE has been used for encryption. The client submits the query: SELECT name FROM customer WHERE name > 'Lady Gaga'. Using Det-RPE the query should be rewritten to: SELECT name FROM customer WHERE (run = 1 AND 3 < code < 10) OR (run = 2 AND 3 < code < 10).

However, since this query is revealing some information about the partition relationships, we will use fixed range query rewrite mechanisms. Thus, the original query will be rewritten as follows to cover both fixed ranges, f r 1 and f r 2 that contain the result: SELECT name FROM customer WHERE (run = 1 AND 0 < code < 10) OR (run = 2 AND 0 < code < 10). This is the whole table in this example. The result includes two additional false positives, namely, "Beatles" and "Elton John" that will be filtered out during the postprocessing. Obviously, using Fixed Ranged Query Rewrite returns a super-set of the result that needs to be post-filtered and leads to performance loss. On the other hand, the security guarantees and analysis will deviate from what we have discussed earlier in Section 4.

Analysis of Query Log Attack

According to Table 4, OPE schemes are safe against query analysis, however Modular OPE cannot safely handle min/max and rank queries. Probabilistic OPE cannot handle range queries without revealing the borders, so using Fixed Ranged Query Rewrite protects the encryption scheme from query log analysis. In case of RPE, range queries are problematic because they help to reconstruct the total order, which is exactly what RPE is trying to hide. Hence, Fixed Ranged Query Rewrite helps again to limit the ROW advantage under query log attack. Assuming we have a uniform code distribution within a range in all runs, Equation 6 changes into:

Adv ROW Det-RPE-FR (A Q ) = P r[Exp ROW Det-RPE-FR (A Q ) = 1] = Rank f r x -1 Rank f r (y,r) -1 r-Rank f r x r u -Rank f r (y,r) r r U (8)
Informally speaking, the randomness is no more distributed throughout the domain, but is only available within the fixed range. From Equation 8 we reach the following conclusions:

• If U = r then we have a uniform probability distribution. This means although no range query is possible within a fixed range (like having AES in each range). Among different fixed ranges, range queries are possible. • Getting better security is achievable by both increasing the range size and the number of runs. However they both come at the cost of performance. • Range size is the main parameter whereas the domain size does not play a role anymore.

Database Functionality

After the security assessment of RPE, we also want to compare its supported functionality to the state-of-the-art. Table 6 summarizes which SQL operators can be efficiently implemented for which encryption technique. We can see that the RPE variants support most of the desired SQL operators, which allows them to be used in practice while semantically secure encryption schemes (like e.g. AES in CBC mode or fully homomorphic encryption schemes [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF] become inefficient as soon as we want to ask range, in, order-by or group-by queries. RPE also allows indexes to be build on top of it as usual. For a full description on query rewrite and referential integrity, we refer the curious reader to our Technical Report [START_REF] Hildenbrand | Query processing on encrypted data in the cloud[END_REF].

Performance Analysis and Experimental Results

In order to measure to what extent missing SQL operator influence query performance, we implemented the TPC-H benchmark on the architecture shown in figure 1. We have executed a number of experiments with different varying parameters, e.g. the number of runs or the number of codes per value in a single run for Prob-RPE. We measured total response time, post-processing time, network cost and query compilation time. For space reasons we only present the most important results and reference to our technical report [START_REF] Sanamrad | POP: a new encryption scheme for dynamic databases[END_REF] for the complete numbers and explanations.

All experiments were conducted on two separate machines for client and server. The client was written in Java, ran on a machine with 24 GB of memory and communicated to the database server using JDBC. The server machine had 132 GB of memory available and hosted a MySQL 5.6 database. Both machines had 8 cores and ran a Debianbased Linux distribution. We measured end-to-end response time for all queries in separation, thereby using a scaling factor of 10 (which means that the size of the plaintext data set is 10 GB). Metrics used in aggregate functions (e.g., volume of orders) and surrogates (e.g., order numbers) were left unencrypted while all other (sensitive) attributes, such as names, dates, etc. were encrypted. Whenever SQL operators on encrypted data were not supported, the entire data was shipped and then aggregated and filtered during the post-processing step at the encryption layer. Wherever the TPC-H benchmark defines an index on an attribute a, we created the same index on the encrypted value of a as well as a composite index on (a run, a).

Figure 4 shows the response time for different encryption functions compared to Plain, which is the response time for query processing on unencrypted data. Det-OPE is a deterministic OPE scheme as proposed by [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF] and was used as a gold standard to compare against two different RPE variants that both used fixed-range query rewrite. The deterministic RPE version is denoted by Det-RPE-FR, while Prob-RPE-FR stands for the probabilistic version. We can see that for a majority of queries and RPE variants, response time is at most three times higher than Plain and twice as high as Det-OPE. Sometimes, it is even smaller than the baselines because the partitioning (together with the composite indexes) allows for parallelized query processing, which was employed in the presence of Top-N queries. As expected, Prob-RPE-FR can add significant overhead. However, we believe this overhead to be reasonable as the security gain is substantial as shown in the previous sections. We also measured the performance of deterministic AES-ECB [START_REF] Katz | Introduction to modern cryptography: principles and protocols[END_REF], but did not include the results in the graph because most queries did not finish withing 30 minutes and therefore had an overhead ranging from about 20x to 200x. AES-CBC [START_REF] Katz | Introduction to modern cryptography: principles and protocols[END_REF], a representative of semantically secure encryption schemes, would perform even worse. The number of runs, U , is an important parameter of all RPE schemes. Figure 5 shows how the running time of Det-RPE-FR increases with the number of runs for the first six TPCH queries and relative to Plain. We chose these queries because they cover a wide spectrum of different operators (range predicates, aggregates, Top N, sub-selects, etc.). Overall, it can be seen that the curves are fairly flat. Only for Q6, there is a significant (but still linear) increase in the response time with a growing number of runs. Q2 and Q3 are Top N queries and are therefore executed with a degree of parallelism equal to U , which result in a decreasing response time. Q1, Q4 and Q5 have a similar behavior like most TPCH-queries: their curves stay fairly flat. This shows that partitioning does generally not hurt RPE.

Related Work

To fill the gap between no security/high performance and high security/low performance, there have been a number of proposals for encryption techniques that support query processing without decrypting the data. Examples are [START_REF]Privacy-preserving data mining[END_REF], [START_REF] Damiani | Balancing confidentiality and efficiency in untrusted relational DBMSs[END_REF], [START_REF] Hacigümüs | Executing SQL over encrypted data in the database-service-provider model[END_REF]. However, these approaches return a superset of the desired result and lose a lot of time into decrypting and filtering out the false positives.

On the other hand, the goal of fully homomorphic encryption (FHE) [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF], [START_REF]A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF], [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF], [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF], [START_REF] Smart | Fully homomorphic encryption with relatively small key and ciphertext sizes[END_REF] is to strongly encrypt the data and process it directly without decryption. [START_REF] Wang | Is Homomorphic Encryption the Holy Grail for Database Queries on Encrypted Data[END_REF] shows, at a conceptual level, how FHE can be used in databases. However, when taken to practice, databases explode in size because of the huge keys required by FHE. Therefore, the practicality of FHE in databases is an open question and no performance evaluation has been published so far.

Another important class of encryption techniques for databases are variants of orderpreserving encryption (OPE), first introduced by Agrawal et al. [START_REF] Venkatesan | Order preserving encryption for numeric data[END_REF]. Examples include Random (Modular) OPE [START_REF] Boldyreva | Order-preserving encryption revisited: Improved security analysis and alternative solutions[END_REF], [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF], Mutable OPE [START_REF] Popa | An ideal-security protocol for order-preserving encoding[END_REF], Indistinguishability-based OPE [START_REF] Malkin | Order-Preserving Encryption Secure Beyond One-Wayness[END_REF], Generalized OPE [START_REF] Wozniak | Beyond the ideal object: towards disclosure-resilient order-preserving encryption schemes[END_REF], [START_REF] Xiao | A Note for the Ideal Order-Preserving Encryption Object and Generalized Order-Preserving Encryption[END_REF], Structure Preserving Database Encryption [START_REF] Elovici | A structure preserving database encryption scheme[END_REF], Probabilistic OPE [START_REF] Yang | Privacy-preserving queries on encrypted data[END_REF], OPE with Splitting and Scaling [START_REF] Wang | Efficient secure query evaluation over encrypted XML databases[END_REF], Multivalued OPE [START_REF] Kadhem | MV-OPES: Multivalued-order preserving encryption scheme: A novel scheme for encrypting integer value to many different values[END_REF], Multivalued partial OPE [START_REF] Kadhem | A Secure and Efficient Order Preserving Encryption Scheme for Relational Databases[END_REF], and Chaotic OPE [START_REF] Seungmin | Chaotic order preserving encryption for efficient and secure queries on databases[END_REF]. RPE is based on Random OPE and Modular Random OPE from [START_REF] Boldyreva | Order-preserving encryption revisited: Improved security analysis and alternative solutions[END_REF], [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF], but very different from all the other OPE derivatives in the sense that it either solves a different problem (i.e. addresses different attacks) or uses different techniques. Systems that exploit OPE are CryptDB [START_REF] Popa | Cryptdb: protecting confidentiality with encrypted query processing[END_REF] and Monomi [START_REF] Tu | Processing analytical queries over encrypted data[END_REF]. RPE can be integrated into these systems to make them more secure.

Secure hardware has recently been exploited in the TrustedDB [START_REF] Bajaj | TrustedDB: a trusted hardware based database with privacy and data confidentiality[END_REF] and Cipherbase [3] projects. They are an interesting approach, but how to reach good performance, especially for analytical workloads, is still open. Again, RPE can be plugged-in into these systems in order to allow for faster, but still secure query processing.

Most commercial database products support strong encryption using AES [START_REF] Katz | Introduction to modern cryptography: principles and protocols[END_REF], e.g. Oracle [START_REF] Nanda | Transparent Data Encryption[END_REF] and Microsoft SQL Server [START_REF] Hsueh | Database encryption in SQL server 2008 enterprise edition[END_REF]. Unfortunately, they only support encryption for data at rest at the disk level, which means that these approaches do not address attacks issued by a curious database administrator or any other party that can access to the data in memory.

Conclusion

This paper presented different variants of Randomly Partitioned Encryption, a set of novel methods for encrypting cloud databases, thereby addressing real world attacker scenarios like Domain, Frequency and Query Log attacks. To the best of our knowledge, this is the first time that these attacks were formally defined and their success probability with respect to both, existing order-preserving encryption schemes, and the proposed RPE variants, analyzed. Moreover, the paper showed that the additional performance cost introduced by these new encryption schemes is reasonably small and gave a detailed overview of similar and related work in the literature.

Fig. 1 :

 1 Fig. 1: Client-Server Database Architecture

Fig. 2 :

 2 Fig. 2: RPE Principle

Fig. 3 :

 3 Fig. 3: ROW advantage under Domain Attack

Fig. 4 :

 4 Fig. 4: TPC-H response times of different encryption functions relative to Plain, scaling factor 10

Fig. 5 :

 5 Fig. 5: Response Time of TPC-H Queries 1 to 6 for Det-RPE-FR, vary U from 1 to 16

Table 1 :

 1 Qualitative Security & Performance Analysis of selected Database Encryption Schemes

	Adversary Model	Domain Attack Frequency Attack Query Log Attack Performance
	OPE

Table 2 :

 2 Det-RPE Example: U = 2

	Clear Text	Run 1 Run 2 Code ( run, y )
	Beatles	1	2, 1
	Beatles	1	2, 1
	Beatles	1	2, 1
	Elton John	1	1, 1
	Madonna	2	2, 2
	Madonna	2	2, 2
	Metallica	3	2, 3
	Nelly Furtado	2	1, 2
	Tina Turner	3	1, 3

Table 3 :

 3 Prob-RPE with U = 2

Table 4 :

 4 SQL Operator Simulatability for different Encryption Schemes

	SQL-Operator	OPE MOPE [6] Prob-OPE [18], [35] POP [17], [26] Det-RPE Prob-RPE *-RPE-FR
	WHERE (=, !=)/IN
	WHERE (<, >)/LIKE(Prefix%)
	Equi-Join
	TOP N
	ORDER BY (sort)
	MIN/MAX
	Table

Table 5 :

 5 Two fixed ranges of size 3, r = 3

	Fixed Range Customer Names Run 1 Run 2 Code ( run, y )
		Beatles	3	2, 3
	f r1	Elton John	1	1, 1
		Madonna	5	2, 5
		Metallica	9	2, 9
	f r2	Nelly Furtado	6	1, 6
		Tina Turner	7	1, 7

Table 6 :

 6 Supported SQL Operators: State of the Art vs. RPE

	SQL-Operator	OPE MOPE[6] POP[17, 26] Det-RPE Prob-RPE FHE [12] AES-CBC [19]
	DISTINCT
	WHERE (=, !=)
	WHERE (<, >)
	LIKE(Prefix%)
	LIKE(%Suffix)
	IN
	Equi-Join
	Non Equi-Join
	TOP N
	ORDER BY
	SUM
	MIN/MAX
	GROUP BY

adversaries that do not actively manipulate data, but try to infer information as defined in[START_REF] Katz | Introduction to modern cryptography: principles and protocols[END_REF]

Sanamrad, Braun, Kossmann, and Ramarathnam


Michael G Solomon

Vaidy Sunderam

Li Xiong
email: lxiong@emory.edu

Towards Secure Cloud Database with Fine-Grained Access Control

Keywords: Confidentiality, Searchable Encryption, Ciphertext Policy, Fine-grained Access Control, Cloud

Outsourcing data to cloud environments can offer ease of access, provisioning, and cost benefits, but makes the data more vulnerable to disclosure. Loss of complete control over the data can be offset through encryption, but this approach requires an omniscient third party key authority to handle key management, increasing overhead complexity. We present the ZeroVis framework that provides confidentiality for data stored in a cloud environment without requiring a third party key manager. It combines fine-grained access control with the ability to search over encrypted data to allow existing applications to migrate to cloud environments with very minimal software changes, while maintaining data provider control over who can consume that data.

Introduction

An agreement with a Cloud Service Provider (CSP) [START_REF] Gowrigolla | Design and auditing of cloud computing security[END_REF] to store data in a public, community, or hybrid cloud environment can provide the benefits of outsourced maintenance and capability to alter capacity based on demand [START_REF] Carroll | Secure cloud computing: Benefits, risks and controls[END_REF]. However, the cost of outsourcing data storage is diminished control over data security [START_REF] Shen | The security of cloud computing system enabled by trusted computing technology[END_REF][START_REF] Jansen | Guidelines on security and privacy in public cloud computing[END_REF]. CSP environments are untrusted [START_REF] Farcasescu | Trust model engines in cloud computing[END_REF] in which local levels of control cannot be attained [START_REF] Khan | Establishing trust in cloud computing[END_REF][START_REF] Jansen | Guidelines on security and privacy in public cloud computing[END_REF]. Traditional access control methods are often insufficient for CSP [START_REF] Khan | Establishing trust in cloud computing[END_REF][START_REF] Kulkarni | Cloud security challenges[END_REF] hosted databases. Lacking sufficient confidentiality controls not only exposes the data to additional vulnerabilities, but is also possibly a violation of laws, regulations, or contract terms [START_REF] Mather | Cloud Security and Privacy: An Enterprise Perspective on Risks and Compliance. Theory in practice[END_REF]. The primary challenge is to extend confidentiality assurances into untrusted domains [START_REF] Kulkarni | Cloud security challenges[END_REF]. Since different data consumers have different privileges, data access must be individualized and restricted to authorized consumers. And to be functionally effective, the protected data must be searchable without incurring excessive overhead or exposing any of the protected data to any entities in the untrusted environment [START_REF] Chow | Controlling data in the cloud: Outsourcing computation without outsourcing control[END_REF].

A common method to protect data in any untrusted environment is to encrypt data before sending it outside the trusted domain [START_REF] Elmasri | Fundamentals of Database Systems [With Access Code[END_REF]. In multiuser database scenarios, solutions using most traditional encryption implementations are suboptimal, requiring an additional key-management layer thereby degrading performance and scalability [START_REF] Zou | A practical and flexible key management mechanism for trusted collaborative computing[END_REF][START_REF] Lee | A cryptographic key management solution for hipaa privacy/security regulations[END_REF][START_REF] De | Over-encryption: Management of access control evolution on outsourced data[END_REF].

Traditional data encryption techniques require a single key, or a pair of keys, to encrypt and decrypt each data item. The most fine-grained approach to using encryption for data stored in a database requires a separate key for each cell (each column within a row), and a trusted key authority to store keys and manage access to them based on predetermined access criteria. The opposite extreme approach would be to use a single key or key pair to encrypt and decrypt all protected cells in the database, an approach similar to various transparent data encryption schemes [START_REF] Ferretti | Transparent access on encrypted data distributed over multiple cloud infrastructures[END_REF][START_REF] Deshmukh | Transparent data encryption-solution for security of database contents[END_REF]. This approach makes it easier to manage keys but introduces a single point of compromise. A balance between the two extremes is to define partitions of encrypted data (the set of encrypted cells in a database that share the same encryption/decryption key), and are often implemented as roles [START_REF] Zhou | Enforcing role-based access control for secure data storage in the cloud[END_REF]. While this approach is a good compromise between minimum and maximum granularity, the common use of key access managers does still grant access control authority to the key access manager, instead of giving the authority to the data provider. Running Example. Difficulties with balancing data protection and ease of access are common in medical data collection. Consider the following scenario. Four research teams, A, B, C, and D, need patient data. Table 1 shows four research teams, along with the specific treatments they are studying and the general context of their work. The primary challenge to be addressed is to obtain current data that is pertinent to their research, while complying with HIPAA rules and patient constraints. Patient constraints allow a patient to control who can access her data, such as researchers, medical service providers, and next of kin to access her data. A patient can submit her data with constraints, such as "allow authorized cancer researchers to access my data".

Contributions. We propose a framework that addresses the need of confidentiality in an untrusted environment along with maintaining data provider control over data consumer access without an omniscient key manager. Our framework, termed ZeroVis1 , combines the ability to search across encrypted data [START_REF] Raluca | Cryptdb: Protecting confidentiality with encrypted query processing[END_REF] with fine-grained access control [START_REF] Bethencourt | Ciphertext-policy attribute-based encryption[END_REF] to provide confidentiality protection, searchability for efficient access, and data owner initiated access control, all in an untrusted storage environment. Our framework will provide a one-to-many (one data provider to many data consumers) data confidentiality layer that can be accessed by existing legacy applications to allow current host-bound applications to migrate to a cloud storage environment and maintain confidentiality. Our framework does not require a trusted third party to manage encryption keys for data providers and consumers. Nor does it require specific permission for each new data consumer (e.g. research team). In essence, each data provider (patient) specifies an access policy (based on attributes rather than identities) for her data that determines who can access protected portions of her data. Traditional key management schemes require a key manager to associate authorized data providers and authorized data consumers with keys (a many-to-many relationship). Our framework assumes the existence of an attribute manager that maintains valid attributes for authorized data consumers (instead of many keys), regardless how many partitions they can access.

Given our running example, assume that a patient received treatment at an oncologist's office. The patient specified that the data to describe and record the visit is saved with the following access policy: "treatment='Z51.11' AND (context=cancer OR context=tobacco use)" (i.e. only data consumers that possess the treatment attribute with a value of Z51.112 and the context attribute with either the values of cancer or tobacco can access her data.)

Our framework proposes the use of CP-ABE (Ciphertext Policy Attribute Based Encryption) [START_REF] Bethencourt | Ciphertext-policy attribute-based encryption[END_REF] to control access to data based on the data consumer's attributes. Only consumers who possess attributes that satisfy the ciphertext's access policy can decrypt. In the running example, all research teams can retrieve any encrypted database row. However, only A and C can decrypt the data since their attributes (treatment and context) satisfy the CP-ABE access policy. Our framework also utilizes layered encryption in combination with CP-ABE to support efficient query processing on encrypted data. In this paper we present an implementation of our framework and a performance study with different database sizes the demonstrate the feasibility of our proposed approach.

Related Work

The ZeroVis framework most closely relates to searchable encryption and distributed/federated encryption key management. Broadcast encryption [START_REF] Fiat | Broadcast encryption[END_REF] was first proposed as a solution to the problem of sending secure transmissions from one site to an arbitrary number of recipients. This scheme is similar to ours, but differs in its reliance on a known hierarchical distribution pattern and set of privileged users. Later work based on [START_REF] Fiat | Broadcast encryption[END_REF] increases scalability [START_REF] Phan | Adaptive cca broadcast encryption with constant-size secret keys and ciphertexts[END_REF] [START_REF] Kim | Efficient semi-static secure broadcast encryption scheme[END_REF] and even integrate Attribute Based Encryption techniques for greater utility [START_REF] Zhou | On efficient ciphertext-policy attribute based encryption and broadcast encryption: Extended abstract[END_REF].

Attribute Based Encryption (ABE) [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] addressed the problem of encrypting data for an arbitrary number of recipients. Unlike broadcast encryption, ABE keys are derived instead of simply shared. Goyal proposed an extension to Identity Based Encryption (IBE) [START_REF] Boneh | Identity-based encryption from the weil pairing[END_REF] that uses attributes and access policies, not distinct identities, to encrypt and decrypt data. The two primary forms of ABE are Ciphertext Policy ABE (CP-ABE) and Key Policy ABE (KP-ABE). KP-ABE embeds the access policy in the user's private key [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF], while CP-ABE embeds the access policy in the ciphertext [START_REF] Bethencourt | Ciphertext-policy attribute-based encryption[END_REF]. KP-ABE gives control over who can decrypt data to the key generator, while CP-ABE ensures that the encryptor (data owner) retains control over who can decrypt her data [START_REF] Bethencourt | Ciphertext-policy attribute-based encryption[END_REF]. ABE solves the problem of providing access to private data for specified recipient without traditional key management issues, and is proposed in several outsourcing secure data schemes [START_REF] Yu | Achieving secure, scalable, and fine-grained data access control in cloud computing[END_REF][START_REF] Ibraimi | Ciphertext-policy attribute-based threshold decryption with flexible delegation and revocation of user attributes[END_REF][START_REF] Yu | Attribute based data sharing with attribute revocation[END_REF], but the technique alone does not map well to encrypting data for storage in a database due to its lack of a mechanism to efficiently search encrypted data. Li et. al. [START_REF] Li | Scalable and secure sharing of personal health records in cloud computing using attribute-based encryption[END_REF] uses both CP-ABE and KP-ABE schemes to store personal health record (PHR) data in a semi-trusted environment. Their proposed framework extends the basic ABE notion to include Multi-Authority ABE (MA-ABE) [START_REF] Chase | Improving privacy and security in multi-authority attribute-based encryption[END_REF] to allow different attribute authorities with different data needs to collectively generate users' secret keys based on distinct sets of user attributes. This approach of securing PHR data focuses primarily on storing documents and does not address the problem of efficiently searching across many PHR data items.

CryptDB [START_REF] Raluca | Cryptdb: Protecting confidentiality with encrypted query processing[END_REF] is research software that addresses the performance limitations of accessing encrypted data stored in a database. Multiple copies of each encrypted column are stored, using different encryption algorithms, to support many requirements of common application queries. Although CryptDB does solve the access performance issue, it relies on distinct keys that are bound to user identities. Further, CryptDB focuses primarily on transaction related queries. The Monomi [START_REF] Tu | Processing analytical queries over encrypted data[END_REF] project uses many of CryptDB's techniques to address analytical queries, extending the CryptDB concept by splitting query processing between the server and the client. While more scalable than CryptDB for analytical queries, it still does not provide a scalable method for one-to-many encryption.

Verifiable Attribute-based Keyword Search over Outsourced Encrypted Data (VABKS) [START_REF] Zheng | Vabks: Verifiable attribute-based keyword search over outsourced encrypted data[END_REF] uses ABE to provide access control and solves the problem of searching across encrypted data in the cloud by adding encrypted keyword indexes to the ABE payload. While VABKS does provide searchability for ABE encrypted data, the technique is document-centric, requiring a defined list of searchable keywords for each ABE item, limiting its usefulness for searching across many database items.

Our approach builds on selected concepts from each of the above, and adds data provider controlled access control to better address efficient encrypted data access and overcome difficulties associated with distributed access control.

Problem Definition and Building Blocks

Consider a database D, with tables T 1 .. T i . Each Table contains rows R 1 .. R j , each with columns C 1 .. C k . Clients access the database contents as data providers (DP), data consumers (DC), or as both roles. Data providers store data in the database (INSERT, UPDATE), and data consumers retrieve data from the database (SELECT). In a database that uses client-based encryption to protect stored data, clients access data in one or more columns (C 1 , C 2 , ..., C k ) from one or more rows (R 1 , R 2 , ..., R j ) from one or more tables (T 1 , T 2 , ..., T i ). Data providers encrypt data before storing it in the database and data consumers must decrypt data after retrieving it from the database. In this model, the database only stores encrypted versions of protected cells and never sees the plaintext version of the data. The primary problem with this approach is in the difficulty of generating and managing the keys to encrypt and decrypt data. Data providers and data consumers must share keys to access data, and the number of keys grows with a higher level of desired fine-grained access (i.e. a need for more encryption partitions.)

We built the ZeroVis framework on two primary building blocks, Ciphertex Policy Attribute Based Encryption (CP-ABE), and CryptDB. Each component brings desirable features to ZeroVis, but neither one solves our problem alone. Ciphertex Policy Attribute Based Encryption. A CP-ABE scheme provides fine-grained access control over data [START_REF] Bethencourt | Ciphertext-policy attribute-based encryption[END_REF]. CP-ABE associates a user with a set of descriptive attributes to generate the user's secret key, SK. Data are encrypted under an access policy such that only users whose attributes match the access policy can decrypt the data. To encrypt a message M using CP-ABE, the encryptor provides an access policy which is expressed as a boolean expression containing selected attributes and values for M. Figure 1 shows the access policy presented earlier in a tree structure. The message is then encrypted based on the access structure, T. Decryptors generate SK based on their attributes. A decryptor is only able to decrypt ciphertext, CT, when her SK satisfies the access policy used to encrypt the message. Unauthorized users cannot decrypt CT even if they collude and combine their disjoint attributes. CP-ABE works well for encrypting individual shared data where the file's name or identifier is known, but there is no provision for searching ciphertext, thereby making CP-ABE alone insufficient for database queries.

CryptDB. CryptDB is a DBMS that provides confidentiality for data stored on an untrusted database server [START_REF] Raluca | Cryptdb: Protecting confidentiality with encrypted query processing[END_REF]. The system provides neartransparent confidentiality by intercepting database queries and rewriting them in such a way as to execute over encrypted data. Decryption for consumption never occurs on the server, only at the trusted proxy. CryptDB also incorporates an encryption strategy that can adjust the encryption level of each column based on user queries. At runtime, the CryptDB proxy analyzes each query and determines the encryption needs based on the query components. The proxy will either then map each query component to an encrypted data item or request an encryption layer adjustment. All data is initially stored by CryptDB encrypted into several layers, with each layer encrypted with one of six encryption methods. The resulting value is called "encryption onion". CryptDB will only "peel" an onion layer (decrypt the outer layer) if a query requires an inner layer to successfully complete. This dynamic ability to alter encryption layers gives CryptDB the flexibility to maintain confidentiality while still responding to query requirements. The database server peels onion layers with user defined functions, and will never remove the innermost layer that would expose the original plaintext. Although CryptDB does provide the ability to select and search encrypted data on an untrusted sever, it still requires user-based encryption keys. CryptDB must rely on an external authority to enforce key management, including authorizing multiple consumers to decrypt a provider's data.

ZeroVis Framework

Framework Overview

To overcome the problems described in the previous section, our approach integrates CP-ABE with the ability to search across encrypted data, e.g. as provided in CryptDB, to synthesize a solution that supports single data provider encryption accessible by multiple data consumers for data stored in an untrusted environment, along with the ability to efficiently retrieve the data without decrypting in the cloud.

Figure 2 shows the ZeroVis framework. The core of our framework is the ZeroVis proxy which is responsible for encrypting data and queries and decrypting query results. The data provider submits data along with access policies through ZeroVis Proxy which encrypts the data via CP-ABE and searchable encryption and stores the encrypted data through an unmodified DBMS. A data consumer submits a query along with a pregenerated secret key, SK, (generated from the data consumer's attributes) through the ZeroVis proxy which encrypts the query. The DBMS returns encrypted results of the query to the ZeroVis proxy, which decrypts the results and returns the plaintext to the data consumer.

One additional requirement of a complete framework in a production environment is an Attribute Authority (AA). The AA is responsible for authorizing users, and managing attributes associated with those users. The framework depends on the AA to supply authenticated attributes for each authenticated user, and to prevent unauthorized users from submitting queries through the framework. Users can submit queries directly to the untrusted DBMS, but without the necessary master key from the AA, decryption attempts are unsuccessful.

Data Insertion and Encryption

To encrypt data, the DP provides the trusted proxy with the plaintext data and an access policy. Figure 3 shows the data flow with an example INSERT query. The trusted proxy encrypts the plaintext data, translates the query components into their encrypted counterparts (for query elements that are stored encrypted in the DBMS), and submits the encrypted payload, along with the embedded access policy, to the DBMS. Notice in Figure 3 there are 2 ciphertext values. The first represents existing CryptDB encryption and the second depicts the new CP-ABE CT added by ZeroVis.

Data Retrieval and Decryption

To decrypt data, a DC must first generate a secret key, SK, based on her attributes. In most implementations, a trusted AA will generate a key for each identity upon new user registration. The DC provides a set of descriptive attributes, SX, such as treatment and context interest areas (for our running example). Attributes can describe an entity's state, status, or authorized interest areas. The AA generates SK based on the supplied SX and returns SK to the DC on demand. For example, a research team member may possess attributes "treatment=Z51.11, context=cancer". The DC then presents SK (generated by the AA) to the trusted proxy when attempting to access encrypted data. The trusted proxy translates the supplied query elements into their encrypted counterparts (for query elements that are stored encrypted in the DBMS), and submits the query, depicted in figure 3. The proxy then translates the returned data from the encrypted state, CT, as stored in the DBMS, depicted in figure 4, into plaintext state, M, for the application. The CP-ABE decryption algorithm will only return plaintext message, M, when the supplied SK satisfies the data's embedded access policy that was provided by the DP. If the supplied key does not satisfy the access policy the proxy simply returns a null value.

The process of modifying data (UPDATE) is essentially a combination of a data retrieval operation followed by a data submission operation. While the process of updating data is straightforward, the implementation of the framework would need to ensure updates are well-behaved and do not allow unauthorized data or policy modifications. Users updating data must possess SK to retrieve data and an access policy to encrypt changes. Traditional access controls would be necessary to limit data and policy updates to authorized users.

Implementation

Our test implementation of ZeroVis was built on the architecture described above. The data consumer issues queries to the ZeroVis proxy. The ZeroVis proxy re-writes each query and submits it to the mySQL database server. We built the ZeroVis proxy by modifying the CryptDB proxy, which was built by modifying mysql-proxy. Both CryptDB and Ze-roVis can be implemented using other proxy software and any DBMS the chosen proxy supports. Both the ZeroVis proxy and the MySQL database server run on computers running Linux. ZeroVis supports both interactive clients through a shell prompt and existing applications through a connection to the proxy. Both client types require that users register with an AA.

We implemented the ZeroVis framework by integrating CP-ABE into CryptDB proxy. CryptDB provides query re-writing and capability to search across encrypted data. The addition of CP-ABE as a new encryption method within CryptDB gives the framework one-to-many encryption capability. The first change to CryptDB was to create a new column for each protected column. CryptDB normally creates 2 or 3 columns to store encrypted data using different methods to support different types of queries. The new column for each plaintext column stores the CP-ABE CT. We added a new encryption layer, ABE, to each onion definition, added a new ABE security level, and added a new class to handle CP-ABE encryption and decryption operations. The new class uses cpabetoolkit functions to encrypt and decrypt data. We modified the CryptDB proxy query re-writing code to replace requested columns with CP-ABE columns. We retain the CryptDB obfuscated column names in the queries to allow the database to select data using searchable data. The database then returns only CP-ABE encrypted data. The proxy attempts to decrypt each column and returns successfully decrypted data to the client.

With the new functionality in place to handle CP-ABE, we extended the proxy to fetch the user's CP-ABE SK, based on the MySQL database user id. The private key will be provided by the AA in more robust implementations. Additional modifications to the proxy also fetch and store the current user's default access policy for CP-ABE encryption operations. The ZeroVis system currently creates CP-ABE CT for every encrypted column. The CP-ABE encryption uses the current user's access policy. Decryption uses the current user's SK, previously generated using the CP-ABE keygen() function. Future work will extend the supported SQL syntax to allow users to optionally provide access policies with every query.

Performance Results

Experiment Setup. Our performance assessment is based on a straightforward CP-ABE addition to CryptDB as described above. Our goal was to determine the additional overhead CP-ABE added to the existing CryptDB implementation. We created multiple copies of test databases, all based on subsets of the TPC-C [START_REF]Transaction Processing Performance Council[END_REF] benchmark database. Test databases of different sizes were built by altering the number of rows in the item, warehouse, and district tables, all based on cardinality relationships defined in the TPC-C specification. The resulting 5 test databases DB-a, DB-b, DB-c, DB-d, DB-e have row cardinality of 1912, 2975, 7156, 18622, 35756 respectively, which are approximately increasing in a logarithmic scale. We created sets of queries, both single row and multiple row returned sets, to assess the general performance of the ZeroVis framework. The queries were simple, single table INSERT statements to load varying size subsets of the TPC-C database, and single table SELECT statements to retrieve 1 row (150 SELECTs) and sets (150 SELECTs) from the item, stock, and customer tables. The SELECT queries to retrieve sets of rows were randomly generated to select a range from the domain of each table. The test sever had an Intel Core 2 2.0 GHz(x2) processor with 3GB RAM running Ubuntu 13.10. The client/proxy computer had an Intel Core i7 2.4 GHz(x8) processor with 16GB RAM running Ubuntu 13.10. The two computers were connected via a 100Mbit/s Ethernet connection.

Results. Adding CP-ABE results in an additional encryption operation for each protected column, adding substantial observed space and computation time overhead. CryptDB, without CP-ABE, is approximately 26% slower (throughput loss) than native MySQL [START_REF] Raluca | Cryptdb: Protecting confidentiality with encrypted query processing[END_REF] when running the TPC-C benchmark. Encryption and decryption times are linearly related to the number of leaf nodes in the CP-ABE access policy. According to Bethenourt et al, [START_REF] Bethencourt | Ciphertext-policy attribute-based encryption[END_REF], their implementation of CP-ABE took approximately 0.5 seconds to encrypt a payload with 20 policy leaf nodes, while only taking 0.04 seconds to decrypt. One reason why the encryption operation is so much slower is that it includes parsing and processing the provided policy. The decrypt operation does not directly interact with attributes. Generating the key, based on supplied attributes, is a separate function that must be completed prior to any decryption attempt. Figure 6 shows the resulting database size (in MB) of the 5 test databases with varying row cardinality (approximately increasing in a logarithmic scale) for CryptDB (without CP-ABE) and ZeroVis (with CP-ABE) respectively. As the figure illustrates, the overhead incurred by ZeroVis increases linearly with the row cardinality. The current implementation stores a complete CP-ABE ciphertext payload for every protected database column, which includes the access policy and the encrypted data. Our future work will explore reducing redundancy through consolidating CP-ABE access policies which we expect will significantly decrease the overhead. As mentioned above, the current test ZeroVis implementation constructs the access policy tree for each column, even if all columns share the same policy. It is expected that reducing CP-ABE access policy redundancy will also reduce computational overhead for future ZeroVis framework versions and result in ZeroVis performing more closely to CryptDB. Figure 8 shows times for queries that return single rows, and sets of rows (range queries). We submitted 300 SELECT queries for each database instance, 150 distinct queries and 150 range queries. The queries were scaled to consider the range of data stored in each database (randomly generated to exercise the full range of data in each table). Queries use both indexed and non-indexed criteria. The disparity between CryptDB and ZeroVis performance for range queries is due to ZeroVis' current larger data storage requirements. Additional tests with the proxy and sever running on a single machine showed that network costs were not responsible for the higher overhead of ZeroVis. The queries in our test returned most of the columns from each table, requiring CP-ABE decryption operations for each column. While decrypting multiple columns is normal expected behavior, the redundancy of storing and transporting multiple copies of the access policy for each column increases the workload.We believe reducing redundant CP-ABE operations and normalizing the access policy storage technique will reduce ZeroVis' computational overhead and additional costs of the framework, resulting in performance closer to CryptDB than the current ZeroVis implementation.

Conclusions and Future Work

In this paper we showed how combining CP-ABE with encrypted data searching solves the problem of storing and retrieving confidential data from an untrusted environment, while giving the data provider control over who accesses her data. While other frameworks provide some of these capabilities, ours is the only one to our knowledge that accomplishes this without relying on traditional key management techniques. Our framework is the first to specifically address the need for one-to-many encryption in a database environment, which requires support for efficient queries across encrypted data.

This paper describes the initial ZeroVis framework implementation. Future framework changes are necessary to create a more production viable framework.A specific requirement for a trusted AA needs to be included. Although we only generally described the need for the AA,the AA will be an integral component of a completed framework. It will be responsible for authorizing users, securely storing their attributes, and providing the ZeroVis proxy with sufficient authentication information and attributes to properly handle encryption and decryption operations for authorized users. The AA will act as the layer of protection that stops attackers from arbitrarily providing unauthorized attributes to the CP-ABE encryption/decryption functions. The AA will also manage the master key required for encryption/decryption operations.

Additional work is necessary to reduce the storage and computational overhead of CP-ABE. Others have already studied this problem, including Constant-size CP-ABE (CP-ABE) [START_REF] Zhou | On efficient ciphertext-policy attribute based encryption and broadcast encryption: Extended abstract[END_REF] and techniques discussed in [START_REF] Kim | Efficient semi-static secure broadcast encryption scheme[END_REF] and [START_REF] Bethencourt | Ciphertext-policy attribute-based encryption[END_REF]. We will also explore normalizing the CP-ABE ciphertext,which is currently a concatenation of the access policy and the encrypted payload. The access policy comprises over 90% of the ciphertext size. Denormalizing the CP-ABE ciphertext will reduce the storage (and network transmission) requirements for multiple columns that share the same access policy.

Fig. 1 .

 1 Fig. 1. CP-ABE Access Tree)

Fig. 2 .

 2 Fig. 2. ZeroVisibility Cloud Framework.

Fig. 3 .

 3 Fig. 3. Submitting Data (INSERT)

Fig. 4 .

 4 Fig. 4. Retrieving Data (SELECT request)

Fig. 5 .

 5 Fig. 5. Retrieving Data (SELECT response)

Fig. 6 .

 6 Fig. 6. Resulting DB Sizes for test DBs (of logarithmically increasing row cardinality)

Fig. 7 .

 7 Fig. 7. Database load time

Fig. 8 .

 8 Fig. 8. Database Query time

Table 1 .

 1 Data Access Example: Research teams and contexts of interest

	Team Treatment Research Context	Description
	A	Z51.11	Cancer	Effectiveness of different treatment
	B	E66.09	Nutritional health	Impact of obesity on heart disease
	C	Z51.11	Tobacco use AND Heart	Impact of lifestyle and heart disease
			disease	on cancer treatment effectiveness
	D	Modified Diet Nutrition	Measurable benefits of various diets

Like flying an instrument approach with limited or no visibility -only pilots with proper equipment, clearance, and the current local frequencies can land.

Z51.11 is the ICD10 code for "Encounter for antineoplastic chemotherapy", which also corresponds to the ICD9 code V58.11.

* Research supported in part by NSF grant OCI-1124418 and AFOSR DDDAS grant FA9550-12-1-0240 ** Research supported in part by NSF grant CNS-1117763 and AFOSR DDDAS grant FA9550-12-1-0240