Cryptology ePrint Archive: Report 2019/518

Fast Database Joins for Secret Shared Data

Payman Mohassel and Peter Rindal and Mike Rosulek

Abstract: 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.

Category / Keywords: cryptographic protocols / Set Intersection, Database, Join, Secret Sharing, three party,

Date: received 17 May 2019

Contact author: peterrindal at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190520:202246 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]