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

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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. Minor revision.
Keywords
DatabasesCryptographic DatabasesORAMIndexesPerformanceEncrypted Databases
Contact author(s)
rogerio pontes @ pm me
blfportela @ gmail com
mbb @ fc up pt
rmvilaca @ di uminho pt
History
2021-07-08: received
Short URL
https://ia.cr/2021/917
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/917,
      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{https://eprint.iacr.org/2021/917}},
      url = {https://eprint.iacr.org/2021/917}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.