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

Marshall Ball, Tim Randolph

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

For k = ω(log n), we prove a Ω(k2n/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.

Original languageEnglish (US)
Title of host publication3rd Conference on Information-Theoretic Cryptography, ITC 2022
EditorsDana Dachman-Soled
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772389
DOIs
StatePublished - Jul 1 2022
Event3rd Conference on Information-Theoretic Cryptography, ITC 2022 - Cambridge, United States
Duration: Jul 5 2022Jul 7 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume230
ISSN (Print)1868-8969

Conference

Conference3rd Conference on Information-Theoretic Cryptography, ITC 2022
Country/TerritoryUnited States
CityCambridge
Period7/5/227/7/22

Keywords

  • Private Simultaneous Messages
  • Secure computation

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'A Note on the Complexity of Private Simultaneous Messages with Many Parties'. Together they form a unique fingerprint.

Cite this