Cryptology ePrint Archive: Report 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.

Category / Keywords: Secure two-party computation, Simulation-based security, Set-intersection, Set-union, Oblivious pseudorandom function evaluation

Date: received 2 Dec 2009, last revised 4 May 2010

Contact author: carmit hazay at weizmann ac il, kobbi@cs bgu ac il

Available format(s): PDF | BibTeX Citation

Version: 20100504:115736 (All versions of this report)

Short URL: ia.cr/2009/594

Discussion forum: Show discussion | Start new discussion