The field of privacy preserving joins (PPJ) considers the question of how mutually distrustful entities share data in a privacy preserving way such that no party learns more than what can be deduced from its input and output alone. In my thesis, I focus on general join operations involving arbitrary predicates. Previous researchers have considered solutions using a trusted third party (TTP) and general secure multi-party computation. The former requires a high level of trust in the TTP by all entities. The latter is a well-known theoretical result of computing general joins in a privacy preserving way. However, the computation and communication complexity is normally too high for this approach to be practical.

In my thesis, I explore solutions that strike a balance between the level of required trust and performance. I propose solutions to compute privacy preserving joins efficiently through a trusted third party with secure coprocessors being the only trusted component. I present a rigorous definition of privacy preserving joins under this setting, propose privacy preserving join algorithms and prove their correctness and security. I give explicit expressions for their computation costs, evaluate their performance, and show that the performance is superior than that of secure multi-party computation.




Download Full History