This is the first post in a series on how to design end-to-end encrypted databases.

As we produce and consume increasing amounts of data, we are witnessing several conflicting trends. On one hand, these datasets are becoming increasingly privacy-sensitive and, on the other, they are becoming harder to secure. This is well-illustrated by the constant occurrence of data breaches. In 2017, we learned that the Yahoo! email breach affected 3 billion users. In 2016, the Democratic National Committee was hacked and Wikileaks published 19, 252 emails and 8, 034 attachments from the attack, affecting the outcome of the 2016 U.S. Presidential election. The frequency of data breaches points to the fact that the data we produce is not adequately secured. While systems sometimes encrypt data in transit and at rest, there are many stages in our data's lifetime where it remains unencrypted; especially when it is in use.

An alternative way of deploying cryptography is end-to-end encryption. In this approach, the data is encrypted by the user before it even leaves its device. Encrypted systems and services provide much stronger security and privacy guarantees than the current generation of systems. The main challenge in building such systems, however, is that end-to-end encryption breaks many of the applications and services we rely on, including cloud computing, analytics, spam filtering, databases and search.

Encrypted Search

This tension between encryption and computation has motivated cryptographers to develop ways to compute on encrypted data. In the context of search and database algorithms, these solutions are sometimes referred to as encrypted search algorithms (ESA). ESAs have been studied by the cryptography community for almost two decades. The problem of searching on encrypted data was first considered explicitly in a paper by Song, Wagner and Perrig [SWP00] (though previous work by Goldreich and Ostrovsky [GO96] could also be used to solve the problem). A few years later, Reza Curtmola, Juan Garay, Aroki Chief Scientist Seny Kamara and Rafail Ostrovsky proposed the first practical (and optimal) solution to this problem together with a framework to formally analyze the security of ESAs [CGKO06]. Since then, cryptographers have developed many new techniques to design and analyze ESAs each achieving various tradeoffs between security and performance in different adversarial models.

Encrypted Databases

One of the most important applications of ESAs is the design of encrypted databases (EDB); that is, database management systems (DBMS) that can operate on encrypted data. Roughly speaking, there are two kinds of databases: relational, which store data as tables and are queried using SQL; and non-relational (a.k.a. NoSQL), which do not store data as tables and are queried with low-level query operations. Relational DBMSs are the most widely used and are a 40 billion dollar industry which includes products from software giants like Oracle, IBM, and Microsoft.

Encrypting a DBMS is one of the "holy-grails" of database security. The first attempts to do this [HILM02] relied on a quantization-based approach which leaked too much information to be considered secure. In [PRZB11], a different approach was proposed based on deterministic encryption and order-revealing encryption [AKSX04,BBO07,BCLO09]. This was implemented in a system called CryptDB that could support a non-trivial subset of SQL. Deterministic and order-revealing encryption are examples of property-preserving encryption (PPE) schemes which means they are designed to reveal specific properties of their plaintext in order to facilitate certain computations. PPE-based encrypted databases have the advantage of being legacy-friendly and of providing good performance. As a result, this approach was quickly adopted by some academic systems like Cipherbase [ABE13] and commercial systems like SEEED and Microsoft's SQL Server Always Encrypted [MAE].

Unfortunately, PPE-based EDBs were never formally analyzed (e.g., using standard methods from cryptography) or subjected to any cryptanalytic evaluation prior to their adoption. As a result, in 2015, Muhammad Naveed, Aroki Chief Scientist Seny Kamara and Charles Wright showed that PPE-based EDBs suffered from significant information leakage and could be attacked in practice with very high success rates in the weakest possible adversarial model [NKW15]. In the setting of electronic medical records, for example, sensitive attributes of up to 99% of patients could be recovered with a snapshot attack (i.e., without even seeing any queries).

A New Generation of EDBs

Given the high level of interest in encrypted database technology from academia, industry and government (e.g., IARPA funded a large program in 2011) and the inherent weaknesses of quantization- and PPE-based solutions, the design of practical and secure encrypted databases remains an important open problem.

We at Aroki believe we have solved the key challenges impeding the development and deployment of encrypted databases. Practical and secure EDBs will have a significant impact on security and privacy in healthcare, cloud computing, mobile devices, voting systems, surveillance, blockchains and a host of other areas.

Aroki's technologies demonstrate the feasibility of encrypted database systems whose security is rigorously analyzed by the cryptography community and whose performance is competitive with commercial plaintext database systems like MongoDB, Dynamo, PostgreSQL, SQL Server, and Oracle.

Conclusion

In the next part of this series, we will discuss the different kinds of adversarial models to consider when designing an encrypted database.

How to Encrypt a Database: Introduction (Part 1)

Recent Posts

How to Encrypt a Database: Adversarial Models (Part 2)

The End of Ransomware

Hardware vs. Software for Secure Databases