Secure set union and bag union computation for guaranteeing anonymity of distrustful participants

The computation of the union operator for different distributed datasets involves two challenges when participants are curious and can even act malicious: guaranteeing anonymity and guaranteeing security. Anonymity means that the owner of a certain data item cannot be identified provided that more than two participants act. Security means that no participant can underhandedly prevent data items of other participants from being included in the union. We present a protocol for computing both, the set union and the bag union of data sets of different participants that guarantees both properties: anonymity and security even if participants act malicious, i.e.modify messages or change or stop the protocol. We prove the correctness of the protocol and give experimental results that show the applicability of our protocol in a common environment. © 2008 Academy Publisher.