2026-07-24T05:41:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16485 2024-03-06T10:57:36Z ddc:004 open_access

A Note on the Complexity of Private Simultaneous Messages with Many Parties Ball, Marshall Randolph, Tim Secure computation Private Simultaneous Messages 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marshall Ball and Tim Randolph 2022 Is Part Of LIPIcs, Volume 230, 3rd Conference on Information-Theoretic Cryptography (ITC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2022.7 urn:nbn:de:0030-drops-164855 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.7 eng https://creativecommons.org/licenses/by/4.0/legalcode