View article

We present novel protocols to compute SQL-like join operations on secret shared database tables with non-unique join keys. Previous approaches to the problem had the restriction that the join keys of both the input tables must be unique or had quadratic overhead. Our work lifts this restriction, allowing one or both of the secret shared input tables to have an unknown and unbounded number of repeating join keys while achieving efficient O(n log n) asymptotic communication/computation and O(log n) rounds of interaction, independent of the multiplicity of the keys.

We present two join protocols, Join-OM and Join-MM. The first, Join-OM is optimized for the case where one table has a unique primary key while the second, Join-MM is for the more general setting where both tables contain duplicate keys. Both protocols require O(n log n) time and O(log n) rounds to join two tables of size n. Our framework for …