Please note: This master’s thesis presentation will take place in DC 3317.
Ruidi Wei, Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Florian Kerschbaum
This thesis introduces the first efficient oblivious algorithm for acyclic multi-way joins with band conditions, extending the classical Yannakakis algorithm to support inequality predicates $(>, <, \geq, \leq)$ without leaking sensitive information through memory access patterns. Band joins, which match tuples over value ranges rather than exact keys, are widely used in temporal, spatial, and proximity-based analytics but present unique challenges in oblivious computation.
Our approach employs a novel dual-entry technique that transforms range matching into cumulative sum computations, enabling multiplicity computation in an oblivious manner. The algorithm achieves $\ourcomplexity$ complexity, where $\numtables$ is the number of tables, matching state-of-the-art oblivious equality joins up to a factor of $\numtables$ while supporting full band constraints. We implement the method using Intel SGX with batch processing and evaluate it on the TPC-H benchmark dataset, demonstrating practical performance and strong obliviousness guarantees under an honest-but-curious adversary model.