2026-07-25T05:43:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18339 2024-03-06T11:01:42Z ddc:004 open_access

MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More Keller, Hannah Orlandi, Claudio Paskin-Cherniavsky, Anat Ravi, Divya Secure Multiparty Computation Bottleneck Complexity Information-theoretic 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 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. [Orlandi et al., 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., 2022] 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hannah Keller and Claudio Orlandi and Anat Paskin-Cherniavsky and Divya Ravi 2023 Is Part Of LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2023.11 urn:nbn:de:0030-drops-183391 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.11 eng https://creativecommons.org/licenses/by/4.0/legalcode