Aarhus University Seal

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

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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. [28] 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 [28] 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).

Original languageEnglish
Title of host publication4th Conference on Information-Theoretic Cryptography, ITC 2023
EditorsKai-Min Chung
Place of publicationWadern
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Publication yearJul 2023
Article number11
ISBN (electronic)9783959772716
Publication statusPublished - Jul 2023
Event4th Conference on Information-Theoretic Cryptography, ITC 2023 - Aarhus, Denmark
Duration: 6 Jun 20238 Jun 2023


Conference4th Conference on Information-Theoretic Cryptography, ITC 2023
SeriesLeibniz International Proceedings in Informatics, LIPIcs

Bibliographical note

Publisher Copyright:
© Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, and Divya Ravi; licensed under Creative Commons License CC-BY 4.0 4th Conference on Information-Theoretic Cryptography (ITC 2023)

    Research areas

  • Bottleneck Complexity, Information-theoretic, Secure Multiparty Computation

See relations at Aarhus University Citationformats

ID: 341299953