OPE-encrypted columns to the server if users request order queries on those columns. OPE is proven to be equivalent to a random mapping that preserves order. 1 However, such a mapping leaks half of the data bits in the worst case. 2 We are currently working on a new scheme that provably reveals only order and leaks no bits in addition.

homomorphic encryption (hOM). HOM is as secure a probabilistic encryption scheme as RND, but allows the server to perform computations on encrypted data with the final result decrypted at the proxy. Although fully homomorphic encryption is prohibitively slow, homomorphic encryption for specific operations is efficient. To support additions, we implemented the Paillier cryptosystem. 17 With Paillier, multiplying the encryptions of two values results in an encryption of the sum of the values, that is, HOMK (x) · HOMK ( y) = HOMK (x + y), where the multiplication is performed modulo some public-key value. To compute SUM aggregates, the proxy replaces SUM with calls to a UDF that performs Paillier multiplication on a column encrypted with HOM. HOM can also be used to compute averages by having the DBMS server return the sum and the count separately, and to increment values (e.g., SET id = id + 1). HOM ciphertexts are 2048 bits long.

Join ( JOiN and OPe-JOiN). A separate encryption scheme is needed to allow equality join between two columns, because we use different column-specific keys for DET to prevent correlations between columns. JOIN not only supports all the operations allowed by DET, but also enables the server to determine repeating values between two different columns. OPE-JOIN enables joins by order relations. We provide a new cryptographic scheme for JOIN (Section 3. 4).

need an adaptive scheme that dynamically adjusts encryption strategies.

CryptDB’s adjustable query-based encryption technique solves this problem by dynamically adjusting the layer of encryption on the DBMS server. The idea is to encrypt each data item in one or more onions: that is, each value is dressed in layers of increasingly stronger encryption, as shown in Figures 2 and 3. Each layer of each onion enables a certain class of computation, as explained earlier.

Multiple onions are required because the computations supported by different encryption schemes are not always strictly ordered. Depending on the type of the data, CryptDB may not maintain all onions for each column. For instance, the Search onion does not make sense for integers, and the Add onion does not make sense for strings.

For each layer of each onion, the proxy uses the same key for encrypting values in the same column, and different keys across tables, columns, onions, and onion layers. Using the same key for all values in a column allows the proxy to perform operations on a column without having to compute separate keys for each row that will be manipulated. Using different keys across columns prevents the server from learning any additional relations. All of these keys are derived from the master key MK. For example, for table t, column c, onion o, and encryption layer l, the proxy uses the key

Kt,c,o,l = PRPMK (table t, column c, onion o, layer l ), ( 1)

where PRP is a pseudorandom permutation (e.g., AES).

Each onion starts out with the most secure encryption scheme as the top level (RND for onions Eq and Ord, HOM for onion Add, and SEARCH for onion Search). As the proxy receives SQL queries from the application, it determines whether layers of encryption need to be removed. If a query requires predicate P on column c, the proxy first establishes what onion layers are needed to compute P on c. If the encryption of c is not already at an onion layer that allows P, the proxy strips off the onion layers to allow P on c, by sending the corresponding onion key to the server. The proxy never decrypts the data past the least-secure non-plaintext encryption onion layer, which may be overridden by the schema developer to be a more secure layer (e.g., one may

Word search (SearCh). SEARCH is used to perform searches on encrypted text to support operations such as MySQL’s LIKE operator. SEARCH is nearly as secure as RND. We implemented the method of Song et al. 22 SEARCH currently supports only full word searches.

When the user performs a query such as SELECT FROM messages WHERE msg LIKE “% alice %”,the proxy gives the DBMS server a token, which is an encryption of alice. The server cannot decrypt the token to figure out the underlying word. Using a user-defined function, the DBMS server checks if any of the word encryptions in any message match the token. All that the server learns from a SEARCH query is whether the token matched a message or not, and only for the tokens requested by the user. The server would learn the same information when returning the result set to the users, so the scheme reveals the minimal amount of additional information needed to return the result.

Figure 2. onion encryption layers and the classes of computation they allow. onion names stand for the operations they allow at some of their layers (equality, order, Search, and addition). a random iV for RnD (Section 3. 1), shared by the RnD layers in Eq and Ord, is also stored for each data item.

3. 2. adjustable query-based encryption Our goal is to use the most secure encryption schemes that enable running the requested queries. For example, if the application issues no queries that compare data items in a column, or that sort a column, the column should be encrypted with RND. For columns that require equality checks but not order checks, DET suffices. The problem is that the query set is not always known in advance. Thus, we

any value
DET: equality selection
RND: no functionality
JOIN: equality join
OPE-JOIN:
range join
OPE: order
any value
RND: no functionality
SEARCH
text value

Onion Search

int value HOM: add

Onion Eq
Onion Ord
Onion Add