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.2022.7
URN: urn:nbn:de:0030-drops-164855
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16485/
Go to the corresponding LIPIcs Volume Portal

Ball, Marshall ; Randolph, Tim

A Note on the Complexity of Private Simultaneous Messages with Many Parties

pdf-format:
LIPIcs-ITC-2022-7.pdf (0.7 MB)

Abstract

For k = ω(log n), we prove a Ω(k²n / log(kn)) lower bound on private simultaneous messages (PSM) with k parties who receive n-bit inputs. This extends the Ω(n) lower bound due to Appelbaum, Holenstein, Mishra and Shayevitz [Journal of Cryptology, 2019] to the many-party (k = ω(log n)) setting. It is the first PSM lower bound that increases quadratically with the number of parties, and moreover the first unconditional, explicit bound that grows with both k and n. This note extends the work of Ball, Holmgren, Ishai, Liu, and Malkin [ITCS 2020], who prove communication complexity lower bounds on decomposable randomized encodings (DREs), which correspond to the special case of k-party PSMs with n = 1. To give a concise and readable introduction to the method, we focus our presentation on perfect PSM schemes.

BibTeX - Entry

@InProceedings{ball_et_al:LIPIcs.ITC.2022.7,
  author =	{Ball, Marshall and Randolph, Tim},
  title =	{{A Note on the Complexity of Private Simultaneous Messages with Many Parties}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{7:1--7:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-238-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{230},
  editor =	{Dachman-Soled, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16485},
  URN =		{urn:nbn:de:0030-drops-164855},
  doi =		{10.4230/LIPIcs.ITC.2022.7},
  annote =	{Keywords: Secure computation, Private Simultaneous Messages}
}

Keywords: Secure computation, Private Simultaneous Messages
Collection: 3rd Conference on Information-Theoretic Cryptography (ITC 2022)
Issue Date: 2022
Date of publication: 30.06.2022

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