Paper 2023/1743
Explicit Lower Bounds for Communication Complexity of PSM for Concrete Functions
Abstract
Private Simultaneous Messages (PSM) is a minimal model of secure computation, where the input players with shared randomness send messages to the output player simultaneously and only once. In this field, finding upper and lower bounds on communication complexity of PSM protocols is important, and in particular, identifying the optimal one where the upper and lower bounds coincide is the ultimate goal. However, up until now, functions for which the optimal communication complexity has been determined are few: An example of such a function is the two-input AND function where
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Indocrypt 2023
- Keywords
- secure multiparty computationprivate simultaneous messagescommunication complexitylower boundsconcrete functions
- Contact author(s)
-
kazumasa shinagawa np92 @ vc ibaraki ac jp
nuida @ imi kyushu-u ac jp - History
- 2023-11-13: approved
- 2023-11-11: received
- See all versions
- Short URL
- https://ia.cr/2023/1743
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1743, author = {Kazumasa Shinagawa and Koji Nuida}, title = {Explicit Lower Bounds for Communication Complexity of {PSM} for Concrete Functions}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1743}, year = {2023}, url = {https://eprint.iacr.org/2023/1743} }