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 computationSimulation-based securitySet-intersectionSet-unionOblivious 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.