Fast Database Joins and PSI for Secret Shared Data
Payman Mohassel, Peter Rindal, Mike Rosulek
Abstract
We present a scalable protocol for database joins on 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. Provided that all joins operate on unique primary keys, 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.
Topics & Concepts
JoinsComputer scienceScalabilityProtocol (science)Join (topology)DatabaseSQLOverhead (engineering)Set (abstract data type)RowTheoretical computer scienceProgramming languageMathematicsAlternative medicineMedicineCombinatoricsPathologyCryptography and Data SecurityDistributed systems and fault tolerancePrivacy-Preserving Technologies in Data