Paper 2023/683

MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More

Abstract

The bottleneck-complexity (BC) of secure multiparty computation (MPC) protocols is a measure of the maximum number of bits which are sent and received by any party in a protocol. As the name suggests, the goal of studying BC-efficient protocols is to increase overall efficiency by making sure that the workload in the protocol is somehow "amortized'' by the protocol participants. Orlandi et al. (PKC 2022) initiated the study of BC-efficient protocols from simple assumptions in the correlated randomness model and for semi-honest adversaries. In this work, we extend the study of Orlandi et al. in two primary directions: (a) to a larger and more general class of functions and (b) to the information-theoretic setting. In particular, we offer semi-honest secure protocols for the useful function classes of abelian programs, 'read-$k$' non-abelian programs, and 'read-$k$' generalized formulas. Our constructions use a novel abstraction, called 'incremental function secret-sharing' (IFSS), that can be instantiated with unconditional security or from one-way functions (with different efficiency trade-offs).