Information Sharing across Private Databases: Secure Union Revisited

There is a growing demand for sharing information across multiple autonomous and private databases. The problem is usually formulated as a secure multi-party computation problem in which a set of parties wish to jointly compute a function of their private inputs such that the parties learn only the result of the function but nothing else. In this paper we perform an analysis and an experimental evaluation of existing and potential solutions for secure multi-party computation of union. We also present an alternative random shares based protocol and show that the protocol, although quite simple, is efficient while providing reasonable level of security that can be adjusted by users. We formally analyze the security properties and the cost of our protocol. We also experimentally compare the various existing and potential solutions and show the tradeoff between different protocols in terms of security, efficiency and accuracy.