TY - GEN
T1 - A Note on the Complexity of Private Simultaneous Messages with Many Parties
AU - Ball, Marshall
AU - Randolph, Tim
N1 - 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 -