Secure Join Operations in Multi-Identifier Databases: Performance and Practicality
Proceedings of the VLDB Endowment · 01.05.2026 · 19 (9) · 1854-1866
DOI: 10.14778/3819518.3819519 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 19.08.2026. Verfasst von Wen-jie Lu und 6 weiteren Autor:innen. Die Arbeit nennt 43 Literaturangaben.
Abstract (Originalsprache)
In this work, we present an efficient and cryptographically secure protocol for multi-key inner-join computation that addresses the limitations of existing approaches. Our protocol leverages established Circuit Private Set Intersection (PSI) techniques to privately compute left-joins over individual key columns. These results are then securely aggregated into a final inner-join table using a novel private permutation protocol, which achieves a speedup of approximately 2× to 4× over prior methods. To enhance utility without compromising privacy, we introduce a deduplication mechanism based on ordered left-joins, enabling first-key deduplication while revealing no sensitive matching information. We formally analyze the security of our construction in the semi-honest model. Furthermore, we optimize the equality testing subroutine, a core component of Circuit PSI, reducing its round complexity without an increase in computational overhead. Empirically, our system demonstrates strong scalability, processing up to 1.8 × 10 4 records of 4 keys per second per CPU core. This represents a significant improvement over industry solutions such as Google's and Meta's, which are not only slower but also reveal more information about the input databases.
Zitieren
APA
Lu, W., Niu, Y., Zhao, Y., Dai, W., Lu, D., Wang, L., & Yan, Q. (2026). Secure Join Operations in Multi-Identifier Databases: Performance and Practicality. Proceedings of the VLDB Endowment, 19(9), 1854-1866. https://doi.org/10.14778/3819518.3819519
Vancouver
Lu W, Niu Y, Zhao Y, Dai W, Lu D, Wang L, et al. Secure Join Operations in Multi-Identifier Databases: Performance and Practicality. Proceedings of the VLDB Endowment. 2026;19(9):1854-1866. doi:10.14778/3819518.3819519
BibTeX
@article{Lu2026,
author = {Lu, Wen-jie and Niu, Yongchuan and Zhao, Yongjun and Dai, Wei and Lu, Donghang and Wang, Li and Yan, Qiang},
title = {Secure Join Operations in Multi-Identifier Databases: Performance and Practicality},
journal = {Proceedings of the VLDB Endowment},
year = {2026},
volume = {19},
number = {9},
pages = {1854--1866},
doi = {10.14778/3819518.3819519}
}
EUVIMED