Payman Mohassel, Peter Rindal & Mike Rosulek ~ eprint/2019/518
We present a scalable database join protocol for secret shared data in the honest majority three party setting. The key features of our protocol are a rich set of SQL-like join/select queries and the ability to compose join operations together due to the inputs and outputs being generically secret shared between the parties. Given that the keys being joined on are unique, no information is revealed to any party during the protocol. In particular, not even the sizes of intermediate joins are revealed. All of our protocols are constant-round and achieve O(n) communication and computation overhead for joining two tables of n
rows.
In addition to performing database joins our protocol, we implement two applications on top of our framework. The first performs joins between different governmental agencies to identify voter registration errors in a privacy-preserving manner. The second application considers the scenario where several organizations wish to compare network security logs to more accurately identify common security threats, e.g. the IP addresses of a bot net. In both, cases the practicality of these applications depends on efficiently performing joins on millions of secret shared records. For example, our three party protocol can perform a join on two sets of 1 million records in 4.9 seconds or, alternatively, compute the cardinality of this join in just 3.1 seconds.