Differentially Oblivious Multi-way Join
Open Access
- 18 May 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (3) , 1-26
Abstract
Processing joins in encrypted database systems presents a fundamental trade-off between privacy and efficiency. Fully oblivious algorithms can offer perfect access-pattern privacy but incur prohibitive costs by padding the execution to the worst-case output size. This limitation can be further enlarged on multi-way joins, where the worst-case output size can be exponentially large in terms of the database size. To overcome this barrier, differentially oblivious (DO) algorithms are introduced to enable instance-specific efficiency by sacrificing the perfect access-pattern privacy. While promising for two-way joins, extending this paradigm to multi-way joins has remained a significant open challenge. In this paper, we establish that designing efficient DO multi-way join algorithms is fundamentally equivalent to the problem of releasing join size differentially privately, but under new constraints imposed by an oblivious execution model. To solve this, we introduce relaxed-residual sensitivity, a novel sensitivity measure for counting the join size that is both differentially private and efficiently computable within an oblivious context. Based on this measure, we develop a principled DO padding mechanism that minimizes overhead while rigorously satisfying privacy. Our DO multi-way join algorithms achieve a polynomial speedup over their fully oblivious counterparts and come with a theoretical optimality guarantee for a large class of join queries. We have implemented our algorithms, and empirical evaluations confirm their substantial performance advantages, making differentially oblivious multi-way joins closer to a practical solution for secure query processing.Keywords
This publication has 40 references indexed in Scilit:
- Towards Practical Oblivious Join ProcessingIEEE Transactions on Knowledge and Data Engineering, 2023
- A Theory of Composition for Differential Obliviousness2023
- Spreading the Privacy Blanket:2022
- Scape: Scalable Collaborative Analytics System on Private Database with Malicious Security2022
- Path Oblivious Heap: Optimal and Practical Oblivious Priority Queue2020
- Oblix: An Efficient Oblivious Search Index2018
- On Acyclic Conjunctive Queries and Constant Delay Enumeration2007
- Smooth sensitivity and sampling in private data analysis2007
- Software protection and simulation on oblivious RAMsJournal of the ACM, 1996
- Answering queries using templates with binding patterns (extended abstract)1995