Welcome to the resource topic for 2023/1743
Title:
Explicit Lower Bounds for Communication Complexity of PSM for Concrete Functions
Authors: Kazumasa Shinagawa, Koji Nuida
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.
ePrint: https://eprint.iacr.org/2023/1743
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .