Paper 2023/683

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

Hannah Keller, Aarhus University
Claudio Orlandi, Aarhus University
Anat Paskin-Cherniavsky, Ariel University
Divya Ravi, Aarhus University

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

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Information-Theoretic Cryptography (ITC) 2023
Bottleneck complexitySemi-honest securityInformation-theoreticGarbled circuits
Contact author(s)
hkeller @ cs au dk
orlandi @ cs au dk
anatpc @ ariel ac il
divya @ cs au dk
2023-05-15: approved
2023-05-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hannah Keller and Claudio Orlandi and Anat Paskin-Cherniavsky and Divya Ravi},
      title = {MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More},
      howpublished = {Cryptology ePrint Archive, Paper 2023/683},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.