Cryptology ePrint Archive: Report 2021/917

CODBS: A cascading oblivious search protocol optimized for real-world relational database indexes

Rogério Pontes and Bernardo Portela and Manuel Barbosa and Ricardo Vilaça

Abstract: Encrypted databases systems and searchable encryption schemes still leak critical information (e.g.: access patterns) and require a choice between privacy and efficiency. We show that using ORAM schemes as a black-box is not a panacea and that optimizations are still possible by improving the data structures. We design an ORAM-based secure database that is built from the ground up: we replicate the typical data structure of a database system using different optimized ORAM constructions and derive a new solution for oblivious searches on databases. Our construction has a lower bandwidth overhead than state-of-the-art ORAM constructions by moving client-side computations to a proxy with an intermediate (rigorously defined) level of trust, instantiated as a server-side isolated execution environment. We formally prove the security of our construction and show that its access patterns depend only on public information. We also provide an implementation compatible with SQL databases (PostgresSQL). Our system is 1.2 times to 4 times faster than state-of-the-art ORAM-based solutions.

Category / Keywords: applications / Databases, Cryptographic Databases, ORAM, Indexes, Performance, Encrypted Databases

Date: received 6 Jul 2021

Contact author: rogerio pontes at pm me, blfportela at gmail com, mbb at fc up pt, rmvilaca at di uminho pt

Available format(s): PDF | BibTeX Citation

Version: 20210708:135845 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]