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

Hannah Keller*, Claudio Orlandi*, Anat Paskin-Cherniavsky*, Divya Ravi*

*Corresponding author for this work

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

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 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 dateJul 2023
Pages11:1-11:22
Article number11
ISBN (Electronic)9783959772716
DOIs
Publication statusPublished - Jul 2023
Event4th Conference on Information-Theoretic Cryptography, ITC 2023 - Aarhus, Denmark
Duration: 6 Jun 20238 Jun 2023

Conference

Conference4th Conference on Information-Theoretic Cryptography, ITC 2023
Country/TerritoryDenmark
CityAarhus
Period06/06/202308/06/2023
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume267
ISSN1868-8969

Keywords

  • Bottleneck Complexity
  • Information-theoretic
  • Secure Multiparty Computation

Fingerprint

Dive into the research topics of 'MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More'. Together they form a unique fingerprint.

Cite this