Efficient Oblivious Database Joins

Summary: Oblivious equi-joins achieve near-optimal O(n log n) complexity without ORAM, using sorting networks and provably data-independent constructions. A compact implementation delivers practical performance and resilience across SGX, MPC, and other remote-execution settings. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hc3e6058cb66d57cc
Venue: VLDB
Year: 2020
Pagerank: 9.0841817e-05
Overall Rank: 2,074 | 86.06%
DOI: 10.14778/3407790.3407814

Incoming Non-self Citations Over Time

Authors

1. Simeon Krastnikov (University of Waterloo)
2. Florian Kerschbaum (University of Waterloo)
3. Douglas Stebila (University of Waterloo)

BibTeX Citation

@article{krastnikov_vldb20,
        title = {{Efficient Oblivious Database Joins}},
        author = {Krastnikov, Simeon and Kerschbaum, Florian and Stebila, Douglas},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {11},
        pages = {2132--2145},
        doi = {10.14778/3407790.3407814},
        url = {https://doi.org/10.14778/3407790.3407814},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,455	Towards Practical Oblivious Join	2022	SIGMOD	8.4390594e-05
2,582	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	8.2594787e-05
3,306	FedKNN: Secure Federated k-Nearest Neighbor Search	2024	SIGMOD	7.4422756e-05
6,128	Cryptographically Secure Private Record Linkage Using Locality-Sensitive Hashing	2024	VLDB	5.8783975e-05
6,731	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB	5.6939772e-05
7,482	OBIR-tree: An Efficient Oblivious Index for Spatial Keyword Queries on Secure Enclaves	2025	SIGMOD	5.5128501e-05
7,558	Doquet: Differentially Oblivious Range and Join Queries with Private Data Structures	2023	VLDB	5.4964611e-05
9,569	OasisDB: An Oblivious and Scalable System for Relational Data	2025	VLDB	5.1571823e-05
9,657	SODA: A Set of Fast Oblivious Algorithms in Distributed Secure Data Analytics	2023	VLDB	5.1453267e-05
9,966	Secure Sampling for Approximate Multi-party Query Processing	2023	SIGMOD	5.1038322e-05
10,437	Differentially Oblivious Multi-way Join	2026	SIGMOD	4.9793485e-05
10,704	Bifrost: A Much Simpler Secure Two-Party Data Join Protocol for Secure Data Analytics	2026	VLDB	4.9793485e-05
10,724	Secure Multi-Party Sampling over Joins	2026	VLDB	4.9793485e-05
10,752	Enabling Index-free Adjacency in Oblivious Graph Processing with Delayed Duplications	2026	VLDB	4.9793485e-05
11,015	Vodka: Rethink Benchmarking Philosophy in HTAP Systems	2026	VLDB	4.9793485e-05
11,225	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	4.9793485e-05
11,301	Alchemy: A Query Optimization Framework for Oblivious SQL	2025	VLDB	4.9793485e-05
11,444	Towards Practical Oblivious Map	2025	VLDB	4.9793485e-05
11,526	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.9793485e-05
11,750	Cracking-Like Join for Trusted Execution Environments	2023	VLDB	4.9793485e-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,495	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.00010484897

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,660	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
2	5,579	Oblivious RAM: A Dissection and Experimental Evaluation	2016	VLDB
3	361	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD
4	10,724	Secure Multi-Party Sampling over Joins	2026	VLDB
5	11,750	Cracking-Like Join for Trusted Execution Environments	2023	VLDB
6	10,754	Secure Join Operations in Multi-Identifier Databases: Performance and Practicality	2026	VLDB
7	11,444	Towards Practical Oblivious Map	2025	VLDB
8	11,225	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB
9	10,437	Differentially Oblivious Multi-way Join	2026	SIGMOD
10	2,455	Towards Practical Oblivious Join	2022	SIGMOD