License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2023.11
URN: urn:nbn:de:0030-drops-183391
URL: https://drops.dagstuhl.de/opus/volltexte/2023/18339/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-ITC-2023-11.pdf (0.9 MB)

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

BibTeX - Entry

@InProceedings{keller_et_al:LIPIcs.ITC.2023.11,
  author =	{Keller, Hannah and Orlandi, Claudio and Paskin-Cherniavsky, Anat and Ravi, Divya},
  title =	{{MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18339},
  URN =		{urn:nbn:de:0030-drops-183391},
  doi =		{10.4230/LIPIcs.ITC.2023.11},
  annote =	{Keywords: Secure Multiparty Computation, Bottleneck Complexity, Information-theoretic}
}

Keywords: Secure Multiparty Computation, Bottleneck Complexity, Information-theoretic
Collection: 4th Conference on Information-Theoretic Cryptography (ITC 2023)
Issue Date: 2023
Date of publication: 21.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI