2026-07-21T14:19:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22966 2025-10-02T12:19:48Z ddc:004 open_access

Optimal Oblivious Algorithms for Multi-Way Joins Hu, Xiao Wu, Zhiang oblivious algorithms multi-way joins worst-case optimality In cloud databases, cloud computation over sensitive data uploaded by clients inevitably causes concern about data security and privacy. Even if cryptographic primitives and trusted computing environments are integrated into query processing to safeguard the actual contents of the data, access patterns of algorithms can still leak private information about data. Oblivious RAM (ORAM) and circuits are two generic approaches to address this issue, ensuring that access patterns of algorithms remain oblivious to the data. However, deploying these methods on insecure algorithms, particularly for multi-way join processing, is computationally expensive and inherently challenging. In this paper, we propose a novel sorting-based algorithm for multi-way join processing that operates without relying on ORAM simulations or other security assumptions. Our algorithm is a non-trivial, provably oblivious composition of basic primitives, with time complexity matching the insecure worst-case optimal join algorithm, up to a logarithmic factor. Furthermore, it is cache-agnostic, with cache complexity matching the insecure lower bound, also up to a logarithmic factor. This clean and straightforward approach has the potential to be extended to other security settings and implemented in practical database systems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiao Hu and Zhiang Wu 2025 Is Part Of LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2025.25 urn:nbn:de:0030-drops-229662 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.25 eng https://creativecommons.org/licenses/by/4.0/legalcode