Abstract

End-to-end encrypted relational database management systems (EDBs) are the “holy grail” of database security and have been studied by the research community for the last 20 years. During this time, several systems have been proposed with a variety of limitations that include weak security, poor performance and restricted query expressiveness. We contend that this state of affairs is due, in part, to a lack of cohesion between the techniques and methodologies of the database and cryptography communities. We believe that the only way to make significant progress on this important problem is to properly leverage techniques and ideas from the two communities. Towards this end, we identify five key design principles for end-to-end encrypted relational databases. These principles include security, performance and expressiveness considerations. We describe a system called KafeDB; the first encrypted relational database system that meets these principles. KafeDB is based on a new database encryption scheme called OPX that supports a nontrivial subset of SQL queries. Our prototype, built on top of PostgreSQL, shows the feasibility of our approach. TPC-H shows our prototype is about one to three order of magnitude slower than optimized plaintext PostgreSQL and requires about one order of magnitude more storage while offering end-to-end security.