Yaping Li and Minghua Chen

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-137

November 22, 2007

http://www2.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},
    Year= {2007},
    Month= {Nov},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-137.html
%F Li:EECS-2007-137