Privacy Preserving Joins on Secure Coprocessors

Yaping Li

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2008-158
December 14, 2008

http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-158.pdf

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.

Advisor: Doug Tygar


BibTeX citation:

@phdthesis{Li:EECS-2008-158,
    Author = {Li, Yaping},
    Title = {Privacy Preserving Joins on Secure Coprocessors},
    School = {EECS Department, University of California, Berkeley},
    Year = {2008},
    Month = {Dec},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-158.html},
    Number = {UCB/EECS-2008-158},
    Abstract = {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.}
}

EndNote citation:

%0 Thesis
%A Li, Yaping
%T Privacy Preserving Joins on Secure Coprocessors
%I EECS Department, University of California, Berkeley
%D 2008
%8 December 14
%@ UCB/EECS-2008-158
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-158.html
%F Li:EECS-2008-158