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.18
URN: urn:nbn:de:0030-drops-183462
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18346/
Go to the corresponding LIPIcs Volume Portal

Hiwatashi, Keitaro ; Nuida, Koji

Exponential Correlated Randomness Is Necessary in Communication-Optimal Perfectly Secure Two-Party Computation

pdf-format:
LIPIcs-ITC-2023-18.pdf (0.7 MB)

Abstract

Secure two-party computation is a cryptographic technique that enables two parties to compute a function jointly while keeping each input secret. It is known that most functions cannot be realized by information-theoretically secure two-party computation, but any function can be realized in the correlated randomness (CR) model, where a trusted dealer distributes input-independent CR to the parties beforehand. In the CR model, three kinds of complexities are mainly considered; the size of CR, the number of rounds, and the communication complexity.
Ishai et al. (TCC 2013) showed that any function can be securely computed with optimal online communication cost, i.e., the number of rounds is one round and the communication complexity is the same as the input length, at the price of exponentially large CR. In this paper, we prove that exponentially large CR is necessary to achieve perfect security and online optimality for a general function and that the protocol by Ishai et al. is asymptotically optimal in terms of the size of CR. Furthermore, we also prove that exponentially large CR is still necessary even when we allow multiple rounds while keeping the optimality of communication complexity.

BibTeX - Entry

@InProceedings{hiwatashi_et_al:LIPIcs.ITC.2023.18,
  author =	{Hiwatashi, Keitaro and Nuida, Koji},
  title =	{{Exponential Correlated Randomness Is Necessary in Communication-Optimal Perfectly Secure Two-Party Computation}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{18:1--18:16},
  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/18346},
  URN =		{urn:nbn:de:0030-drops-183462},
  doi =		{10.4230/LIPIcs.ITC.2023.18},
  annote =	{Keywords: Secure Computation, Correlated Randomness, Lower Bound}
}

Keywords: Secure Computation, Correlated Randomness, Lower Bound
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