TY - GEN
T1 - A Note on the Complexity of Private Simultaneous Messages with Many Parties
AU - Ball, Marshall
AU - Randolph, Tim
N1 - Funding Information:
Funding Marshall Ball: Part of this work was performed while the author was a student at Columbia University and a postdoc at University of Washington. This material is based upon work supported by the National Science Foundation under Grant #2030859 to the Computing Research Association for the CIFellows Project. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation nor the Computing Research Association. Tim Randolph: This material is based upon work supported by the following grants: NSF CCF-1563155, NSF IIS-1838154, NSF CCF-1814873, NSF CCF-1703925, NSF CCF-2106429, and NSF CCF-2107187.
Funding Information:
Marshall Ball: Part of this work was performed while the author was a student at Columbia University and a postdoc at University of Washington. This material is based upon work supported by the National Science Foundation under Grant #2030859 to the Computing Research Association for the CIFellows Project. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation nor the Computing Research Association. Tim Randolph: This material is based upon work supported by the following grants: NSF CCF-1563155, NSF IIS-1838154, NSF CCF-1814873, NSF CCF-1703925, NSF CCF-2106429, and NSF CCF-2107187. The authors thank Tal Malkin for helpful discussion, and several anonymous reviewers for helpful comments on an earlier draft.
Publisher Copyright:
© Marshall Ball and Tim Randolph; licensed under Creative Commons License CC-BY 4.0
PY - 2022/7/1
Y1 - 2022/7/1
N2 - 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.
AB - 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.
KW - Private Simultaneous Messages
KW - Secure computation
UR - http://www.scopus.com/inward/record.url?scp=85134339706&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85134339706&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITC.2022.7
DO - 10.4230/LIPIcs.ITC.2022.7
M3 - Conference contribution
AN - SCOPUS:85134339706
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 3rd Conference on Information-Theoretic Cryptography, ITC 2022
A2 - Dachman-Soled, Dana
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 3rd Conference on Information-Theoretic Cryptography, ITC 2022
Y2 - 5 July 2022 through 7 July 2022
ER -