Paper 2022/1600

Secret-Shared Joins with Multiplicity from Aggregation Trees

Saikrishna Badrinarayanan, Snap
Sourav Das, University of Illinois Urbana Champaign
Gayathri Garimella, Oregon State University
Srinivasan Raghuraman, Visa (United States)
Peter Rindal, Visa (United States)

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, \ProtoUni and \ProtoDup. The first, \ProtoUni is optimized for the case where one table has a unique primary key while the second, \ProtoDup 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 computing joins requires an efficient sorting protocol and generic secure computation for circuits. We concretely instantiate our protocols in the honest majority three-party setting. Our join protocols are built around an efficient method to compute structured aggregations over a secret shared input vector $\V\in \mathbb{D}^n$. If the parties have another secret-shared vector of control bits $\B \in \{0, 1\}^n$ to partition $\V$ into sub-vectors (that semantically relates to the join operations). A structured aggregation computes a secret shared vector $\V'\in \mathbb{D}^n$ where every sub-vector $(\V_b,...,\V_e)$ (defined by the control bits) is aggregated as $\V_i'=\V_b\op...\op \V_i$ for $i\in \{b,...,e\}$ according to some user-defined operator $\op$. Critically, the $b,e$ indices that partition the vector are secret. It's trivial to compute aggregations by sequentially processing the input vector and control bits. This would require $O(n)$ rounds and would be very slow due to network latency. We introduce Aggregation Trees as a general technique to compute aggregations in $O(\log n)$ rounds. For our purpose of computing joins, we instantiate $\op \in$ \textsf{\{copy previous value, add\}}, but we believe that this technique is quite powerful and can find applications in other useful settings.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2022
Secure Joins Oblivious Sorting PSI Private Aggregation
Contact author(s)
garimelg @ oregonstate edu
srraghur @ visa com
peterrindal @ gmail com
2022-11-21: approved
2022-11-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Saikrishna Badrinarayanan and Sourav Das and Gayathri Garimella and Srinivasan Raghuraman and Peter Rindal},
      title = {Secret-Shared Joins with Multiplicity from Aggregation Trees},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1600},
      year = {2022},
      doi = {10.1145/3548606},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.