Towards Practical Oblivious Join

Many companies choose the cloud as their data and IT infrastructure platform. However, the remote access brings security and privacy issues in public cloud. Although encryption is necessary to ensure the data security and privacy, adversaries can still learn sensitive information by observing data access patterns. ORAM is proposed to protect against access pattern attacks. However, directly deploying ORAMs in an encrypted database brings large computational overhead. In this work, we focus on oblivious join processing. Existing studies are restricted to either 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. We ensure the obliviousness in join processing and also bound the total number of tuple retrievals. The experimental evaluation shows the effectiveness and efficiency of our algorithms over real-world datasets.