Paper 2021/917

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

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


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.

Available format(s)
Publication info
Preprint. MINOR revision.
DatabasesCryptographic DatabasesORAMIndexesPerformanceEncrypted Databases
Contact author(s)
rogerio pontes @ pm me
blfportela @ gmail com
mbb @ fc up pt
rmvilaca @ di uminho pt
2021-07-08: received
Short URL
Creative Commons Attribution


      author = {Rogério Pontes and Bernardo Portela and Manuel Barbosa and Ricardo Vilaça},
      title = {CODBS: A cascading oblivious search protocol optimized for real-world relational database indexes},
      howpublished = {Cryptology ePrint Archive, Paper 2021/917},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.