In this paper, we design a system to perform privacy preserving joins of data from mutually distrustful organizations, leveraging the power of a secure coprocessor. The only trusted component is the secure coprocessor.

Under this setting, we critique a questionable assumption in a previous privacy definition that leads to unnecessary information leakage. We then remove the assumption and propose a new justifiable definition. Based on this new definition, we propose three provable correct and secure algorithms to compute general joins of arbitrary predicates. Our solutions overcome the challenge of the limited memory capacity of a secure coprocessor, by utilizing available cryptographic tools in a nontrivial way. We discuss different memory requirements of our proposed algorithms, and explore how to trade little privacy with significant performance improvement. We evaluate the performance of our algorithms by numerical examples and show the performance superiority of our approach over that of the secure multi-party computation.




Download Full History