Efficient Set Operations in the Presence of Malicious Adversaries

The authors 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. The 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. The protocols readily transform into protocols that are UC-secure, and they discuss how to perform these transformations.