OBLIVIATOR: OBLIVIous Parallel Joins and other OperATORs in Shared Memory Environments

We introduce oblivious parallel operators designed for both non-foreign key and foreign key equi-joins. Obliviousness ensures nothing is revealed about the data besides input/output sizes, even against a strong adversary that can observe memory access patterns. Our solution achieves this by combining trusted hardware with efficient oblivious primitives for compaction and sorting, and two oblivious algorithms: (i) an oblivious aggregation tree, which can be described as a variation of the parallel prefix sum, customized for trusted hardware, and (ii) a novel algorithm for obliviously expanding the elements of a relation. In the sequential setting, our oblivious join performs 4.6x - 5.14x faster than the prior state-of-the-art solution (Krastnikov et al., VLDB 2020) on data sets of size n=2^24. In the parallel setting, our algorithm achieves a speedup of up to roughly 16x over the sequential version, when running with 32 threads (becoming up to 80x compared to the sequential algorithm of Krastnikov et al.). Finally, our oblivious operators can be used independently to support other oblivious relational database queries, such as oblivious selection and oblivious group-by.