Efficient Set Operations in the Presence of Malicious Adversaries
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.
set intersection set union simulation-based security oblivious pseudorandom function evaluation secure two-party computation