Yaping Li

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2008-158

December 14, 2008

http://www2.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.

Advisors: 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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-158.html
%F Li:EECS-2008-158