Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Privacy Preserving Joins

Yaping Li and Minghua Chen

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2007-137
November 22, 2007

http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-137.pdf

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.


BibTeX citation:

@techreport{Li:EECS-2007-137,
    Author = {Li, Yaping and Chen, Minghua},
    Title = {Privacy Preserving Joins},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2007},
    Month = {Nov},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-137.html},
    Number = {UCB/EECS-2007-137},
    Abstract = {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.}
}

EndNote citation:

%0 Report
%A Li, Yaping
%A Chen, Minghua
%T Privacy Preserving Joins
%I EECS Department, University of California, Berkeley
%D 2007
%8 November 22
%@ UCB/EECS-2007-137
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-137.html
%F Li:EECS-2007-137