Please note: This master’s thesis presentation will take place in DC 2314.
Nafis Ahmed, Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Sujaya Maiyya
We present parallel doubly oblivious algorithms for both non-foreign key and foreign key joins using an oblivious radix partitioning technique. Oblivious query processing enables secure execution over encrypted data when organizations outsource data to the cloud. When the cloud server processes encrypted data within hardware enclaves, the data is vulnerable to side-channel leaks caused by data-dependent memory access patterns and control flow. Our algorithms efficiently defend against these vulnerabilities by combining data partitioning with parallel execution. Specifically, we propose a doubly oblivious radix partitioning approach that divides input arrays into disjoint partitions without leaking information about duplicate elements, unlike vanilla radix partitioning, which reveals duplicate counts. This is especially important for join operations, where duplicate keys are common.
To construct our join algorithm, we apply oblivious radix partitioning independently to each input table, allowing the algorithm to compare tuples only within corresponding partitions. When input tables are presorted, our oblivious join algorithm is the first to avoid resorting them, yielding significant speed-ups over the state-of-the-art schemes. Beyond joins, our oblivious radix partitioning technique is a standalone primitive with applications to a broad class of problems, including oblivious group-by and aggregation, private set intersection and union, and private contact discovery.