International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient Set Operations in the Presence of Malicious Adversaries

Authors:
Carmit Hazay
Kobbi Nissim
Download:
DOI: 10.1007/s00145-011-9098-x
Search ePrint
Search Google
Abstract: We revisit the problem of constructing efficient secure two-party protocols for the problems of set intersection and set union, focusing on the model of malicious parties. Our main results are constant-round protocols that exhibit linear communication and a (practically) linear number of exponentiations with simulation-based security. At the heart of these constructions is a technique based on a combination of a perfectly hiding commitment and an oblivious pseudorandom function evaluation protocol. Our protocols readily transform into protocols that are UC secure, and we discuss how to perform these transformations.
BibTeX
@article{jofc-2012-29491,
  title={Efficient Set Operations in the Presence of Malicious Adversaries},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={25},
  pages={383-433},
  doi={10.1007/s00145-011-9098-x},
  author={Carmit Hazay and Kobbi Nissim},
  year=2012
}