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 $(2\log_2 3)$-bit communication is optimal. In this paper, we provide new upper and lower bounds for several concrete functions. For lower bounds, we introduce a novel approach using combinatorial objects called abstract simplicial complexes to represent PSM protocols. Our method is suitable for obtaining non-asymptotic explicit lower bounds for concrete functions. By deriving lower bounds and constructing concrete protocols, we show that the optimal communication complexity for the equality and majority functions with three input bits are $3\log_2 3$ bits and $6$ bits, respectively. We also derive new lower bounds for the $n$-input AND function, three-valued comparison function, and multiplication over finite rings.
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}
}