Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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