The Complexity of Multiparty PSM Protocols and Related Models
We study the efficiency of computing arbitrary k-argument functions in the Private Simultaneous Messages (PSM) model of [10, 14]. This question was recently studied by Beimel et al. [6], in the two-party case (\(k=2\)). We tackle this question in the general case of PSM protocols for \(k\ge 2\) parties. Our motivation is two-fold: On one hand, there are various applications (old and new) of PSM protocols for constructing other cryptographic primitives, where obtaining more efficient PSM protocols imply more efficient primitives. On the other hand, improved PSM protocols are an interesting goal on its own. In particular, we pay a careful attention to the case of small number of parties (e.g., \(k=3,4,5\)), which may be especially interesting in practice, and optimize our protocols for those cases.