Network Security & Privacy
- Secure Multi-Party Computation of Boolean Circuits
with Applications to Privacy in On-Line Marketplaces
Protocols for generic secure multi-party computation (MPC)
come in two forms: they either represent the function being
computed as a boolean circuit, or as an arithmetic circuit
over a large field. Either type of protocol can be used for
any function, but the choice of which type of protocol to use
can have a significant impact on efficiency. The magnitude
of the effect, however, has never been quantified.
With this in mind, we implement the MPC protocol of
Goldreich, Micali, and Wigderson, which uses a boolean
representation and is secure against a semi-honest adver-
sary corrupting any number of parties. We then consider
applications of secure MPC in on-line marketplaces, where
customers select resources advertised by providers and it is
desired to ensure privacy to the extent possible. We observe
that problems here are most naturally formulated in terms
of boolean circuits, and we study the performance of our
MPC implementation relative to existing ones. We find that
our protocol easily handles tens of customers/providers and
thousands of resources, and outperforms existing implemen-
tations including FairplayMP, VIFF, and SEPIA.
- People
- Seung Geol Choi, Postdoc researcher, Computer Science Department, University of Maryland
- Kyung-Wook Hwang, Ph.D. student, Electrical Engineering Department, Columbia University
- Jonathan Katz, Professor, Computer Science Department, University of Maryland
- Tal Malkin, Professor, Computer Science Department, Columbia University
- Dan Rubenstein, Professor, Computer Science Department, Columbia University
- Source code
- Our GMW implementation for MPC (written in C++):
tar.gz, zip, README(PDF)
Last updated in May 2011