Welcome to the resource topic for 2025/183
Title:
OBLIVIATOR: Oblivious Parallel Joins and other Operators in Shared Memory Environments
Authors: Apostolos Mavrogiannakis, Xian Wang, Ioannis Demertzis, Dimitrios Papadopoulos, Minos Garofalakis
Abstract: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.6\times- 5.14\times 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 16\times over the sequential version, when running with 32 threads (becoming up to 80\times 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.
ePrint: https://eprint.iacr.org/2025/183
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .