Efficient Oblivious Database Joins

Summary: Oblivious equi-join without ORAM, built from sorting networks; data-independent, provably secure. Time near O(n log n) for O(n) outputs, with a compact implementation, suitable for SGX and secure MPC, and robust against side channels. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12105
Venue: VLDB
Year: 2020
Pagerank: 9.256923e-05
Overall Rank: 2,089 | 85.49%
DOI: 10.14778/3407790.3407814

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,608	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	8.4205138e-05
2,663	Towards Practical Oblivious Join	2022	SIGMOD	8.3448927e-05
4,017	FedKNN: Secure Federated k-Nearest Neighbor Search	2024	SIGMOD	7.0241303e-05
6,495	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB	5.9185619e-05
7,973	Doquet: Differentially Oblivious Range and Join Queries with Private Data Structures	2023	VLDB	5.5696218e-05
8,617	Cryptographically Secure Private Record Linkage Using Locality-Sensitive Hashing	2024	VLDB	5.4598872e-05
9,245	OBIR-tree: An Efficient Oblivious Index for Spatial Keyword Queries on Secure Enclaves	2025	SIGMOD	5.3572577e-05
9,250	OasisDB: An Oblivious and Scalable System for Relational Data	2025	VLDB	5.3572577e-05
9,337	SODA: A Set of Fast Oblivious Algorithms in Distributed Secure Data Analytics	2023	VLDB	5.3449422e-05
9,638	Secure Sampling for Approximate Multi-party Query Processing	2023	SIGMOD	5.3018378e-05
10,231	Bifrost: A Much Simpler Secure Two-Party Data Join Protocol for Secure Data Analytics	2026	VLDB	5.1725247e-05
10,254	Secure Multi-Party Sampling over Joins	2026	VLDB	5.1725247e-05
10,283	Enabling Index-free Adjacency in Oblivious Graph Processing with Delayed Duplications	2026	VLDB	5.1725247e-05
10,305	Vodka: Rethink Benchmarking Philosophy in HTAP Systems	2026	VLDB	5.1725247e-05
10,553	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	5.1725247e-05
10,661	Alchemy: A Query Optimization Framework for Oblivious SQL	2025	VLDB	5.1725247e-05
10,873	Towards Practical Oblivious Map	2025	VLDB	5.1725247e-05
10,973	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	5.1725247e-05
11,239	Cracking-Like Join for Trusted Execution Environments	2023	VLDB	5.1725247e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,525	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.00010560316

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,545	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	7.3847662e-05
3,104	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB	7.821278e-05
3,639	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.304411e-05
5,442	Oblivious RAM: A Dissection and Experimental Evaluation	2016	VLDB	6.2858497e-05
355	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020433058
10,254	Secure Multi-Party Sampling over Joins	2026	VLDB	5.1725247e-05
11,239	Cracking-Like Join for Trusted Execution Environments	2023	VLDB	5.1725247e-05
10,873	Towards Practical Oblivious Map	2025	VLDB	5.1725247e-05
10,553	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	5.1725247e-05
2,663	Towards Practical Oblivious Join	2022	SIGMOD	8.3448927e-05