Figure 3. examples of (a) how CryptDB transforms a table’s schema and encrypts a database, and of (b) a query flow showing onion
adjustments. Strings of the form “x…” denote ciphertexts (not shown to their full length).
Outer onion layers are
( 2) Need for
but it is at : adjust!
( 6) results:
( 3) removing onion layer
( 5) results:
specify that credit card information may at worst be at DET,
and never at OPE).
CryptDB implements onion layer decryption using UDFs
that run on the DBMS server. For example, in Figure 3, to
decrypt onion Ord of column 2 in Table 1 to layer OPE, the
proxy issues the following query to the server, invoking the
UPDATE Table1 SET
C2-Ord = DECRYPT_RND(K, C2-Ord, C2-IV,)
where K is the appropriate key computed from Equation ( 1).
At the same time, the proxy updates its own internal state to
remember that column C2-Ord in Table1 is now at layer OPE
in the DBMS.
Note that onion decryption is performed entirely by the
DBMS server. In the steady state, no server-side decryptions are needed, because onion decryption happens only
when a new class of computation is requested on a column. For example, after an equality check is requested on
a column and the server brings the column to layer DET,
the column remains in that state, and future queries with
equality checks require no decryption. This property is the
main reason why CryptDB’s run-time overhead is modest
3. 3. executing over encrypted data
Once the onion layers in the DBMS are at the layer necessary
to execute a query, the proxy transforms the query to operate
on these onions. In particular, the proxy replaces column
names in a query with corresponding onion names, based
on the class of computation performed on that column.
For example, for the schema shown in Figure 3, a reference
to the Name column for an equality comparison will be
replaced with a reference to the C2-Eq column.
The proxy also replaces each constant in the query with
a corresponding onion encryption of that constant, based
on the computation in which it is used. For instance, if a
query contains WHERE Name =“Alice”, the proxy encrypts
“Alice” by successively applying all encryption layers corre-
sponding to onion Eq that have not yet been removed
read query execution. To understand query execution over
ciphertexts, consider the example schema shown in Figure 3(a).
Initially, each column in the table is dressed in all onions
of encryption, with RND, HOM, and SEARCH as outermost
layers, as shown in Figure 2. At this point, the fields are protected with strong encryption schemes. Figure 3(b) then
shows an example of processing an equality predicate on the
encrypted data. This query (step 1) requires a lower onion
layer for execution than the one present in the DBMS, so
the proxy removes this layer at the server using the UPDATE
query in ( 2) by invoking the decryption UDF. Column C1
corresponds to ID, and xe243 is the Eq onion encryption
of “ 23” with keys KT1,C1,Eq,JOIN and KT1,C1,Eq,DET (see Figure 2).
After the DB server processes the adjustment in ( 3), the
proxy issues the transformed select query ( 4), and receives
encrypted results ( 5). Note that the proxy must request the
random IV from column C2-IV in order to decrypt the
RND ciphertext from C2-Eq. Finally, the proxy decrypts the
results from the server using keys KT1,C2,Eq,RND, KT1,C2,Eq,DET, and
KT1,C2,Eq,JOIN, obtains the result “Alice,” and returns it to the
application ( 6).
Write query execution. CryptDB supports INSERT, DELETE,
and UPDATE queries in a similar way to SELECT. An UPDATE
of a column value based on an existing column value, such as
salary = salary + 1, is more involved. 18