This is a summary of the paper “Processing Analytical Queries over Encrypted Data” by Tu et al. (VLDB 2013). All the information is based on my understanding of the paper and may contain inaccuracies.
MONOMI is a system that allows analytical queries over encrypted data. It is based on CryptDB and focus on overcoming some of the latter’s limitations, especially the lack of support for analytical queries.
MONOMI introduces the Designer component, which receives a sample of the database workload and outputs the physical design of the database. At the time of the execution, a second component (Planner) is used to generate query plans and choose the best one using simple pruning heuristics.
The cryptographic schemes used by MONOMI are similar to the ones used in CryptDB and include randomized AES with CBC, deterministic AES with CMC or FFX, order-preserving encryption, Paillier and SEARCH.
The evaluation uses the TPC-H workload and reveals a performance overhead of 1.24 to 1.72 times compared to the unencrypted version of the DBMS. The storage overhead is about 1.72 times.
The execution of a query is split between the server and the client, so expressions that cannot be evaluated on the server (mainly those expressions would require decryption) are executed on the client.
The components Designer and Planner are helpful in setting up the database and when choosing the best query plan. Other than that, a number of optimization techniques are also proposed:
- Per-row computation: The system uses additional columns to store the result of expressions that cannot be computed over the encrypted data, thus allowing the server to use these precomputed values in queries.
- Space-efficient encryption: To minimize ciphertext expansion, MONOMI uses FFX mode. Ciphertext packing is also used with the Paillier encryption scheme.
- Grouped homomorphic addition: Allows computations of aggregated over columns packed into one Paillier plaintext.
- Conservative pre-filtering: Estimates a the result of a predicate, and reduces data transfer by filtering the encrypted data on the server.
Similarly to CryptDB, computations that require multiple steps (e.g., multiplication followed by a comparison) cannot be fully executed on the server because the different cryptosystems used for each of these operations are not compatible.
In addition, also similarly to CryptDB, MONOMI does not provide fine-grained (i.e., cell level) access control.
Finally, security constraints are not considered, but the authors claim that it would be simple to set minimum security thresholds during the setup of the system.
A simple presentation about MONOMI, based on my understanding, is available at SlideShare:
Although I have not tried to work with it in practice, the prototypes for the Designer and Planner modules were made available by the authors at GitHub.
I came across an interesting overview about encrypted databases and I believe it gives a good look at the bigger picture regarding systems like CryptDB and MONOMI.