Document Open Access Logo

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

Authors Marshall Ball, Tim Randolph

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITC.2022.7.pdf
  • Filesize: 0.65 MB
  • 12 pages

Document Identifiers

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)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get 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

Author Details

Marshall Ball
  • Courant Institute of Mathematical Sciences, New York University, NY, USA
Tim Randolph
  • Columbia University, New York, NY, USA

Funding

  • Ball, Marshall: 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.
  • Randolph, Tim: 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.

Acknowledgements

The authors thank Tal Malkin for helpful discussion, and several anonymous reviewers for helpful comments on an earlier draft.

References

  1. Benny Applebaum, Thomas Holenstein, Manoj Mishra, and Ofer Shayevitz. The communication complexity of private simultaneous messages, revisited. Journal of Cryptology, pages 1-37, 2019. Google Scholar
  2. 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.
  3. 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. Google Scholar
  4. 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. Google Scholar
  5. 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. Google Scholar
  6. 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.
  7. I Nečiporuk Eduard. On a boolean function. In Soviet Math. Dokl, volume 7, pages 999-1000, 1966. Google Scholar
  8. 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. Google Scholar
  9. 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. Google Scholar
  10. 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.
  11. 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. Google Scholar
  12. 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. Google Scholar
  13. Edward I Nechiporuk. A boolean function. Engl. transl. in Sov. Phys. Dokl., 10:591-593, 1966. Google Scholar
  14. 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.
  15. 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. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact