Towards Practical Oblivious Join

Zhao Chang, Dong Xie, Sheng Wang, Feifei Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Many individuals and companies choose the public cloud as their data and IT infrastructure platform. But remote accesses over the data inevitably bring the issue of trust. Despite strong encryption schemes, adversaries can still learn sensitive information from encrypted data by observing data access patterns. Oblivious RAMs (ORAMs) are proposed to protect against access pattern attacks. However, directly deploying ORAM constructions in an encrypted database brings large computational overhead. In this work, we focus on oblivious joins over a cloud database. Existing studies in the literature are restricted to either primary-foreign key joins or binary equi-joins. Our major contribution is to support general binary and multiway equi-joins. We integrate B-tree indices into ORAMs for each input table and retrieve blocks through the indices in join processing. The key points are to address the security issue (i.e., leaking the number of accesses to any index) in the extended existing solutions and bound the total number of block accesses. Our index nested-loop join algorithm can also support some types of band joins obliviously. The effectiveness and efficiency of our algorithms are demonstrated through extensive evaluations over real-world datasets. Our method shows orders of magnitude speedup for oblivious multiway equi-joins in comparison with baseline algorithms.

Original languageEnglish (US)
Title of host publicationSIGMOD 2022 - Proceedings of the 2022 International Conference on Management of Data
PublisherAssociation for Computing Machinery
Number of pages15
ISBN (Electronic)9781450392495
StatePublished - Jun 10 2022
Event2022 ACM SIGMOD International Conference on the Management of Data, SIGMOD 2022 - Virtual, Online, United States
Duration: Jun 12 2022Jun 17 2022

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078


Conference2022 ACM SIGMOD International Conference on the Management of Data, SIGMOD 2022
Country/TerritoryUnited States
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems


Dive into the research topics of 'Towards Practical Oblivious Join'. Together they form a unique fingerprint.

Cite this