Paper 2017/1238

Efficient Oblivious Data Structures for Database Services on the Cloud

Thang Hoang, Ceyhun D. Ozkaptan, Gabriel Hackebeil, and Attila A. Yavuz


Database-as-a-service (DBaaS) allows the client to store and manage structured data on the cloud remotely. Despite its merits, DBaaS also brings significant privacy issues. Existing encryption techniques (e.g., SQL-aware encryption) can mitigate privacy concerns, but they still leak information through access patterns, which are vulnerable to statistical inference attacks. Oblivious Random Access Machine (ORAM) can seal such leakages; however, the recent studies showed significant challenges on the integration of ORAM into databases. That is, the direct usage of ORAM on databases is not only costly but also permits very limited query functionalities. In this paper, we propose new oblivious data structures called Oblivious Matrix Structure (OMAT) and Oblivious Tree Structure (OTREE), which allow tree-based ORAM to be integrated into database systems in a more efficient manner with diverse query functionalities supported. OMAT provides special ORAM packaging strategies for table structures, which not only offers a significantly better performance but also enables a broad range of query types that may not be efficient in existing frameworks. On the other hand, OTREE allows oblivious conditional queries to be performed on tree-indexed databases more efficiently than existing techniques. We implemented our proposed techniques and evaluated their performance on a real cloud database with various metrics, compared with state-of-the-art counterparts.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. IEEE Transactions on Cloud Computing
Privacy-enhancing TechnologiesOblivious Data StructureORAM
Contact author(s)
hoangmin @ oregonstate edu
2018-12-05: last of 2 revisions
2017-12-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thang Hoang and Ceyhun D.  Ozkaptan and Gabriel Hackebeil and Attila A.  Yavuz},
      title = {Efficient Oblivious Data Structures for Database Services on the Cloud},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1238},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.