DROPS

Document

DOI: 10.4230/LIPIcs.ITC.2023.11

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

Authors: Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, and Divya Ravi

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

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

Cite as

Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, and Divya Ravi. MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ITC.2023.11},
  URN =		{urn:nbn:de:0030-drops-183391},
  doi =		{10.4230/LIPIcs.ITC.2023.11},
  annote =	{Keywords: Secure Multiparty Computation, Bottleneck Complexity, Information-theoretic}
}

Search Results

Documents authored by Keller, Hannah

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

Abstract

Cite as

Thanks for your feedback!

Could not send message