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
DET: equality selection
RND: no functionality
JOIN: equality join
RND: no functionality