International Association
for Cryptologic Research

Bottleneck complexity is an efficiency measure of secure multiparty computation (MPC) introduced by Boyle et al. (ICALP 2018) to achieve load-balancing. Roughly speaking, it is defined as the maximum communication complexity required by any player within the protocol execution. Since it is impossible to achieve sublinear bottleneck complexity in the number of players $n$ for all functions, a prior work constructed MPC protocols with low bottleneck complexity for specific functions including the AND function and general symmetric functions. However, the previous protocol for a symmetric function needs to assume a computational primitive of garbled circuits. Its unconditionally secure variant has exponentially large bottleneck complexity in the depth of an arithmetic formula computing the function, which limits the class of symmetric functions the protocol can compute with sublinear bottleneck complexity in $n$. In this paper, we propose for the first time unconditionally secure MPC protocols computing any symmetric function with sublinear bottleneck complexity in $n$. Our first protocol is an application of the one-time truth-table protocol by Ishai et al. (TCC 2013). We devise a novel technique to express the truth-table as an array of two or higher dimensions and obtain two other protocols with better trade-offs. We also propose an unconditionally secure protocol with lower bottleneck complexity tailored to the AND function. It avoids pseudorandom functions used by the previous protocol, preserving bottleneck complexity up to a logarithmic factor in $n$. As an application, we construct an unconditionally secure protocol for private set intersection (PSI), which computes the intersection of players' private sets. This is the first PSI protocol with sublinear bottleneck complexity in $n$ and to the best of our knowledge, there has been no such protocol even under cryptographic assumptions.