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: 12292
Venue: VLDB
Year: 2020
Pagerank: 9.2632279e-05
Overall Rank: 2,045 | 85.98%
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,417	Towards Practical Oblivious Join	2022	SIGMOD	8.6061949e-05
2,573	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	8.4015654e-05
3,906	FedKNN: Secure Federated k-Nearest Neighbor Search	2024	SIGMOD	7.0287643e-05
6,601	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB	5.8246671e-05
7,337	OBIR-tree: An Efficient Oblivious Index for Spatial Keyword Queries on Secure Enclaves	2025	SIGMOD	5.6393827e-05
7,420	Doquet: Differentially Oblivious Range and Join Queries with Private Data Structures	2023	VLDB	5.6226175e-05
8,732	Cryptographically Secure Private Record Linkage Using Locality-Sensitive Hashing	2024	VLDB	5.3766157e-05
9,384	OasisDB: An Oblivious and Scalable System for Relational Data	2025	VLDB	5.2755515e-05
9,476	SODA: A Set of Fast Oblivious Algorithms in Distributed Secure Data Analytics	2023	VLDB	5.2634238e-05
9,785	Secure Sampling for Approximate Multi-party Query Processing	2023	SIGMOD	5.2209769e-05
10,221	Differentially Oblivious Multi-way Join	2026	SIGMOD	5.093636e-05
10,519	Bifrost: A Much Simpler Secure Two-Party Data Join Protocol for Secure Data Analytics	2026	VLDB	5.093636e-05
10,542	Secure Multi-Party Sampling over Joins	2026	VLDB	5.093636e-05
10,570	Enabling Index-free Adjacency in Oblivious Graph Processing with Delayed Duplications	2026	VLDB	5.093636e-05
10,591	Vodka: Rethink Benchmarking Philosophy in HTAP Systems	2026	VLDB	5.093636e-05
10,816	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	5.093636e-05
10,905	Alchemy: A Query Optimization Framework for Oblivious SQL	2025	VLDB	5.093636e-05
11,092	Towards Practical Oblivious Map	2025	VLDB	5.093636e-05
11,183	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	5.093636e-05
11,437	Cracking-Like Join for Trusted Execution Environments	2023	VLDB	5.093636e-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,459	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.00010717725

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,134	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB
2	3,617	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
3	5,444	Oblivious RAM: A Dissection and Experimental Evaluation	2016	VLDB
4	360	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD
5	10,542	Secure Multi-Party Sampling over Joins	2026	VLDB
6	11,437	Cracking-Like Join for Trusted Execution Environments	2023	VLDB
7	11,092	Towards Practical Oblivious Map	2025	VLDB
8	10,816	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB
9	10,221	Differentially Oblivious Multi-way Join	2026	SIGMOD
10	2,417	Towards Practical Oblivious Join	2022	SIGMOD