On the Communication Complexity of Private Function Sharing and Computation

This paper studies the communication complexity of sharing and computing a private function f among n parties holding private inputs x
i
with 1 ≤ i ≤ n in the information theoretical setting. Each party locally computes a message from a share of f and send it to a referee in parallel. The referee obtains the output f (x
1
,…,x
n
) while keeping f and x
i
private other than what can be inferred from the output. The communication complexity is evaluated by the maximum length of shares and messages. First, a lower bound on the communication complexity is presented. In particular, the length of the message is lower bounded by a restricted f. Second, the lower bound increases as the robustness level becomes larger, indicating a tradeoff between efficiency and robustness. For well-known families of functions, the lower bounds are instantiated, some of which matches the latest upper bounds up to a constant factor.