[Resource Topic] 2023/683: MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More

Welcome to the resource topic for 2023/683

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

Authors: Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, Divya Ravi


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).

ePrint: https://eprint.iacr.org/2023/683

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .