Efficient Set Operations in the Presence of Malicious Adversaries

Carmit Hazay; Kobbi Nissim

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2009/594

Efficient Set Operations in the Presence of Malicious Adversaries

Carmit Hazay and Kobbi Nissim

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. In 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.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: Secure two-party computation Simulation-based security Set-intersection Set-union Oblivious pseudorandom function evaluation
Contact author(s): carmit hazay @ weizmann ac il
kobbi @ cs bgu ac il
History: 2010-05-04: last of 2 revisions; 2009-12-04: received; See all versions
Short URL: https://ia.cr/2009/594
License: CC BY

BibTeX

@misc{cryptoeprint:2009/594,
      author = {Carmit Hazay and Kobbi Nissim},
      title = {Efficient Set Operations in the Presence of Malicious Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2009/594},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/594}},
      url = {https://eprint.iacr.org/2009/594}
}