Differentially Oblivious Multi-way Join

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.