WE2.R3.4

Towards Optimal Non-interactive Secure Multiparty Computation for Abelian Programs

Maki Yoshida, National Institute of Information and Communications Technology, Japan

Session:
Secure Multiparty Computation

Track:
14: Secure Communication and Computation

Location:
Ypsilon IV-V-VI

Presentation Time:
Wed, 10 Jul, 12:30 - 12:50

Session Chair:
Shun Watanabe, Tokyo University of Agriculture and Technology
Abstract
Non-interactive secure multiparty computation is a method to share and compute a private function $f$ among $n$ parties holding private inputs $x_i$ with $1\leq i\leq 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,\ldots, 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. In the previous work, several kinds of function families, upper and lower bounds have been improved and the only gaps remaining are for the group products and the Abelian programs (including symmetric functions). This paper improves the communication complexity of both function families towards the optimum by deriving a new lower bound for the group products that matches the previous upper bound (up to a constant factor) and the first asymptotically optimal upper bound for the Abelian programs.
Resources