LIPIcs.ITC.2022.7.pdf
- Filesize: 0.65 MB
- 12 pages
Document
A Note on the Complexity of Private Simultaneous Messages with Many Parties
Authors
-
Part of:
Volume:
3rd Conference on Information-Theoretic Cryptography (ITC 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Conference on Information-Theoretic Cryptography (ITC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-30
File
Document Identifiers
Acknowledgements
The authors thank Tal Malkin for helpful discussion, and several anonymous reviewers for helpful comments on an earlier draft.
Cite AsGet BibTex
Marshall Ball and Tim Randolph. A Note on the Complexity of Private Simultaneous Messages with Many Parties. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITC.2022.7
https://doi.org/10.4230/LIPIcs.ITC.2022.7
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Cryptographic protocols
- Theory of computation → Communication complexity
- Security and privacy → Information-theoretic techniques
Keywords
- Secure computation
- Private Simultaneous Messages
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Benny Applebaum, Thomas Holenstein, Manoj Mishra, and Ofer Shayevitz. The communication complexity of private simultaneous messages, revisited. Journal of Cryptology, pages 1-37, 2019.
- Leonard Assouline and Tianren Liu. Multi-party PSM, revisited. Technical report, Cryptology ePrint Archive, Report 2019/657, 2019. URL: https://eprint.iacr.org/2019/657.
-
Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, and Tal Malkin. On the complexity of decomposable randomized encodings, or: How friendly can a garbling-friendly PRF be? In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
-
Paul Beame, Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. Nondeterminism and an abstract formulation of Nečiporuk’s lower bound method. ACM Transactions on Computation Theory (TOCT), 9(1):1-34, 2016.
-
Amos Beimel, Yuval Ishai, Ranjit Kumaresan, and Eyal Kushilevitz. On the cryptographic complexity of the worst functions. In Theory of Cryptography Conference, pages 317-342. Springer, 2014.
- Amos Beimel, Eyal Kushilevitz, and Pnina Nissim. The complexity of multiparty PSM protocols and related models. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part II, volume 10821 of Lecture Notes in Computer Science, pages 287-318. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-78375-8_10.
-
I Nečiporuk Eduard. On a boolean function. In Soviet Math. Dokl, volume 7, pages 999-1000, 1966.
-
Uri Feige, Joe Killian, and Moni Naor. A minimal model for secure computation. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 554-563, 1994.
-
Orr Fischer, Rotem Oshman, and Uri Zwick. Public vs. private randomness in simultaneous multi-party communication complexity. In International Colloquium on Structural Information and Communication Complexity, pages 60-74. Springer, 2016.
- Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions (extended abstract). In 25th Annual Symposium on Foundations of Computer Science, West Palm Beach, Florida, USA, 24-26 October 1984, pages 464-479. IEEE Computer Society, 1984. URL: https://doi.org/10.1109/SFCS.1984.715949.
-
Yuval Ishai and Eyal Kushilevitz. Private simultaneous messages protocols with applications. In Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pages 174-183. IEEE, 1997.
-
Yuval Ishai and Eyal Kushilevitz. Randomizing polynomials: A new representation with applications to round-efficient secure computation. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 294-304. IEEE, 2000.
-
Edward I Nechiporuk. A boolean function. Engl. transl. in Sov. Phys. Dokl., 10:591-593, 1966.
- Alexander A. Razborov and Steven Rudich. Natural proofs. J. Comput. Syst. Sci., 55(1):24-35, 1997. URL: https://doi.org/10.1006/jcss.1997.1494.
-
Andrew Chi-Chih Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 162-167. IEEE, 1986.