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

Hannah Keller; Claudio Orlandi; Anat Paskin-Cherniavsky; Divya Ravi

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

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

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Information-Theoretic Cryptography (ITC) 2023
Keywords: Bottleneck complexity Semi-honest security Information-theoretic Garbled circuits
Contact author(s): hkeller @ cs au dk
orlandi @ cs au dk
anatpc @ ariel ac il
divya @ cs au dk
History: 2023-05-15: approved; 2023-05-13: received; See all versions
Short URL: https://ia.cr/2023/683
License: CC BY

BibTeX

@misc{cryptoeprint:2023/683,
      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{https://eprint.iacr.org/2023/683}},
      url = {https://eprint.iacr.org/2023/683}
}