DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2026.76

Ideal Private Simultaneous Messages Schemes and Their Applications

Authors: Keitaro Hiwatashi and Reo Eriguchi

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Private Simultaneous Messages (PSM) is a minimal model for secure computation, where two parties, Alice and Bob, have private inputs x,y and a shared random string. Each of them sends a single message to an external party, Charlie, who can compute f(x,y) for a public function f but learns nothing else. The problem of narrowing the gap between upper and lower bounds on the communication complexity of PSM has been widely studied, but the gap still remains exponential. In this work, we study the communication complexity of PSM from a different perspective and introduce a special class of PSM, referred to as ideal PSM, in which each party’s message length attains the minimum, that is, their messages are taken from the same domain as inputs. We initiate a systematic study of ideal PSM with a complete characterization, several positive results, and applications. First, we provide a characterization of the class of functions that admit ideal PSM, based on permutation groups acting on the input domain. This characterization allows us to derive asymptotic upper bounds on the total number of such functions and a complete list for small domains. We also present several infinite families of functions of practical interest that admit ideal PSM. Interestingly, by simply restricting the input domains of these ideal PSM schemes, we can recover most of the existing PSM schemes that achieve the best known communication complexity in various computation models. As applications, we show that these ideal PSM schemes yield novel communication-efficient PSM schemes for functions with sparse or dense truth-tables and those with low-rank truth-tables. Furthermore, we obtain a PSM scheme for general functions that improves the constant factor in the dominant term of the best known communication complexity. An additional advantage is that our scheme simplifies the existing construction by avoiding the hierarchical design of internally invoking PSM schemes for smaller functions.

Cite as

Keitaro Hiwatashi and Reo Eriguchi. Ideal Private Simultaneous Messages Schemes and Their Applications. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 76:1-76:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hiwatashi_et_al:LIPIcs.ITCS.2026.76,
  author =	{Hiwatashi, Keitaro and Eriguchi, Reo},
  title =	{{Ideal Private Simultaneous Messages Schemes and Their Applications}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{76:1--76:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.76},
  URN =		{urn:nbn:de:0030-drops-253633},
  doi =		{10.4230/LIPIcs.ITCS.2026.76},
  annote =	{Keywords: secure computation, private simultaneous messages, communication complexity}
}

Document

DOI: 10.4230/LIPIcs.ITC.2023.18

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

Authors: Keitaro Hiwatashi and Koji Nuida

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

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.

Cite as

Keitaro Hiwatashi and Koji Nuida. Exponential Correlated Randomness Is Necessary in Communication-Optimal Perfectly Secure Two-Party Computation. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ITC.2023.18},
  URN =		{urn:nbn:de:0030-drops-183462},
  doi =		{10.4230/LIPIcs.ITC.2023.18},
  annote =	{Keywords: Secure Computation, Correlated Randomness, Lower Bound}
}

Search Results

Documents authored by Hiwatashi, Keitaro

Ideal Private Simultaneous Messages Schemes and Their Applications

Abstract

Cite as

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

Abstract

Cite as

Thanks for your feedback!

Could not send message